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 != 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 = {@ v₁, v₂, ..., v_n @} (where v_i = i for each i if the first form of the constructor is used, or the ith element of the enumerated or indexed set S otherwise), and edge-set E = { e₁, e₂, ..., e_q }. 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 < v_i, N_i > 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 = { u₁, u₂, ..., u_r }, the edges [v_i, u₁], ..., [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 < [v_i, v_j], c > 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₁, N₂, ..., 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 ∈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 x 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 < v_i, N_i > where N_i will be interpreted as a set of out-neighbours for the vertex v_i.

(iii)

A tuple of the form < [ v_i, v_j], c > 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 < v_i, N_i > where N_i will be interpreted as a set of out-neighbours for the vertex v_i.

(ii)

A tuple of the form < [v_i, v_j], c > where v_i, v_j are vertices in V and c a non-negative capacity.

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

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