[JavaLilly]

This is an assignment. I am trying to convert Dijkstra's algorithm into a max flow problem by changing Dijkstra's algorithm to focus on flows instead of distance. Then I tried to take the relax edge method and implement it in Ford Fulkerson's has augmenting path.

I tried implementing the relax in edge in Ford Fulkerson. I tried to substitute it for has augmenting path, but I couldn't get the parameters quite right. So then I tried putting it into the has augmenting path which is what I put below. Logically, it makes sense to me, but I keep getting an Illegal Increase exception and I don't know why. Could you point me in the right direction? I thought maybe it was saying that because I was trying to relax an edge and increase the index when I wasn't supposed to, but I am still confused.

Thanks for any advice.

  // is there an augmenting path? 
    // if so, upon termination edgeTo[] will contain a parent-link representation of such a path
    private boolean hasAugmentingPath(FlowNetwork G, int s, int t) {
        edgeTo = new FlowEdge[G.V()];
        marked = new boolean[G.V()];

        // breadth-first search
        IndexMaxPQ<Double> q = new IndexMaxPQ<Double>(G.V());
        q.insert(s, Double.POSITIVE_INFINITY);
        marked[s] = true;
        while (!q.isEmpty()) {
            int v = q.delMax();

            for (FlowEdge e : G.adj(v)) {
                int w = e.other(v);

                //  if residual capacity from v to w
                if (e.residualCapacityTo(w) > 0) {
                    /**
                    q.insert(w, e.flow());
                    edgeTo[w] = e;
                    System.out.println(e);
                     **/
                     
                    marked[w] = true;
                    double flowKeep = e.flow();// = 0.0; //keeps track of the current flow on an edge
                    if (flowKeep < e.capacity()) { // the flow on the FlowEdge is greater than the flow on that before it                      
                        flowKeep = e.capacity();//set flowKeep to that new edge
                        edgeTo[w] = e;//make edge to w the new "last edge" looked at
                        if (q.contains(w)) q.decreaseKey(w, flowKeep);
                        else                q.insert(w, flowKeep);
                    }
                }

            }
        }

        // is there an augmenting path?
        return marked[t];
    }

[macosxnerd101]

Dijkstra's algorithm really isn't practical to use for flow maximization. Ford-Fulkerson is a completely different algorithm. This is how it works:

-Start at A and do a BFT on its children
    -For each child
       -If flow < capacity
          -Mark it with (A as the parent, + for going forward, capacity - flow)
          -Push the label onto the queue

    -While the sink Z hasn't been reached and there are augmentable edges:
         -Poll an element from the queue, call it C
         -For each child of c:
             -If the forward flow < capacity
                  Mark it with (C as the parent, + for going forward, Min(capacity - flow, flow into C))
                 -Push the label onto the queue
             -Else if the backward flow > 0
                  -Mark the edge with (C as the parent, - for going backwards, Min(edge flow into the current child, flow into C)
                  -Push the label onto the queue

    -Augment the vertices based on the path of C and repeat from A

I don't see things like handling backwards flow in your implementation.

[JavaLilly]

Thank you, I am going to try this out. You explanation makes a lot of sense.
I hadn't thought about looking at backward flow. Why would I need to though? If I find the flow going one way, do I need to double check it?

[macosxnerd101]

What happens is if you have additional flow coming into a vertex, it can push flow back and direct it along another path, thus augmenting the flow. It re-routes the flow.

[JavaLilly]

So if I have (where s is my source and t is my sink),
/ --- w \
s -----|--t
\ --- v /

The backward flow I need to calculate into w would be the effect of the flow coming in from v and from s?

This post has been edited by JavaLilly: 08 December 2012 - 09:00 PM

[macosxnerd101]

Think about it this way: If you have flow from A -> B and C -> B, you could push the flow from A -> B back from B -> C, then from C to other vertices.