Construction of Networks#

Networks are constructed in a similar way to multidigraphs (Subsection Construction of a General Multidigraph). In this implementation the order \(n\) of a network is bounded by 134217722. See Section Bounds on the Graph Order 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:

> 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 ] ;

Run in calculator

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, 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.

> 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 > @}

Run in calculator