Graphs [HB 102]

Changes:

• The semantics for graph equality have been made consistent with the fact that graphs may have different labellings and/or different supports. If G and H are two graphs, G eq H if and only if G and H are structurally equal, if they have the same support and if they have the same vertex and edge labelling.
• If G is a graph with support S and vertex and/or edge labels L, the function StandardGraph returns a graph H with same vertex and edge set as G, with vertex and/or edge labels L, but with standard support 1, ..., Order(G).
• The interface allowing for vertex and edge addition or deletion has been modified so to keep in line with the Magma philosophy. In some instances it was possible to specify a vertex or an edge by means of integers in the appropriate range. Now vertices and edges will have to be specified by a standard Magma object of type GrphVert and GrphEdge respectively.

  The old interface has been retained for backward compatibility but is no longer documented.

• Similarly, the signature for the function AssignLabels has been modified so that vertices and edges are now only specified by objects of type GrphVert and GrphEdge respectively. Again, previous signatures that referred to vertices and edges by means of integers have been retained for backward compatibility.
• Our definition of a eulerian graph or digraph has been modified in order to conform with the currently accepted definition. An undirected graph is eulerian if and only if all vertices have even degree. A directed graph is eulerian if and only if each vertex has same in- and out-degree. That is, a graph is eulerian if and only if it has a eulerian circuit. Note that we do not require the graph to be connected.

New Features:

• It is now possible to create a NullGraph in Magma, that is, a graph with no vertices. It is also possible to test whether a graph is null, using IsNullGraph.
• The function Conversion is now available for digraphs. If G is a digraph, Conversion(G) returns a digraph with the same vertex set as G and whose edges are the edges of G with the direction reversed.
• If G is a graph with support S and vertex and/or edge labels L, the function UnlabelledGraph returns a graph H with same vertex and edge set as G, with support S but without vertex and/or edge labelling.
• The functions IsVertexLabelled and IsEdgeLabelled applied to a graph G determine if the vertices or edges of G are labelled.
• The classical linear-time 3-connectivity algorithm from Hopcroft and Tarjan has been implemented, with corrections of our own and from Gutwenger and Mutzel.

  The function IsTriconnected determines if a graph is 3-connected. The function Splitcomponents splits a graph G into components that can be easily reconstructed as 3-connected graphs. Finally, the function SeparationVertices finds the cut vertices and/or the separator pairs of a graph.

• A general connectivity machinery has been put in place for graphs and digraphs. It allows to test for vertex and edge connectivity (IsKVertexConnected and IsKEdgeConnected) and to compute the vertex and edge connectivity of a graph (VertexConnectivity and EdgeConnectivity).

  The underlying algorithms are flow-based algorithms; we have implemented two of them: the Dinic algorithm and a push-relabel method. For more details on these algorithms see say.

  the section network below. The push-relabel method is usually (much) faster than Dinic, expect possibly in very sparse graphs with a small connectivity number. This is why the former algorithm is the default algorithm used in all connectivity computations; users may choose Dinic by setting an optional parameter.

• A natural extension of the flow-based machinery is the algorithm that computes a maximum matching for a bipartite graph G: the function MaximumMatching returns a maximum matching of G as a list of edges of G.

Bug Fixes:

• Several problems related to the deletion of a graph or of its vertex or edge set have been solved.