title: Having trouble understanding a pseudocode max-flow algorithm for geometric constraint solving
body: <p>So I'm trying to work my way through <a href="http://www.cs.purdue.edu/homes/cmh/distribution/papers/Constraints/book98.pdf" rel="nofollow noreferrer">this paper</a>, which is primarily about finding minimal dense subgraphs of a weighted graph (in the context of geometric constraint solving).</p>
  
  <p>A dense subgraph is one where the sum of the edge weights and the sum of the vertex weights are equal.</p>
  
  <p>The author explains that this is somehow equivalent to the max-flow algorithm, and so he proposes a variation on the standard max-flow algorithm which he says is more efficient for this problem. However I am not too familiar with the concepts and I'm finding the actual description very obtuse. Perhaps someone could help me with it?</p>
  
  <p>The algorithm is stated as follows:
  <img src="https://i.imgur.com/Kc286.png" alt="Image 1">
  <img src="https://i.imgur.com/Sn4ZS.png" alt="Image 2"></p>
  
  <p>I'm terrible confused about what step 17 is supposed to be, where the flows are actually initialized, and how the augmentation process works. </p>
  
  <p>The paper provides an example:
  <img src="https://i.imgur.com/BmRAN.png" alt="Image 3"></p>
  
  <p>So I tried to step through the example, but I couldn't get it to do what it's supposed to. It seems like when it loops the first time, it visits e1, v0, and v2, and labels e0 and e2. Then it visits e0 and labels v2. Then it visits e2, but all of its vertices have already been visited, so the algorithm never does anything. How does it augment the path?</p>
  
  <p>Thanks in advance.</p>