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]:=