When implementing Ford-Fulkerson or Dinitz algorithms for maximum network flow there are two operations that need to be performed on the graph:
Ideally the first operation will be linear with respect to the number of neighbours and the second one should be constant. In addition the memory required for the graph representation should be linear with respect to the number of edges(note that for most practical applications of max network flow algorithms I have seen the number of edges is about linear times the number of vertices). All the estimations for the complexity for the two algorithms will only hold if the constraints above are met.
The problem is that none of the classical graph representations is able to meet the above requirements:
Using adjacency matrix, finding the reverse edge of a given edge can be done in constant time. However iterating over all neighbours is linear with respect to the number of all vertices and also the required memory is quadratic with respect to the number of vertices.
Using this representation, iterating over all neighbours will not be linear with respect to the number of neighbours and also finding the reverse edge for a given edge is not constant.
Using this representation we can iterate over all neighbours in linear time and also the needed memory is linear with respect to the number of edges. Still, finding the reverse edge for a given edge will be linear with respect to the number of neighbours of the destination vertex.
With a slight modification of this representation we could improve that - if instead of neighbours list we keep some binary search tree of the neighbours we could find the reverse edge with logarithmic complexity. And even better - if we use hash map instead of binary search tree we will have constant amortized complexity. Still this representation does not feel right - although still linear, a hash map has some memory overhead. Also it only has amortized constant complexity thus some operations may in fact be slower.
So my question is: what graph representation is appropriate to implement maximum network flow algorithms?
I would describe Ivaylo's representation as "edge-contiguous". There's also an "endpoint-contiguous" representation, which I believe from an extremely unscientific sample to be in wider use. I have implemented both at various times.
Absent hard data, my hypothesis would be that the endpoint-contiguous representation is better for the usual suspects network flow algorithms than the edge-contiguous representation, since edge-contiguous incurs a random access each time an arc is scanned, and endpoint-contiguous, each time flow is pushed on an arc (which presumably was preceded by scanning the arc). The clear upside of this representation is that it supports unsymmetric graphs (not so relevant for network flow). The clear downside of this representation is that changing the topology of the graph is much slower.
The representation consists of two arrays. first, with n+1 elements, stores the index of the first arc with the specified tail. The extra entry is m, the total number of arcs, so that the indexes of arcs with tail v are first[v] inclusive through first[v+1] exclusive. On Ivaylo's graph,
[0] = 0->1, [1] = 0->2,
[2] = 1->0, [3] = 1->2, [4] = 1->3,
[5] = 2->0, [6] = 2->1, [7] = 2->3, [8] = 2->4,
[9] = 3->1, [10] = 3->2, [11] = 3->5,
[12] = 4->2, [13] = 4->5,
[14] = 5->3, [15] = 5->4,
the array first is
0, 2, 5, 9, 12, 14, 16.
The arcs themselves are stored in an m-element array of the following structure type.
struct Arc {
int head;
int capacity;
int symmetric;
};
symmetric is the index of the symmetric arc.