title: Appropriate graph representation for network flow algorithms
body: <p>When implementing <a href="http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm" rel="nofollow">Ford-Fulkerson</a> or <a href="http://en.wikipedia.org/wiki/Dinic%27s_algorithm" rel="nofollow">Dinitz</a> algorithms for maximum network flow there are two operations that need to be performed on the graph:</p>
  
  <ul>
  <li>Iterate over all neighbours of a given vertex</li>
  <li>Find the reverse edge of a given edge(this is needed for the graph modification when a flow is added along an augmenting path).</li>
  </ul>
  
  <p>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. </p>
  
  <p>The problem is that none of the classical graph representations is able to meet the above requirements:</p>
  
  <h2>Adjacency Matrix</h2>
  
  <p>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 <strong>all vertices</strong> and also the required memory is quadratic with respect to the number of vertices.</p>
  
  <h2>Edges list</h2>
  
  <p>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.</p>
  
  <h2>Neighbours list</h2>
  
  <p>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. </p>
  
  <p>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. </p>
  
  <h2>The question</h2>
  
  <p>So my question is: what graph representation is appropriate to implement maximum network flow algorithms? </p>