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.
> 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 3The 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)); 4it 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.
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.
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.
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.
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.
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.
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.