Graph Utilities Package
The
Graph Utilities Package contains a number of functions useful for graph theory applications.
Functions in the Graph Utilities Package.
A graph can be represented by a list of rules or its adjacency matrix. Graphs in the
Combinatorica Package format are also supported.
AdjacencyMatrix
Finding the adjacency matrix of a graph
Given a graph in any of the formats supported by the Graph Utilities Package,
AdjacencyMatrix returns a matrix representing this graph.
The graph
g can be specified by a rule list, an adjacency matrix, or the
Combinatorica representation of a graph.
The rows and columns of the
SparseArray object correspond to vertices in the order returned by
VertexList[g].
This shows the adjacency matrix of a small graph. The 2 on the diagonal represents the two loops at vertex 1. The off-diagonal element 2 represents the two multiedges {b→a, b→a}.
Out[3]//MatrixForm= |
| |  |
|
The ith row/column of the matrix represents the vertex VertexList[g][[i]]. That is, in the above matrix, the first row corresponds to vertex b, the second to vertex a.
| Out[4]= |  |
|
This converts a graph into a sparse matrix, with two additional unconnected vertices added. It basically pads the matrix above with two columns and rows of zeros.
Out[5]//MatrixForm= |
| |  |
|
This shows the adjacency matrix of a graph specified by a Combinatorica object.
Out[6]//MatrixForm= |
| |  |
|
Input in the form of a matrix is unchanged.
Out[7]//MatrixForm= |
| |  |
|
Bicomponents
| Bicomponents[g] | gives the biconnected components of the undirected graph g |
Finding biconnected components.
Bicomponents[g] returns a list of all biconnected components in the undirected graph g.
A vertex
v is a cutpoint of a graph
g if
g is not connected after removing the vertex
v and all edges. A graph is biconnected if it has no cutpoint. A biconnected component (bicomponent) is a maximal subgraph that has no cutpoint.
This shows that a simple line with two vertices is biconnected.
| Out[8]= |  |
|
This shows two cycles linked by a line. Each of the cycles forms a bicomponent. The line breaks into two bicomponents.
| Out[10]= |  |
| Out[11]= |  |
|
ClosenessCentrality
Finding the closeness centrality.
The closeness centrality of a vertex
u is defined as the inverse of the sum of the distance from
u to all other vertices. The closeness centrality of a vertex in a disconnected graph is based on the closeness centrality of the component where this vertex belongs.
This calculates the closeness centrality of a grid graph and plots the graph so that vertices of high centrality are red.
| Out[13]= |  |
|
If a vertex does not have any paths to reach other vertices, the centrality of that vertex is zero.
| Out[20]= |  |
|
Centrality of a disconnected graph is calculated by treating each component separately.
| Out[21]= |  |
| Out[15]= |  |
|
Options for ClosenessCentrality
| | |
| Weighted | True | whether edge weight is used in calculating shortest path |
| Normalize | True | whether to normalize the output |
Options for ClosenessCentrality.
Weighted
The
Weighted option specifies whether edge weights are to be taken into account when calculating distances. Possible values are
True (the default) or
False.
Weighted->False means that edges are assumed to have unit length.
This shows a complete graph of three vertices, with one of the edges 2→3 repeated twice, thus having an edge weight of 2. This reduces the centrality of vertex 2.
| Out[22]= |  |
|
If it is intended that edge weights should all be one, then Weighted->False should be specified.
| Out[23]= |  |
|
Normalize
The
Normalize option specifies whether the output is normalized to give a maximal centrality of 1. Possible values are
True or
False (the default).
This calculates the closeness centrality of a complete graph of three vertices. Since the sum of the distance from any vertex to any other vertex is 2, the closeness for each vertex is 1/2 = 0.5.
| Out[25]= |  |
|
This normalizes the output.
| Out[26]= |  |
|
CommunityModularity, CommunityStructureAssignment, and CommunityStructurePartition
Functions for finding and assessing community structure.
CommunityStructurePartition gives the partition of a graph into communities. The partition groups the vertices into communities, such that there is a higher density of edges within communities than between them.
CommunityStructureAssignment gives the result as an assignment.
This defines a small graph.
| Out[30]= |  |
|
This finds the partition of the graph into communities.
| Out[31]= |  |
|
This shows the assignment of vertices into communities.
| Out[34]= |  |
|
This shows which vertices are assigned into which community.
| Out[33]= |  |
|
This plots the graph, with each community colored differently.
| Out[35]= |  |
|
Algorithms for finding community structure
Much relational information can be represented in graphs. One graph feature is community structure, which is the gathering of vertices into groups such that there is a higher density of edges within groups than between them. The discovery and analysis of community structure in graphs is useful in a number of applications. For example, in software engineering, it is sometimes necessary to group source code in directories so that interrelated routines are located in the same directory. In social networks, it is often necessary to identify groups of friends that form a close-knit community. In parallel computing, it is desirable to partition computing tasks, so that highly related tasks are placed on the same processor.
A number of algorithms exist that identify community structure in a network. One such algorithm is that of [
16]. The key concept is a quantity called community modularity. Suppose the graph of concern is
g={V, E}, and the vertex set
V is partitioned into
k subsets
V=
Vi such that each subset belongs to one community. Then the community modularity
Q of this partition is defined as
Q=
(ei i-ai2)
Here,
ei i is the percentage of number of edges that has both ends in community
Vi, and
ai is the percentage of edges that start from community
Vi. In other words,
ei i=|{ (u, v)|u
Vi, vVi, (u, v)E}|/|E|
ai=|{ (u, v)|uVi, (u, v)E}|/|E|.
Clearly,
Q≤
(ei i-ai2)≤
ei i≤1. Typically, for a random partition of
V,
Q is close to zero, while the partition of
V that gives a large positive value of
Q indicates a significant community structure.
Therefore the algorithm of [
16] starts by assigning every vertex into its own community, and calculates the change in
Q that will result from merging two communities into one. It then merge the two communities that give the highest positive change in
Q. This process is repeated on the merged network. The process terminates if the highest change is found to be negative.
The Weighted Option for CommunityStructurePartition, CommunityStructureAssignment, and CommunityModularity
The following option is accepted.
Option for CommunityStructurePartition, CommunityStructureAssignment and CommunityModularity.
The
Weighted option specifies whether edge weights are to be taken into account. Possible values for this option are
True or
False (the default).
This defines a graph with edge weights of 1 except the edge between vertices 3 and 4, which has an edge weight of 2. |
This finds and shows the three communities, ignoring the edge weights.
| Out[41]= |  |
|
This shows that when edge weight is taken into account, the larger edge weight between vertices 3 and 4 means that these two vertices are now placed in the same community.
| Out[44]= |  |
|
EdgeList
| EdgeList[g] | give a list of edges in the graph g. |
Finding the list of edges.
This gives the list of vertices of a simple graph.
| Out[45]= |  |
|
This converts a Combinatorica graph object to a rule list.
| Out[102]= |  |
| Out[103]= |  |
| Out[106]= |  |
|
| Out[104]= |  |
| Out[107]= |  |
|
ExpressionTreePlot
Functions for plotting an expression tree.
ExpressionTreePlot plots the expression tree of an expression. It has the same options as
TreePlot.
This gives an expression tree plot, with tooltips for each vertex giving the subexpression from that vertex down.
| Out[52]= |  |
|
This shows an expression tree up to level 2 with its root at the left.
| Out[53]= |  |
|
GraphCoordinates and GraphCoordinates3D
| GraphCoordinates[g] | calculate a visually appealing two-dimensional layout and return the coordinates of the vertices |
| GraphCoordinates3D[g] | calculate a visually appealing three-dimensional layout and return the coordinates of the vertices |
Graph drawing functions that return coordinates.
GraphCoordinates returns the coordinates of the vertices as computed using a graph drawing algorithm. It is useful when the coordinates of the vertices are needed, rather than a drawing of the graph, or when one needs to draw a graph repeatedly using the same layout but different style.
GraphCoordinates accepts the same options as
GraphPlot.
This defines and plots a small graph.
| Out[55]= |  |
|
This gives the coordinates of the vertices in the previous drawing.
| Out[56]= |  |
|
This plots the graph with two different styles, using the layout already calculated.
| Out[58]= |  |
|
The relationship between vertices and coordinates is given below.
| Out[8]= |  |
|
GraphCoordinates only returns the position of the vertices, so when used for
LayeredGraphPlot, curved edges will not be reproduced, although multiedges and self-loops will still be drawn.
Needs["GraphUtilities`"]
| Out[60]= |  |
|
This finds the vertex coordinates of the previous plot.
| Out[61]= |  |
|
This shows that the curved edges between vertices 1 and 3 are not reproduced.
| Out[62]= |  |
|
Options for GraphCoordinates and GraphCoordinates3D
GraphDistance, GraphPath, and GraphDistanceMatrix
| GraphDistance[g,start,end] | give the distance from vertex i to vertex j in the graph g |
| GraphPath[g,start,end] | find a shortest path between vertices start and end in graph g |
| GraphDistanceMatrix[g] | give a matrix in which the (i, j)th entry is the length of a shortest path in g between vertices i and j |
| GraphDistanceMatrix[g,Parent] | return a three-dimensional matrix in which the (1, i, j)th entry is the length of a shortest path from i to j and the (2, i, j)th entry is the predecessor of j in a shortest path from i to j. |
Finding shortest distance, shortest path, and all-pairs shortest distances and paths.
GraphDistance returns the graph distance from one vertex to another.
Infinity is returned if no path exists from
i to
j. By default every edge is assumed to have an edge weight of 1.
GraphPath and
GraphDistanceMatrix find shortest path and all-pairs shortest paths.
This shows a dodecahedron in two dimensions.
| Out[72]= |  |
|
This shows that the distance between vertices 7 and 18 is 4, and gives the path.
| Out[87]= |  |
| Out[90]= |  |
|
This shows that there is no path from vertex 7 to 6.
| Out[76]= |  |
| Out[91]= |  |
|
This finds the distances between all vertices.
Out[93]//MatrixForm= |
| |  |
|
This defines a simple directed graph.
| Out[96]= |  |
|
This calculates the distance between vertices.
Out[79]//MatrixForm= |
| |  |
|
This shows the predecessors in the shortest path, for example, the path from 1 to 3 has predecessor 4 ( prd[[1, 3]]), the path from 1 to 4 has predecessor 5 ( prd[[1, 4]]), and therefore the path from 1 to 3 is {1, 5, 4, 3}.
Out[81]//MatrixForm= |
| |  |
| Out[82]= |  |
|
This confirms the shortest path.
| Out[97]= |  |
|
Algorithms for shortest paths
In the following it is assumed that
w (i, j) is the edge weight of edge
{i, j}, and
d (i, j) is the current estimate of the length of the shortest path from vertex
i to vertex
j.
Single-source shortest path algorithms
Single-source shortest path algorithms find the shortest path from one vertex
u to all other vertices.
Dijkstra's algorithm assumes that edge weights are nonnegative.
S: the set of vertices whose shortest distance to
u has been found.
Q: the set of vertices not in
S that
S "touches", stored in a heap.
1. picks in
Q the vertex
i with the smallest
d value. This step has complexity
O (Log[|V|])with a binary heap or with a Fibonacci heap, and in all cases it will be repeated |V| times.
2. places vertex
i in
S, inserts all neighbors
j of
i in
Q, if vertex
j is not in
Q. If
d[j]>d[i]+w[i, j], it sets
d[j]=d[i]+w[i, j] and updates the heap. Each insertion/update to the heap has complexity
O (Log[|V|]) with a binary heap, and
O (1) with a Fibonacci heap, and in all,
|E| update operations and
|V| insertions are needed.
So the overall complexity is
O ( (|V|+|E|)Log|V|) with a binary heap, and
O (|V|Log|V|+|E|+|V|) with a Fibonacci heap.
The Bellman-Ford algorithm works even if edge weights are negative. It works by looping through each edge
{i, j}, if
d[j]>d[i]+w[i, j], set
d[j]=d[i]+w[i, j]. Since this looping is carried out
|V|-1 times, the Bellman-Ford algorithm has a complexity of
O (|E||V|), which is much higher than Dijkstra's algorithm. Therefore it is only used if the graph contains negative weights. The algorithm can detect negative weight cycles.
All-pairs shortest path algorithms
All-pairs shortest path algorithms find shortest paths between all vertex pairs.
The Floyd-Warshall
algorithm sets all distances to
initially, except for neighboring vertices, for which the distance is set to the edge weights. It then loops over all vertex pairs
{i, j}, and relaxes if
d[i, j]<d[i, k]+d[k, j], in which case it sets
d[i, j]=d[i, k]+d[k, j]. This is so that at any iteration
k, the distance
d[i, j] represents the shortest distance between vertices
i and
j, passing through only vertices
1, 2, ..., k. This algorithm has a complexity of
O (|V|3). It works even for negative weights, but does not detect negative weight cycles.
If the edge weights are nonnegative, the Dijkstra algorithm can be applied repeatedly to each vertex, for single-source shortest paths. This gives a complexity of
O ( (|V|+|E|)|V|Log|V|) with a binary heap, and
O (|V|2Log|V|+|E||V|) with a Fibonacci heap.
If there are negative edge weights, then the Dijkstra algorithm can not be applied directly. The Johnson algorithm first makes all edge weights positive, by associating a value
p[i] to every vertex
i, such that
w[i, j]+p[i]-p[j]≥0 if
i
j. The edge weights are then modified by
w[i, j]:=w[i, j]+p[i]-p[j].
To modify the edge weights, a virtual vertex
s is added that is linked to every vertex, with an edge weight of 0. Then for any vertex
i,
p[i] is defined as the distance of
s to
i. So for every edge
{i, j},
p[j]≤p[i]+w[i, j], otherwise
p[j] is not the length of a true shortest path. Hence
w[i, j]+p[i]-p[j]≥0.
This modification does not change the shortest path, hence the Dijkstra algorithm can then be applied to the weight-modified graph. After that, the distance is modified back by
d[i, j]:=d[i, j]+p[j]-p[i].The Johnson algorithm has the same complex as the Dijkstra algorithm when edge weights are nonnegative, otherwise it has the same complexity as the Bellman-Ford algorithm.
Options for GraphPath, GraphDistanceMatrix, and GraphDistance
Options for GraphPath and GraphDistanceMatrix.
| | |
| Weighted | False | whether edge weight is used in calculating shortest paths |
Option for GraphDistance.
Method
The option
Method specifies the algorithm used to find the shortest paths. By default
Method is set to
Automatic, which uses Johnson's algorithm. Other possible values for this option are
"BellmanFord",
"Dijkstra",
"FloydWarshall", and
"Johnson".
Weighted
The option
Weighted specifies whether edge weights are to be taken into account when finding shortest paths. Possible values are
True or
False.
GraphEdit
| GraphEdit[] | interactively create and edit a graph |
| GraphEdit[g] | interactively edit the graph g |
Interactive graph editing.
GraphEdit is a
J/Link application. On executing this function, a Java window will be opened. Users can then enter a new graph or modify an existing graph, and get the resulting graph back in
Mathematica.
The graph
g may be specified by a rule list, an adjacency matrix, or the
Combinatorica representation of a graph.
Vertices and edges can be added by clicking and dragging with the mouse. Vertices can be moved after setting "Drawing mode" to "Move" and dragging the mouse on the vertices. Vertices can be deleted after setting "Drawing mode" to "Delete" and selecting the vertices to be deleted by clicking.
Users can hold the
Ctrl key and click the vertex (using the first mouse button) in the
GraphEdit window to edit the vertex labels.
On closing the window, a drawing of the graph, a representation of the graph as a list of rules, the coordinates, and the vertex labels are returned.
LineScaledCoordinate
| LineScaledCoordinate[{{x1,y1},{x2,y2},...,{xk,yk}},r] |
| give the coordinate of a point in the polyline {{x1, y1}, {x2, y2}, ..., {xk, yk}}, at a scaled distance of r from point {x1, y1} |
| LineScaledCoordinate[{{x1,y1},{x2,y2},...,{xk,yk}}] |
| equivalent to LineScaledCoordinate[ {{x1, y1}, {x2, y2}, ..., {xk, yk}}, 0.5] |
Finding the coordinates of a point on a polyline.
LineScaledCoordinate is often used in conjunction with the
EdgeRenderingFunction option of
GraphPlot,
GraphPlot3D, or
LayeredGraphPlot, to add text or graphics along the edge of a graph.
This displays the vertices that form the edges 60% along the arrow.
| Out[2]= |  |
|
MaximalBipartiteMatching
Finding the maximal bipartite matching.
MaximalBipartiteMatching gives a maximal set of nonadjacent edges between the two vertex sets of the bipartite graph.
The bipartite graph represented by an
m×
n matrix consists of the row and column vertex sets
R={1, 2, ..., m} and
C={1, 2, ..., n}, with a vertex
iR and
jC connected if the matrix element
gij≠0.
The bipartite graph represented by a rule list
{i1->j1, i2->j2, ...} consists of vertex sets
R=Union[{i1, i2, ...}] and
C=Union[{j1, j2, ...}], with a vertex
iR and
jC connected if the rule
i->j is included in the rule list.
MaximalBipartiteMatching returns a list of index pairs
{{i1, j1}, ..., {ik, jk}}, where the number of pairs
k is not larger than either vertex set.
This finds a maximal matching.
| Out[5]= |  |
|
Applications
MaximalBipartititeMatching can be used to permute as many entries as possible onto the diagonal of a sparse matrix.
This defines a random 50×60 sparse matrix with approximately 4% of the elements nonzero. Needs["GraphUtilities`"]
| Out[6]= |  |
| Out[7]= |  |
|
This finds unmatched rows and columns. |
This orders the matrix by permuting matched rows and columns to the principal diagonal block first.
| Out[15]= |  |
|
MaximalBipartititeMatching can be used to find the structural rank of a sparse matrix. The structural rank of a matrix is the number of entries in the maximal matching of the bipartite graph of the matrix. It is an upper bound on the numeric rank of the matrix. A matrix has structural full rank if it can be permuted so that the diagonal has no zero entries.
This shows that on average, a random 50×50 matrix with 4% nonzero entries has structural rank of 39.4.
| Out[24]= |  |
|
MaximalIndependentEdgeSet
Finding the maximal independent edge set.
MaximalIndependentEdgeSet gives an approximate maximal set of pairwise nonadjacent edges of
g. A maximal independent edge set of a graph is also called a maximal matching.
This defines a graph and finds a maximal independent edge set.
| Out[27]= |  |
|
This plots the graph so that edges in the maximal independent edge set are red.
| Out[31]= |  |
|
The defines a graph with edge weights and finds a maximal independent edge set. |
