|
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:
- (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.
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.
We create a multidigraph G with a support set;
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:
- (i)
- The multigraph G;
- (ii)
- The vertex-set V of G;
- (iii)
- The edge-set E of G.
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.
AddVertex(~G) : GrphMult ->
AddVertices(~G, n) : GrphMult, RngIntElt ->
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.
G - U : GrphMult, { GrphVert } -> GrphMult
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.
G -:= U : GrphMult, { GrphVert } ->
RemoveVertex(~G, v) : GrphMult, GrphVert ->
RemoveVertices(~G, U) : GrphMult, { GrphVert } ->
The procedural versions of the previous functions.
G + [ u, v ] : GrphMultDir, { [ GrphVert, GrphVert ] } -> GrphMultDir, GrphEdge
G + [ u, v ] : GrphNet, { [ GrphVert, GrphVert ] } -> GrphNet, GrphEdge
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.
G + [ { u, v } ] : GrphMultUnd, [ { GrphVert, GrphVert } ] -> GrphMultUnd
G + { [ u, v ] } : GrphMultDir, { [ GrphVert, GrphVert ] } -> GrphDir
G + [ [ u, v ] ] : GrphMultDir, [ [ GrphVert, GrphVert ] ] -> GrphDir
G + { [ u, v ] } : GrphNet, { [ GrphVert, GrphVert ] } -> GrphNet
G + [ [ u, v ] ] : GrphNet, [ [ GrphVert, GrphVert ] ] -> GrphNet
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.
G +:= [ u, v ] : GrphDir, [ GrphVert, GrphVert ] ->
G +:= [ u, v ] : GrphNet, [ GrphVert, GrphVert ] ->
G +:= { { u, v } }: GrphMultUnd, { { GrphVert, GrphVert } } ->
G +:= [ { u, v } ] : GrphMultUnd, [ { GrphVert, GrphVert } ] ->
G +:= { [ u, v ] } : GrphMultDir, { [ GrphVert, GrphVert ] } ->
G +:= [ [ u, v ] ] : GrphMultDir, [ [ GrphVert, GrphVert ] ] ->
G +:= { [ u, v ] } : GrphNet, { [ GrphVert, GrphVert ] } ->
G +:= [ [ u, v ] ] : GrphNet, [ [ GrphVert, GrphVert ] ] ->
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.
AddEdge(G, u, v, l) : GrphMultUnd, GrphVert, GrphVert, . -> GrphMult, GrphEdge
AddEdge(G, u, v, l) : GrphMultDir, GrphVert, GrphVert, . -> GrphMultDir, GrphEdge
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.
AddEdge(~G, u, v, l) : GrphMultUnd, GrphVert, GrphVert, . ->
AddEdge(~G, u, v, l) : GrphMultDir, GrphVert, GrphVert, . ->
AddEdge(~G, u, v, c) : GrphNet, GrphVert, GrphVert, RngIntElt ->
AddEdge(~G, u, v, c, l) : GrphNet, GrphVert, GrphVert, RngIntElt, . ->
Procedural versions of the previous functions for adding edges to a graph.
AddEdges(G, S) : GrphMultUnd, [ { GrphVert, GrphVert } ] -> GrphMultUnd
AddEdges(G, S) : GrphMultDir, { [ GrphVert, GrphVert ] } -> GrphMultDir
AddEdges(G, S) : GrphMultDir, [ [ GrphVert, GrphVert ] ] -> GrphMultDir
AddEdges(G, S) : GrphNet, { [ GrphVert, GrphVert ] } -> GrphNet
AddEdges(G, S) : GrphNet, [ [ GrphVert, GrphVert ] ] -> GrphNet
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.
AddEdges(~G, S) : GrphMultUnd, [ { GrphVert, GrphVert } ] ->
AddEdges(~G, S) : GrphMultDir, { [ GrphVert, GrphVert ] } ->
AddEdges(~G, S) : GrphMultDir, [ [ GrphVert, GrphVert ] ] ->
AddEdges(~G, S) : GrphNet, { [ GrphVert, GrphVert ] } ->
AddEdges(~G, S) : GrphNet, [ [ GrphVert, GrphVert ] ] ->
AddEdges(~G, S, L) : GrphMult, SeqEnum, SeqEnum ->
These are procedural versions of the previous functions for adding edges to a graph.
G - { e } : GrphMult, { GrphEdge } -> GrphMult
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.
G - { [u, v] } : GrphMultDir, { [ GrphVert, GrphVert ] } -> GrphMultDir
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.
G -:= { e } : GrphMult, { GrphEdge } ->
G -:= { { u, v } } : GrphMultUnd, { { GrphVert, GrphVert rbrace } ->
G -:= { [u, v] } : GrphMultDir, { [ GrphVert, GrphVert ] } ->
RemoveEdge(~G, e) : GrphMult, GrphEdge ->
RemoveEdges(~G, S) : GrphMult, { GrphEdge } ->
RemoveEdge(~G, u, v) : GrphMult, GrphVert, GrphVert ->
RemoveEdges(~G, S) : GrphMultDir, { { GrphVert, GrphVert } } ->
RemoveEdges(~G, S) : GrphMultDir, { [ GrphVert, GrphVert ] } ->
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:
- (i)
- The multigraph G;
- (ii)
- The vertex-set V of G;
- (iii)
- The edge-set E of G.
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.
Union(G, H) : GrphMultDir, GrphMultDir -> GrphMultDir
G join H : GrphMultUnd, GrphMultUnd -> GrphMultUnd
G join H : GrphMultDir, GrphMultDir -> GrphMultDir
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.
N join H : GrphNet, GrphNet -> GrphNet
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.
& join S : [ GrphMultDir ] -> GrphMultDir
& join S : [ GrphNet ] -> GrphNet
& join S : { MultiUnd } -> GrphMultUnd
& join S : { GrphMultDir } -> GrphMultDir
& join S : { GrphNet } -> GrphNet
The union of the multigraphs or networks in the sequence
or the set S.
EdgeUnion(G, H) : GrphMultDir, GrphMultDir -> GrphMultDir
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.
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|