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 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.
|
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)
Mkl = ni Bkl
where ni = 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.
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).
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(nn).
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(n5).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.
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).
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