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).
Construct the network N with vertex-set V = {@ v1, v2, ..., vn @} (where vi = 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 = { e1, e2, ..., eq }. 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:
In addition to these four basic ways of specifying the edges list, the items in edges may also be:
- (a)
- A pair [vi, vj] of vertices in V. The directed edge [vi, vj] from vi to vj 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 < vi, Ni > where Ni will be interpreted as a set of out-neighbours for the vertex vi. The elements of the sets Ni must be elements of V. If Ni = { u1, u2, ..., ur }, the edges [vi, u1], ..., [vi, ur] will be added to N, all with capacity 1 (or 0 if they are loops).
- (c)
- A tuple of the form < [vi, vj], c > where vi, vj are vertices in V and c the non-negative capacity of the directed edge [vi, vj] added to N.
- (d)
- A sequence [ N1, N2, ..., Nn ] of n sets, where Ni will be interpreted as a set of out-neighbours for the vertex vi. All the edges [vi, ui], ui ∈Ni, are added to N with capacity 1 (or 0 if they are loops).
- (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 [vi, vj] of vertices in V.
- (ii)
- Tuples of the form < vi, Ni > where Ni will be interpreted as a set of out-neighbours for the vertex vi.
- (iii)
- A tuple of the form < [ vi, vj], c > where vi, vj 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 < vi, Ni > where Ni will be interpreted as a set of out-neighbours for the vertex vi.
- (ii)
- A tuple of the form < [vi, vj], c > where vi, vj are vertices in V and c a non-negative capacity.
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 ] ;
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 H160E1, 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.
<[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 > @}