|
Much of the functionality for simple graphs
(see Section The Vertex--Set and Edge--Set of a Graph) also applies to multigraphs.
We will not repeat here the functions pertaining to the vertex-set
and edge-set of a graph, but concentrate instead on the edges.
Indeed, there is a difference in the manner in which
multigraph edges are created and
accessed when compared to simple graph edges.
Since multigraphs may have multiple edges from u to v, it is necessary
to know
how many of these edges there are, and how each can be accessed.
More importantly a scheme is required to uniquely identify an edge.
Recall that a multigraph is represented by means of an adjacency list,
so any edge from u to v can be identified by its index in this list.
If there is more than one edge from u to v, then
a list of indices will identify each edge from u to v.
Thus, the index of the edge in the adjacency list will be
the means by which this edge can be uniquely identified.
This has a bearing on how an edge can be coerced into a multigraph:
Successful coercion will require two vertices u and v
so that v is a neighbour of u, and a valid index i in
the multigraph's adjacency list.
That is, the position i in the list is the index of an edge
from u to v.
Indices(u, v) : GrphVert, GrphVert -> SeqEnum
Given vertices u and v of a multigraph G, returns
the indices of the possibly multiple edge from u to v.
Multiplicity(u, v) : GrphVert, GrphVert -> RngIntElt
Given vertices u and v of a multigraph G, returns
the multiplicity of the possibly multiple edge from u to v.
Returns 0 if u is not adjacent to v.
Given vertices u and v of a multigraph G, returns
all the edges from u to v as a sequence of elements
of the edge-set of G.
Given a vertex u of an undirected multigraph G, returns
all the edges incident to u as a set of elements
of the edge-set of G.
If G is a multidigraph, the function returns
all the edges incident to and from u as a set of elements
of the edge-set of G.
Given the edge-set E of the undirected multigraph G and objects u, v
belonging to the support of G corresponding to adjacent
vertices, returns the edge from u to v which corresponds
to the edge with index i in the adjacency list of G.
This requires that the edge at i in the adjacency list of G is an edge
from u to v.
Given the edge-set E of the multidigraph G and objects u, v
belonging to the support of G corresponding to adjacent
vertices, returns the edge from u to v which corresponds
to the edge with index i in the adjacency list of G.
This requires that the edge at i in the adjacency list of G is an edge
from u to v.
{E . i} : GrphEdgeSet, RngIntElt -> GrphEdge
Let E be the edge-set of G.
If G is a simple graph (digraph) then this function is as
described in Subsection Creating Edges and Vertices.
If G is a multigraph or multidigraph, then this function returns the edge
at index i in the adjacency list of G, provided i is a valid
index.
EndVertices(e) : GrphEdge -> [ GrphVert, GrphVert ]
Given an edge e in an undirected multigraph G,
returns the end vertices of e as a set of vertices {u, v}.
If G is a multidigraph, returns e's end vertices
as a sequence of vertices [u, v].
Given an edge e = {u, v} or e = [u, v], returns vertex u.
This is useful in the undirected case since it indicates, where relevant,
the direction
in which the edge has been traversed.
Given an edge e = {u, v} or e = [u, v], returns vertex v.
This is useful in the undirected case since it indicates, where relevant,
the direction
in which the edge has been traversed.
Given an edge e in a multi(di)graph G,
returns the index of e in the
adjacency list of G.
Returns true if the edge s is equal to the edge t.
It s and t are edges in a multi(di)graph G,
returns true if and only if
s and t have the same index in the adjacency list of G.
> G := MultiGraph< 3 | < 1, {2, 3} >, < 1, {2} >, < 2, {2, 3} > >;
The graph G has a loop at vertex 2:
> Edges(G);
{@ < {1, 2}, 1 >, < {1, 2}, 5 >, < {1, 3}, 3 >, < {2, 2}, 7 >, < {2,
3}, 9 > @}
> E := EdgeSet(G);
> E.7;
< {2, 2}, 7 >
> assert InitialVertex(E.7) eq TerminalVertex(E.7);
The graph G has a multiple edge from vertex 1 to vertex 2:
> u := VertexSet(G)!1;
> v := VertexSet(G)!2;
> I := EdgeIndices(u, v);
> I;
[ 5, 1 ]
> assert #I eq Multiplicity(u, v);
>
> E := EdgeSet(G);
> e1 := E!< { 1, 2 }, I[1] >;
> e2 := E!< { 1, 2 }, I[2] >;
> e1, e2;
< {1, 2}, 5 > < {1, 2}, 1 >
> EndVertices(e1);
{ 1, 2 }
> EndVertices(e2);
{ 1, 2 }
> assert Index(e1) eq I[1];
> assert Index(e2) eq I[2];
>
> assert e1 eq E.I[1];
> assert not e2 eq E.I[1];
> assert e2 eq E.I[2];
> assert not e1 eq E.I[2];
We have seen that these two edges can be accessed directly:
> Edges(u, v);
[ < {1, 2}, 5 >, < {1, 2}, 1 > ]
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|