|
The construction of a sub-network is
very similar to the construction of a sub-multidigraph
(see Subsection Subgraphs).
Additional flexibility is available for setting edge capacities
in the subgraph.
There are two constraints when building a subgraph
(see the introduction to Section Elementary Invariants and Predicates for Multigraphs).
Let N be a network, and H a subgraph of N.
Then, given any vertices u, v of H,
the edge multiplicity from u to v is no greater
in H than it is in N,
and the total capacity
from u to v in H is no greater than the
total capacity from u to v in N.
Failure to satisfy these constraints will result in a run-time error
when constructing a sub-network.
Assume that we intend to add an edge from u to v in H. Assume
also that the total capacity from u to v in N is CN,
that the total capacity from u to v in H is CH before
adding the edge from u to v in H,
and that the total capacity from u to v in H is CH'
after adding the edge from u to v in H.
In order to satisfy the "capacity constraint"
it is enough that CH' ≤CN, i.e. that
CH + c ≤CN where c is the capacity of the edge
one wants to add in H.
There are two methods for adding an edge from u to v.
Firstly, adding the edge [u, v] to H without specifying its
capacity in H assumes that the edge [u, v] will be added
with capacity CN.
This implies that CH is zero, since we require that
CH + CG ≤CN.
Secondly, adding the edge [u, v] to H when specifying its capacity
as c assumes that the edge [u, v] will be added
with capacity c such that CH + c ≤CN.
Note that the support set, vertex labels and edge labels and weights,
if applicable,
are transferred from the network to the sub-network.
Construct the network H as a subgraph (sub-network) of N.
The function returns three values: The network H,
the vertex-set V of H; and the edge-set E of H.
If N has a support set and/or if N has vertex/edge labels,
and/or edge weights
then all these attributes are transferred to the subgraph H.
Edge capacities are also transferred to H unless
they are specifically set as explained below.
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 N.
The resulting subgraph will be the subgraph induced on the subset
of VertexSet(N) defined by the vertices in list.
- (b)
- An edge of N.
The resulting subgraph will be the subgraph with vertex-set
VertexSet(N)
whose edge-set consists of the edges in list
subject to the multiplicity and capacity constraints being satisfied.
- (c)
- A pair of [vi, vj] of vertices of N.
The resulting subgraph will be the subgraph with vertex-set
VertexSet(N)
whose edge-set consists of the edges [vi, vj] in list
whose capacity is assumed to be the total capacity
from vi to vj in N.
The multiplicity and capacity constraints must be satisfied.
- (d)
- A tuple of the form < [vi, vj], c > where
vi, vj are vertices of N and c the
non-negative capacity of the edge [vi, vj]
to be added to H.
The resulting subgraph will be the subgraph with vertex-set
VertexSet(N)
whose edge-set consists of the edges as they are given in list,
subject to the multiplicity and capacity constraints being satisfied.
- (e)
- A set of
- (i)
- Vertices of N.
- (ii)
- Edges of N.
- (iii)
- Pairs of vertices of N.
- (iv)
- Tuples of the form < [vi, vj], c > where
vi, vj are vertices of N and c the
non-negative capacity of the edge [vi, vj]
to be added to H.
We start by constructing a network with some multiple edges.
> N := Network< 4 |
> < [1, 2], 2 >, < [1, 2], 3 >, < [1, 4], 5 >,
> < [2, 3], 1 >, < [2, 3], 3 >, < [3, 4], 1 >, < [3, 4], 6 > >;
> N;
Network
Vertex Neighbours
1 4 [ 5 ] 2 [ 3 ] 2 [ 2 ] ;
2 3 [ 3 ] 3 [ 1 ] ;
3 4 [ 6 ] 4 [ 1 ] ;
4 ;
> V := VertexSet(N);
> E := EdgeSet(N);
We construct a subgraph H of N induced by some of N's vertices
and we obtain
the mapping from the vertices of N to the vertices of H and vice-versa.
> H := sub< N | V!1, V!3, V!4 >;
> assert IsSubgraph(N, H);
> H;
Network
Vertex Neighbours
1 3 [ 5 ] ;
2 3 [ 1 ] 3 [ 6 ] ;
3 ;
> V!VertexSet(H)!1, VertexSet(H)!V!1;
1 1
> V!VertexSet(H)!2, VertexSet(H)!V!3;
3 2
> V!VertexSet(H)!3, VertexSet(H)!V!4;
4 3
The next statements illustrate the "capacity constraint": That is,
given any pair [u, v] of vertices of H, H a subgraph of N,
the total capacity from u to v in H can not be greater than
the total capacity from u to v in N.
The subgraph constructor will fail whenever this rule cannot be
satisfied.
We give a few examples below.
> Edges(N);
{@ < [1, 2], 1 >, < [1, 2], 2 >, < [1, 4], 3 >, < [2, 3], 4 >, < [2, 3], 5 >,
< [3, 4], 6 >, < [3, 4], 7 > @}
> E.1, E.2;
< [1, 2], 1 > < [1, 2], 2 >
> Capacity(E.1);
2
> Capacity(E.2);
3
> Capacity(V!1, V!2);
5
>
> H := sub< N | E.1, E.1 >;
> H;
Network
Vertex Neighbours
1 2 [ 2 ] 2 [ 2 ] ;
2 ;
3 ;
4 ;
Adding twice the edge E.1 to H is a valid operation since
the resulting total capacity from 1 to 2 in H is 4 while
it is 5 in N.
> > H := sub< N | E.2, E.2 >;
>> H := sub< N | E.2, E.2 >;
^
Runtime error in sub< ... >: RHS argument 2 - Edge multiplicity and capacity
not compatible with subgraph constructor
>
Adding twice the edge E.2 (which has capacity 3) to H would have
resulted in the total capacity from 1 to 2 in H to be 6,
while it is 5 in N.
> H := sub< N | E!< [1, 2], 1 >, E!< [1, 2], 1 > >;
> H;
Network
Vertex Neighbours
1 2 [ 2 ] 2 [ 2 ] ;
2 ;
3 ;
4 ;
This succeeded since the total capacity from 1 to 2 in H is now 4.
> > H := sub< N | E!< [1, 2], 2 >, E!< [1, 2], 2 > >;
>> H := sub< N | E!< [1, 2], 2 >, E!< [1, 2], 2 > >;
^
Runtime error in sub< ... >: RHS argument 2 - Edge multiplicity and capacity
not compatible with subgraph constructor
>
Again, this operation failed as it would have resulted
in the total capacity from 1 to 2 in H to be 6.
> H := sub< N | < [ V!1, V!2 ], 2 >, < [ V!1, V!2 ], 2 > >;
> H;
Network
Vertex Neighbours
1 2 [ 2 ] 2 [ 2 ] ;
2 ;
3 ;
4 ;
This operation is valid since
the total capacity from 1 to 2 in H is now 4.
> > H := sub< N | < [ V!1, V!2 ], 2 >, < [ V!1, V!2 ], 4 > >;
>> H := sub< N | < [ V!1, V!2 ], 2 >, < [ V!1, V!2 ], 4 > >;
^
Runtime error in sub< ... >: RHS argument 2 - Tuple must be <[vertex,
vertex], capacity> with total edge multiplicity and capacity compatible with
subgraph constructor
>
This operation cannot succeed as
the total capacity from 1 to 2 in H would be 6.
> H := sub< N | [ V!1, V!2 ] >;
> H;
Network
Vertex Neighbours
1 2 [ 5 ] ;
2 ;
3 ;
4 ;
Adding the edge [1, 2] without specifying its capacity
implies that an edge from 1 to 2 is added with capacity 5 to H,
which is the total capacity from 1 to 2 in N.
> > H := sub< N | [ V!1, V!2 ], [ V!1, V!2 ] >;
>> H := sub< N | [ V!1, V!2 ], [ V!1, V!2 ] >;
^
Runtime error in sub< ... >: RHS argument 2 - Sequence must be
[vertex, vertex] with vertices of the LHS and must be unique
>
Adding twice the edge [1, 2] without specifying its capacity
would have resulted in the total
capacity from 1 to 2 in H to be 10.
This operation cannot succeed.
Finally, let us illustrate the edge multiplicity constraint.
> > H := sub< N | E.4, E.4, E.4 >;
>> H := sub< N | E.4, E.4, E.4 >;
^
Runtime error in sub< ... >: RHS argument 3 - Edge multiplicity and capacity
not compatible with subgraph constructor
>
Although the above statement satisfies the capacity constraint
> Capacity(E.4);
1
> Capacity(V!InitialVertex(E.4), V!TerminalVertex(E.4));
4
it cannot succeed since the edge multiplicity constraint
is violated.
> EdgeMultiplicity(V!InitialVertex(E.4), V!TerminalVertex(E.4));
2
Almost all the functions to add or remove either vertices or edges
that are available for multidigraphs also apply to networks;
they are not listed here,
see Section Incremental Construction of Multigraphs for details.
The only exception is the function
AddEdge
which differs for multidigraphs and networks.
It is replaced by the functions
AddEdge
and
AddEdge
which are specialised functions for adding
capacitated edges to networks.
There are a few more such specialised functions which
are listed below, they all concern adding edges to a network.
Note that whenever an edge is added to a network
using the general multidigraph functions,
which do not allow specifying an edge capacity,
the edge to be added is always
taken to have capacity 1 (or 0 if a loop).
Given two vertices u and v of a network N,
and c a non-negative integer,
adds an edge from u to v with capacity c.
The support and edge capacities are retained.
This function returns two values: The modified network, and the edge
newly created (added).
This feature is especially useful when adding parallel edges.
N + [ < [ u, v ], c > ] : GrphNet, [ < [ GrphVert, GrphVert ], RngIntElt > ] -> GrphNet
Given tuples of the form < [ u, v ], c >, u and v vertices of
the network N and c a non-negative integer,
adds the edges from u to v with capacity c.
Tuples can be contained in a set or a sequence; the latter is
useful when dealing with duplicates.
The support and edge capacities are retained.
N +:= { < [ u, v ], c > } : GrphNet, { < [ GrphVert, GrphVert ], RngIntElt > } ->
N +:= [ < [ u, v ], c > ] : GrphNet, [ < [ GrphVert, GrphVert ], RngIntElt > ] ->
The procedural versions of the previous three functions.
Tuples can be contained in a set or a sequence; the latter is
useful when dealing with duplicates.
AddEdge(N, u, v, c) : GrphNet, GrphVert, GrphVert, RngIntElt -> GrphNet, GrphEdge
Given two vertices u and v of the network N, and c a non-negative integer,
adds an edge from u to v with capacity c.
The support and edge capacities are retained.
This function returns the modified network and the newly created edge.
This feature is especially useful when adding parallel edges.
AddEdge(N, u, v, c, l) : GrphNet,GrphVert, GrphVert, RngIntElt, . -> GrphNet, GrphEdge
Given two vertices u and v of the network N, c a non-negative integer,
and a label l,
adds an edge from u to v with capacity c and label l.
The support and edge capacities are retained.
This function returns the modified network and the newly created edge.
This feature is especially useful when adding parallel edges.
AddEdges(N, S) : GrphNet, [ < [ GrphVert, GrphVert ], RngIntElt > ] -> GrphNet
Given a network N and a set or a sequence S of tuples, this function
includes the edges specified in S.
The tuples must be of the form < [ u, v ], c >, where u and v vertices of
N and c a non-negative integer.
The support and existing vertex and edge decorations are retained.
AddEdge(~N, u, v, c, l) : GrphNet, GrphVert, GrphVert, RngIntElt, . ->
AddEdges(~N, S) : GrphNet, { < [ GrphVert, GrphVert ], RngIntElt > } ->
AddEdges(~N, S) : GrphNet, [ < [ GrphVert, GrphVert ], RngIntElt > ] ->
Procedural versions of previous functions adding edges to a network.
Tuples can be contained in a set or a sequence; the latter is
useful when dealing with duplicates.
It is possible to construct a new network from the union of two
networks.
For more details, we refer the reader
to Subsection Unions of Multigraphs.
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|