GraphTheory
A substantial effort was put into Graph Theory for Maple 2020, including significant advances in visualization, flexible graph manipulation options, powerful analysis tools, and support for over 20 new special graphs and graph properties.
withGraphTheory:
Centrality
Graph Styling Improvements
Style Vertices and Edges by Properties
Graph Layout Methods
Self-Loops
Geometric Graphs
Split Graphs
ContractSubgraph
SpecialGraphs
Maple 2020 offers eight new functions for calculating the centrality of vertices in a graph. These are:
Betweenness centrality
Closeness centrality
Degree centrality
Eigenvector centrality
Harmonic centrality
Information centrality
Katz centrality
PageRank centrality
Here is an example of a simple social graph where the graph centrality measures social influence.
vertices≔Alice, Bob, Andrew, Ned, Fred, Gerald, Sarah, Herbet, Cormac, Hopkins, Maggie:
edges_weights≔ Hopkins, Fred, 9, Hopkins, Andrew, 18, Bob, Fred, 27, Bob, Andrew, 14, Bob, Alice, 25, Bob, Herbet, 33, Bob, Ned, 3, Bob, Cormac, 5, Maggie, Andrew, 51, Fred, Alice, 12, Fred, Herbet, 38, Fred, Ned, 5, Sarah, Alice, 6, Sarah, Herbet, 3, Gerald, Andrew, 4, Gerald, Herbet, 3, Andrew, Alice, 4, Andrew, Herbet, 44, Andrew, Ned, 9, Alice, Herbet, 112, Alice, Ned, 5, Herbet, Ned, 11:
Gs≔Graphvertices,edges_weights
Gs≔Graph 1: an undirected weighted graph with 11 vertices and 22 edge(s)
DrawGraphGs, layout=spring,stylesheet=vertexcolor = Niagara DeepBlue ,vertexfontcolor = white ,vertexborder = false ,vertexshape = stadium ,vertexfont = Arial, 10 ,vertexpadding = 8 ,edgecolor = Niagara Burgundy,title=Social Media Graph,titlefont=Arial,16,size=600,600
centrality≔EigenvectorCentralityGs
centrality≔0.237978443268371,0.131195758579289,0.116408170276784,0.0410886760673835,0.113645015600347,0.00850460849139520,0.0148924786849715,0.271820184196355,0.00435475160238433,0.0207000263726866,0.0394118868600335
ind≔sortcentrality,`>`,output=permutation:
Statistics:-BarChartseqverticesi=centralityi,i in ind,title=Most Influential Social Media Users,titlefont=Arial,16,font=Arial,10,axesfont=Arial,10,labels=Centrality,,labelfont=Arial,14,axes=frame,color=ColorTools:-Color0, 79, 128255,size=600,400,style=surface
The stylesheet option to DrawGraph is now fully supported for animations and all options except the ones controlling the shapes of vertices and arrows are supported for three-dimensional graphs.
S ≔ SpecialGraphs:-SoccerBallGraph;
S≔Graph 2: an undirected unweighted graph with 60 vertices and 90 edge(s)
DrawGraphS, stylesheet=vertexcolor=Yellow, vertexfontcolor=Red, dimension=3
The animate option to DrawGraph can now be set to a positive integer to control the number of frames generated.
P ≔ SpecialGraphs:-PetersenGraph;
P≔Graph 4: an undirected unweighted graph with 10 vertices and 15 edge(s)
DrawGraphP, layout=spring, animate=25, stylesheet=vertexcolor=SeaGreen, vertexborder=DarkSeaGreen;
A few new ways to style graphs were also added. A new arrowshape style was added for directed edges allowing any shape supported by plottools. As well, the arrowpos directive has been greatly improved to be more accurate. Vertex borders can now be given a color including several special dynamic coloring options "_contrast", "_blend", and "_match" which are also supported for vertex font colors, edge color, and edge font colors.
New commands have been introduced for adding styles to graph components that are independent of the concept of "highlighting". These are StyleVertex, StyleEdge, and StyleSubgraph and have basically the same calling sequences as their Highlight equivalents. They differ from their Highlight versions in that when called multiple times, they add to the existing style rather than replace it and they build on the base default style rather than the base "highlighted" style.
Gd ≔ GraphMatrix0,2,9,4,0,1,3,0,0
Gd≔Graph 5: a directed weighted graph with 3 vertices and 5 arc(s)
StyleEdgeGd, 2,3, fontcolor=_match, color=_blend, arrowshape=line, arrowpos=0;StyleVertexGd, 2,3, color=Red,shape=square;
StyleVertexGd, 2, color=Blue;
DrawGraphGd;
You can now visually style graph vertices and edges with respect to properties, such as centrality or weight. For example, given its centrality, the color of a vertex can be chosen from a gradient of colors—this lets you emphasize the more important vertices in a graph. Similarly, those edges with greater weight can be assigned greater thickness.
For more information, see StyleVerticesByProperty and StyleEdgesbyProperty.
In this example, given the
eigenvector centrality of a vertex, we linearly transition between two colors and two font sizes.
weight of an edge, we linearly transition between two colors and thicknesses.
c1≔ DarkSeaGreen:c2≔SeaGreen:StyleVerticesByPropertyGs,EigenvectorCentrality, fontsizescheme=10,16,colorscheme=c1, c2:StyleEdgesByPropertyGs,WeightMatrix,colorscheme=c1, c2,thicknessscheme=1,6:
DrawGraphGs,style=spring,stylesheet=vertexfontcolor=white,vertexborder=false,vertexpadding=4,title=Social Media Graph,titlefont=Arial,16,size=600,600,showweights=false
In this example, we demonstrate the valuesplit styling option that styles with a discrete set of values rather than a gradient or range:
for vertices, we assign specific colors and font sizes to ranges of the eigenvector centrality.
for edges, we assign specific colors and thicknesses to ranges of the weight.
c1≔#67809F:c2≔#004F79:c3≔#96281B:StyleVerticesByPropertyGs,EigenvectorCentrality,colorscheme=valuesplit,..0.1=c1,0.1..0.25=c2,c3,fontsizescheme=valuesplit,..0.2=10,18;StyleEdgesByPropertyGs,WeightMatrix,colorscheme=valuesplit,..20=c1,c2,thicknessscheme=valuesplit,..10=1,10..20=2,4:
Maple 2020 offers a number of new ways to lay out plots of graphs. The style option from previous version has been renamed layout to better clarify the difference between stylesheets and the layout of the vertices. (The old option name style will continue to be supported as an alias for layout however). A new option layoutoptions has been added to pass in options to layout methods to further customize them.
Gp ≔ GraphTheory:-SpecialGraphs:-PetersenGraph;
Gp≔Graph 7: an undirected unweighted graph with 10 vertices and 15 edge(s)
DrawGraph Gp, layout=spring, layoutoptions=initial=circle, constantonly=true ;
There is a new interactive method to lay out graphs manually starting from a selected layout. A plot component is created where vertices can either be dragged or selected and moved to new positions. The new position will be stored as the 'user' layout, and will be the default layout for future calls to DrawGraph.
Gr ≔ RandomGraphs:-RandomGraph10, 25;
Gr≔Graph 3: an undirected unweighted graph with 10 vertices and 25 edge(s)
DrawGraphGr , layout= interactive, layoutoptions=initial=spring
DrawGraphGr
There are a few new layout methods, most notably, a new spectral two- and three-dimensional layout method.
G1≔RandomGraphs:-RandomGraph100, 250
G1≔Graph 8: an undirected unweighted graph with 100 vertices and 250 edge(s)
DrawGraphG1,layout=spectral
DrawGraphG1,layout=spectral,dimension=3
A full list of layout methods is on the Graph Layout Methods help page. The grid and random layout methods are also new in Maple 2020 and support two and three dimensions.
The core routines of the GraphTheory package have been extended to support graphs with self-loops. Graphs with self-loops may be directed or undirected, and weighted or unweighted.
The number of self-loops in a graph is displayed in the graph description along with the vertex and edge count:
G ≔SpecialGraphs:-DeBruijnGraph5,3
G≔Graph 11: a directed unweighted graph with 125 vertices, 620 arc(s), and 5 self-loop(s)
Several new commands have been added to work with self-loops:
HasSelfLoops returns true if a graph has an edge or arc to itself.
NumberOfSelfLoops returns the number of self-loops in a graph.
SelfLoops returns the set of self-loops in a graph.
The HasSelfLoop and NumberOfSelfLoops commands permit querying graphs for the existence and number of self-loops, respectively, while SelfLoops returns the set of vertices with self-loops.
HasSelfLoopG
true
NumberOfSelfLoopsG
5
SelfLoopsG
1,32,63,94,125
Directed Graphs with Self-Loops
The support for self-loops extends to both directed and undirected graphs. Here is a directed graph with a self-loop at vertex 1:
G1 ≔ Graph1,1,1,2,1,3,1,4,3,4,2,3
G1≔Graph 8: a directed unweighted graph with 4 vertices, 5 arc(s), and 1 self-loop(s)
DrawGraphG1
NumberOfSelfLoopsG1
1
The Edges command now returns self-loops in its list of edges. If only edges between distinct vertices are desired, the option selfloops=false can be specified:
EdgesG1
1,1,1,2,1,3,1,4,2,3,3,4
EdgesG1,selfloops=false
1,2,1,3,1,4,2,3,3,4
The in-degree and out-degree of a vertex are each increased by one when it receives a self-loop:
InDegreeG1,1
OutDegreeG1,1
4
Undirected Graphs with Self-Loops
We can produce a copy of G1 which discards the directionality of its edges while preserving self-loops by calling UnderlyingGraph with the selfloops option:
G2≔ UnderlyingGraphG1,selfloops
G2≔Graph 9: an undirected unweighted graph with 4 vertices, 5 edge(s), and 1 self-loop(s)
DrawGraphG2
By convention, the degree of a vertex is increased by 2 when it receives a self-loop:
DegreeSequenceG2
5,2,3,2
In a simple graph the smallest possible girth (length of the shortest cycle) is 3. In a graph with a self-loop, the length of the shortest cycle is 1:
GirthG2
By definition, any graph with a self-loop cannot be colored with any number of colors. The chromatic polynomial therefore is identically zero:
ChromaticPolynomialG2,x
0
Removing self-loops
We can generate a copy of a graph with the self-loops removed simply by calling UnderlyingGraph without specifying the selfloops option:
G3≔ UnderlyingGraphG1
G3≔Graph 10: an undirected unweighted graph with 4 vertices and 5 edge(s)
NumberOfSelfLoopsG3
DegreeSequenceG3
3,2,3,2
GirthG3
3
ChromaticPolynomialG3,x
xx−1x−22
A new Maple 2020 function in RandomGraphs subpackage generates a random geometric graph.
G5≔RandomGraphs:-RandomGeometricGraph10,2,distribution=Weibull3,2,weighted
DrawGraphG5
Maple 2020 contains a new subpackage, GeometricGraphs, for generating graphs from geometric data, such as a set of 2-D or 3-D points. This subpackage includes the following new commands:
DelaunayGraph
EuclideanMinimumSpanningTree
FarthestNeighborGraph
GabrielGraph
GeometricMinimumSpanningTree
NearestNeighborGraph
RelativeNeighborhoodGraph
SphereOfInfluenceGraph
UnitDiskGraph
UrquhartGraph
VisibilityGraph
withGeometricGraphs;
DelaunayGraph,EuclideanMinimumSpanningTree,FarthestNeighborGraph,GabrielGraph,GeometricMinimumSpanningTree,NearestNeighborGraph,RelativeNeighborhoodGraph,SphereOfInfluenceGraph,UnitDiskGraph,UrquhartGraph,VisibilityGraph
points≔Matrix50,2,rand0..100.:
The Euclidean minimum spanning tree, the Delaunay graph, the Gabriel graph, the relative neighborhood graph, and the Urquhart graph are all derived from a Delaunay triangulation of the point data.
These graphs have a hierarchical relationship:
The Euclidean minimum spanning tree is a subgraph of the relative neighborhood graph,
The relative neighborhood graph is a subgraph of the Urquhart graph,
The Urquhart graph is a subgraph of the Gabriel graph.
The Gabriel graph is a subgraph of the Delaunay graph.
Euclidean Minimum Spanning Tree
Relative Neighborhood Graph
Urquhart Graph
Gabriel Graph
Delaunay Graph
Note that we can also build spanning trees for this point data using norms other than the Euclidean norm, for example the 1-norm; the result is similar but not identical to the Euclidean spanning tree.
NearestNeighborGraph and FarthestNeighborGraph return a nearest and farthest neighbor graph for a point set. You can also build k-nearest neighbor and k-farthest neighbor graphs for specified k.
Nearest Neighbor Graph
Farthest Neighbor Graph
2-Nearest Neighbor
2-Farthest Neighbor
The UnitDiskGraph command returns a graph in which two points are connected if their distance falls below a specified threshold.
DrawGraphUnitDiskGraphpoints,15
For a set of points, SphereOfInfluenceGraph draws a circle around each point with radius equal to the distance to its nearest neighbor. The sphere of influence graph is the graph whose vertices correspond to these points in which an edge between two points exists if the corresponding circles intersect at more than one point.
DrawGraphSphereOfInfluenceGraphpoints
Most of these graphs commands are not limited to two dimensions, and can be used to analyze and visualize relationships with higher-dimensional data as well.
points3D≔Matrix50,3,rand0..100.:
IsSplitGraph returns true if a graph is can be partitioned into a clique and an independent set.
G3≔Graph5,1,2,1,3,2,3,2,4,3,4,4,5; DrawGraphG3;
G3≔Graph 12: an undirected unweighted graph with 5 vertices and 6 edge(s)
result, split ≔ IsSplitGraphG3,decomposition
result,split≔true,2,3,4,1,5
HighlightSubgraphG3,InducedSubgraphG3,split1
DrawGraphG3
The ContractSubgraph command returns a new graph with all the vertices in S merged into a single vertex. The neighborhood of the new vertex will be the union of the neighborhoods of all of merged vertices.
C≔CycleGraph6:H≔ContractSubgraphC,1,2,6
H≔Graph 13: an undirected unweighted graph with 4 vertices and 4 edge(s)
DrawGraphH
Maple 2020 provides support for 18 additional Special Graphs, bringing the total to 97.
withSpecialGraphs:
Barnette-Bosák-Lederberg Graph
Berlekamp-van Lint-Seidel Graph
Biggs-Smith Graph
Brouwer-Haemers Graph
DrawGraphBarnetteBosakLederbergGraph,layout=planar, size=250,250
G≔BerlekampVanLintSeidelGraph
G≔Graph 1: an undirected unweighted graph with 243 vertices and 2673 edge(s)
IsStronglyRegularG,parameters
true,22,1,2
DrawGraphBiggsSmithGraph,layout=spectral, size=250,250
G≔BrouwerHaemersGraph
G≔Graph 15: an undirected unweighted graph with 81 vertices and 810 edge(s)
true,20,1,6
ChromaticNumberG
7
De Bruijn Graph
Gewirtz Graph
Golomb Graph
Harr Graph
DrawGraphDeBruijnGraph3,2, size=250,250
G≔GewirtzGraph
G≔Graph 16: an undirected unweighted graph with 56 vertices and 280 edge(s)
true,10,0,2
DrawGraphGolombGraph, layout=planar,size=250,250
DrawGraphHaarGraph7, dimension=3,labelstyle=offset
Harborth Graph
Higman-Sims Graph
M22 Graph
McLaughlin Graph
DrawGraphHarborthGraph,layout=planar, size=250,250
G≔HigmanSimsGraph
G≔Graph 17: an undirected unweighted graph with 100 vertices and 1100 edge(s)
true,22,0,6
6
G≔M22Graph
G≔Graph 18: an undirected unweighted graph with 77 vertices and 616 edge(s)
true,16,0,4
G≔McLaughlinGraph
G≔Graph 2: an undirected unweighted graph with 275 vertices and 15400 edge(s)
true,112,30,56
Meredith Graph
Perkel Graph
Rooks Graph
Schläfli Graph
DrawGraphMeredithGraph,layout=spring, size=250,250
G≔PerkelGraph
G≔Graph 20: an undirected unweighted graph with 57 vertices and 171 edge(s)
IsRegularG
DrawGraphRooksGraph2,3,labelstyle=offset
G≔SchlaefliGraph
G≔Graph 21: an undirected unweighted graph with 27 vertices and 216 edge(s)
true,16,10,8
9
Wells Graph
Wiener-Araya Graph
DrawGraphWellsGraph,layout=spring,size=250,250
DrawGraphWienerArayaGraph,layout=spring
Download Help Document
