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.
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:
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).
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.
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.
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.
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.
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.
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.
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.
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).
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).
Removes the label or capacity or weight of the edge e in the graph G.
Remove the labels or capacities or weights of the edges (of the graph G) in S.
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.
> 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 ]
> 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)
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).