Introduction

Networks are an essential tool in modelling communication and dependence problems. A network is generally defined as a directed graph whose arcs are associated with a cost and a capacity; it may have multiple (i.e., parallel edges).

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. Specializations of this problem are the shortest path problem (where there is no capacity constraint) and the maximum flow problem (where there is no cost constraint). Some of the related problems are the minimum spanning tree problem (finding a spanning tree whose sum of the costs of its arcs is minimum), the matching problem (a pairing of the edges of the graph according to some criteria), and the multicommodity flow problem (where arcs may carry several flows of different nature). For an excellent and comprehensive monograph on networks problems, their implementation and applications, see [RAO93].

In Magma we have concentrated so far on the maximum flow problem (see Section Maximum Flow and Minimum Cut): 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.

Thus in Magma a network is defined as a directed graph, with possibly multiple edges, and whose edges carry a capacity. It is an object of type GrphNet. Since multiple edges are allowed, networks will be represented using an adjacency list, that is, they will have a sparse representation (see Section Sparse Graphs). Loops in networks will always have capacity zero.

In the future we expect to extend the definition of a network so that its edges can carry a cost in addition of a capacity, thus allowing the implementation of algorithms to solve the shortest path problem and the minimum spanning tree problem.