1 Replies - 1461 Views - Last Post: 15 January 2013 - 01:05 PM Rate Topic: -----

#1 f_chopin  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 15-January 13

Error in ford fulkerson priority first search algorithm implementation

Posted 15 January 2013 - 11:12 AM

Hello, I'm currently trying to get a ford fulkerson implementation working that uses priority first search. The problem is that it seems to get in an endless loop, specifically the last while-loop in the pfs function. The prev[to] is always 5, so the guard of the while-loop is always true and so it never terminates.

I'm having a lot of trouble finding information on ford fulkerson using a priority first search, this is the best information i could find: http://community.top...als&d2=maxFlow. Any help getting this working would be really appreciated.I'm pretty sure it's something small, but I can't seem to find it.

Thanks.

public static void main(String[] args) {
				
		// the graph
		int capacity[][] = new int[6][6];
		int n = 6;
		capacity[0][1] = 16;
		capacity[0][2] = 13;
		capacity[1][2] = 10;
		capacity[2][1] = 4;
		capacity[3][2] = 9;
		capacity[1][3] = 12;
		capacity[2][4] = 14;
		capacity[4][3] = 7;
		capacity[3][5] = 20;
		capacity[4][5] = 4;

		
		int maxflow = maxflow(capacity, n, 0, 5);
	}
	
	static int maxflow(int[][] c, int n, int s, int t) {
		int flow = 0;
		while (true) {
			int path = pfs(c, n, s, t);
			if (path <= 0) {
				break;
			} else {
				flow += path;
			}
		}
		
		return(flow);
	}
	
	 private static int pfs(int[][] capacity, int n, int source, int sink) {
	        Queue<Node> pq = new PriorityQueue<Node>();
	        pq.add(new Node(source, Integer.MAX_VALUE, -1));

	        int[] prev = new int[n];
	        Arrays.fill(prev, -1);

	        boolean[] visit = new boolean[n];
	        Arrays.fill(visit, false);

	        int flow = 0;

	        while (!pq.isEmpty()) {
	        	Node top = pq.poll();
	            int from = top.from;

	            if (visit[from]) { }
	            prev[from] = top.from;

	            if (from == sink) {
	                flow = top.flow;
	                break;
	            }
	            visit[from] = true;

	            for (int i = 0; i < n; i++) {
	                if (capacity[from][i] > 0) {
	                    int newFlow = Math.min(capacity[from][i], top.flow);
	                    pq.add(new Node(i, newFlow, from));
	                }
	            }
	        }

	        if (flow == 0) {
	            return 0;
	        }

	        int to = sink;

                // this loop never ends
	        while (prev[to] != -1) {
	            capacity[prev[to]][to] -= flow;
	            capacity[to][prev[to]] += flow;
	            to = prev[to];
	        }
	        return flow;
	    }
	 
	 static class Node implements Comparable<Node> {
	        int from;
	        int flow;
	        int prev;

	        public Node(int from, int flow, int prev) {
	            this.from = from;
	            this.flow = flow;
	            this.prev = prev;
	        }

	        @Override
	        public int compareTo(Node that) {
	            return this.flow >= that.flow ? -1 : 1;
	        }
	    }


Is This A Good Question/Topic? 0
  • +

Replies To: Error in ford fulkerson priority first search algorithm implementation

#2 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12187
  • View blog
  • Posts: 45,250
  • Joined: 27-December 08

Re: Error in ford fulkerson priority first search algorithm implementation

Posted 15 January 2013 - 01:05 PM

Start by printing out the values in your prev array before the infinite loop. You will see it contains the values [0, 1, 2, 3, 4, 5].

Look here. If you've already visited the Node, you cannot revisit it in the same iteration where you find an augmenting path.
if (visit[from]) { }
prev[from] = top.from;



Also here, you need to look at the slack. That is, the difference between the current flow value and the slack, if you are going forward. To push back across an edge, it's the min between the current flow to the receiving vertex and the flow being pushed back that is subtracted from the current flow level.
for (int i = 0; i < n; i++) {
    if (capacity[from][i] > 0) {
           int newFlow = Math.min(capacity[from][i], top.flow);



This statement as well Arrays.fill(visit, false); is unnecessary, as booleans are initialized to false by default.

Also, I'm not a big fan of a matrix setup for Ford-Fulkerson. You only evaluate the adjacent vertices, not all of them. A matrix is one thing on a complete graph, but you cannot assure completeness on all graphs when writing the implementation. An adjacency list implementation is a lot cleaner, and it makes it easier to encapsulate your data.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1