GraphTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : What's New and Release Notes : updates/Maple2020/GraphTheory

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

Centrality

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.

verticesAlice, 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:

GsGraphvertices,edges_weights

GsGraph 1: an undirected weighted graph with 11 vertices and 22 edge(s)

(1.1)

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

centralityEigenvectorCentralityGs

centrality0.237978443268371,0.131195758579289,0.116408170276784,0.0410886760673835,0.113645015600347,0.00850460849139520,0.0148924786849715,0.271820184196355,0.00435475160238433,0.0207000263726866,0.0394118868600335

(1.2)

indsortcentrality,`>`,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

Graph Styling Improvements

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;

SGraph 2: an undirected unweighted graph with 60 vertices and 90 edge(s)

(2.1)

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;

PGraph 4: an undirected unweighted graph with 10 vertices and 15 edge(s)

(2.2)

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

GdGraph 5: a directed weighted graph with 3 vertices and 5 arc(s)

(2.3)

StyleEdgeGd, 2,3, fontcolor=_match, color=_blend, arrowshape=line, arrowpos=0;StyleVertexGd, 2,3, color=Red,shape=square;

StyleVertexGd, 2, color=Blue;

DrawGraphGd;

Style Vertices and Edges by Properties

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:c2SeaGreen: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:

DrawGraphGs,style=spring,stylesheet=vertexfontcolor=white,vertexborder=false,vertexpadding=4,title=Social Media Graph,titlefont=Arial,16,size=600,600,showweights=false

Graph Layout Methods

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;

GpGraph 7: an undirected unweighted graph with 10 vertices and 15 edge(s)

(4.1)

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;

GrGraph 3: an undirected unweighted graph with 10 vertices and 25 edge(s)

(4.2)

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.

G1RandomGraphs:-RandomGraph100, 250

G1Graph 8: an undirected unweighted graph with 100 vertices and 250 edge(s)

(4.3)

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.

Self-Loops

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

GGraph 11: a directed unweighted graph with 125 vertices, 620 arc(s), and 5 self-loop(s)

(5.1)

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

(5.2)

NumberOfSelfLoopsG

5

(5.3)

SelfLoopsG

1,32,63,94,125

(5.4)

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

G1Graph 8: a directed unweighted graph with 4 vertices, 5 arc(s), and 1 self-loop(s)

(5.5)

DrawGraphG1

NumberOfSelfLoopsG1

1

(5.6)

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

(5.7)

EdgesG1,selfloops=false

1,2,1,3,1,4,2,3,3,4

(5.8)

The in-degree and out-degree of a vertex are each increased by one when it receives a self-loop:

InDegreeG1,1

1

(5.9)

OutDegreeG1,1

4

(5.10)

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

G2Graph 9: an undirected unweighted graph with 4 vertices, 5 edge(s), and 1 self-loop(s)

(5.11)

DrawGraphG2

By convention, the degree of a vertex is increased by 2 when it receives a self-loop:

DegreeSequenceG2

5,2,3,2

(5.12)

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

1

(5.13)

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

(5.14)

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

G3Graph 10: an undirected unweighted graph with 4 vertices and 5 edge(s)

(5.15)

NumberOfSelfLoopsG3

0

(5.16)

DegreeSequenceG3

3,2,3,2

(5.17)

GirthG3

3

(5.18)

ChromaticPolynomialG3,x

xx1x22

(5.19)

Geometric Graphs

A new Maple 2020 function in RandomGraphs subpackage generates a random geometric graph.

G5RandomGraphs:-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

(6.1)

pointsMatrix50,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.

points3DMatrix50,3,rand0..100.:

Split Graphs

IsSplitGraph returns true if a graph is can be partitioned into a clique and an independent set.

G3Graph5,1,2,1,3,2,3,2,4,3,4,4,5; DrawGraphG3;

G3Graph 12: an undirected unweighted graph with 5 vertices and 6 edge(s)

result, split  IsSplitGraphG3,decomposition

result,splittrue,2,3,4,1,5

(7.1)

HighlightSubgraphG3,InducedSubgraphG3,split1 

DrawGraphG3

ContractSubgraph

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.

CCycleGraph6:HContractSubgraphC,1,2,6

HGraph 13: an undirected unweighted graph with 4 vertices and 4 edge(s)

(8.1)

DrawGraphH

SpecialGraphs

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

GBerlekampVanLintSeidelGraph

GGraph 1: an undirected unweighted graph with 243 vertices and 2673 edge(s)

(9.1)

IsStronglyRegularG,parameters

true,22,1,2

(9.2)

DrawGraphBiggsSmithGraph,layout=spectral,  size=250,250

GBrouwerHaemersGraph

GGraph 15: an undirected unweighted graph with 81 vertices and 810 edge(s)

(9.3)

IsStronglyRegularG,parameters

true,20,1,6

(9.4)

ChromaticNumberG

7

(9.5)

De Bruijn Graph

Gewirtz Graph

Golomb Graph

Harr Graph

DrawGraphDeBruijnGraph3,2,  size=250,250

GGewirtzGraph

GGraph 16: an undirected unweighted graph with 56 vertices and 280 edge(s)

(9.6)

IsStronglyRegularG,parameters

true,10,0,2

(9.7)

ChromaticNumberG

4

(9.8)

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

GHigmanSimsGraph

GGraph 17: an undirected unweighted graph with 100 vertices and 1100 edge(s)

(9.9)

IsStronglyRegularG,parameters

true,22,0,6

(9.10)

ChromaticNumberG

6

(9.11)

GM22Graph

GGraph 18: an undirected unweighted graph with 77 vertices and 616 edge(s)

(9.12)

IsStronglyRegularG,parameters

true,16,0,4

(9.13)

ChromaticNumberG

5

(9.14)

GMcLaughlinGraph

GGraph 2: an undirected unweighted graph with 275 vertices and 15400 edge(s)

(9.15)

IsStronglyRegularG,parameters

true,112,30,56

(9.16)

Meredith Graph

Perkel Graph

Rooks Graph

Schläfli Graph

DrawGraphMeredithGraph,layout=spring, size=250,250

GPerkelGraph

GGraph 20: an undirected unweighted graph with 57 vertices and 171 edge(s)

(9.17)

IsRegularG

true

(9.18)

ChromaticNumberG

3

(9.19)

DrawGraphRooksGraph2,3,labelstyle=offset

GSchlaefliGraph

GGraph 21: an undirected unweighted graph with 27 vertices and 216 edge(s)

(9.20)

IsStronglyRegularG,parameters

true,16,10,8

(9.21)

ChromaticNumberG

9

(9.22)

Wells Graph

Wiener-Araya Graph

DrawGraphWellsGraph,layout=spring,size=250,250

DrawGraphWienerArayaGraph,layout=spring