V
 the type of the verticespublic class Graph<V extends Vertible<V>> extends Object
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); ... }
WeightedGraph
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 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.

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 nonbacktracking 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 nonbacktracking 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.

public static final char SEPARATOR
protected boolean undirected
protected boolean weighted
Weighted Graph
.protected int[][] adjacency
protected int numberOfEdges
protected ArrayList<ArrayList<Function<Integer,Integer>>> modifiableHashimoto
(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.protected double[] relevance
Hashimoto matrix
of the
remaining network. Network relevance is an important notion to study
system relevance, network stability, or network reliability.getRelevance(int)
public Graph()
public Graph(ArrayList<V> vertices, V[] arrayTemplate)
vertices
 array of the vertices forming this grapharrayTemplate
 an array of the type of vertices. This array may be empty.
It is necessary technically because generic array creation is prohibited in Java.public Graph(V[] vertices)
vertices
 an array of the vertices of this graphpublic Graph(boolean undirected, V[] vertices)
undirected
 indicator whether this graph is undirectedvertices
 an array of the vertices of this graphpublic Graph(int[][] adjacency, V[] arrayTemplate)
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!adjacency
 the adjacency matrix determining the adjacencies of each vertex of this grapharrayTemplate
 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.IllegalArgumentException
 if adjacency is not a square matrixpublic Graph(boolean undirected, int[][] adjacency, V[] arrayTemplate)
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!undirected
 flag indicating whether this graph is undirectedadjacency
 the adjacency matrix determining the adjacencies of each vertex of this grapharrayTemplate
 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.IllegalArgumentException
 if adjacency is not a square matrix,
or if the graph is undirected and the adjacency matrix is not symmetricpublic Graph(V[] vertices, int[][] adjacency)
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!vertices
 array of the vertices forming this graphadjacency
 the adjacency matrix determining the adjacencies of each vertex of this graphIllegalArgumentException
 if adjacency is not a square matrix or if
the number of vertices does not equal the length of the adjacency matrixpublic Graph(boolean undirected, V[] vertices, int[][] adjacency)
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!undirected
 flag indicating whether this graph is undirectedvertices
 array of the vertices forming this graphadjacency
 the adjacency matrix determining the adjacencies of each vertex of this graphIllegalArgumentException
 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 symmetricpublic Graph(ArrayList<V> vertices, int[][] adjacency, V[] arrayTemplate)
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!vertices
 array of the vertices forming this graphadjacency
 the adjacency matrix determining the adjacency of each edge of this grapharrayTemplate
 an array of the type of vertices. This array may be empty.
It is necessary technically because generic array creation is prohibited in Java.protected final int computeNumberOfEdges()
public int[][] computeHashimoto()
public int[][] getModifiedHashimoto(int i)
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.
i
 the node of the graph to be removed virtuallymodifiableHashimoto
public void setUndirected(boolean undirected)
undirected
 flag which is true if this graph is undirectedpublic boolean isUndirected()
public void setVertices(V[] vertices)
vertices
 an array of all vertices of this graphpublic V[] getVertices()
public V getVertex(int i)
i
of this graph.
If a vertex with this index does not exist, it returns null
.i
 the indexpublic int[][] getAdjacency()
public int getNumberOfEdges()
i
of this graph.
If a vertex with this index does not exist, it returns null
.public HashSet<Edge<V>> collectEdges()
public int getDegree(V vertex)
vertex
 a vertex of the graphIllegalArgumentException
 if this graph is directedgetDegree(int)
,
getIndegree(org.mathIT.graphs.Vertible)
,
getOutdegree(org.mathIT.graphs.Vertible)
public int getDegree(int i)
i
 the index of a vertex of the graphIllegalArgumentException
 if this graph is directedgetDegree(org.mathIT.graphs.Vertible)
,
getIndegree(int)
,
getOutdegree(int)
public int[] getDegrees()
IllegalArgumentException
 if this graph is directedgetDegree(org.mathIT.graphs.Vertible)
,
getDegree(int)
,
getIndegrees()
,
getOutdegrees()
public int getIndegree(V vertex)
vertex
 a vertex of the graphgetIndegree(int)
public int getIndegree(int i)
i
 the index of a vertex of the graphgetIndegree(org.mathIT.graphs.Vertible)
public int getOutdegree(V vertex)
vertex
 a vertex of the graphgetIndegree(int)
public int getOutdegree(int i)
i
 the index of a vertex of the graphgetOutdegree(org.mathIT.graphs.Vertible)
public int[] getIndegrees()
getIndegree(org.mathIT.graphs.Vertible)
,
getIndegree(int)
public int[] getOutdegrees()
getOutdegree(org.mathIT.graphs.Vertible)
,
getOutdegree(int)
public double getRelevance(int i)
Hashimoto matrix
of the
remaining network. Network relevance is an important notion to study
system relevance, network stability, or network reliability.
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).
i
 index of a nodepublic Matrix laplacian()
public Graph<V> subgraph(Set<V> vertices)
vertices
 a set of vertices of this graphIllegalArgumentException
 if a vertex of the set is not found in this graphpublic Graph<V> subgraph(V[] vertices)
vertices
 an array of vertices of this graphIllegalArgumentException
 if a vertex of the vertex array is not found in this graphpublic int depthFirstSearch(int start, V goal)
start
 index of the current vertexgoal
 the searched vertexpublic int depthFirstSearch(V start, V goal)
null
, the
algorithm visits each vertex of the graph reachable from the start vertex
exactly once.start
 the start vertexgoal
 the searched vertexprotected int breadthFirstSearch(V start, V goal)
start
 start vertexgoal
 the searched vertexpublic LinkedList<LinkedList<V>> getCycles(V x)
x
 the start vertexhasCycles()
public boolean hasCycles()
getCycles(org.mathIT.graphs.Vertible)
public ArrayList<Graph<V>> getComponents(V x)
x
 the start vertexpublic int[] topologicalSort()
public Clustering detectClusters()
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^{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^{5}).Clustering.modularity(int[][], int, int[])
,
Clustering.modularity(int[][], int, int[], int[])
public Clustering detectClustersExactly()
public Clustering getRelevanceClusters()
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.public String toString()
public String toHTMLString()
public JTable toJTable()
JTable
.JTable
public StringBuilder toCSV()
public void saveAsCSV()
public static Graph<SimpleVertex> createGraphFromCSVFile()
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
.public static Graph<SimpleVertex> createGraph(int[][] adjacency)
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
.adjacency
 the adjacency matrix determing the adjacencys of each edge of this graphpublic static Graph<SimpleVertex> create(JTable jTable) throws NumberFormatException
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
.jTable
 the adjacency matrix determing the adjacencys of each edge of this graphNumberFormatException
 if the input table does not represent an adjacency matrixpublic static void show(JTable table)
table
 a tablepublic static void main(String[] args)
args
 arguments