Browse by Topic

# New in 13: Graphs & Networks

Two years ago we released Version 12.0 of the Wolfram Language. Here are the updates in graphs and networks since then, including the latest features in 13.0. The contents of this post are compiled from Stephen Wolfram’s Release Announcements for 12.1, 12.2, 12.3 and 13.0.

### The Beginning of Computational Topology (March 2020)

In the past few versions, we’ve introduced deeper and deeper coverage of computational geometry. In coming versions, we’re going to be covering more and more of computational topology too. Things like EulerCharacteristic and PolyhedronGenus were already in Version 12.0. In Version 12.1 we’re introducing several powerful functions for dealing with the topology of simplicial complexes, of the kind that are for example used in representing meshes.

This makes a connectivity graph for the dimension-0 components of a dodecahedron, i.e. its corners:

 ✕ `MeshConnectivityGraph[Dodecahedron[], 0]`

Here’s the corresponding result for the connectivity of lines to lines in the dodecahedron:

 ✕ `MeshConnectivityGraph[Dodecahedron[], 1]`

And here’s the connectivity of corners to faces:

 ✕ `MeshConnectivityGraph[Dodecahedron[], {0, 2}]`

It’s a very general function. Here are the graphs for different dimensional cells of a Menger sponge:

 ✕ `Table[MeshConnectivityGraph[MengerMesh[2, 3], d], {d, 0, 3}]`

Given a mesh, it’s often useful to do what amounts to a topological search. For example, here’s a random Voronoi mesh:

 ✕ `vm = VoronoiMesh[RandomReal[1, {200, 2}]]`

Here are the 10 closest mesh cells to position {.5, .5} (the 2 before each index indicates that these are dimension-2 cells):

 ✕ `NearestMeshCells[vm, {.5, .5}, 10]`

Now highlight these cells:

 ✕ `HighlightMesh[vm, %]`

### More with Graphs (May 2021)

In case one ever doubted that graphs are important, our Wolfram Physics Project has made it pretty clear over the past year that at the lowest level physics is all about graphs. And in fact our whole Physics Project was basically made possible by the rich graph functionality in the Wolfram Language.

In Version 12.3 we’ve continued to expand that functionality. Here, for example, is a new 3D visualization function for graphs:

 ✕ `LayeredGraphPlot3D[KaryTree[255], BoxRatios -> {1, 1, 1}]`

And here’s a new 3D graph embedding:

 ✕ `Graph3D[GridGraph[{20, 20}], GraphLayout -> "SphericalEmbedding"]`

We’ve been able to find spanning trees in graphs since Version 10 (2014). In Version 12.3, however, we’ve generalized FindSpanningTree to directly handle objects—like geo locations—that have some kind of coordinates. Here’s a spanning tree based on the positions of capital cities in Europe:

 ✕ ```FindSpanningTree[ EntityClass["Country", "Europe"][ EntityProperty["Country", "CapitalCity"]]]```

And now in Version 12.3 we can use the new GeoGraphPlot to plot this on a map:

 ✕ `GeoGraphPlot[%]`

By the way, in a “geo graph” there are “geo” ways to route the edges. For example, you can specify that they follow (when possible) driving directions (as provided by TravelDirections):

 ✕ `GeoGraphPlot[%%, GraphLayout -> "Driving"]`

### Graph Coloring (December 2021)

The graph theory capabilities of Wolfram Language have been very impressive for a long time (and were critical, for example, in making possible our Physics Project). But in Version 13.0 we’re adding still more.

A commonly requested set of capabilities revolve around graph coloring. For example, given a graph, how can one assign “colors” to its vertices so that no pair of adjacent vertices have the same color? In Version 13.0 there’s a function FindVertexColoring that does that:

 ✕

And now we can “highlight” the graph with those colors:

 ✕

The classic “graph coloring” problem involves coloring geographic maps. So here, for example, is the graph representing the bordering relations for US states:

 ✕

Now it’s an easy matter to find a 4-coloring of US states:

 ✕

There are actually a remarkable range of problems that can be reduced to graph coloring. Another example has to do with scheduling a “tournament” in which all pairs of people “play” each other, but everyone plays only one match at a time. The collection of matches needed is just the complete graph:

 ✕

Each match corresponds to an edge in the graph:

 ✕

And now by finding an “edge coloring” we have a list of possible “time slots” in which each match can be played:

 ✕

EdgeChromaticNumber tells one the total number of matches needed:

 ✕

Map coloring brings up the subject of planar graphs. Version 13.0 introduces new functions for working with planar graphs. PlanarFaceList takes a planar graph and tells us how the graph can be decomposed into “faces”:

 ✕

FindPlanarColoring directly computes a coloring for these planar faces. Meanwhile, DualPlanarGraph makes a graph in which each face is a vertex:

 ✕

### Subgraph Isomorphism & More (December 2021)

It comes up all over the place. (In fact, in our Physics Project it’s even something the universe is effectively doing throughout the network that represents space.) Where does a given graph contain a certain subgraph? In Version 13.0 there’s a function to determine that (the All says to give all instances):

 ✕

A typical area where this kind of subgraph isomorphism comes up is in chemistry. Here is the graph structure for a molecule:

 ✕

Now we can find a 6-cycle:

 ✕

Another new capability in Version 13.0 has to do with handling flow graphs. The basic question is: in “flowing” through the graph, what vertices are critical, in the sense that they “have to be visited” if one’s going to get to all future vertices? Here’s an example of a directed graph (yes, made from a multiway system):

 ✕

Now we can ask for the DominatorTreeGraph, which shows us a map of what vertices are critical to reach where, starting from A:

 ✕

This now says for each vertex what its “dominator” is, i.e. what the nearest critical vertex to it is:

 ✕

If the graph represents causal or other dependency of one “event” on others, the dominators are effectively synchronization points, where everything has to proceed through one “thread of history”.

### The Calculus of Annotations (March 2020)

How do you add metadata annotations to something you’re computing with? For Version 12.1 we’ve begun rolling out a general framework for making annotations—and then computing with and from them.

Let’s talk first about the example of graphs. You can have both annotations that you can immediately “see in the graph” (like vertex colors), and ones that you can’t (like edge weights).

Here’s an example where we’re explicitly constructing a graph with annotations:

 ✕ ```Graph[{Annotation[1 -> 2, EdgeStyle -> Red], Annotation[2 -> 1, EdgeStyle -> Blue]}]```

Here we’re annotating the vertices:

 ✕ ```Graph[{Annotation[x, VertexStyle -> Red], Annotation[y, VertexStyle -> Blue]}, {x -> y, y -> x, y -> y}, VertexSize -> .2]```

AnnotationValue lets you query values of annotations:

 ✕ ```AnnotationValue[{%, x}, VertexStyle]```

Something important about AnnotationValue is that you can assign it. Set g to be the graph:

 ✕ `g = CloudGet["https://wolfr.am/L9rgvixl"];`

Now do an assignment to an annotation value:

 ✕ `AnnotationValue[{g, x}, VertexStyle] = Green`

Now the graph has changed:

 ✕ `g`

You can always delete the annotation if you want:

 ✕ `AnnotationDelete[{g, x}, VertexStyle]`

If you don’t want to permanently modify a graph, you can just use Annotate to produce a new graph with annotations added (3 and 5 are names of vertices):

 ✕ ```Annotate[{CloudGet["https://wolfr.am/L9rpqPJ0"], {3, 5}}, VertexSize -> .3]```

Some annotations are important for actual computations on graphs. An example is edge weighting. This puts edge-weight annotations into a graph—though by default they don’t get displayed:

 ✕ ```Graph[Catenate[ Table[Annotation[i -> j, EdgeWeight -> GCD[i, j]], {i, 5}, {j, 5}]]]```

This displays the edge weights:

 ✕ `Graph[%, EdgeLabels -> "EdgeWeight"]`

And this actually does a computation that includes the weights:

 ✕ ```WeightedAdjacencyMatrix[ CloudGet["https://wolfr.am/L9rtJdd9"]] // MatrixForm```

You can use your own custom annotations too:

 ✕ ```Graph[{Annotation[x, "age" -> 10], Annotation[y, "age" -> 20]}, {x -> y, y -> x, y -> y}]```

This retrieves the value of the annotation:

 ✕ `AnnotationValue[{CloudGet["https://wolfr.am/L9rx8Mxe"], x}, "age"]`

Annotations are ultimately stored in an AnnotationRules option:

 ✕ `Options[CloudGet["https://wolfr.am/L9rx8Mxe"], AnnotationRules]`

You can always give all annotations as a setting for this option.

A major complexity with annotations is when in a computation they should be preserved—or combined—and when they should be dropped. We always try to keep annotations whenever it makes sense:

 ✕ `TransitiveReductionGraph[CloudGet["https://wolfr.am/L9rBdIZt"]]`

Annotations are something quite general, that apply not only to graphs, but to an increasing number of other constructs too. But in Version 12.1 we’ve added something else that’s specific to graphs, and that handles a complicated case there. It has to do with multigraphs, i.e. graphs with multiple edges between the same vertices. Take the graph:

 ✕ `Graph[{1 -> 2, 1 -> 2}]`

How do you distinguish these two edges? It’s not a question of annotation; you actually want these edges to be distinct, just like the vertices in the graph are distinct. Well, in Version 12.1, you can give names (or “tags”) to edges, just like you give names to vertices:

 ✕ `EdgeTaggedGraph[{1 -> 2, 1 -> 2} -> {a, b}]`

In the edge list for this graph the edges are shown “tagged”:

 ✕ `EdgeList[%]`

The tags are part of the edge specification:

 ✕ `InputForm[%]`