DiscreteMath`GraphPlot

Introduction

DiscreteMath`GraphPlot provides functions for aesthetic straight-edge drawing of graphs. Algorithms implemented include the spring model (also known as spring embedding), the spring-electrical model, high-dimensional embedding, radial drawing, and layered drawing methods. The package also contains a number of functions useful for graph theory applications.

The package is designed to work efficiently for very large graphs. In this package, a graph is represented by its adjacency matrix. Graphs from the Combinatorica package are also supported, as are graphs specified by a rule list.

This loads the package.

In[1]:=

Graph Theory Notations

A graph consists of a set of vertices (also called nodes) and a set of edges . Two vertices form an edge of the graph if

If implies that , then is an undirected graph. Otherwise it is a directed graph. The former can be drawn using line segments, while the latter can be drawn with arrows. In an undirected graph, it is often convenient to denote that an edge exists between and with the notation .

For example, this is a directed graph.

Here is a undirected graph.

Graphs and Matrices

In this package, a graph can be represented by one of three data structures.

A graph can be represented by a rule list. For example, represents the following directed graph.

A graph can also be represented by its adjacency matrix. Let be a directed graph. Assuming that the vertices are indices from to , that is, , then the adjacency matrix of is an matrix, with entries if and otherwise. For example, the following adjacency matrix represent the same directed graph as above.

An undirected graph, on the other hand, is represented by a symmetric adjacency matrix. The matrix entries if and otherwise. For example, this adjacency matrix represents the undirected graph that follows it.

Because of the zero entries in an adjacency matrix, it is often convenient to represent the matrix using a SparseArray. For example, the previous matrix can be written as the following sparse array.

In[2]:=

A bipartite graph, also called a bigraph, is a special graph in which the vertices can be decomposed into two sets, and C, such that no edges exist between vertices within R, and no edges exist between vertices within C. Assuming that there are vertices in R and vertices in C, a bipartite graph can be represented by an matrix with all entries zero except if , , and forms an edge.

Sometimes a graph will have attributes associated with the vertices and edges. Weights are one such attribute. Edge weights can be included in the adjacency matrix by making contain the weight for the edge Vertex weights cannot be easily included in the adjacency matrix. However, a separate vector of length can be used to contain the vertex weights.

Finally, graphs from the Combinatorica package are also supported.

GraphPlot/GraphPlot3D

This plots a graph specified by a rule list.

In[3]:=

GraphPlot and GraphPlot3D work with disconnected graphs. The individual components are laid out in a visually appealing way.

In[4]:=

GraphPlot and GraphPlot3D are designed to work with very large graphs. This plots a graph defined by a matrix from a structural engineering application. An image of the actual application can be seen at the following URL:
http://math.nist.gov/MatrixMarket/data/Harwell-Boeing/dwt/dwt_1005.html

In[6]:=

In[7]:=

GraphPlot and GraphPlot3D also work with graphs created by the Combinatorica package. This example creates a butterfly graph using Combinatorica and shows the layout Combinatorica assigned.

In[8]:=

This draws the same graph using GraphPlot.

In[9]:=

GraphPlot may produce slightly different output on different platforms, due to floating point differences.

Graph Drawing Algorithms

Graphs are often used to encapsulate the relationship between items. Graph drawing enables visualization of these relationships. The usefulness of the visual representation depends upon whether the drawing is aesthetic. While there are no strict criteria for aesthetic drawing, it is generally agreed that such a drawing has minimal edge crossing and even spacing between vertices. This problem has been studied extensively in the literature, and many approaches have been proposed. Two popular straight-edge drawing algorithms, the spring model and spring-electrical model, work by minimizing the energy of physical models of the graph. The high-dimensional embedding method, on the other hand, is quite different.

Spring model

The spring model assigns force between each pair of nodes. When two nodes are too close together, a repelling force comes into effect. When two nodes are too far apart, they are subject to an attractive force. This scenario can be illustrated by linking the vertices with springs--hence the name "spring model" (or "spring embedding method").

This algorithm works by adding springs to all edges and adding looser springs to all vertex pairs that are not adjacent. Thus, in two dimensions, the total energy of the system is

Here, and are the coordinate vectors of nodes and , and is the Euclidean distance between them. is the natural length of the spring between vertex and vertex , and can be chosen as the graph distance between and . The parameters are the strength of the springs, where R is a parameter representing the strength of the strings. is the number of vertices.

The layout of the graph vertices is calculated by minimizing this energy function. One way to minimize the energy function is by iteratively moving each of the vertices along the direction of the spring force until an approximate equilibrium is reached. Multilevel techniques are used to overcome local minima.

The spring model works well for problems like regular grid graphs, in which it is possible to lay out the graph so that physical distances between vertices are proportional to the graph distances. This model does, however, require more memory and CPU time. To reduce its complexity, vertices that are far apart are ignored in the calculation of the force and energy. See the method option InferentialDistance for more information.

In[10]:=

Spring-electrical model

The disadvantage of the spring model is that it requires knowing the graph distance between every pair of vertices. The spring-electrical model uses two forces. The attractive force, , is restricted to adjacent vertices and is proportional to the physical distance between them. The electrical force, , on the other hand, is global and is inversely proportional to the distance between nodes and . Overall, the energy to be minimized is , where

Here, is a constant that regulates the relative strength of the repulsive and attractive forces, is the Euclidean distance between nodes and , and K is the natural spring length. For a graph of two vertices, the ideal distance between the vertices is , which gives a total energy of zero.

The layout of the graph vertices is calculated by minimizing the energy function. One way to do this is by iteratively moving each of the vertices along the direction of the spring force until an approximate equilibrium is reached. Multilevel techniques are used to overcome local minima, and an octree data structure is used to reduce the computational complexity in some cases.

In general, the spring-electrical model works well for most problems. With multilevel and octree techniques, it is implemented very efficiently with a complexity of about . A side-effect of this algorithm is that vertices at the periphery tend to be closer to each other than those in the center.

In[11]:=

This tendency can be alleviated with the method option RepulsiveForcePower, which is described later.

High-dimensional embedding

In the high-dimensional embedding method, a graph is embedded in a high number of dimensions and then projected back linearly to two or three dimensions.

First, a k-dimensional coordinate system is created based on k centers. The centers are a set of k vertices that are chosen to be as far apart as possible. The first vertex is selected at random, and then each of the remaining centers is chosen as the farthest vertex from the previously selected centers. In other words, if j centers have been selected, is the vertex whose shortest distance to the j centers is larger than or equal to the shortest distance of all the other vertices to the j centers.

Here, there are n k-dimensional coordinate vectors, where n is the total number of vertices in the graph. Each vertex has the coordinates {}, where is the graph distance between the vertex and the center . The n k-dimensional coordinate vectors form an n × k matrix X, where is the -th row of .

Since it is only possible to draw in two and three dimensions, and since the coordinates are correlated, the coordinates are projected back to two or three dimensions by a suitable linear combination.

Here, the graph with n coordinates and k centers is projected back to 2 dimensions. To make this projection shift-invariant, X is first normalized to .

Let be two k-dimensional linear combination vectors. The two linear combinations should be uncorrelated, so they must be orthogonal to each other.

Each must be as far away from 0 as possible.

To achieve this, let and be the two eigenvectors that correspond to the first two largest eigenvalues of the k x k symmetric matrix . This process of choosing two highly uncorrelated vectors is also known as principal component analysis.

For the purpose of drawing the graph in two dimensions, the coordinates of the vertices are given by and

The high-dimensional embedding method tends to be very fast but its results are often of lower quality than force-directed algorithms.

Algorithms for drawing trees

If the graph represents a tree, algorithms that are designed to draw trees are more suitable. Two such algorithms are the radial drawing algorithm and the layered drawing algorithm [1]. In the radial drawing algorithm, a reasonable root of the tree is chosen. Then, starting from that root of the tree, each sub-tree is drawn inside a wedge, with the angle of the wedge proportional to the number of leaves in that sub-tree. In the layered drawing algorithm, a reasonable root of the tree is chosen. Then, starting from that root, sub-trees of the root are recursively drawn such that vertices on the same level have the same coordinate, and the horizontally closest vertices of adjacent sub-trees are of unit distance apart. The root is placed at the center of the -coordinates of its sub-trees and its y-coordinate is one unit above them.

Options for GraphPlot/GraphPlot3D

In addition to options for Graphics and Graphics3D, the following options are accepted.

Method

GraphPlot and GraphPlot3D have several methods available. The method is specified by the Method option, which either takes the method given as a string or a list whose first element is the method (given as a string) and whose remaining elements are method-specific options. All method-specific options should also be given as strings.

The following are valid values of the Method option.

VertexStyleFunction

Possible values for this option are Automatic, None, or a user-supplied function. The user-supplied function should be of the form f[i_]:=..., where is a vertex index.

By default, VertexStyleFunction is set to None. A point is drawn for each vertex, but the point is not labeled. If VertexStyleFunction is set to Automatic, a point and a label are drawn for each vertex when graphs are small.

Sometimes it is convenient to be able to define a custom style. In this example, vertices are plotted as red disks.

In[12]:=

To draw no vertices at all, define VertexStyleFunction to be the empty list.

In[13]:=

In[14]:=

EdgeStyleFunction

Possible values for this option are Automatic, None, or a user-supplied function. A user-supplied function should be of the form f[i_,j_]:= ..., where and are the two vertex indices of an edge.

With the default setting of None, a black line is drawn for each edge. If EdgeStyleFunction is set to Automatic, the styles of the edges are chosen automatically. Colors are assigned based on the absolute entry values of the matrix: red for the largest entries and blue for the smallest ones. For pattern matrices, colors are assigned based on the length of the edges: red for the largest lengths and blue for the smallest ones. Arrows are used for small graphs when the matrix is unsymmetric.

This shows how the entry values of the matrix affect the colors of the arrows.

In[15]:=

Here, the colors are based on the length of the edges.

In[16]:=

Sometimes it is convenient to be able to define a custom style. An EdgeStyleFunction uses the form f[i_, j_]:= ..., where and are indices of two vertices that form an edge. In this example, the edges are plotted as gray arrows.

In[17]:=

To draw no edges at all, define EdgeStyleFunction as the empty list.

In[18]:=

In[19]:=

PlotStyle

This specifies the style in which objects are drawn.

Here, objects are drawn in blue with a point size of 0.1.

In[20]:=

RandomSeed

This specifies what random seed is used. In the spring model and spring-electrical model, the random seed is used to generate the initial vertex placement. In the high-dimensional embedding method, it is used to select the first of the k centers. The random seed usually changes the orientation of the drawing of a graph, but sometimes it also changes the drawing. Possible values of RandomSeed are Automatic or an integer.

In[21]:=

In[22]:=

In[23]:=

VertexCoordinates

This specifies the coordinates of the vertices. This option should only be used if the user knows the coordinates of the vertices. Possible values of VertexCoordinates are None or a list of coordinates.

This draw the Petersen Graph using known coordinates.

In[24]:=

This draws it using the spring model algorithm.

In[25]:=

Common method options for SpringModel and SpringElectricalModel

Both the SpringModel and SpringElectricalModel methods belong to the family of so-called "force-directed methods". These methods work by calculating the force on each vertex, and iteratively moving the vertex along the force in an effort to minimize the overall system's energy. These two methods have the following common options.

Tolerance

This specifies the tolerance used in terminating the energy minimization process. If the average change of coordinates of each vertex is less than the tolerance, the energy minimization process is terminated and the current coordinates are given as output. Possible values are Automatic or a positive real machine number.

MaxIterations

This specifies the maximum number of iterations to be used in attempting to minimize the energy. Possible values are Automatic (the default) or a positive integer.

RecursionMethod

This specifies whether a multilevel algorithm is used to lay out the graph. In a multilevel algorithm, the graph is successively coarsened into smaller and smaller graphs. The smaller graphs are laid out first, and those layouts are interpolated into the finer graphs and then further refined. Possible values of RecursionMethod are Automatic (the default), Multilevel, or None.

The following are suboptions for Multilevel.

The following are possible values for CoarseningScheme.

StepControl

This defines how step length is modified during energy minimization. It can be Automatic (the default), "Monotonic" (where step length can only be decreased), "NonMonotonic" (where step length can be made larger or smaller), or "StrictlyMonotonic" (where step length is strictly reduced between iterations).

EnergyControl

Valid values are Automatic (the default), "Monotonic", or "NonMonotonic". When the value is "Monotonic", a step along the force will only be accepted if the energy is lowered. When the value is "NonMonotonic", a step along the force will be accepted even if the energy is not lowered.

StepLength

This gives the initial step length used in moving the vertices around. Possible values are Automatic (the default) or a positive real machine number.

InferentialDistance

Possible values are Automatic (the default) or a positive machine integer. The SpringModel method requires calculating the graph distance between vertices. InferentialDistance specifies a cut-off distance value. When the graph distance between a vertex i and a vertex j is greater than the value of InferentialDistance, the spring force between i and j is ignored. For the SpringElectricalModel method, a small positive machine integer value for InferentialDistance causes the repulsive force from far-away vertices to be ignored.

Method options for SpringElectricalModel

Octree

Possible values are Automatic (the default), True, or False. This specifies whether to use an octree data structure (in three dimensions) or a quadtree data structure (in two dimensions) in the calculation of repulsive force. Use of an octree data structure minimizes the complexity of computation by approximating the long range repulsive force.

RepulsiveForcePower

Possible values are negative machine numbers, with -1 as the default. In the spring-electrical model, repulsive force between two vertices and is by default. If the value of RepulsiveForcePower is r (with r < 0), then the repulsive force is defined as A smaller repulsive force over long distance often has the boundary effect that vertices in the periphery are closer to each other than those in the center are. For example, with a repulsive force power of -2, the boundary vertices are not as close to each other as they are with the default value of -1.

In[26]:=

In[27]:=

This option can often be useful in drawing trees, as described later.

Method options for HighDimensionalEmbedding

RefinementMethod

This specifies whether the result should be further refined, and which method should be used to refine it. Possible values are None (the default), SpringModel, or SpringElectricalModel.

Further examples

Using non-default methods and options

Although the default method works well for most cases, an alternative method occasionally works better. Five methods are available: SpringElectricalModel, SpringModel, HighDimensionalEmbedding, RadialDrawing, and LayeredDrawing. Here is an example where a non-default method works better.

This is the default drawing.

In[28]:=

Here is an alternative, which looks better.

In[32]:=

Here is a speed comparison of three of the models. It illustrates that HighDimensionalEmbedding tends to be the fastest method, followed by SpringElectricalModel and SpringModel. SpringElectricalModel uses the least memory, followed by HighDimensionalEmbedding and SpringModel. Both SpringElectricalModel and SpringModel produce good, although different, drawings; the drawings produced by HighDimensionalEmbedding are of lower quality.

In[33]:=

In[35]:=

In[36]:=

The default method usually works well for tree-like graphs, but sometimes SpringModel draws a tree that is more expanded.

In[37]:=

In[39]:=

A similar effect can be achieved with a repulsive force power smaller than the default (-1), so that the repulsive force decays more quickly over distance.

In[40]:=

For such tree-like graphs, a tree drawing algorithm may be preferable.

In[41]:=

In[42]:=

For trees, use TreePlot for greater control over graph layout.

Improving performance

Although performance is very good with the default settings, a number of options that increase drawing speed and reduce memory usage are available.

This is a drawing with default option settings.

In[43]:=

A coarsening scheme based on the maximal independent vertex set is often faster than the default coarsening scheme. It also uses less memory, and it usually offers a comparable layout quality.

In[45]:=

In[46]:=

Drawing speed can be increased by setting a smaller number of iterations, a smaller inferential distance, or a lower tolerance. These settings tend to reduce quality, but for most graphs the drawings are acceptable.

For example, this sets the number of iterations to be 30. It is faster than the default.

In[47]:=

This sets the inferential distance to 2 and the number of iterations to 40. It is also faster than the default.

In[48]:=

This sets the inferential distance to 2 and the number of iterations to 20. It is much faster than the default.

In[49]:=

A combination of the previous options is even faster.

In[50]:=

HighDimensionalEmbedding tends to be the fastest method, but the quality of the drawing is often not as good.

In[51]:=

Force-directed methods (SpringModel or SpringElectricalModel) can be used to refine the output of HighDimensionalEmbedding, but the result is not always an improvement.

In[52]:=

For comparison, here is the drawing produced by SpringModel. It is the slowest method, but it is the only one that draws the mesh using orthogonal lines.

In[53]:=

GraphCoordinates/GraphCoordinates3D

GraphCoordinates[g, options] 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.

This plots a graph.

In[54]:=

This gives the coordinates of the vertices in the previous drawing.

In[56]:=

This plots the graph with each edge labeled with the indices of the pair of vertices that forms the edge. Since the coordinates are known, they can be reused as the value of the VertexCoordinates option. This saves the cost of recomputing the graph layout.

In[57]:=

Options for GraphCoordinates/GraphCoordinates3D

The following options are accepted. For more information about these options, see Options for GraphPlot/GraphPlot3D.

This returns the coordinates given by the spring model method.

In[58]:=

TreePlot

TreePlot[g] plots the graph g as a tree. It provides greater control over layout than the LayeredDrawing and RadialDrawing methods for GraphPlot.
TreePlot[g] uses the layered drawing algorithm. This algorithm starts from the root of the tree, and recursively draws sub-trees of the root such that vertices on the same level have the same coordinate, and the horizontally closest vertices of adjacent sub-trees are of unit distance apart. The root is placed at the center of the -coordinates of its sub-trees, and its y-coordinate is one unit above them. TreePlot[g, "RootPosition"->Center] uses the radial drawing algorithm. This algorithm starts from the root of the tree and draws each sub-tree inside a wedge, with the angle of the wedge proportional to the number of leaves in that sub-tree. By default, TreePlot chooses the root that gives the shortest tree, however it is possible to use any vertex as a root with TreePlot[g, r].

This defines a k-ary tree. KaryTree[n] gives a binary tree with n levels.

In[59]:=

This plots a binary tree with 5 levels. By default, TreePlot chooses the root that gives the shortest tree.

In[60]:=

This plots the same tree but with vertex as the root. This tree now has noticeably more layers.

In[62]:=

Options for TreePlot

TreePlot accepts the following option, as well as all options for Graphics and the GraphPlot options VertexStyleFunction , EdgeStyleFunction , and PlotStyle.

AspectRatio

This specifies the ratio of height to width for the plot. Valid values are Automatic or a positive real machine number. The default value is Automatic, which is different from the default value of AspectRatio for Graphics.

RootPosition

This specifies the position of the root of the tree. Possible values are Automatic, Top, Bottom, Left, Right, and Center.

This is the same tree as the previous plot, but the root of the tree is in the center.

In[63]:=

This plots the same tree with the root on the left.

In[64]:=

This plots a more complex k-ary tree with 4 levels.

In[65]:=

TreeSizeFunction

The value of this option is a function that specifies the height of each level of the tree plot. The default function specifies a height of one unit. The function takes the level in the tree as an argument. The first level is that between the root of the tree and its children.

This plots the previous -ary tree with the height of each level proportional to .

In[66]:=

GraphDistance

GraphDistance[g, i, j] calculates the graph distance between i and j. If there is no path from i to j, the graph distance is Infinity.

This shows a dodecahedron in two dimensions.

In[67]:=

In[68]:=

The distance between vertex 11 and vertex 15 is 1.

In[69]:=

The distance between vertex 11 and vertex 20 is 5.

In[70]:=

This function defines a random directed graph (a random sparse matrix).

In[71]:=

This function calculates the average distance between vertices 1 and of a random directed graph of vertices having average degree .

In[72]:=

The average of such random graphs of degree 2 follows.

In[73]:=

Out[73]=

When the average degree is increased to 10, the average distance is reduced.

In[74]:=

Out[74]=

PseudoDiameter

Calculating the pseudo-diameter of an undirected graph.

For an undirected graph , PseudoDiameter[g] gives a list containing the pseudo-diameter of the graph and two vertices that achieve this diameter. If the graph is disconnected, the pseudo-diameter for each of the components is returned, along with the two vertices that achieve that diameter.

The algorithm used finds an approximate diameter of the graph (hence the term "pseudo"). The algorithm works by starting from a vertex , and finds a vertex among all the vertices that are farthest away from . This process is repeated by treating as the new starting vertex . The process stops when the graph distance between and no longer increases. This distance is the pseudo-diameter.

If the option Aggressive->True is used, when the distance between and no longer increases, the algorithm will be carried out for one extra step by starting from each vertex that is farthest away from . The pseudo-diameter is the farthest distance possible from all such .

This shows that the graph of a square has a pseudo-diameter of 2, and that vertices 1 and 3 achieve this diameter (i.e., the graph distance between vertices 1 and 3 is 2).

In[75]:=

In[77]:=

Out[77]=

The diameter of this graph is also 2.

In[78]:=

In[81]:=

Out[81]=

For a disconnected graph, a list of the diameters and the vertices that achieved them is given for each of the components. In the following example, vertex 3 is isolated, so the component that consists solely of this vertex has a diameter of 0.

In[82]:=

Out[82]=

To calculate the pseudo-diameter of a random undirected graph, a function giving random symmetric sparse matrices is needed.

In[83]:=

This function can be used to determine the average pseudo-diameter of random undirected graphs of 100 vertices with an average degree of 2. The largest pseudo-diameter is chosen if there is more than one component. With Aggressive->True, the pseudo-diameter is slightly larger.

In[84]:=

Out[87]=

This calculates the pseudo-diameter of a two-dimensional torus.

In[88]:=

In[89]:=

Out[90]=

This highlights the two vertices that achieve this diameter.

In[91]:=

MaximalBipartiteMatching

Finding a maximal bipartite matching.

MaximalBipartiteMatching[

] returns the maximal matching of the bipartite graph represented by the matrix g. For a matrix of m × n vertices, the bipartite graph consists of vertex sets and , where two vertices and are connected if the matrix element .

In[92]:=

Out[92]=

This sparse matrix records the favorite drink of 4 people.

In[93]:=

Out[94]=

The preferences are shown in this figure.

This calculates the maximal bipartite matching.

In[95]:=

Out[95]=

The matching (shown in red) indicates that Tom should have coffee, Rob should have coke, Adam should have tea, and Anton should have juice.

Applications

MaximalBipartiteMatching can be used to order a matrix to have as many nonzero entries on the diagonal as possible.

This forms the maximal matching for a 50 × 50 random matrix with an average of 2 elements per row. The RandomSparseMatrix function was defined earlier.

In[96]:=

Out[98]=

This forms a permutation matrix that permutes as many nonzero entries as possible to the diagonal.

In[99]:=

Out[100]=

These plots show the permuted matrix.

In[101]:=

In[102]:=

MaximalIndependentVertexSet

Finding a maximal independent vertex set.

For an undirected graph, an independent vertex set is a set of vertices such that no two vertices in the set share an edge. A maximal independent vertex set is an independent set such that adding another vertex will make it no longer independent.

MaximalIndependentVertexSet[

] gives a maximal independent vertex set of an undirected graph .

MaximalIndependentVertexSet[

] gives a maximal independent vertex set of the undirected graph , with priority given to vertices with higher vertex weight as given by the vector vtxwgt. The length of vtxwgt must be the same as the row dimension of .

This is an undirected graph of three vertices linked in a line.

In[103]:=

In[104]:=

The set of vertices forms a maximal independent vertex set.

In[105]:=

Out[105]=

MaximalIndependentVertexSet can take a second argument that gives vertex weights. This example shows that the maximal independent vertex set is not unique. Here, priority is given to the second vertex .

In[106]:=

Out[106]=

This shows a two-dimensional torus. The Torus2D function was defined earlier.

In[107]:=

This displays a maximal independent vertex set of this torus with red dots; the rest of the vertices are in green.

In[108]:=

MaximalIndependentEdgeSet

Finding a maximal independent edge set.

MaximalIndependentEdgeSet[

] returns a maximal independent edge set (also known as a maximal matching) of an undirected graph .

This matrix represents a hexagon.

In[112]:=

Out[112]=

In[113]:=

This shows that vertex 1 is matched to vertex 2, vertex 3 is matched to vertex 4, and vertex 5 is matched to vertex 6.

In[114]:=

Out[114]=

This can be visualized by assigning red to matched edges and green to unmatched edges.

In[115]:=

This shows a maximal matching of a two-dimensional torus. The Torus2D function was defined earlier.

In[119]:=

To give preference to edges with higher weight, set the option Weighted to True. With this option, the graph should be represented by a symmetric matrix with the entry values representing edge weights. In this example, because the edge weight of edge {1, 6} is now larger than the other edges linked to vertex 1, edge {1, 6} is matched instead of edge {1, 2}.

In[124]:=

Out[125]=

StrongComponents

Finding strongly connected components.

StrongComponents[

] returns a list of all strongly connected components in the directed graph g. A strongly connected component in a directed graph is a set of vertices such that there is a path between any two nodes in the set.

This shows a simple directed graph and its matrix representation.

In[126]:=

This finds the strongly connected components of the graph. It turns out that there are no strongly connected components consisting of more than just one vertex.

In[127]:=

Out[127]=

If, on the other hand, an arc from 3 to 2 is added, then becomes a strongly connected component.

In[128]:=

Out[128]=

Applications

Finding the number of connected components in an undirected graph

StrongComponents can be used to work out how many connected components there are in an undirected graph.

This shows a symmetric matrix representing a disconnected graph.

In[129]:=

Out[130]//MatrixForm=

In[131]:=

This shows that the graph has 2 disconnected components.

In[132]:=

Out[132]=

This shows how the number of components changes with the average degree of the graph for an undirected graph with 100 vertices. RandomSymmetricSparseMatrix was defined earlier.

In[133]:=

Ordering a matrix into block triangular form

The output from StrongComponents can also be used to reorder a matrix into block triangular form.

This generates a random directed graph of dimensions 100 × 100, with average degree 2. The RandomSparseMatrix function was defined earlier.

In[139]:=

Out[139]=

This displays the matrix.

In[140]:=

This finds the strongly connected vertices.

In[141]:=

This orders the matrix by symmetrically permuting its rows and columns with the list of strongly connected vertices. The reordered matrix is shown.

In[142]:=

The reordered matrix is block triangular, with one big block. The other components are single vertices.

In[145]:=

Out[145]=

To make the matrix block triangular with as many nonzero entries on the diagonal as possible, first use MaximalBipartiteMatching to permute entries to the diagonal, and then use StrongComponents to find the strongly connected components.

In[146]:=

Now the block is much smaller. The rest of the strongly connected components consist of single vertices.

In[154]:=

Out[154]=

MinCut

Finding a mincut.

MinCut[g, k] gives the partitioning of the undirected graph into parts such that the number of edges cut by the partitioning is approximately minimized. This function is based on the METIS software.

This sparse matrix represents the following graph.

In[155]:=

In[156]:=

This shows that the best partitioning of this graph into two parts divides the vertices into two groups: and . The previous graph shows that there is only one edge between these two groups, .

In[157]:=

Out[157]=

Applications

Ordering symmetric matrices into block diagonal form

To put a symmetric matrix into block diagonal form with k blocks and a minimized number of off-diagonal elements, reorder the matrix into the order given by the partitioning.

This generates a symmetric sparse block diagonal matrix with 2 blocks and adds two off-diagonal elements.

In[158]:=

In[163]:=

This applies a random permutation to the matrix.

In[164]:=

This partitions the graph into 2 subdomains.

In[168]:=

This reorders the matrix into the order given by the partitioning. The block diagonal form is recovered.

In[169]:=

Partition a graph with minimal edge-cuts

One of the important uses of the MinCut function is in partitioning graphs and meshes into subdomains of roughly equal size, so that the number of edges cut by the partition is minimized. This is important in areas such as parallel computing, where each processor works on one subdomain and the communication overhead between processors must be minimized. The communication overhead is proportional to the number of edges cut, so the number of edges cut by the partition must be minimized.

Suppose a parallel finite element structural analysis is to be carried out on a three-dimensional structure. An irregular mesh over the structure gives the graph shown here.

In[170]:=

In[171]:=

To perform this analysis on four processors, the mesh must be partitioned into four subdomains with a minimal number of edges between them. This partitions the graph into four such parts.

In[172]:=

This plots the partitioned graph, coloring nodes according to the part to which they belong. For a clearer illustration, this three-dimensional structure is plotted in two dimensions. The result appears quite reasonable: each subdomain is well connected, and the boundaries between subdomains are minimized.

In[174]:=

VertexList

Getting a list of all vertices.

VertexList[g] returns a list of all the vertices in a graph. Internally, vertices of a graph are indexed from 1 to , with being the number of vertices. VertexList[i] gives the -th vertex. This function is particularly useful for graphs specified using a rule list.

This specifies a graph using a rule list.

In[178]:=

This gives the list of vertices.

In[180]:=

Out[180]=

This highlights the edge from 1 to in red.

In[181]:=

References

[1] G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis, Algorithms for the Visualization of Graphs, Prentice-Hall, 1999.

[2] T. M. J. Fruchterman and E. M. Reigold, "Graph drawing by Force Directed Placement", Software--Practice and Experience, 21, 1991 pp. 1129-1164.

[3] P. Eades, "A Heuristic for Graph Drawing", Congressus Nutnerantiunt, 42, 1984 pp. 149-160.

[4] N. Quinn and M. Breur, "A Force Directed Component Placement Procedure for Printed Circuit Boards", IEEE Trans. on Circuits and Systems, CAS-26, (6), 1979 pp. 377-388.

[5] T. Kamada and S. Kawai, "An Algorithm for Drawing General Undirected Graphs", Information Processing Letters, 31, 1989 pp. 7-15.

[6] D. Harel and Y. Koren, "Graph Drawing by High-Dimensional Embedding", in Proceedings of 10th Int. Symp. Graph Drawing (GD'02); Lecture Notes in Computer Science, Vol. 2528, Springer Verlag, 2002 pp. 207-219.

[7] C. Walshaw, "A Multilevel Algorithm for Force-Directed Graph Drawing", J. Graph Algorithms Appl., 7, 2003 pp. 253-285.