# Construction of Networks

Networks are constructed in a similar way to multidigraphs (Subsection [Construction of a General Multidigraph](../Multigraphs/multig-constr.md#multigraph-subsec-dir-constr)). In this implementation the order $n$ of a network is bounded by 134217722. See Section [Bounds on the Graph Order](../Graphs/graph-digraph.md#graph-subsec-graph-size) for more details on this.

Let $N$ be the network to be constructed. In all cases, whenever an edge $[u, v]$, $u \neq v$, is to be added to $N$, its capacity will be set to 1 (0 if a loop) unless either its capacity is explicitly given at construction time, or it is the edge of a network, in which case the capacity of the edge remains as it was in the original network.

As an example, if $D$ is a digraph, then the edges of the network $N$ constructed as `N := Network< Order(D) | D >`; will be all the edges of $D$ whose capacity is set as 1 (or 0 if they are loops).

## `Network<n | edges >: RngIntElt, List -> GrphNet, GrphVertSet, GrphEdgeSet`

## `Network<S | edges >: SetEnum, List -> GrphNet, GrphVertSet, GrphEdgeSet`

## `Network<S | edges >: SetIndx, List -> GrphNet, GrphVertSet, GrphEdgeSet`

Construct the network $N$ with vertex-set $V = \lbrace @ v_1, v_2, \ldots, v_n @ \rbrace$ (where $v_i = i$ for each $i$ if the first form of the constructor is used, or the $i$th element of the enumerated or indexed set $S$ otherwise), and edge-set $E = \lbrace e_1, e_2, \ldots, e_q \rbrace$. This function returns three values: The network $N$, the vertex-set $V$ of $N$; and the edge-set $E$ of $N$.

The elements of $E$ are specified by the list $edges$, where the items of $edges$ may be objects of the following types:

**(a)**
A pair $[v_i, v_j]$ of vertices in $V$. The directed edge $[v_i, v_j]$ from $v_i$ to $v_j$ with capacity 1 (or 0 if it is a loop) will be added to the edge-set for $N$.

**(b)**
A tuple of the form $\langle v_i, N_i \rangle$ where $N_i$ will be interpreted as a set of out-neighbours for the vertex $v_i$. The elements of the sets $N_i$ must be elements of $V$. If $N_i = \lbrace u_1, u_2, \ldots, u_r \rbrace$, the edges $[v_i, u_1], \ldots, [v_i, u_r]$ will be added to $N$, all with capacity 1 (or 0 if they are loops).

**(c)**
A tuple of the form $\langle [v_i, v_j], c \rangle$ where $v_i$, $v_j$ are vertices in $V$ and $c$ the non-negative capacity of the directed edge $[v_i, v_j]$ added to $N$.

**(d)**
A sequence $[ N_1, N_2, \ldots, N_n ]$ of $n$ sets, where $N_i$ will be interpreted as a set of out-neighbours for the vertex $v_i$. All the edges $[v_i, u_i]$, $u_i \in N_i$, are added to $N$ with capacity 1 (or 0 if they are loops).

In addition to these four basic ways of specifying the $edges$ list, the items in $edges$ may also be:

**(e)**
An edge $e$ of a graph (or di/multi/multidigraph) or network of order $n$. If $e$ is an edge of a network $H$, then it will be added to $N$ with the capacity it has in $H$. If $e$ is not a network edge, then it will be added to $N$ with capacity 1, or 0 if it is a loop.

**(f)**
An edge-set $E$ of a graph (or di/multi/multidigraph) or network of order $n$. Every edge $e$ in $E$ will be added to $N$ according to the rule set out for a single edge.

**(g)**
A graph (or di/multi/multidigraph) or network $H$ of order $n$. Every edge $e$ in $H$’s edge-set is added to $N$ according to the rule set out for a single edge.

**(h)**
A $n\times n$ (0, 1)-matrix $A$. The matrix $A$ will be interpreted as the adjacency matrix for a digraph $H$ on $n$ vertices and the edges of $H$ will be included among the edges of $N$ with capacity 1 (0 if loops).

**(i)**
A set of

**(i)**
Pairs of the form $[v_i, v_j]$ of vertices in $V$.

**(ii)**
Tuples of the form $\langle v_i, N_i \rangle$ where $N_i$ will be interpreted as a set of out-neighbours for the vertex $v_i$.

**(iii)**
A tuple of the form $\langle[ v_i, v_j], c \rangle$ where $v_i$, $v_j$ are vertices in $V$ and $c$ a non-negative capacity.

**(iv)**
Edges of a graph (or di/multi/multidigraph) or network of order $n$.

**(v)**
Graphs (or di/multi/multidigraphs) or networks of order $n$.

**(j)**
A sequence of

**(i)**
Tuples of the form $\langle v_i, N_i \rangle$ where $N_i$ will be interpreted as a set of out-neighbours for the vertex $v_i$.

**(ii)**
A tuple of the form $\langle [v_i, v_j], c \rangle$ where $v_i$, $v_j$ are vertices in $V$ and $c$ a non-negative capacity.

## `Example: GrphNet Constr (ex-4c4672)`

We construct a network from a digraph, and observe that the edges that are not loops have a capacity of 1:

```magma
> SetSeed(1, 0);
> n := 5;
> d := 0.2;
> D := RandomDigraph(n, d : SparseRep := true);
> N := Network< n | D >;
> D;
Digraph
Vertex  Neighbours

1       2 1 ;
2       3 2 ;
3       ;
4       5 ;
5       2 ;

> N;
Network
Vertex  Neighbours

1       1 [ 0 ] 2 [ 1 ] ;
2       2 [ 0 ] 3 [ 1 ] ;
3       ;
4       5 [ 1 ] ;
5       2 [ 1 ] ;

```

## Magma Output: Printing of a Network

Magma displays a network $N$ in the form of a list of vertices, each accompanied by a list of its outgoing capacitated edges (each followed by the capacity of the edge in brackets). Thus, in the previous example [Example: GrphNet Constr](#example-ex-4c4672), it can be verified that all edges have capacity 1 (since the network was constructed from a digraph) except those edges that are loops.

If the network has multiple edges from $u$ to $v$, then *each* edge from $u$ to $v$, or rather its end-point $v$, is printed followed by the capacity of that edge. Also, the end-points in the adjacency list are not ordered and appear in the order in which they were created. The next example illustrates these two points.

### `Example: GrphNet Constr2 (ex-5be897)`

We construct a network from a set of tuples $<[vertex, vertex], capacity>$ and we exhibit a multiple edge.

```magma
> n := 5;
> C := 5;
> M := 3;
> T := [];
> for i in [1..12] do
>     u := Random(1, n);
>     v := Random(1, n);
>     m := Random(1, M);
>     for j in [1..m] do
>        c := Random(0, C);
>        if u eq v then
>            Append(~T, < [u, u], 0 >);
>        else
>            Append(~T, < [u, v], c >);
>        end if;
>     end for;
> end for;
> T;
[
  <[ 5, 4 ], 1>, <[ 5, 4 ], 3>, <[ 5, 4 ], 2>, <[ 5, 4 ], 1>,
  <[ 5, 4 ], 5>, <[ 1, 3 ], 2>, <[ 1, 3 ], 2>, <[ 5, 5 ], 0>,
  <[ 5, 5 ], 0>, <[ 2, 1 ], 2>, <[ 4, 2 ], 2>, <[ 4, 2 ], 5>,
  <[ 4, 2 ], 1>, <[ 4, 1 ], 3>, <[ 4, 1 ], 4>, <[ 4, 1 ], 3>,
  <[ 2, 3 ], 1>, <[ 2, 3 ], 3>, <[ 4, 3 ], 5>, <[ 4, 3 ], 3>,
  <[ 4, 3 ], 4>, <[ 2, 2 ], 0>, <[ 2, 2 ], 0>, <[ 5, 4 ], 0>,
  <[ 4, 4 ], 0>
]
> N := Network< n | T >;
> N;
Network
Vertex  Neighbours

1       3 [ 2 ] 3 [ 2 ] ;
2       2 [ 0 ] 2 [ 0 ] 3 [ 3 ] 3 [ 1 ] 1 [ 2 ] ;
3       ;
4       4 [ 0 ] 3 [ 4 ] 3 [ 3 ] 3 [ 5 ] 1 [ 3 ] 1 [ 4 ] 1 [ 3 ] 2
        [ 1 ] 2 [ 5 ] 2 [ 2 ] ;
5       4 [ 0 ] 5 [ 0 ] 5 [ 0 ] 4 [ 5 ] 4 [ 1 ] 4 [ 2 ] 4 [ 3 ] 4
        [ 1 ] ;

> Edges(N);
{@ < [1, 3], 6 >, < [1, 3], 7 >, < [2, 1], 10 >, < [2, 2], 22 >,
< [2, 2], 23 >, < [2, 3], 17 >, < [2, 3], 18 >, < [4, 1], 14 >,
< [4, 1], 15 >, < [4, 1], 16 >, < [4, 2], 11 >, < [4, 2], 12 >,
< [4, 2], 13 >, < [4, 3], 19 >, < [4, 3], 20 >, < [4, 3], 21 >,
< [4, 4], 25 >, < [5, 4], 1 >, < [5, 4], 2 >, < [5, 4], 3 >,
< [5, 4], 4 >, < [5, 4], 5 >, < [5, 4], 24 >, < [5, 5], 8 >,
< [5, 5], 9 > @}

```