Multigraphs (New) [HB 109]

Multigraphs, both directed and undirected, appear in Magma for the first time. They may have multiple (ie. parallel) edges and/or loops. Multigraphs are represented by means of an adjacency list. In what follows, the generic term ``multigraph'' will be used whenever we discuss directed and undirected multigraphs.

New Features:

• There is a larger upper-bound on the order of a multigraph (134217722) than on the order of a graph (65535); this made possible by the adjacency list representation.

• Edges are uniquely identified, and one can determine the multiplicity of an edge between any two vertices.

• Vertices and edges can be labelled, and edges can be assigned capacities and/or weights.

• Most basic access functions and predicates that apply to simple graphs are available for multigraphs.

• Maximum flow and shortest-paths algorithms may be applied to a multigraph.

• It is possible to determine if a multigraph is planar, or triconnected (both operations involve linear-time algorithms).

• Incremental graph construction (using the sub<> constructor, or by adding/removing vertices/edges) retains the support and vertex/edge decoration of the original graph.