|
In this implementation, it is only possible to assign labels
as vertex decorations.
A vertex labelling of a graph G is a partial map from
the vertex-set of G into a set L of labels.
Assigns the label l to the vertex u in the graph G.
AssignLabels(~G, S, L) : GrphMult, [GrphVert], SeqEnum ->
AssignLabels(~G, S, L) : GrphMult, {@ GrphVert @}, SeqEnum ->
Assigns the labels in L to the corresponding vertices in G in the
sequence or indexed set S.
If for vertex u the corresponding entry
in L is not defined then any existing label of
u is removed.
Assigns the labels in L to the corresponding vertices in the
graph G.
Returns true if and only if the vertex u has a label.
Returns true if and only if the vertex-set V is labelled.
Returns true if and only if vertices of the graph G are labelled.
The label of the vertex u.
An error is raised if u is not labelled.
The sequence L of labels of the vertices in the sequence S.
If an element of S has no label,
then the corresponding entry in L is undefined.
The sequence L of labels of the vertices in the vertex-set V.
If an element of V has no label,
then the corresponding entry in L is undefined.
The sequence L of labels of the vertices of G.
If a vertex of G has no label, then the
corresponding entry in L is undefined.
Removes the label of the vertex u.
Remove the labels of the vertices in S.
Remove the labels of the vertices in the graph G.
Simple graph or multigraph edges can be assigned three
different types of decorations:
- -
- a label,
- -
- a capacity,
- -
- a weight.
Edge labels can be objects of any Magma type.
Edge capacities
must be non-negative integers (and loops must be assigned
a zero capacity).
Edge weights must be elements of a totally ordered ring.
Not all edges need to be assigned labels
when labelling edges, nor do all edges need to be
assigned capacities or weights when assigning either
decoration.
In the latter case, if some edges have been assigned
a capacity or a weight, then
the capacity or weight of any remaining unassigned
edge is always taken to be zero.
One may want to assign capacities to edges in order
to apply a network-flow algorithm to
the graph (Section Maximum Flow and Minimum Cut).
By assigning weights to edges one may also be able
to run a shortest-path algorithm (Section Distances, Shortest Paths and Minimum Weight Trees).
AssignCapacity(~G, e, c) : GrphMult, GrphEdge, RngIntElt ->
AssignWeight(~G, e, w) : GrphMult, GrphEdge, RngElt ->
Assigns the label l or the capacity c or the weight w to the
edge e in the graph G.
The capacity of any edge must be a non-negative integer except in
the case of a loop when it must be zero.
The weight w must be an element from a totally ordered ring.
AssignLabels(~G, S, D) : GrphMult, {@ GrphEdge @}, SeqEnum ->
AssignCapacities(~G, S, D) : GrphMult, [GrphEdge], [RngIntElt] ->
AssignCapacities(~G, S, D) : GrphMult, {@ GrphEdge @}, [RngIntElt] ->
AssignWeights(~G, S, D) : GrphMult, [GrphEdge], [RngElt] ->
AssignWeights(~G, S, D) : GrphMult, {@ GrphEdge @}, [RngElt] ->
Assigns the labels or capacities or
weights in the sequence D to the corresponding edges in the
sequence or indexed set S.
If for some edge e the corresponding entry in D
is not defined then any existing label or capacity or weight of
e is removed.
The same constraints regarding capacity and weight
apply as in the single edge assignment case.
AssignCapacities(~G, D) : GrphMult, [RngIntElt] ->
AssignWeights(~G, D) : GrphMult, [RngElt] ->
Assigns the labels or capacities or
weights in the sequence D to the corresponding edges in graph G.
Let E be the edge-set of G and let
d be the decoration at position i in D, that is, d = D[i].
Then the corresponding edge e in E which will be
decorated is E.i (see E.i).
If for some edge e the corresponding entry in D
is not defined then any existing label or capacity or weight of
e is removed.
The same constraints regarding capacity and weight
apply as in the single edge assignment case.
While it is the case that an edge is considered
to be labelled if and only if it has been assigned
a label, an edge may have a default capacity (weight) of zero.
Let e be an edge of a graph G and assume that e has not
been assigned a capacity (weight).
If any other edge of G has been assigned a capacity (weight),
then the edge-set of G is considered to be capacitated
(weighted).
In which case the capacity (weight) of e has a default value of zero.
If no other edge of G has been assigned a capacity (weight),
then the edge-set of G is considered to be uncapacitated
(unweighted).
In which case asking for the capacity (weight) of e results
in an error.
This is in contrast to the labelling situation where there is
no concept of a "default" label.
The edge-set of G is considered to be labelled if and only if
at least one edge of G has been labelled,
while any edge of G is considered to be labelled if and only if
e has been labelled.
Returns true if and only if the edge e has a label.
Returns true if and only if the edge-set is labelled;
that is, if and only if at least one edge of
E has been assigned a label.
IsEdgeLabelled(G) : Grph -> BoolElt
Returns true if and only if the edge-set of G is labelled.
Returns true if and only if the edge-set is capacitated;
that is, if and only if at least one edge of
E has been assigned a capacity.
IsEdgeCapacitated(G) : Grph -> BoolElt
Returns true if and only if the edge-set of G is capacitated.
Returns true if and only if the edge-set is weighted;
that is, if and only if at least one edge of
E has been assigned a weight.
IsEdgeWeighted(G) : Grph -> BoolElt
Returns true if and only if the edge-set of G is weighted.
An edge may have a default capacity and weight of zero, see
Subsubsection Testing for Edge Decorations for
more details.
The label of the edge e.
An error is raised if e has not been assigned a capacity.
The capacity of the edge e.
Let G be the parent graph of e.
An error is raised if the edge-set of G is uncapacitated.
If the edge-set of G is capacitated but e has not been assigned
a capacity, then Capacity(e) returns zero as the default value.
The weight of the edge e.
Let G be the parent graph of e.
An error is raised if the edge-set of G is unweighted.
If the edge-set of G is weighted but e has not been assigned
a weight, then Weight(e) returns zero as the default value.
Capacities(S) : [GrphEdge] -> SeqEnum
Weights(S) : [GrphEdge] -> SeqEnum
The sequence D of labels or capacities or weights
of the edges in the sequence S.
Let E be the edge-set of the parent graph of the edges.
If E is unlabelled or uncapacitated or unweighted
then D is the null sequence.
If an element of S has no label
then the corresponding entry in D is undefined.
If an element of S has no capacity or weight
while E is capacitated or weighted
then the corresponding entry in D has the default value of zero.
Capacities(E) : GrphEdgeSet -> SeqEnum
Weights(E) : GrphEdgeSet -> SeqEnum
The sequence D of labels or capacities or weights
of the edges in the edge-set E.
If E is unlabelled or uncapacitated or unweighted
then D is the null sequence.
If an element of E has no label
then the corresponding entry in D is undefined.
If an element of E has no capacity or weight
while E is capacitated or weighted
then the corresponding entry in D has the default value of zero.
The corresponding entry i in D of any edge e is such that
e = E.i (see E.i).
EdgeLabels(G) : Grph -> SeqEnum
EdgeCapacities(G) : GrphMult -> SeqEnum
EdgeCapacities(G) : Grph -> SeqEnum
EdgeWeights(G) : GrphMult -> SeqEnum
EdgeWeights(G) : Grph -> SeqEnum
The sequence D of labels or capacities or weights
of the edges in edge-set E of the graph G.
If E is unlabelled or uncapacitated or unweighted
then D is the null sequence.
If an element of E has no label
then the corresponding entry in D is undefined.
If an element of E has no capacity or weight
while E is capacitated or weighted
then the corresponding entry in D has the default value of zero.
The corresponding entry i in D of any edge e is such that
e = E.i (see E.i).
DeleteCapacity(~G, e) : GrphMult, GrphEdge ->
DeleteWeight(~G, e) : GrphMult, GrphEdge ->
Removes the label or capacity or weight of the edge e in the graph G.
DeleteCapacities(~G, S) : GrphMult, [GrphEdge] ->
DeleteWeights(~G, S) : GrphMult, [GrphEdge] ->
Remove the labels or capacities or weights of the edges (of the graph G) in S.
DeleteCapacities(~G) : GrphMult ->
DeleteWeights(~G) : GrphMult ->
Remove the labels or capacities or weights of the edges in the edge
set of the graph G.
Starting with a graph G, the functions below return a graph that is
isomorphic as a simple graph to G, but without the vertex and edge
labels of G, (or without the edge capacities or weights of G in the case of a
network). Should one require a copy of a graph without the support of G,
see Subsection Operations on the Support.
Should one require a copy of a graph without the support of G
and without the vertex/edge decorations of G, see
Subsection Converting between Simple Graphs and Multigraphs.
Return the (vertex and edge) unlabelled graph structurally identical
to G, whose edges have the same capacities and weights as those in G.
The support of G is also retained in the resulting graph.
Return the uncapacitated graph structurally identical to G,
whose vertices and edges have the same labels, and whose edges have
the same weights as those in G.
The support of G is also retained in the resulting graph.
Return the unweighted graph structurally identical to G, whose
vertices and edges have the same labels, and whose edges have the
same capacities as those in G.
The support of G is also retained in the resulting graph.
The labelling operations are illustrated by constructing a 2-colouring
of the complete bipartite graph K 3, 4.
Use is made of the function Distance(u, v) which returns the distance
between vertices u and v.
> K34, V, E := BipartiteGraph(3, 4);
> L := [ IsEven(Distance(V!1, v)) select "red" else "blue" : v in Vertices(K34) ];
> AssignLabels(Vertices(K34), L);
> VertexLabels(K34);
[ red, red, red, blue, blue, blue, blue ]
Another illustration is the creation of the Cayley graph of a group.
In this example Sym(4) is used.
> G<a,b> := FPGroup(Sym(4));
> I, m := Transversal(G, sub<G | 1>);
> S := Setseq(Generators(G));
> N := [ {m(a*b) : b in S} : a in I ];
> graph := StandardGraph(Digraph< I | N >);
> AssignLabels(VertexSet(graph), IndexedSetToSequence(I));
> V := VertexSet(graph);
> E := EdgeSet(graph);
> for i in [1..#I] do
> AssignLabels([ E![V | i, Index(I, m(I[i]*s))] : s in S], S);
> end for;
In this graph, [1,2,5,4] is a cycle.
So the corresponding edge labels should multiply to the identity.
> &*Labels([ EdgeSet(graph) | [1,2], [2,5], [5,4], [4,1] ]);
a^4
> G;
Finitely presented group G on 2 generators
Relations
b^2 = Id(G)
a^4 = Id(G)
(a^-1 * b)^3 = Id(G)
We turn to multigraphs to illustrate a point
with respect to the listing of the edge decorations.
We assign random labels, capacities and weights
to a multigraph.
> G := MultiGraph< 3 | < 1, {2, 3} >, < 1, {2} >, < 2, {2, 3} > >;
> E := EdgeSet(G);
> I := Indices(G);
>
> for i in I do
> AssignLabel(~G, E.i, Random([ "a", "b", "c", "d" ]));
> 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;
>
> EdgeLabels(G);
[ c, undef, c, undef, d, undef, c, undef, c ]
> EdgeCapacities(G);
[ 2, undef, 3, undef, 2, undef, 0, undef, 3 ]
> EdgeWeights(G);
[ 3, undef, 2, undef, 1, undef, 2, undef, 1 ]
Since G is undirected, the edge {v, u} and the edge {v, u}
are the same object, and thus they have the same index:
> V := VertexSet(G);
> u := V!1;
> v := V!3;
> Indices(u, v);
[ 3 ]
> Indices(v, u);
[ 3 ]
However, since G is represented by means of an adjacency list,
the undirected edge {u, v} is stored twice in the list,
and so there are two positions in the list associated
with the edge.
By convention, these positions are contiguous,
but, more importantly from the user's perspective,
the function Index that returns the index of the edge
{u, v} always returns the odd index associated with the
edge.
This explains why, for an undirected multigraph, the sequence returned
by a function like EdgeLabels will always have undefined
elements.
Finally note that the loop {2, 2}, which was assigned no capacity,
is shown to have capacity zero:
> E := EdgeSet(G);
> E.7;
< {2, 2}, 7 >
> Capacity(E.7);
0
This is in accordance with the definition of the default value
for edge capacity and weight
(see Subsubsection Testing for Edge Decorations).
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|