As noted in the Introduction Introduction, most of the functions listed in this section correctly handle a graph's support and vertex/edge decorations. That is, these attributes are inherited by the graph created as a result of applying such a function.
The construction of subgraphs from multigraphs or multidigraphs is similar to the construction of subgraphs from simple graphs or digraphs (see Subsection Subgraphs and Quotient Graphs).
Note that the support set, vertex labels and edge decorations are transferred from the supergraph to the subgraph.
Construct the multigraph H as a subgraph of G. The function returns three values: The multigraph H, the vertex-set V of H; and the edge-set E of H. If G has a support set and/or if G has vertex/edge labels, and/or edge capacities or edge weights then all these attributes are transferred to the subgraph H.The elements of V and of E are specified by the list list whose items can be objects of the following types:
If the list of vertices and edges happens to contain duplicate elements, they will be ignored by the subgraph constructor. It is easy to recover the map that sends the vertices of the subgraph to the vertices of the supergraph and vice-versa: Simply coerce the vertex of the subgraph into the supergraph's vertex-set, and, if applicable, coerce the vertex of the supergraph into the subgraph's vertex-set.
- (a)
- A vertex of G. The resulting subgraph will be the subgraph induced on the subset of VertexSet(G) defined by the vertices in list.
- (b)
- An edge of G. The resulting subgraph will be the subgraph with vertex-set VertexSet(G) whose edge-set consists of the edges in list.
- (c)
- A set of
- (i)
- Vertices of G.
- (ii)
- Edges of G.
we assign labels to its vertices, and labels, capacities and weights to its edges. This demonstrates the fact that any subgraph of G retains the support set, as well as the vertex and edge decorations.
> S := {@ "a", "b", "c" @};
> G := MultiDigraph< S | < 1, {2, 3} >, < 1, {2} >, < 2, {2, 3} > >;
> G;
Multidigraph
Vertex Neighbours
a b c b ;
b c b ;
c ;
>
> V := VertexSet(G);
> for u in V do
> AssignLabel(~G, u, Random([ "X", "Y", "Z" ]));
> end for;
>
> E := EdgeSet(G);
> I := Indices(G);
> for i in I do
> AssignLabel(~G, E.i, Random([ "D", "E", "F" ]));
> if not InitialVertex(E.i) eq TerminalVertex(E.i) then
> AssignCapacity(~G, E.i, Random(1, 3));
> end if;
> AssignWeight(~G, E.i, Random(1, 3));
> end for;
>
> VertexLabels(G);
[ Z, Y, Z ]
> EdgeLabels(G);
[ E, F, D, E, E ]
> EdgeCapacities(G);
[ 2, 1, 3, 0, 2 ]
> EdgeWeights(G);
[ 2, 1, 3, 1, 1 ]
>
> V := VertexSet(G);
> H := sub< G | V!1, V!2 >;
> H;
Multidigraph
Vertex Neighbours
a b b ;
b b ;
>
> for u in VertexSet(H) do
> assert Label(u) eq Label(V!u);
> end for;
>
> for e in EdgeSet(H) do
> u := InitialVertex(e);
> v := TerminalVertex(e);
>
> assert SequenceToSet(Labels(Edges(u, v)))
> eq SequenceToSet(Labels(Edges(V!u, V!v)));
> assert SequenceToSet(Capacities(Edges(u, v)))
> eq SequenceToSet(Capacities(Edges(V!u, V!v)));
> assert SequenceToSet(Weights(Edges(u, v)))
> eq SequenceToSet(Weights(Edges(V!u, V!v)));
> end for;
Note that since G is a multidigraph it is not possible to coerce
an edge of H into the edge-set of G. This is because edge coercion
for multi(di)graphs involves the coercion of both the end-vertices
and the index of the edge.
A correspondence is established between the edges of H and the edges of G by retrieving all the edges in H and G having same end-vertices.
The complete functionality for adding and removing vertices or edges in simple graphs (see Subsection Incremental Construction of Graphs) is also available for multigraphs.
Note that some functions adding an edge to a multigraph also return the newly created edge. This feature is useful when there is a need to determine the index of this edge in the adjacency list of the modified multigraph. Also, there is the possibility of removing all the edges from u to v for given vertices u and v of the multigraphs.
Further, whenever a vertex or an edge is added or removed from a graph, the existing vertex labels and the edge labels or capacities or weights are retained. The support of the graph is retained in all cases except when adding a new vertex.
Unless otherwise specified, each of the functions described in this section returns three values:
Given a non-negative integer n, adds n new vertices to the multigraph G. The existing vertex labels and edge labels or capacities or weights are retained, but the support will become the standard support.
The procedural version of the previous function. AddVertex adds one vertex only to G.
Given a graph G and a label l, adds a new vertex with label l to G. The existing vertex labels and edge labels or capacities or weights are retained, but the support will become the standard support.
Given a graph G and a non-negative integer n, and a sequence L of n labels, adds n new vertices to G with labels from L. The existing vertex labels and edge labels or capacities or weights are retained, but the support will become the standard support.
Given a vertex v of G, or a set U of vertices of G, removes v (or the vertices in U) from G. The support, vertex labels, and edge labels or capacities or weights are retained.
The procedural versions of the previous functions.
Given a graph G and a pair of vertices of G, add the edge to G described by this pairs. If G is undirected then the edge must be given as a set of (two) vertices, if G is directed the edge is given as a sequence of (two) vertices. If G is a network, then the edge is added with a capacity of 1 (0 if a loop). The support, vertex labels, and edge labels or capacities or weights are retained. This set of functions has two return values: The first is the modified graph and the second is the newly created edge. This feature is especially useful when adding parallel edges.
Given a graph G and a set or a sequence of pairs of vertices of G, add the edges to G described by these pairs. If G is undirected then the edges must be given as a set of (two) vertices, if G is directed the edges are given as a sequence of (two) vertices. If G is a network, then the edges are added with a capacity of 1 (0 if a loop). The support, vertex labels, and edge labels or capacities or weights are retained.
The procedural versions of the previous four functions.
Given a graph G, two vertices of G u and v, returns a new edge between u and v. If G is a network, the edge is added with a capacity of 1 (0 if loop). The support, vertex labels, and edge labels or capacities or weights are retained. This function has two return values: The first is the modified graph and the second is the newly created edge. This feature is especially useful when adding parallel edges.
Given a graph G which is not a network, two vertices of G u and v, and a label l, adds a new edge with label l between u and v. The support, vertex labels, and edge labels or capacities or weights are retained. This function has two return values: The first is the modified graph and the second is the newly created edge.
Given a network G, two vertices of G u and v, and a non-negative integer c, adds a new edge from u to v with capacity c. The support, vertex labels, and edge labels or capacities or weights are retained. This function has two return values: The first is the modified graph and the second is the newly created edge.
Given a network G, two vertices of G u and v, a non-negative integer c, and a label l, adds a new edge from u to v with capacity c and label l. If G is a network, then add a new edge with label l and capacity c between u and v. The support, vertex labels, and edge labels or capacities or weights are retained. This function has two return values: The first is the modified graph and the second is the newly created edge.
Procedural versions of the previous functions for adding edges to a graph.
Given a graph G, and a sequence or set S of pairs of vertices of G, the edges specified in S are added to G. The elements of S must be sets or sequences of two vertices of G, depending upon whether G is undirected or directed respectively.If G is a network, the edges are added with a capacity of 1 (0 if a loop). The support, vertex labels, and edge labels or capacities or weights are retained.
Given a graph G, a sequence S of pairs of vertices of G, and a sequence L of labels of the same length, the edges specified in S are added to G with its corresponding label as given in L. The elements of S must be sets or sequences of two vertices of G, depending upon whether G is undirected or directed respectively. If G is a network, the edges are added with a capacity of 1 (0 if loop). The support, vertex labels, and edge labels or capacities or weights are retained.
These are procedural versions of the previous functions for adding edges to a graph.
Given an edge e or a set S of edges of a multigraph G, this function creates a graph that corresponds to G with the edge e (respectively, set of edges S) removed. The resulting multigraph will have vertex-set V(G) and edge-set E(G) - { e } (respectively, E(G) - S). The support, vertex labels and edge labels are retained on the remaining edges.
Given a graph G and a set S of pairs { u, v } or [u, v], u, v vertices of G, this function forms the graph having vertex-set V(G) and edge-set E(G) - S. That is, the graph returned is the same as G except that all the edges specified by pairs in S have been removed. An edge is represented as a set if G is undirected, and as a sequence otherwise. The support, vertex labels and edge labels are retained on the remaining edges.
These operations represent procedural versions of the previous functions. Whenever an edge is represented as a pair {u, v} or [u, v] of vertices of G, it is assumed that all the edges from u to v are to be removed from G.
As in the case of simple graphs (see Subsection Constructing Complements, Line Graphs; Contraction, Switching) it is possible to insert a vertex in a multigraph edge. The new edges thus created will be unlabelled with their capacities and weights set as follows: (These rules apply regardless as to whether the edge-set is capacitated and/or weighted).
Let e be an edge from u to v with capacity c and weight w in a multigraph G. After the insertion of a new vertex x in e, the edge e will be replaced by two edges, one from u to x and the other from x to v, both having capacity c and weight w.
These rules apply regardless as to whether the edge-set is capacitated and/or weighted.
The contraction operation can only be applied to a pair of vertices, since contracting a single multigraph edge which might have parallel edges is meaningless. The graph's support and vertex/edges decorations are retained when contracting its edges.
Each of the functions described below returns three values:
Given an edge e of the multigraph G, this function inserts a new vertex of degree 2 in e. If appropriate, the two new edges that replace e will have the same capacity and weight as e. They will be unlabelled. The vertex labels and the edge decorations of G are retained, but the resulting graph will have standard support.
Given a set T of edges belonging to the multigraph G, this function inserts a vertex of degree 2 in each edge belonging to the set T.
Given an edge e = {u, v} of the graph G, form the graph obtained by removing the edge e and then identifying the vertices u and v. New parallel edges and new loops may result from this operation but any new loop will be assigned zero capacity. With the above exception, the edge decorations are retained, as are the support and the vertex labels of G.
Given vertices u and v belonging to the multigraph G, this function returns the multigraph obtained by identifying the vertices u and v. New parallel edges and new loops may result from this operation but any new loop will be assigned zero capacity. With the above exception, the edge decorations are retained, as are the support and the vertex labels of G.
Given a set S of vertices belonging to the multigraph G, this function returns the multigraph obtained by identifying all of the vertices in S.
Of the union operations available for simple graphs (see Section Unions and Products of Graphs) only Union and EdgeUnion have been implemented for multigraphs. It is straightforward to write Magma code for other union functions with multigraphs.
In contrast with the other standard graph constructions, the support, vertex labels and edge decorations are generally not handled by the functions listed below. Thus, the resulting graph will always have standard support and no vertex labels nor edge decorations. The one exception occurs in the case of networks, where edge capacities are properly handled.
Given multi(di)graphs G and H with disjoint vertex sets V(G) and V(H) respectively, this function constructs their union, i.e. the multi(di)graph with vertex-set V(G) ∪V(H), and edge-set E(G) ∪E(H). The resulting multi(di)graph has standard support and no vertex labels nor edge decorations.
Given networks N and H with disjoint vertex sets V(N) and (H) respectively, construct their union, i.e. the network with vertex-set V(N) ∪V(H), and edge-set E(N) ∪E(H). The resulting network has standard support and capacities but neither vertex labels, edge labels nor weights retained.
The union of the multigraphs or networks in the sequence or the set S.
Given multi(di)graphs G and H having the same number of vertices, construct their edge union K. This construction identifies the i-th vertex of G with the i-th vertex of H for all i. The edge union has the same vertex-set as G (and hence as H) and there is an edge from u to v in K if and only if there is an edge from u to v in either G or H. The resulting multi(di)graph has standard support but neither vertex labels nor edge decorations.
Given networks N and H having the same number of vertices, construct their edge union K. This construction identifies the i-th vertex of N with the i-th vertex of H for all i. The edge union has the same vertex-set as N (and hence as H) and there is an edge [u, v] with capacity c in K if and only if either there is an edge [u, v] with capacity c in N or if there is an edge [u, v] with capacity c in H. The resulting network has standard support and the inherited edge capacities but neither vertex labels, edge labels nor weights.