Networks (New) [HB 103]

Networks are a new Magma category with type GrphNet. Networks are defined as digraphs whose edges are associated with a capacity; there may be parallel edges and loops. The fundamental network flow problem is the minimum cost flow problem, that is, determining a maximum flow at minimum cost from a specified source to a specified sink. So far we have concentrated on the maximum flow problem: Finding the maximum flow that can be pushed from a source to a sink subject to the capacity constraints of the edges in the network.

Two flow-based algorithms have been implemented: The Dinic algorithm with added heuristics from B. McKay, and the push-relabel method with heuristics mainly due to Cherkassky and Goldberg et al . The latter usually out-performs Dinic, however Dinics might be best for very sparse networks with a very small flow and whose edge capacities are small.

The Dinic algorithm consists of two phases. The first phase constructs a layered network which consists of the ``useful'' edges of the network: Those edges through which a flow can be pushed. The second phase finds a maximal flow by constructing paths from the source to the sink. These two phases are repeated until no new layered network can be constructed due to the fact that there is no path of ``useful'' edges from the source to the sink. The flow is then maximum.

The generic push-relabel algorithm constructs a flow by pushing the maximum possible flow out of the source into its neighbours, and then pushing the excess flow at those vertices into their own neighbours. This is repeated until all vertices of the network except the source and the sink have a excess flow of zero. Of course this means that some flow might have been pushed back into the source. Specific heuristics for zero-one networks (i.e. whose edge capacities are either zero or one) and for general networks result in a very efficient implementation (when compared to Dinic). Thus the push-relabel method is the default algorithm when computing a maximum flow, although users may choose Dinic if they so desire.

Since networks allow parallel edges, they will be represented as an adjacency list: This is the sparse graph representation which was first introduced in the previous Magma release V2.9. The possible existence of parallel edges actually introduces the most significant distinction between a simple graph and a network (from the users point of view): Edges in a network will require a unique identification, an identification which is obviously not a necessity in a graph where multiple edges are disallowed.

The scheme chosen to identify edges in a network is to associate it with its index in the graph's adjacency list. This is possible since our implementation guarantees that edge indices remain constant during the graph's lifetime, even though vertices and edges may have been added or removed.

In short, most basic access functions and predicates that apply to simple graphs are also available for networks. They are not listed here, a full description can be found in the Magma manual. The following list highlights the most significant features of networks in Magma. Please be aware that for the time being it is not possible to label vertices and edges in a network. This feature should be available in the next release.

New Features:

• The function EdgeIndices(u, v) returns the indices in the adjacency list of the graph of all the directed edges from u to v. The function EdgeMultiplicity(u, v) returns the multiplicity of the edge from u to v.
• An edge e of type GrphEdge in a network N is uniquely identified by EndVertices(e) and Index(e) in the adjacency list of N.
• If E is the edge set of a network N, then E.i designates the edge in N with index i in N's adjacency list. Note that those semantics are different from the ones applying in the simple graph case.

  For if F is the edge set of a simple graph G, then F.i designates the ith edge in the list of edges of G as given by Edges(G). It is likely that from the next Magma release onwards the latter semantics will be changed so that F.i always designates the edge with index i in the adjacency list of the graph, be it simple or not.

• If e of type GrphEdge is an edge of a network N from vertex u to vertex v, then Capacity(e) returns the capacity associated with e while Capacity(u, v) returns the total capacity from vertex u to vertex v.
• Incremental construction of networks by addition or deletion of vertices and edges works in a similar fashion as in the simple digraph case, the only difference being the possibility of creating parallel edges and the necessity to associate each edge with a capacity.
• The semantics for network equality work as follows: Let N and M be two networks. Then N eq M if and only if Order(N) eq Order(M), if N and M have same support and the total capacity from vertex u to vertex v in N is equal to the total capacity from vertex u to vertex v in M for all ordered pairs of vertices. That is, it is possible that N equals M without it being necessary that they have the same number of edges from u to v for any given two vertices u and v.
• The semantics for IsSubgraph(N, M) are similar. M is a subgraph of N if and only if the total capacity from vertex u to vertex v in M is no greater than the total capacity from vertex u to vertex v in N.
• Given two vertices s and t in a network N, MaximumFlow(s, t) returns the value of the maximum flow in N from s to t. Given two sequences S and T of vertices in a network N, MaximumFlow(S, T) returns the value of the maximum flow in N from the vertices in S to the vertices in T.
• Let e of type GrphEdge be an edge in a network N from vertex u to vertex v. After a maximum flow computation in N, Flow(e) returns the flow carried by the edge e, while Flow(u, v) returns the total flow vertex u to vertex v. If no maximum flow computation has been performed on N then both functions return zero.
• Given two vertices s and t in a network N, MinimumCut(s, t) returns the minimum cut in N corresponding to the maximum flow from s to t in N. Similarly, given two sequences S and T of vertices in a network N, MinimumCut(S, T) returns the minimum cut corresponding to the maximum flow from the vertices in S to the vertices in T.