Networks are an essential tool in modelling communication systems 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 a comprehensive monograph on networks, their implementation and applications, see [AMO93].
For convenience we provide users with the Magma network object with type GrphNet. It differs from the Magma multidigraph object having type GrphMultDir in one respect only: its edges are always assumed to be capacitated. The edges of a network have a capacity of one by default, unless they are specifically assigned a capacity. The loops in a network always have capacity zero. Since networks are a specialisation of multidigraphs, all the functions applying to multidigraphs also apply to networks. Below we outline those few functions that specifically concern networks, namely, their construction.