In this implementation, the order n of a multigraph or multidigraph is bounded by 134217722. See Section Bounds on the Graph Order in Chapter GRAPHS for more details.
Undirected multigraphs are constructed in a similar way to graphs (Subsection Construction of a General Graph).
Construct the multigraph G with vertex-set V = {@ v1, v2, ..., vn @} (where vi = i for each i if the first form of the constructor is used, or the ith element of the enumerated or indexed set S otherwise), and edge-set E = { e1, e2, ..., eq }. This function returns three values: The multigraph G, the vertex-set V of G; and the edge-set E of G.The elements of E are specified by the list edges, where the items of edges may be objects of the following types:
In addition to these three basic ways of specifying the edges list, the items in edges may also be:
- (a)
- A pair {vi, vj} of vertices in V. The undirected edge {vi, vj} from vi to vj will be added to the edge-set for G.
- (b)
- A tuple of the form < vi, Ni > where Ni will be interpreted as a set of neighbours for the vertex vi. The elements of the sets Ni must be elements of V. If Ni = { u1, u2, ..., ur }, the edges {vi, u1}, ..., {vi, ur} will be added to G.
- (c)
- A sequence [ N1, N2, ..., Nn ] of n sets, where Ni will be interpreted as a set of neighbours for the vertex vi. The edges {vi, ui}, ui ∈Ni, are added to G.
- (d)
- An edge e of a graph or digraph or multigraph or multidigraph or network of order n. If e is an edge from u to v, then the edge {u, v} is added to G.
- (e)
- An edge-set E of a graph or digraph or multigraph or multidigraph or network of order n. Every edge e in E will be added to G according to the rule set out for a single edge.
- (f)
- A graph or a digraph or a multigraph or a multidigraph or a network H of order n. Every edge e in H's edge-set is added to G according to the rule set out for a single edge.
- (g)
- A set of
- (i)
- Pairs of the form {vi, vj} of vertices in V.
- (ii)
- Tuples of the form < vi, Ni > where Ni will be interpreted as a set of neighbours for the vertex vi.
- (iii)
- Edges of a graph or digraph or multigraph or multidigraph or network of order n.
- (iv)
- Graphs or digraphs or multigraphs or multidigraphs or networks of order n.
- (h)
- A sequence of
- (i)
- Tuples of the form < vi, Ni > where Ni will be interpreted as a set of neighbours for the vertex vi.
> G := MultiGraph< 3 | < 1, {2, 3} >, < 1, {2} >, < 2, {2, 3} > >;
> G;
Multigraph
Vertex Neighbours
1 2 3 2 ;
2 3 2 2 1 1 ;
3 2 1 ;
Multidigraphs are constructed in the same way as digraphs (Subsection Construction of a General Digraph).
Construct the multidigraph G with vertex-set V = {@ v1, v2, ..., vn @} (where vi = i for each i if the first form of the constructor is used, or the ith element of the enumerated or indexed set S otherwise), and edge-set E = { e1, e2, ..., eq }. This function returns three values: The multidigraph G, the vertex-set V of G; and the edge-set E of G.The elements of E are specified by the list edges, where the items of edges may be objects of the following types:
In addition to these four basic ways of specifying the edges list, the items in edges may also be:
- (a)
- A pair [vi, vj] of vertices in V. The directed edge [vi, vj] from vi to vj will be added to the edge-set for G.
- (b)
- A tuple of the form < vi, Ni > where Ni will be interpreted as a set of out-neighbours for the vertex vi. The elements of the sets Ni must be elements of V. If Ni = { u1, u2, ..., ur }, the edges [vi, u1], ..., [vi, ur] will be added to G.
- (c)
- A sequence [ N1, N2, ..., Nn ] of n sets, where Ni will be interpreted as a set of out-neighbours for the vertex vi. All the edges [vi, ui], ui ∈Ni, are added to G.
- (d)
- An edge e of a graph or digraph or multigraph or multidigraph or network of order n. If e is an edge from u to v, then the edge [u, v] is added to G. Thus, if e is an undirected edge from u to v, both edges [u, v] and [v, u] are added to G.
- (e)
- An edge-set E of a graph or digraph or multigraph or multidigraph or network of order n. Every edge e in E will be added to G according to the rule set out for a single edge.
- (f)
- A graph or a digraph or a multigraph or a multidigraph or a network H of order n. Every edge e in H's edge-set is added to G according to the rule set out for a single edge.
- (g)
- A set of
- (i)
- Pairs of the form [vi, vj] of vertices in V.
- (ii)
- Tuples of the form < vi, Ni > where Ni will be interpreted as a set of out-neighbours for the vertex vi.
- (iii)
- Edges of a graph or digraph or multigraph or multidigraph or network of order n.
- (iv)
- Graphs or digraphs or multigraphs or multidigraphs or networks of order n.
- (h)
- A sequence of
- (i)
- Tuples of the form < vi, Ni > where Ni will be interpreted as a set of out-neighbours for the vertex vi.
> G := MultiDigraph< 3 | < 1, {2, 3} >, < 1, {2} >, < 2, {2, 3} > >;
> G;
Multidigraph
Vertex Neighbours
1 2 3 2 ;
2 3 2 ;
3 ;
A multi(di)graph is displayed by listing, for each vertex, all of its adjacent vertices. If the multigraph has multiple edges from u to v, then the adjacency list of u contains as many copies of the vertex v as there are edges from u to v.
The vertices in the adjacency list are not ordered, they appear in the order in which they were created. See the previous examples H159E1 and H159E2.
The support of a multi(di)graph is subject to exactly the same operations as simple graphs (see Subsection Operations on the Support).
The indexed set used in the construction of G (or the graph for which V is the vertex-set), or the standard set {@ 1, ..., n @} if it was not given.
If G is a graph having n vertices and S is an indexed set of cardinality n, return a new graph H equal to G but whose support is S. That is, H is structurally equal to G and its vertex and edge decorations are the same as those for G (see Sections Vertex Decorations: Labels and Edge Decorations).
The procedural version of the above function.
Returns a graph H that is isomorphic to G but defined on the standard support. That is, H is structurally equal to G and its vertex and edge decorations are the same as those for G.
> S := {@ "a", "b", "c" @};
> G := MultiGraph< S | < 1, {2, 3} >, < 1, {2} >, < 2, {2, 3} > >;
> G;
Multigraph
Vertex Neighbours
c b a b ;
b a b b c c ;
a b c ;
> StandardGraph(G);
Multigraph
Vertex Neighbours
1 2 3 2 ;
2 3 2 2 1 1 ;
3 2 1 ;