Advances in Graphs and Networks

Jaebum Jung, Yan Zhuang
Algorithms R&D, Wolfram Research

ABSTRACT

The Wolfram Language provides easy access to powerful graph functionalities. Familiarize yourself with the new features in version 12 and get a sneak peek into the upcoming versions. 
Learn how to use Wolfram Language graph capabilities in computational geometry, transportation,  optimization, automated network visualization and more.

Multigraph

Graphs with multiple edges.

Graph[{1\[UndirectedEdge]2,2\[UndirectedEdge]3,3\[UndirectedEdge]1,3\[UndirectedEdge]1,3\[UndirectedEdge]1}, PlotTheme->"Minimal", EdgeLabels->"Name",EdgeLabelStyle->20]

Multigraph

Graph[{1\[UndirectedEdge]2,2\[UndirectedEdge]3,Labeled[3\[UndirectedEdge]1,"First"],Labeled[3\[UndirectedEdge]1,"Second"],Labeled[3\[UndirectedEdge]1,"Third"]}, PlotTheme->"Minimal", EdgeLabels->"Name",EdgeLabelStyle->20]

Multigraph - Tagged Edge

size=100;Grid[{{Style[UndirectedEdge[1,2],size]},{Style[UndirectedEdge[1,2],size]},{Style[UndirectedEdge[1,2],size]}},Spacings->{0,5}]

Multigraph - Tagged Edge

size=100;Grid[{{Style[UndirectedEdge[1,2, 1],size]},{Style[UndirectedEdge[1,2, 2],size]},{Style[UndirectedEdge[1,2, 3],size]}},Spacings->{0,3}]

Multigraph - Tagged Edge

{UndirectedEdge[3,1], UndirectedEdge[3,1]}

{UndirectedEdge[3,1, "Me"], UndirectedEdge[3,1, "Brother"]}

Graph[{1\[UndirectedEdge]2,2\[UndirectedEdge]3,Labeled[(UndirectedEdge[3, 1, "Me"]),"First"],Labeled[(UndirectedEdge[3, 1, "Brother"]),"Second"]}, PlotTheme->"Minimal", EdgeLabelStyle->20]

Edge Tagged Graph

(RefLink[EdgeTaggedGraph, paclet:ref/EdgeTaggedGraph]) construct a graph with automatically generated edge tags and distinguishable parallel edges.

EdgeTaggedGraph[{1\[UndirectedEdge]2,2\[UndirectedEdge]3,Labeled[3\[UndirectedEdge]1,"First"],Labeled[3\[UndirectedEdge]1,"Second"],Labeled[3\[UndirectedEdge]1,"Third"]}, PlotTheme->"Minimal", EdgeLabelStyle->20]

EdgeTaggedGraph[{1\[UndirectedEdge]2,2\[UndirectedEdge]3,Style[3\[UndirectedEdge]1,Blue],Style[3\[UndirectedEdge]1,Green],Style[3\[UndirectedEdge]1,Red]}, PlotTheme->"Minimal", EdgeLabelStyle->20]

Edge Tagged Graph

g=EdgeTaggedGraph[{1\[UndirectedEdge]2,1\[UndirectedEdge]2,2\[UndirectedEdge]3}];

EdgeList[g]

EdgeTaggedGraphQ[g]

EdgeTags[g]

EdgeTags[g,{1,2}]

Index Edge Tagged Graph

(RefLink[IndexEdgeTaggedGraph, paclet:ref/IndexEdgeTaggedGraph]) sets tags of edges in the graph g to their edge indices.

g=EdgeTaggedGraph[{Style[1\[UndirectedEdge]2,Red],Style[1\[UndirectedEdge]2,Blue],2\[UndirectedEdge]3}]

EdgeList[g]

EdgeTags[g]

g2=IndexEdgeTaggedGraph[g]

EdgeList[g3]

EdgeTags[g2]

Inheritance of Annotations

Adding to an already rich set of operations with annotations, Version 12 brings new capabilities to inherit annotations in graph functions.

g=PetersenGraph[5,2,]

Inheritance of Annotations

FindSpanningTree finds a spanning tree of the graph g.

FindSpanningTree[g]

PropertyValue[%,EdgeWeight]

Inheritance of Annotations

Adding to an already rich set of operations with annotations, Version 12 brings new capabilities to inherit annotations in graph functions.

g=PetersenGraph[5,2,]

FindSpanningTree preserves all the annotations from the original graph, including vertex shapes, layout and weights.

FindSpanningTree[g]

PropertyValue[%,EdgeWeight]

FindSpanningTree[g, EdgeStyle->Red]

Extended Support of Annotations

Adding to an already rich set of operations with annotations, Version 12 brings new capabilities to inherit annotations in graph functions.

funs ={"BooleanGraph","ConnectedGraphComponents","DirectedGraph","EdgeAdd","EdgeContract","EdgeDelete","FindSpanningTree","GraphComplement","GraphDifference","GraphDisjointUnion","GraphIntersection","GraphPower","GraphUnion","IndexGraph","LineGraph","NeighborhoodGraph","ReverseGraph","SimpleGraph","Subgraph","TransitiveClosureGraph","TransitiveReductionGraph","UndirectedGraph","VertexAdd","VertexContract","VertexDelete","VertexReplace","WeaklyConnectedGraphComponents"};
data=Map[Hyperlink[#,"paclet:ref/"<>#]& , Partition[funs,3],{2}];
Style[Grid[data,Background->{None,{{Hue[.25,.15,.9],GrayLevel[.9]}}},
FrameStyle->Directive[Thick,White],Alignment->{{Left,Center}}, Dividers->All,Spacings->{1,2}],FontFamily->"Verdana"]

Inheritance Specification

Inheritance of annotations can be specified globally with the AnnotationRules options, individually for each graph option, or for each vertex and edge.

graph=; 
vertices={2,3,4,5,7,20,30,36,37,47,48,53,57,66,71,76,81,82,91,92,93,94,96};

Subgraph[graph,vertices]

With the setting AnnotationRules->None, annotations are not preserved.

Subgraph[graph,vertices,AnnotationRules->None]

Only inherit all EdgeStyle and VertexCoordinates.

Subgraph[graph,vertices,{AnnotationRules->None,EdgeStyle->Inherited,VertexCoordinates ->Inherited}]

Inherit annotations and set annotations for specified vertices or edges.

Subgraph[graph,vertices,AnnotationRules->None,{EdgeStyle->{Red,3\[DirectedEdge]2->Inherited},VertexCoordinates ->Inherited}]

New Graph Predicates

Version 12 adds new predicates for checking weighted graphs.

VertexWeightedGraphQ will give True if there is an explicit VertexWeight property defined.

VertexWeightedGraphQ[CompleteGraph[5,VertexWeight->Range[5]]]

VertexWeightedGraphQ[CompleteGraph[5,EdgeWeight->Range[10]]]

EdgeWeightedGraphQ will give True if there is an explicit EdgeWeight property defined.

EdgeWeightedGraphQ[CompleteGraph[5,EdgeWeight->Range[10]]]

EdgeWeightedGraphQ[CompleteGraph[5,VertexWeight->Range[5]]]

New Vertex Labels

Version 12 adds new vertex labeling scheme depends on specified layout.

CycleGraph[15, VertexLabels->"Name", VertexLabelStyle->30, VertexSize->Medium]

CycleGraph[15, VertexLabels->Placed["Name",{After,Above}],VertexLabelStyle->30,VertexSize->Medium]

g=RandomGraph[{20,30}, VertexLabels->"Name", GraphLayout->"SpringElectricalEmbedding",VertexLabelStyle->18,VertexSize->Medium]

New Layout

Version 12 expands on the already extensive collections of graph layouts with a new graph embedding “GravityEmbedding” — that minimize the energy with vertices as mass points and edges as springs.

g=Graph[ExampleData[{"NetworkGraph","LesMiserables"}],ImageSize->Medium];

Row[{Graph[g],,Graph[g,GraphLayout->"GravityEmbedding"]}]

New PlotTheme

Version 12 introduces a new PlotTheme “IndexLabeled” with a single-color design using labels to differentiate vertices for printing and accessibility. Perfect for preparing figures for publications with one-color specifications.

CompleteGraph[5,PlotTheme-> "IndexLabeled"]

Multicolumn[Framed[Graph[#,PlotTheme-> "IndexLabeled",ImageSize->{150,150},VertexSize->0.5],RoundingRadius->3,FrameStyle->GrayLevel[.6]]&/@{CompleteGraph[5],GridGraph[{4,4}],WheelGraph[10],PetersenGraph[5,3],TuranGraph[5,4],ButterflyGraph[2],HypercubeGraph[3],Graph[GraphData[{"CrossedPrism",6},"EdgeList"],VertexSize->.2],CirculantGraph[10,{2,4}]},3]

Mesh Connectivity Graph

(RefLink[MeshConnectivityGraph, paclet:ref/MeshConnectivityGraph])[mr,0] gives a graph of points connected by lines.

(RefLink[MeshConnectivityGraph, paclet:ref/MeshConnectivityGraph])[mr,d] gives a graph between cells of dimension d that share a cell of dimension d-1.

(RefLink[MeshConnectivityGraph, paclet:ref/MeshConnectivityGraph])[mr,{d,e}, r] gives a graph from cells of dimension d to cells of dimension e that share a cell of dimension r.

mesh=MengerMesh[2]

MeshConnectivityGraph[mesh,0]

MeshConnectivityGraph[mesh,{2,0},1]

Mesh Connectivity Graph

Get the face adjacency of a Voronoi mesh:

mesh=;

centroids =RegionCentroid /@ MeshPrimitives[mesh,2];
Show[{mesh,g=MeshConnectivityGraph[mesh,2,VertexCoordinates-> centroids , VertexLabels->Automatic]}]

HighlightMesh[mesh, AdjacencyList[g, {2,1}]]

ExpressionGraph

ExpressionGraph[expr] gives the tree graph with different levels at different depths.

ExpressionGraph[a+b^Cos[e+1]+c^3+d+Cos[e]]

It gives the “Subexpression” annotations for each vertices.

ExpressionGraph[a+b^Cos[e+1]+c^3+d+Cos[e], VertexLabels->Automatic]

ExpressionGraph[a+b^Cos[e+1]+c^3+d+Cos[e],_Cos,VertexLabels->Automatic]

ExpressionGraph[a+b^Cos[e+1]+c^3+d+Cos[e],1,VertexLabels->Automatic]

ExpressionGraph/@{,,}

Find Shortest Paths in a Molecule

We can use FindShortestPath to find the maximal shortest path between two atoms. Start with a molecule.

m=Molecule["3'-deoxy-3'-[(L-methionyl-L-phenylalanyl)amino]adenosine 5'-(dihydrogen phosphate)"]

MoleculeGraph[m]

Now find the graph distance matrix.

graphDistanceMatrix=m["GraphDistanceMatrix"];
MatrixPlot@graphDistanceMatrix

Find the two atoms that correspond to the longest such distance.

{atom1,atom2}=FirstPosition[graphDistanceMatrix,Max@graphDistanceMatrix]

FindShortestPath will return the list of atom indices.

path=FindShortestPath[MoleculeGraph[m],43,71]

Now use BondList to convert this to a list of bonds.

BondList[m,path]

Solve Max-Cut Problem

This example demonstrates how the new SemidefiniteOptimization in Version 12 may be used to set up a function that efficiently solves a relaxation of the NP-complete max-cut problem.

Find the maximum cut for a random graph.

g=RandomGraph[{15,24}]

Compute the Laplacian matrix of the graph.

L=(DiagonalMatrix[Total[#,{1}]]-#)&[WeightedAdjacencyMatrix[g]];

Use SemidefiniteOptimization to set up a function.

n=Length[First[L]];
e[i_] := SparseArray[{i,i}->1.,{n,n},0.];{Y,sdpmax}=SemidefiniteOptimization[ConstantArray[1,n], Join[{-L/4},Table[e[i], {i,n}]],{"DualMaximizer","DualMaximumValue"}];

Construct a cut by randomized rounding.

U=CholeskyDecomposition[Y];
x=First[MaximalBy[Table[Sign[RandomPoint[Sphere[n]].U],10],1/4#.L.#&]];

{1/4x.L.x,{ Pick[VertexList[g],x,1],Pick[VertexList[g],x,-1]}}

Highlight the cut.

CommunityGraphPlot[g,Last[%],Method->"Hierarchical"]

What’s next?

Learnability

Documentations

Courses

Usability

Utility Functions

Large Graphs

More ...