# Standard Construction for Networks ## Subgraphs The construction of a sub-network is very similar to the construction of a sub-multidigraph (see Subsection [Subgraphs](../Multigraphs/multig-stand-constr.md#multigraph-subsec-stand-constr-sub)). 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](../Multigraphs/multig-elem.md#multigraph-sec-elem)). 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 $C_N$, that the total capacity from $u$ to $v$ in $H$ is $C_H$ before adding the edge from $u$ to $v$ in $H$, and that the total capacity from $u$ to $v$ in $H$ is $C_H'$ after adding the edge from $u$ to $v$ in $H$. In order to satisfy the “capacity constraint” it is enough that $C_H' \leq C_N$, i.e. that $C_H + c \leq C_N$ 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 $C_N$. This implies that $C_H$ is zero, since we require that $C_H + C_G \leq C_N$. 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 $C_H + c \leq C_N$. Note that the support set, vertex labels and edge labels and weights, if applicable, are transferred from the network to the sub-network. ### `sub< N | list >: GrphNet, List -> GrphNet, GrphVertSet, GrphEdgeSet` 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 $[v_i, v_j]$ of vertices of $N$. The resulting subgraph will be the subgraph with vertex-set `VertexSet(N)` whose edge-set consists of the edges $[v_i, v_j]$ in $list$ whose capacity is assumed to be the total capacity from $v_i$ to $v_j$ in $N$. The multiplicity and capacity constraints must be satisfied. **(d)** A tuple of the form $< [v_i, v_j], c >$ where $v_i$, $v_j$ are vertices of $N$ and $c$ the non-negative capacity of the edge $[v_i, v_j]$ 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 $< [v_i, v_j], c >$ where $v_i$, $v_j$ are vertices of $N$ and $c$ the non-negative capacity of the edge $[v_i, v_j]$ to be added to $H$. ### `Example: Constr Sub Network (ex-48c2fa)` We start by constructing a network with some multiple edges. ```magma > 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. ```magma > 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. ```magma > 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$. ```magma > > 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$. ```magma > 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. ```magma > > 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. ```magma > 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. ```magma > > 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. ```magma > 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$. ```magma > > 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. ```magma > > 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 ```magma > Capacity(E.4); 1 > Capacity(V!InitialVertex(E.4), V!TerminalVertex(E.4)); 4 ``` it cannot succeed since the edge multiplicity constraint is violated. ```magma > EdgeMultiplicity(V!InitialVertex(E.4), V!TerminalVertex(E.4)); 2 ``` ## Incremental Construction: Adding Edges 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](../Multigraphs/multig-stand-constr.md#multigraph-subsec-add-rem-ve) for details. The only exception is the function `AddEdge(G, u, v, l)` which differs for multidigraphs and networks. It is replaced by the functions `AddEdge(G, u, v, c)` and `AddEdge(G, u, v, c, l)` 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)*. ### `N + < [ u, v ], c >: GrphNet, < [ GrphVert, GrphVert ], RngIntElt > -> GrphNet, GrphEdge` 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` ### `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 > }` ### `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` ### `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): GrphNet, GrphVert, GrphVert, RngIntElt` ### `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. ## Union of Networks 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](../Multigraphs/multig-stand-constr.md#multigraph-subsec-union).