Graph

java.lang.Object
- org.mathIT.graphs.Graph<V>

Type Parameters:

V - the type of the vertices

Direct Known Subclasses:

WeightedGraph
```
public class Graph<V extends Vertible<V>>
extends Object
```
This class represents a general graph without multiple edges as an array list of vertices and the corresponding adjacency matrix. Each vertex of a graph of this class must be an instance of a class implementing the interface Vertible. To create a graph, a set of vertices implementing Vertible.java is necessary, along with the adjacency matrix. It is important to note that the indices of the vertices depend uniquely on the adjacency matrix adjacency in the sense that an edge from vertex i to vertex j is given if the matrix entry adjacency[i][j] is 1, and 0 otherwise.
Most easily, a vertex class is programmed by extending the vertex class Vertex. For example, if a network of persons is to be established, a class Person can be written such as
```
   public class Person extends Vertex<Person> {
      ...
   }
 
```
and the network of persons as
```
   public class SocialNetwork extends Graph<Person> {
      ...
   }
 
```
A more tedious, but also more flexible way is to implement instead the interface Vertible, e.g.,
```
   public class Person implements Vertible<Person> {
      ...
   }
 
```
If one is interested only in a simple graph consisting of vertices with the minimal set of attributes, the static method createGraph(int[][]) can be invoked,
```
   public class MyGraph {
      int[][] adjacencyMatrix;
      ...
      Graph<SimpleVertex> graph = Graph.create(adjacencyMatrix);
      ...
   }
 
```
Version:

2.0

Author:

Andreas de Vries

See Also:

WeightedGraph

Field Summary

Fields
Modifier and Type	Field and Description
`protected int[][]`	`adjacency` Adjacency matrix. adjacency[i][j] indicates whether there is an edge from vertex i to vertex j.
`protected ArrayList<ArrayList<Function<Integer,Integer>>>`	`modifiableHashimoto` The modiable Hashimoto matrix M(i) consisting of function entries n(i).
`protected int`	`numberOfEdges` Number of edges.
`protected double[]`	`relevance` This array stores the network relevance of all vertices with respect to the entire graph.
`static char`	`SEPARATOR` Column separator for CSV files.
`protected boolean`	`undirected` Flag whether this graph is directed or undirected.
`protected V[]`	`vertices` Array of vertices forming this graph.
`protected boolean`	`weighted` Flag whether this graph is weighted or unweighted.

Constructor Summary

Constructors
Constructor and Description
`Graph()` Creates an empty graph.
`Graph(ArrayList<V> vertices, int[][] adjacency, V[] arrayTemplate)` Creates a directed graph from the specified array list of vertices and the adjacency matrix.
`Graph(ArrayList<V> vertices, V[] arrayTemplate)` Creates a graph with the specified vertices.
`Graph(boolean undirected, int[][] adjacency, V[] arrayTemplate)` Creates a graph from the specified adjacency matrix.
`Graph(boolean undirected, V[] vertices)` Creates a graph with the specified vertices.
`Graph(boolean undirected, V[] vertices, int[][] adjacency)` Creates a graph from the specified array of vertices and the adjacency matrix.
`Graph(int[][] adjacency, V[] arrayTemplate)` Creates a directed graph from the specified adjacency matrix.
`Graph(V[] vertices)` Creates a directed graph with the specified vertices.
`Graph(V[] vertices, int[][] adjacency)` Creates a directed graph from the specified array of vertices and the adjacency matrix.

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`protected int`	`breadthFirstSearch(V start, V goal)` Returns the index of the searched target, or -1 if the target is not contained in this graph.
`HashSet<Edge<V>>`	`collectEdges()` Creates a set of the edges of this graph.
`int[][]`	`computeHashimoto()` The Hashimoto matrix of this graph, also called non-backtracking matrix or edge adjacency matrix.
`protected int`	`computeNumberOfEdges()` Returns the number of edges of this graph.
`static Graph<SimpleVertex>`	`create(JTable jTable)` Creates a graph from the adjacency matrix specified by the input table.
`static Graph<SimpleVertex>`	`createGraph(int[][] adjacency)` Creates a graph from the specified adjacency matrix.
`static Graph<SimpleVertex>`	`createGraphFromCSVFile()` Creates a graph from a CSV file selected by a file chooser dialog.
`int`	`depthFirstSearch(int start, V goal)` Returns the index of the searched target, or -1 if the target is not contained in this graph.
`int`	`depthFirstSearch(V start, V goal)` Returns the index of the searched vertex if it is reachable from the start vertex.
`Clustering`	`detectClusters()` Returns a clustering of this graph which maximizes its modularity.
`Clustering`	`detectClustersExactly()` Finds an optimum clustering by exhaustion.
`int[][]`	`getAdjacency()` Returns the adjacency matrix of this graph.
`ArrayList<Graph<V>>`	`getComponents(V x)` Returns a list of the strongly connected components of this graph which are reachable from vertex x.
`LinkedList<LinkedList<V>>`	`getCycles(V x)` Returns a list of the cycles in this graph starting in x.
`int`	`getDegree(int i)` Returns the degree of the vertex with index i, if this graph is undirected.
`int`	`getDegree(V vertex)` Returns the degree of the vertex with index i, if this graph is undirected.
`int[]`	`getDegrees()` Returns an array of the degrees of all vertices, if this graph is undirected, with the entry i being the degree of the vertex with index i.
`int`	`getIndegree(int i)` Returns the indegree of the vertex with index i.
`int`	`getIndegree(V vertex)` Returns the indegree of a vertex of this graph.
`int[]`	`getIndegrees()` Returns an array of the indegrees of all vertex of this graph, with the entry i being the indegree of the vertex with index i.
`int[][]`	`getModifiedHashimoto(int i)` The modified Hashimoto matrix M(i) of this graph with node i removed; M(i) is also called modified non-backtracking matrix or modified edge adjacency matrix.
`int`	`getNumberOfEdges()` Returns the vertex of index `i` of this graph.
`int`	`getOutdegree(int i)` Returns the outdegree of a vertex of this graph.
`int`	`getOutdegree(V vertex)` Returns the outdegree of a vertex of this graph.
`int[]`	`getOutdegrees()` Returns an array of the outdegrees of all vertex of this graph, with the entry i being the outdegree of the vertex with index i.
`double`	`getRelevance(int i)` Returns the network relevance of vertex i with respect to the entire graph.
`Clustering`	`getRelevanceClusters()` Finds a clustering according to the relevance of each nde of this graph.
`V`	`getVertex(int i)` Returns the vertex of index `i` of this graph.
`V[]`	`getVertices()` Returns an array containing all vertices of this graph.
`boolean`	`hasCycles()` Checks whether this graph contains a cycle.
`boolean`	`isUndirected()` Gets the flag whether this graph is undirected.
`Matrix`	`laplacian()` Returns the Laplacian of this graph.
`static void`	`main(String[] args)` For test purposes...
`void`	`saveAsCSV()` This method asks the user to select a file name and saves a representation of this graph as a CSV file.
`void`	`setUndirected(boolean undirected)` Sets the flag whether this graph is undirected.
`void`	`setVertices(V[] vertices)` Sets the vertices of this graph.
`static void`	`show(JTable table)` This method displays the specified table in a simple option pane.
`Graph<V>`	`subgraph(Set<V> vertices)` Returns the subgraph given by the specified set of vertices of this graph.
`Graph<V>`	`subgraph(V[] vertices)` Returns the subgraph given by the specified array of vertices of this graph.
`StringBuilder`	`toCSV()` Returns a representation of this graph as a text in CSV format.
`String`	`toHTMLString()` Returns a string representation of the object as a table in HTML.
`JTable`	`toJTable()` Returns a string representation of the object as a `JTable`.
`int[]`	`topologicalSort()` Returns a topological sorting of this graph as an integer array σ, where σ(i) is the rank of vertex with index i.
`String`	`toString()` Returns a string representation of this graph.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

- Field Detail
  - SEPARATOR
```
public static final char SEPARATOR
```
    Column separator for CSV files.
    
    See Also:
    
    Constant Field Values
  - undirected
```
protected boolean undirected
```
    Flag whether this graph is directed or undirected.
  - weighted
```
protected boolean weighted
```
    Flag whether this graph is weighted or unweighted. Instances of this class are always unweighted, for weighted graphs consider the subclass Weighted Graph.
  - vertices
```
protected V extends Vertible<V>[] vertices
```
    Array of vertices forming this graph.
  - adjacency
```
protected int[][] adjacency
```
    Adjacency matrix. adjacency[i][j] indicates whether there is an edge from vertex i to vertex j.
  - numberOfEdges
```
protected int numberOfEdges
```
    Number of edges.
  - modifiableHashimoto
```
protected ArrayList<ArrayList<Function<Integer,Integer>>> modifiableHashimoto
```
    The modiable Hashimoto matrix M(i) consisting of function entries n(i). The Hashimoto matrix, also called non-backtracking matrix or edge adjacency matrix, encodes those pairs of adjacent edges for which the start vertex is different from the end vertex (i.e., backtracks are excluded). The modifiable Hashimoto matrix M(i) allows to simulate the removal of node i by its entries n(i). Here the function n(i) in entry (k,l)
    (m)_kl(i) = n(i)
    is defined as the function yielding 1 if and only if edges k and l are adjacent, but are not linked via node i; in all other cases n(i) = 0. By consequence, M(-1) exactly yields the Hashimoto matrix.
  - relevance
```
protected double[] relevance
```
    This array stores the network relevance of all vertices with respect to the entire graph. The network relevance, or influence, of a node is defined by the impact of its removal to the Hashimoto matrix of the remaining network. Network relevance is an important notion to study system relevance, network stability, or network reliability.
    
    See Also:
    
    getRelevance(int)
- Constructor Detail
  - Graph
```
public Graph()
```
    Creates an empty graph.
  - Graph
```
public Graph(ArrayList<V> vertices,
             V[] arrayTemplate)
```
    Creates a graph with the specified vertices.
    
    Parameters:
    
    vertices - array of the vertices forming this graph
    
    arrayTemplate - an array of the type of vertices. This array may be empty. It is necessary technically because generic array creation is prohibited in Java.
  - Graph
```
public Graph(V[] vertices)
```
    Creates a directed graph with the specified vertices. The adjacency matrix is created as the n×n null matrix, i.e., the graph consists of isolated vertices.
    
    Parameters:
    
    vertices - an array of the vertices of this graph
  - Graph
```
public Graph(boolean undirected,
             V[] vertices)
```
    Creates a graph with the specified vertices. The adjacency matrix is created as the n×n null matrix, i.e., the graph consists of isolated vertices.
    
    Parameters:
    
    undirected - indicator whether this graph is undirected
    
    vertices - an array of the vertices of this graph
  - Graph
```
public Graph(int[][] adjacency,
             V[] arrayTemplate)
```
    Creates a directed graph from the specified adjacency matrix. In particular, the adjacency list of each vertex is constructed from the adjacency matrix. If two vertices vertices[i] and vertices[j] do not have an edge connecting them, the respective adjacency matrix entry adjacency[i][j] is expected to have the value 0. In each vertex, previously stored values for its index or its adjacency list are always overwritten with the ones derived by the adjacency matrix!
    
    Parameters:
    
    adjacency - the adjacency matrix determining the adjacencies of each vertex of this graph
    
    arrayTemplate - an array of the type of vertices, containing at least one template vertex. It is necessary technically because generic array creation is prohibited in Java.
    
    Throws:
    
    IllegalArgumentException - if adjacency is not a square matrix
  - Graph
```
public Graph(boolean undirected,
             int[][] adjacency,
             V[] arrayTemplate)
```
    Creates a graph from the specified adjacency matrix. In particular, the adjacency list of each vertex is constructed from the adjacency matrix. If two vertices vertices[i] and vertices[j] do not have an edge connecting them, the respective adjacency matrix entry adjacency[i][j] is expected to have the value 0. In each vertex, previously stored values for its index or its adjacency list are always overwritten with the ones derived by the adjacency matrix!
    
    Parameters:
    
    undirected - flag indicating whether this graph is undirected
    
    adjacency - the adjacency matrix determining the adjacencies of each vertex of this graph
    
    arrayTemplate - an array of the type of vertices, containing at least one template vertex. It is necessary technically because generic array creation is prohibited in Java.
    
    Throws:
    
    IllegalArgumentException - if adjacency is not a square matrix, or if the graph is undirected and the adjacency matrix is not symmetric
  - Graph
```
public Graph(V[] vertices,
             int[][] adjacency)
```
    Creates a directed graph from the specified array of vertices and the adjacency matrix. In particular, the adjacency list of each vertex is constructed from the adjacency matrix. If two vertices vertices[i] and vertices[j] do not have an edge connecting them, the respective adjacency matrix entry adjacency[i][j] is expected to have the value 0. In each vertex, previously stored values for its index or its adjacency list are always overwritten with the ones derived by the adjacency matrix!
    
    Parameters:
    
    vertices - array of the vertices forming this graph
    
    adjacency - the adjacency matrix determining the adjacencies of each vertex of this graph
    
    Throws:
    
    IllegalArgumentException - if adjacency is not a square matrix or if the number of vertices does not equal the length of the adjacency matrix
  - Graph
```
public Graph(boolean undirected,
             V[] vertices,
             int[][] adjacency)
```
    Creates a graph from the specified array of vertices and the adjacency matrix. In particular, the adjacency list of each vertex is constructed from the adjacency matrix. If two vertices vertices[i] and vertices[j] do not have an edge connecting them, the respective adjacency matrix entry adjacency[i][j] is expected to have the value 0. In each vertex, previously stored values for its index or its adjacency list are always overwritten with the ones derived by the adjacency matrix!
    
    Parameters:
    
    undirected - flag indicating whether this graph is undirected
    
    vertices - array of the vertices forming this graph
    
    adjacency - the adjacency matrix determining the adjacencies of each vertex of this graph
    
    Throws:
    
    IllegalArgumentException - if adjacency is not a square matrix, or if the number of vertices does not equal the length of the adjacency matrix, or if the graph is undirected and the adjacency matrix is not symmetric
  - Graph
```
public Graph(ArrayList<V> vertices,
             int[][] adjacency,
             V[] arrayTemplate)
```
    Creates a directed graph from the specified array list of vertices and the adjacency matrix. In particular, the adjacency list of each vertex is constructed from the adjacency matrix. If two vertices vertices[i] and vertices[j] do not have an edge connecting them, the respective adjacency matrix entry adjacency[i][j] is expected to have the value 0. In each vertex, previously stored values for its index or its adjacency list are always overwritten with the ones derived by the adjacency matrix!
    
    Parameters:
    
    vertices - array of the vertices forming this graph
    
    adjacency - the adjacency matrix determining the adjacency of each edge of this graph
    
    arrayTemplate - an array of the type of vertices. This array may be empty. It is necessary technically because generic array creation is prohibited in Java.
- Method Detail
  - computeNumberOfEdges
```
protected final int computeNumberOfEdges()
```
    Returns the number of edges of this graph.
    
    Returns:
    
    the number of edges
  - computeHashimoto
```
public int[][] computeHashimoto()
```
    The Hashimoto matrix of this graph, also called non-backtracking matrix or edge adjacency matrix. It encodes those pairs of adjacent edges for which the start vertex is different from the end vertex (i.e., backtracks are excluded). For symmetric adjacency matrices, the labeling of edges follows the scheme in A. Terras: Zeta Functions of Graphs. Cambridge University Press, Cambridge New York 2011
    
    Returns:
    
    the Hashimoto matrix
  - getModifiedHashimoto
```
public int[][] getModifiedHashimoto(int i)
```
    The modified Hashimoto matrix M(i) of this graph with node i removed; M(i) is also called modified non-backtracking matrix or modified edge adjacency matrix. It encodes those pairs of adjacent edges for which the start vertex is different from the end vertex (i.e., backtracks are excluded). For symmetric adjacency matrices, the labeling of edges follows the scheme in A. Terras: Zeta Functions of Graphs. Cambridge University Press, Cambridge New York 2011. For i = -1 the Hashimoto matrix of the (full) graph is returned. The modified Hashimoto matrix M is related to the Hashimoto matrix B by the equation
    M_kl = n_i B_kl
    
    where n_i = 0 if node i is removed from the graph, and = 1 otherwise. For more details see F. Morone, H.A. Makse (2015): ‘Influence maximization in complex networks through optimal percolation’, Nature 524 (7563), pp. 65–68, doi 10.1038/nature14604 (or preprint arxiv 1506.08326).
    
    The implementation of this method relies on the field modifiableHashimoto of this graph which is computed once and consists of functional lambda expressions, which are simply applied by the argument i.
    
    Parameters:
    
    i - the node of the graph to be removed virtually
    
    Returns:
    
    the modified Hashimoto matrix
    
    See Also:
    
    modifiableHashimoto
  - setUndirected
```
public void setUndirected(boolean undirected)
```
    Sets the flag whether this graph is undirected.
    
    Parameters:
    
    undirected - flag which is true if this graph is undirected
  - isUndirected
```
public boolean isUndirected()
```
    Gets the flag whether this graph is undirected.
    
    Returns:
    
    true if and only if this graph is undirected
  - setVertices
```
public void setVertices(V[] vertices)
```
    Sets the vertices of this graph.
    
    Parameters:
    
    vertices - an array of all vertices of this graph
  - getVertices
```
public V[] getVertices()
```
    Returns an array containing all vertices of this graph.
    
    Returns:
    
    the vertices of this graph
  - getVertex
```
public V getVertex(int i)
```
    Returns the vertex of index i of this graph. If a vertex with this index does not exist, it returns null.
    
    Parameters:
    
    i - the index
    
    Returns:
    
    the vertices of this graph
  - getAdjacency
```
public int[][] getAdjacency()
```
    Returns the adjacency matrix of this graph.
    
    Returns:
    
    the adjacency matrix of this graph
  - getNumberOfEdges
```
public int getNumberOfEdges()
```
    Returns the vertex of index i of this graph. If a vertex with this index does not exist, it returns null.
    
    Returns:
    
    the vertices of this graph
  - collectEdges
```
public HashSet<Edge<V>> collectEdges()
```
    Creates a set of the edges of this graph.
    
    Returns:
    
    a set of the edges of this graph
  - getDegree
```
public int getDegree(V vertex)
```
    Returns the degree of the vertex with index i, if this graph is undirected. The degree of a vertex in an undirected graph is defined as the number of edges incident on it. For a directed graph the notion of degree is ambigous, since an edge is either incident on or outgoing from a vertex, i.e., we have to distinguish the indegree and the outdegree. Note that for an undirected graph the degree of a vertex is equal to its indegree as well as to its outdegree, but its computation requires less computational time.
    
    Parameters:
    
    vertex - a vertex of the graph
    
    Returns:
    
    the degree of the vertex
    
    Throws:
    
    IllegalArgumentException - if this graph is directed
    
    See Also:
    
    getDegree(int), getIndegree(org.mathIT.graphs.Vertible), getOutdegree(org.mathIT.graphs.Vertible)
  - getDegree
```
public int getDegree(int i)
```
    Returns the degree of the vertex with index i, if this graph is undirected. The degree of a vertex in an undirected graph is defined as the number of edges incident on it. For a directed graph the notion of degree is ambigous, since an edge is either incident on or outgoing from a vertex, i.e., we have to distinguish the indegree and the outdegree. Note that for an undirected graph the degree of a vertex is equal to its indegree as well as to its outdegree, but its computation requires less computational time.
    
    Parameters:
    
    i - the index of a vertex of the graph
    
    Returns:
    
    the degree of the vertex
    
    Throws:
    
    IllegalArgumentException - if this graph is directed
    
    See Also:
    
    getDegree(org.mathIT.graphs.Vertible), getIndegree(int), getOutdegree(int)
  - getDegrees
```
public int[] getDegrees()
```
    Returns an array of the degrees of all vertices, if this graph is undirected, with the entry i being the degree of the vertex with index i. The degree of a vertex in an undirected graph is defined as the number of edges incident on it. For a directed graph the notion of degree is ambigous, since an edge is either incident on or outgoing from a vertex, i.e., we have to distinguish the indegree and the outdegree. Note that for an undirected graph the degree of a vertex is equal to its indegree as well as to its outdegree, but its computation requires less computational time.
    
    Returns:
    
    an array of the indegrees of all vertices of this graph
    
    Throws:
    
    IllegalArgumentException - if this graph is directed
    
    See Also:
    
    getDegree(org.mathIT.graphs.Vertible), getDegree(int), getIndegrees(), getOutdegrees()
  - getIndegree
```
public int getIndegree(V vertex)
```
    Returns the indegree of a vertex of this graph. The indegree of a vertex is defined as the number of edges incident on it, or in other words as the number of its predecessors.
    
    Parameters:
    
    vertex - a vertex of the graph
    
    Returns:
    
    the indegree of the vertex
    
    See Also:
    
    getIndegree(int)
  - getIndegree
```
public int getIndegree(int i)
```
    Returns the indegree of the vertex with index i. The indegree of a vertex is defined as the number of edges incident on it, or in other words as the number of its predecessors.
    
    Parameters:
    
    i - the index of a vertex of the graph
    
    Returns:
    
    the indegree of the vertex
    
    See Also:
    
    getIndegree(org.mathIT.graphs.Vertible)
  - getOutdegree
```
public int getOutdegree(V vertex)
```
    Returns the outdegree of a vertex of this graph. The outdegree of a vertex is defined as the number of edges outgoing from it, or in other words as the number of its successors.
    
    Parameters:
    
    vertex - a vertex of the graph
    
    Returns:
    
    the outdegree of the vertex
    
    See Also:
    
    getIndegree(int)
  - getOutdegree
```
public int getOutdegree(int i)
```
    Returns the outdegree of a vertex of this graph. The outdegree of a vertex is defined as the number of edges outgoing from it, or in other words as the number of its successors.
    
    Parameters:
    
    i - the index of a vertex of the graph
    
    Returns:
    
    the outdegree of the vertex
    
    See Also:
    
    getOutdegree(org.mathIT.graphs.Vertible)
  - getIndegrees
```
public int[] getIndegrees()
```
    Returns an array of the indegrees of all vertex of this graph, with the entry i being the indegree of the vertex with index i. The indegree of a vertex is defined as the number of edges incident on it, or in other words as the number of its predecessors.
    
    Returns:
    
    an array of the indegrees of all vertices of this graph
    
    See Also:
    
    getIndegree(org.mathIT.graphs.Vertible), getIndegree(int)
  - getOutdegrees
```
public int[] getOutdegrees()
```
    Returns an array of the outdegrees of all vertex of this graph, with the entry i being the outdegree of the vertex with index i. The outdegree of a vertex is defined as the number of edges outgoing from it, or in other words as the number of its successors.
    
    Returns:
    
    an array of the outdegrees of all vertices of this graph
    
    See Also:
    
    getOutdegree(org.mathIT.graphs.Vertible), getOutdegree(int)
  - getRelevance
```
public double getRelevance(int i)
```
    Returns the network relevance of vertex i with respect to the entire graph. The network relevance, or influence, of a node is defined by the impact of its removal to the Hashimoto matrix of the remaining network. Network relevance is an important notion to study system relevance, network stability, or network reliability.
    After the calculation of the network relevances, the relevance values of all nodes are offered to be stored in a CSV file. In its first row there are stored the maximum and the minimum relevance value of all nodes, each following row consisting of node's label and its relevance value.
    
    Cf. A. Terras: Zeta Functions of Graphs. Cambridge University Press, Cambridge New York 2011, or F. Morone, H.A. Makse (2015): ‘Influence maximization in complex networks through optimal percolation’, Nature 524 (7563), pp. 65–68, doi 10.1038/nature14604 (or preprint arxiv 1506.08326).
    
    Parameters:
    
    i - index of a node
    
    Returns:
    
    network relevance of vertex i
  - laplacian
```
public Matrix laplacian()
```
    Returns the Laplacian of this graph.
    
    Returns:
    
    the Laplacian of this graph
  - subgraph
```
public Graph<V> subgraph(Set<V> vertices)
```
    Returns the subgraph given by the specified set of vertices of this graph.
    
    Parameters:
    
    vertices - a set of vertices of this graph
    
    Returns:
    
    the subgraph given by the specified set of vertices
    
    Throws:
    
    IllegalArgumentException - if a vertex of the set is not found in this graph
  - subgraph
```
public Graph<V> subgraph(V[] vertices)
```
    Returns the subgraph given by the specified array of vertices of this graph.
    
    Parameters:
    
    vertices - an array of vertices of this graph
    
    Returns:
    
    the subgraph given by the specified array of vertices
    
    Throws:
    
    IllegalArgumentException - if a vertex of the vertex array is not found in this graph
  - depthFirstSearch
```
public int depthFirstSearch(int start,
                            V goal)
```
    Returns the index of the searched target, or -1 if the target is not contained in this graph. In this case the algorithm has visited each vertex of the graph exactly once. The algorithm is taken from M. Dom et al.: "Tiefensuche (Ariadne und Co.)", in B. Vöcking et al.; Taschenbuch der Algorithmen. Springer-Verlag, Berlin Heidelberg 2008, p. 65 [DOI 10.1007/978-3-540-76394-9]
    
    Parameters:
    
    start - index of the current vertex
    
    goal - the searched vertex
    
    Returns:
    
    index of the searched vertex, or -1 if it does not exist
  - depthFirstSearch
```
public int depthFirstSearch(V start,
                            V goal)
```
    Returns the index of the searched vertex if it is reachable from the start vertex. If the searched vertex is not reachable, or null, the algorithm visits each vertex of the graph reachable from the start vertex exactly once.
    
    Parameters:
    
    start - the start vertex
    
    goal - the searched vertex
    
    Returns:
    
    index of the searched vertex, or -1 if it does not exist
  - breadthFirstSearch
```
protected int breadthFirstSearch(V start,
                                 V goal)
```
    Returns the index of the searched target, or -1 if the target is not contained in this graph. In this case the algorithm has visited each vertex of the graph exactly once. The algorithm is taken from M. Dom et al.: "Tiefensuche (Ariadne und Co.)", in B. Vöcking et al.; Taschenbuch der Algorithmen. Springer-Verlag, Berlin Heidelberg 2008, p. 71 [DOI 10.1007/978-3-540-76394-9]
    
    Parameters:
    
    start - start vertex
    
    goal - the searched vertex
    
    Returns:
    
    index of the searched vertex, or -1 if it does not exist
  - getCycles
```
public LinkedList<LinkedList<V>> getCycles(V x)
```
    Returns a list of the cycles in this graph starting in x. A cycle is a closed path, i.e., a path where start vertex and end vertex are identical. Note that in a cycle a vertex may be visited several times. For instance, in an undirected graph any path is a cycle, since it can be simply returned in the opposite direction.
    
    Parameters:
    
    x - the start vertex
    
    Returns:
    
    a list of all cycles starting in x
    
    See Also:
    
    hasCycles()
  - hasCycles
```
public boolean hasCycles()
```
    Checks whether this graph contains a cycle. A cycle is a closed path, i.e., a path where start vertex and end vertex are identical. Note that in a cycle a vertex may be visited several times. For instance, in an undirected graph any path is a cycle, since it can be simply returned in the opposite direction.
    
    Returns:
    
    true if this graph has a cycle
    
    See Also:
    
    getCycles(org.mathIT.graphs.Vertible)
  - getComponents
```
public ArrayList<Graph<V>> getComponents(V x)
```
    Returns a list of the strongly connected components of this graph which are reachable from vertex x. Two vertices x and y are connected if there exists a cycle x → ... → y → ... → x, and all vertices being connected to each other form a strongly connected component (SCC).
    
    Parameters:
    
    x - the start vertex
    
    Returns:
    
    a list of all strongly connected components reachable from x
  - topologicalSort
```
public int[] topologicalSort()
```
    Returns a topological sorting of this graph as an integer array σ, where σ(i) is the rank of vertex with index i. array string representation of the object. A topological sorting of a directed graph is a linear ordering of all its vertices, i.e., a bijective mapping σ: V → {1, 2, ..., |V|}. A topological sorting, however, is not possible if the graph is acyclic, i.e., if it contains a cycle. Cf. S.O. Krumke & H. Noltemeier: Graphentheoretische Konzepte und Algorithmen. Teubner, Wiesbaden 2005, §3.2.
    
    Returns:
    
    a topological sorting of this graph, or the zero array if the graph is not acyclic
  - detectClusters
```
public Clustering detectClusters()
```
    Returns a clustering of this graph which maximizes its modularity. For graphs with not more than 11 vertices, the modularity is computed by exhaustion, walking through all possible clusterings as subset partitions of the vertices, and therefore a true otimum clustering is accomplished. For larger graphs, however, the running time of the exhaustive algorithm explodes with estimated time complexity O(nⁿ). For this reason graphs with more than 11 vertices the greedy algorithm as described in U. Brandes et al. (2008): ‘On Modularity Clustering’. Knowledge and Data Engineering, IEEE Transactions on, 20(2): 172–188. doi: 10.1109/TKDE.2007.190689.. This implemantion requires a running time complexity of O(n⁵).
    
    Returns:
    
    an optimum clustering with respect to modularity
    
    See Also:
    
    Clustering.modularity(int[][], int, int[]), Clustering.modularity(int[][], int, int[], int[])
  - detectClustersExactly
```
public Clustering detectClustersExactly()
```
    Finds an optimum clustering by exhaustion. Advisable only for vertices.length < 13.
    
    Returns:
    
    an optimum clustering with respect to modularity
  - getRelevanceClusters
```
public Clustering getRelevanceClusters()
```
    Finds a clustering according to the relevance of each nde of this graph. Here the network relevance, or influence, of a node is defined by the impact of its removal to the Hashimoto matrix of the remaining network. Network relevance is an important notion to study system relevance, network stability, or network reliability. The nodes are clustered into categories of network relevance.
    After the calculation of the network relevances, the relevance values of all nodes are offered to be stored in a CSV file. In its first row there are stored the maximum and the minimum relevance value of all nodes, each following row consisting of node's label and its relevance value.
    
    Cf. A. Terras: Zeta Functions of Graphs. Cambridge University Press, Cambridge New York 2011, or F. Morone, H.A. Makse (2015): ‘Influence maximization in complex networks through optimal percolation’, Nature 524 (7563), pp. 65–68, doi 10.1038/nature14604 (or preprint arxiv 1506.08326).
    
    Returns:
    
    a clustering of nodes with respect to network relevance
  - toString
```
public String toString()
```
    Returns a string representation of this graph.
    
    Overrides:
    
    toString in class Object
    
    Returns:
    
    a string representation of this graph
  - toHTMLString
```
public String toHTMLString()
```
    Returns a string representation of the object as a table in HTML.
    
    Returns:
    
    a HTML table representation of the object
  - toJTable
```
public JTable toJTable()
```
    Returns a string representation of the object as a JTable.
    
    Returns:
    
    a JTable representation of the object
    
    See Also:
    
    JTable
  - toCSV
```
public StringBuilder toCSV()
```
    Returns a representation of this graph as a text in CSV format.
    
    Returns:
    
    a StringBuilder representation of this graph in CSV fomat
  - saveAsCSV
```
public void saveAsCSV()
```
    This method asks the user to select a file name and saves a representation of this graph as a CSV file.
  - createGraphFromCSVFile
```
public static Graph<SimpleVertex> createGraphFromCSVFile()
```
    Creates a graph from a CSV file selected by a file chooser dialog. In particular, the adjacency list of each vertex is derived from the matrix. If two vertices vertices[i] and vertices[j] do not have an edge connecting them, the respective adjacency matrix entry adjacency[i][j] is expected to have the value Double.POSITIVE_INFINITY. The vertices of the returned graph are of the raw type SimpleVertex.
    
    Returns:
    
    the created graph
  - createGraph
```
public static Graph<SimpleVertex> createGraph(int[][] adjacency)
```
    Creates a graph from the specified adjacency matrix. In particular, the adjacency list of each vertex is derived from the matrix. If two vertices vertices[i] and vertices[j] do not have an edge connecting them, the respective adjacency matrix entry adjacency[i][j] is expected to have the value Double.POSITIVE_INFINITY. The vertices of the returned graph are of the raw type SimpleVertex.
    
    Parameters:
    
    adjacency - the adjacency matrix determing the adjacencys of each edge of this graph
    
    Returns:
    
    the created graph
  - create
```
public static Graph<SimpleVertex> create(JTable jTable)
                                  throws NumberFormatException
```
    Creates a graph from the adjacency matrix specified by the input table. In particular, the adjacency list of each vertex is derived from the matrix. If two vertices vertices[i] and vertices[j] do not have an edge connecting them, the respective adjacency matrix entry adjacency[i][j] is expected to have the value Double.POSITIVE_INFINITY. The vertices of the returned adjacencyed graph are of the raw type Vertex.
    
    Parameters:
    
    jTable - the adjacency matrix determing the adjacencys of each edge of this graph
    
    Returns:
    
    the created graph
    
    Throws:
    
    NumberFormatException - if the input table does not represent an adjacency matrix
  - show
```
public static void show(JTable table)
```
    This method displays the specified table in a simple option pane.
    
    Parameters:
    
    table - a table
  - main
```
public static void main(String[] args)
```
    For test purposes...
    
    Parameters:
    
    args - arguments

Class Graph<V extends Vertible<V>>

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

SEPARATOR

undirected

weighted

vertices

adjacency

numberOfEdges

modifiableHashimoto

relevance

Constructor Detail

Graph

Graph

Graph

Graph

Graph

Graph

Graph

Graph

Graph

Method Detail

computeNumberOfEdges

computeHashimoto

getModifiedHashimoto

setUndirected

isUndirected

setVertices

getVertices

getVertex

getAdjacency

getNumberOfEdges

collectEdges

getDegree

getDegree

getDegrees

getIndegree

getIndegree

getOutdegree

getOutdegree

getIndegrees

getOutdegrees

getRelevance

laplacian

subgraph

subgraph

depthFirstSearch

depthFirstSearch

breadthFirstSearch

getCycles

hasCycles

getComponents

topologicalSort

detectClusters

detectClustersExactly

getRelevanceClusters

toString

toHTMLString

toJTable

toCSV

saveAsCSV

createGraphFromCSVFile

createGraph

create

show

main