Creating graphs in Mathematica

This is an overview of the many ways in which one can create graphs in Mathematica. It demonstrates the ubiquity of graphs and how Mathematica makes it easy to experiment with ideas. At the same time, various Mathematica symbols and techniques are presented which we will cover more in depth in later article.

Polyhedral surfaces have been around since antiquity although it wasn’t recognized until Euler that they are in fact closely related to graphs. Take for example the snub-cube

CreatingGraphs_1.png

CreatingGraphs_2.gif

and unwrap its faces

CreatingGraphs_3.png

CreatingGraphs_4.gif

The number of vertices can be found in two ways here, either using the VertexCount property of the PolyHedronData or through the VertexCount property of Graph. The results do not agree though

CreatingGraphs_5.gif

CreatingGraphs_6.png

CreatingGraphs_7.png

because the vertex count of the polyhedron is based on its 3D wrapping while the unwrapped graph duplicates some vertices.

Polyhedrons can be combined to give beautiful graphics

CreatingGraphs_8.png

CreatingGraphs_9.gif

The vertices in this case are contained in two graphs, we can use the GraphUnion command to combine them and thus create a new graph. The letter g will be used in this text to denote a graph.

CreatingGraphs_10.png

CreatingGraphs_11.gif

Turning this graph into a polyhedron is not possible (in a straightforward manner)but we can turn it into a 3d graph, which reveals that it’s almost a tree.

CreatingGraphs_12.png

CreatingGraphs_13.gif

How far away from a tree? That’s something we can answer by looking at spanning trees. Although a spanning tree is not unique it still gives a good indication of how many edges (shortcuts) break the tree-like structure

CreatingGraphs_14.gif

CreatingGraphs_15.gif

A more numerical value can be obtained from the GraphDifference;

CreatingGraphs_16.png

CreatingGraphs_17.png

Once you have a graph there are many ways in which it can be turned into another graph. For example, a line graph of a given graph turns edges into vertices and vice versa;

CreatingGraphs_18.png

CreatingGraphs_19.gif

Being a transformation, one can wonder whether there are graphs which remain invariant under this type of transformation. It’s rather easy to create a simple case, the triangle graph is indeed topologically invariant

CreatingGraphs_20.gif

CreatingGraphs_21.png

and this is true for any cycle graph. Assuming that the symmetry of this graph is the key to invariance is misleading though

CreatingGraphs_22.gif

CreatingGraphs_23.png

and similarly with k-ary trees

CreatingGraphs_24.gif

CreatingGraphs_25.gif

CreatingGraphs_26.png

Another way to transform a graph into another one is by asking what it takes to turn the given graph into a complete one. Say, we take a random graph of 5 vertices and 7 edges

CreatingGraphs_27.png

and take the graph complement

CreatingGraphs_28.png

CreatingGraphs_29.gif

Graphs can be found everywhere in everyday life although it’s not always perceived as such. Millions of people traverse the London tube every day without realizing they do;

CreatingGraphs_30.gif

What is the longest trajectory across the London underground? One way to answer this question is by looking at the distance matrix

CreatingGraphs_31.gif

CreatingGraphs_32.gif

This gives a qualitative result and highlights a few regions with long distances. To find a qualitative answer we take the maximum

CreatingGraphs_33.png

CreatingGraphs_34.png

This corresponds to the so-called graph diameter, defined as the largest distance across the graph (using geodesic paths);

CreatingGraphs_35.png

CreatingGraphs_36.png

Of course, we want to know to which couple of stations this distance corresponds

CreatingGraphs_37.png

CreatingGraphs_38.png

which is a unique solution but can, of course, be traversed in two ways

CreatingGraphs_39.png

CreatingGraphs_40.png

So, let’s take the first one and see what the (shortest) path is connecting them

CreatingGraphs_41.png

The explicit route is hence

CreatingGraphs_42.png

CreatingGraphs_43.png

To represent this in the graph we first simplify the London graph somewhat.

CreatingGraphs_44.gif

CreatingGraphs_45.gif

and then highlight the longest path

CreatingGraphs_46.png

CreatingGraphs_47.gif

Graphs can be obtained from images through mathematical morphology. The following picture of a tree, for instance, can be turned into a tree-ish graph

CreatingGraphs_48.gif

CreatingGraphs_49.png

CreatingGraphs_50.gif

This indeed looks very much like a tree, but looks can be misleading;

CreatingGraphs_51.png

CreatingGraphs_52.png

We can turn this into a genuine tree as follows

CreatingGraphs_53.png

CreatingGraphs_54.gif

It’s actually not a tree but rather a forest, i.e. a collection of trees. This can be seen in various ways. If we apply a tree layout to the graph

CreatingGraphs_55.png

CreatingGraphs_56.gif

we see that there are multiple components. This can be seen by using the ConnectedComponents and the ConnectedGraphQ methods as well

CreatingGraphs_57.png

CreatingGraphs_58.gif
Is connected: False

The world of chemistry also offersa rich collection of graphs. For example, digitonin is a detergent

CreatingGraphs_59.png

CreatingGraphs_60.gif

This molecular structure can be converted to a graph by fetching the edge collection

CreatingGraphs_61.png

CreatingGraphs_62.gif

Mathematica has a rich collection of curated graphs and a fun way to explore a random sample is by means of

CreatingGraphs_63.png

CreatingGraphs_64.gif

There are plenty of categorizations which one can focus on

CreatingGraphs_65.png

CreatingGraphs_66.gif CreatingGraphs_67.gif CreatingGraphs_68.gif CreatingGraphs_69.gif CreatingGraphs_70.gif
CreatingGraphs_71.gif CreatingGraphs_72.gif CreatingGraphs_73.gif CreatingGraphs_74.gif CreatingGraphs_75.gif

The polyhedral graphs can be sampled in a similar way

CreatingGraphs_76.png

CreatingGraphs_77.gif CreatingGraphs_78.gif CreatingGraphs_79.gif CreatingGraphs_80.gif
CreatingGraphs_81.gif CreatingGraphs_82.gif CreatingGraphs_83.gif CreatingGraphs_84.gif
CreatingGraphs_85.gif CreatingGraphs_86.gif CreatingGraphs_87.gif CreatingGraphs_88.gif

Markov processes can be modelled in Mathematica and their graph representation help understand visually the transitions

CreatingGraphs_89.gif

CreatingGraphs_90.gif

This graphical representation does not show the graph as a weighted graph however, but this can be easily done

CreatingGraphs_91.gif

CreatingGraphs_92.gif

There are endless ways to manipulate and customize graphs in Mathematica. Here is an example of a hidden feature, the so-called edge bundling which bundles edges in order to achieve greater clarity.

CreatingGraphs_93.gif

CreatingGraphs_94.gif

There are plenty of graph types in the software industry which are not directly available but which can be obtained with a bit of effort. Below is an example of a standard flowchart with the essential ingredient being the EdgeShapeFunction which we’ll discuss later on as well.

CreatingGraphs_95.gif

This results in a more traditional type of graph representation. While pretty much anything and everything is possible one should note though that Mathematica is more geared towards graph computations rather than graph representations.

CreatingGraphs_96.gif

Mathematica is ideal for rapid prototyping of ideas and combining the multitude of functions. Here is an example of rectangular edges across different types of graph layouts

CreatingGraphs_97.gif

CreatingGraphs_98.gif CreatingGraphs_99.gif CreatingGraphs_100.gif CreatingGraphs_101.gif CreatingGraphs_102.gif
CreatingGraphs_103.gif CreatingGraphs_104.gif CreatingGraphs_105.gif CreatingGraphs_106.gif CreatingGraphs_107.gif

Graph layout is a world on its own and is closely related to graph analysis. Mathematica will by default automatically pick out the most appropriate layout for a given graph as well as the so-called graph packing. Graph packings are about how components of a graph are organized on top of the individual layout. Here is an overview of the possible component arrangements

CreatingGraphs_108.gif

CreatingGraphs_109.gif CreatingGraphs_110.gif CreatingGraphs_111.gif
CreatingGraphs_112.gif CreatingGraphs_113.gif CreatingGraphs_114.gif

You can define your own layout of course and specify explicit coordinates. For example, here is an explicit grid layout

CreatingGraphs_115.png

CreatingGraphs_116.gif

Elements of graphs can be highlighted as we showed above with London underground. Vertices belonging in some way together can also be visualized by means of the CommunityGraphPlot which in a way is a combination of graphs and sets.

CreatingGraphs_117.gif

CreatingGraphs_118.gif

Yet another way to look at graphs is by considering the edges as segments of polygons.

CreatingGraphs_119.gif

CreatingGraphs_120.gif

Conversely, converting a checkered polygon to a graph is possible as well. Taking one of the polygons above we can convert it to a graphics of arrows

CreatingGraphs_121.gif

CreatingGraphs_122.gif

and take the coordinates which we then apply to a cycle graph;

CreatingGraphs_123.gif

CreatingGraphs_124.gif

CreatingGraphs_125.png

Floorplans and maze-like environment are really graphs and it’s easy to generate random mazes like so

CreatingGraphs_126.gif

CreatingGraphs_127.gif

Mathematica contains a rich collection of so-called parametric graphs which have diverse types of regularities.

CreatingGraphs_128.gif

CreatingGraphs_129.gif CreatingGraphs_130.gif CreatingGraphs_131.gif CreatingGraphs_132.gif CreatingGraphs_133.gif
CreatingGraphs_134.gif CreatingGraphs_135.gif CreatingGraphs_136.gif CreatingGraphs_137.gif CreatingGraphs_138.gif
CreatingGraphs_139.gif CreatingGraphs_140.gif CreatingGraphs_141.gif CreatingGraphs_142.gif CreatingGraphs_143.gif

Besides all sorts of graphs with explicit names and the parametric graphs (like k-ary tree) there is a whole arsenal of ways to generate random graphs. There are many reasons why one would want to produce random graphs and it’s in fact an acadmic branch on its own. Among other:
– experiment with existing or invent new graph layout algorithms (graph embeddings)
– research collective behaviors or properties of graphs with certain constraints (statistical physics based on graphs)
– model epidemic and viral algorithms
– test out graph theoretic concepts (centrality and other measures)

Here is a sample of random graphs based on various distributions:

CreatingGraphs_144.gif

CreatingGraphs_145.gif CreatingGraphs_146.gif CreatingGraphs_147.gif
CreatingGraphs_148.gif CreatingGraphs_149.gif CreatingGraphs_150.gif

Sparse arrays are an important ingredient in graph drawing, most matrices deduced from a graph are sparse. Conversely, you can create graphs from sparse arrays. For example, the following ladder diagram is based on a banded sparse array

CreatingGraphs_151.png

CreatingGraphs_152.gif

An interesting way to construct graphs is by looking at relationships between sets of objects. For example, the inclusion or subset operation gives a partially ordered set which can be made even more clear by looking at the so-called transitive reduction of the graph. The transitive reduction removes edges which can be deduced from the transitive closure.

CreatingGraphs_153.gif

CreatingGraphs_154.gif CreatingGraphs_155.gif

Finally, sound can also be converted to a graph by looking at the line graph outputted by default when loading a wave;

CreatingGraphs_156.gif

CreatingGraphs_157.gif

It produces beautiful floral patterns and is a good representation of the complexity of the data. For a comparison, here is the graph corresponding to the alt-sax

CreatingGraphs_158.gif

CreatingGraphs_159.gif