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.

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.

>	$edges_weights := {[{$ $edges_weights := {[{$ $edges_weights := {[{$ $edges_weights := {[{$ $edges_weights := {[{$

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.

The animate option to DrawGraph can now be set to a positive integer to control the number of frames generated.

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.

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.

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.

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.

Graph Layout Methods

Maple 2020 offers a number of new ways to layout 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.

There is a new interactive method to layout 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.

Embedded component

There are a few new layout methods, most notably, a new spectral two- and three-dimensional layout method.

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:

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.

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:

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:

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

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:

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

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:

By definition, any graph with a self-loop cannot be colored with any number of colors. The chromatic polynomial therefore is identically zero:

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:

Geometric Graphs

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

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

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.

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.

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.

Split Graphs

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

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.