On Wed, 9 Sep 2009, David Doria wrote:
Ok... getting even closer... I looked at read_dimacs a little bit and the kolmogorov example again and came up with this:
I put a comment in where I added the reverse edge - this stops the segfault. It seems like there should be a way to do this automatically though - when you add an edge - have it add the reverse edge automatically - is this possible?
I don't know about that.
Also, the cut weight seems to be only 4.3 (the weight of the first edge - where I am expecting it to be 4.3 + 5.1 = 9.4 (the sum of the edge weights). I actually do not need a directional graph, but it seems to be what the cut function is expecting, so I guess I can just use the 2-edge method and divide the weight I actually want by 2 and put it on both edges.
The actual cut is 4.3: the goal is to maximize the flow from s to t, and the capacity there (which can be fulfilled) is 4.3. The flow from t to s doesn't matter since that would reduce the flow in the s->t direction. Similarly, if you want to have undirected edges, you put the full weight on each direction since the algorithm cannot use both directions of a single edge pair (they cancel each other out). -- Jeremiah Willcock