I am trying to implement the Ford Fulkerson Algorithm and have been getting stuck in an infinite loop when either doing my BFS or DFS solution. I am unsure if the bug is in one of those methods or my augment algorithm. Here is the code for each class I am working with.
Graph.java
/**
* Author - Kobie Arndt
*/
import java.lang.reflect.Array;
import java.util.*;
public class Graph {
public Map<String, ArrayList<Edge>> map; // keys are nodes
// each node maps to an
// list of Edges where the
// node is the source
public int flow; // the flow from s -> t in this graph right now
/**
* Construct a Graph object
* @param none
*/
public Graph() {
this.map = new HashMap<String, ArrayList<Edge>>();
}
/**
* add a new node to this Graph
* @param node - is just a string label
*/
public void addNode(String node) {
this.map.put(node, new ArrayList<Edge>());
}
/**
* add a new edge to this graph
* @param node - String - add this edge to nodes adjacency list
* @param e - Edge to add
*/
public void addEdge(String node, Edge e) {
ArrayList<Edge> list;
list = map.get(node);
list.add(e);
map.put(node,list);
}
/**
* Get set of nodes (all string labels) for this graph
@return Set of Strings (nodes) in this graph
*/
public Set<String> getNodes (){
return map.keySet();
}
/**
* Get set of nodes (all string labels) for this graph
@return Set of Strings (nodes) in this graph
*/
public ArrayList<Edge> getEdges (String n) {
return map.get(n);
}
/**
* @return String representation of this Graph, includes the current flow
*/
public String toString() {
String result = "G_" + this.flow + "\n";
Set<String> nodes = this.map.keySet();
for (String n : nodes) {
result += n + "=" + this.map.get(n) + "\n";
}
return result;
}
/**
* @return a residual graph corresponding to this Graph
*/
public ResGraph getResidual() {
ResGraph graphR = new ResGraph();
Set<String> nodes = this.getNodes();
for (String n : nodes)
graphR.addNode(n);
for (String n : nodes) {
ArrayList<Edge> edgeList = this.getEdges(n);
for (Edge e : edgeList) {
if (e.capacity == e.flow)
graphR.addEdge(e.dest, new EdgeB(e.dest, e.source,
e.capacity, e.capacity));
else if (e.flow == 0){
graphR.addEdge(n, new EdgeF(e.source, e.dest,
e.capacity, e.capacity));
}
else {
graphR.addEdge(n,
new EdgeF(e.source, e.dest, e.capacity,
e.capacity-e.flow));
graphR.addEdge(e.dest,
new EdgeB(e.dest, e.source, e.capacity, e.flow));
}
}
}
graphR.flow = this.flow;
return graphR;
}
/**
* @return augment(update) this graph with the new path
*/
public void augment(ArrayList<Edge> path) {
// if the path is empty, there is no update to this graph
if (path.size() <=0) return;
int b = bottleNeck(path);
System.out.println("b" + b);
for (Edge e: path) {
if (e == pickOut(path, e.dest)) {
System.out.println("TRUE");
this.flow += b;
} else {
this.flow -= b;
}
}
// update the flow of this graph with the bottleneck in the path
this.flow +=b;
}
/**
* @return pick out and return an edge from this adjacency
* list given the destination node
*/
private Edge pickOut(ArrayList<Edge> edgeList, String dest) {
for (Edge e : edgeList)
if (dest.equals(e.dest))
return e;
return null;
}
/**
* @return given a path (a listed of Edges), return
* the bottleneck
*/
private int bottleNeck(ArrayList<Edge> path) {
int n = path.size();
int minFlow = path.get(0).flow;
for (int i =1; i < n; i++) {
int flow = path.get(i).flow;
if (flow < minFlow)
minFlow = flow;
}
return minFlow;
}
}
// There is a residual graph for every graph
class ResGraph extends Graph{
/*
* @return String representation of this Graph, includes the current flow
*/
public String toString() {
String result = "G_" + this.flow + "^R\n";
Set<String> nodes = this.map.keySet();
for (String n : nodes) {
result += n + "=" + this.map.get(n) + "\n";
}
return result;
}
// FINISH ONE OF THE FOLLOWING METHODS, either DFS or BFS
/**
* @param source node for search
* @param target node for search
* @return a path from the source node to the target node
* which is a list of Edges
* returns an empty path[] if there is no path
* uses DFS
*/
public ArrayList <Edge> DFS(String source, String target) {
ArrayList<String> Stack = new ArrayList<String>();
Stack.add(source);
ArrayList<String> visited = new ArrayList<String>();
visited.add(source);
ArrayList<Edge> path = new ArrayList<Edge>();
while (!Stack.isEmpty() && !target.equals(Stack.get(Stack.size() - 1))) {
String current = Stack.get(Stack.size() - 1);
System.out.println("Current " + current);
ArrayList<Edge> listOfEdges = getEdges(current);
int index = 0;
boolean isGoodEdge = false;
while (!isGoodEdge && index < listOfEdges.size()) {
Edge currentEdge = listOfEdges.get(index);
System.out.println("current edge " + currentEdge);
if (Objects.equals(currentEdge.source, current) && !visited.contains(currentEdge.dest) && currentEdge.capacity > 0) {
isGoodEdge = true;
System.out.println("DEST " + currentEdge.dest);
Stack.add(currentEdge.dest);
visited.add(currentEdge.dest);
path.add(currentEdge);
}
index++;
}
if(!isGoodEdge){
Stack.remove(Stack.size()-1);
path.remove(path.size() - 1);
}
}
System.out.println(path);
// FINISH ME
return new ArrayList<Edge>(); // dummy return value of
// empty list which signals no path
}
public ArrayList<Edge> bfsHelper(ArrayList<String> strings) {
ArrayList<Edge> result = new ArrayList<>();
for (int i = strings.size() - 1; i >= 1; i--) {
ArrayList<Edge> edges = this.map.get(strings.get(i - 1));
for (Edge e : edges) {
if (Objects.equals(e.dest, strings.get(i))) {
System.out.println("HERE");
result.add(0, e);
System.out.println("RESULT " + result);
break;
}
}
}
return result;
}
/**
* @param source node for search
* @param target node for search
* @return a path from the source node to the target node
* which is a list of Edges
* returns an empty path[] if there is no path
* uses BFS
*/
public ArrayList <Edge> BFS(String source, String target) {
// ArrayList<Edge> path = new ArrayList<Edge>();
// Set<String> nodes = getNodes();
// boolean[] visited = new boolean[nodes.size()];
//
// for (int i = 0; i < nodes.size(); i++) {
// visited[i] = false;
// }
//
// LinkedList<String> queue = new LinkedList<String>();
// queue.add(source);
// path = getEdges(source);
//
//
// for (int i = 0; i < nodes.size(); i++) {
// if (nodes.toArray()[i] == source) {
// visited[i] = true;
// }
// }
//
// while (queue.size() != 0) {
// String u = queue.poll();
// for (int v = 0; v < nodes.size(); v++) {
// if (!visited[v]) {
// System.out.println(nodes.toArray()[v]);
// System.out.println(getEdges((String) nodes.toArray()[v]));
// queue.add((String) nodes.toArray()[v]);
// System.out.println(path);
// visited[v] = true;
// //path.add(getEdges((String) nodes.toArray()[v]));
// }
// }
// }
ArrayList<Edge> result = new ArrayList<>();
if (source.equals(target)) {
result = getEdges(source);
return result;
}
Queue<ArrayList<String>> queue = new LinkedList<>();
ArrayList<String> strings = new ArrayList<>();
strings.add(source);
queue.add(strings);
while (queue.size() != 0) {
System.out.println("queue " + queue);
ArrayList<String> path = queue.poll();
String current = path.get(path.size() - 1);
System.out.println(current);
if (Objects.equals(current, target)) {
return bfsHelper(path);
}
ArrayList<Edge> edges = this.map.get(current);
for (Edge e : edges) {
ArrayList<String> newPath = new ArrayList<>(path);
if (!path.contains((e.dest))) {
result.add(e);
System.out.println("RESULT " + result);
newPath.add(e.dest);
queue.add(newPath);
}
}
// for (Edge e : edges) {
//
// ArrayList<String> newPath = new ArrayList<>(path);
// if (!path.contains(e.dest)) {
// newPath.add(e.dest);
// queue.add(newPath);
// }
// }
// or FINISH ME
}
return new ArrayList<Edge>(); // dummy return value of
// empty list which signals no path
}
}
Edge.java
import java.util.*;
public class Edge {
public String source; // source node
public String dest; // destination node
public int capacity; // flow capacity c_e for this edge
public int flow; // the actual flow on this edge
/**
* Construct a Graph object
* @param source - a node
* @param dest - a destination node
* @param capacity - of this edge
* @param flow - current flow in this edge
* constructs a new edge from source to dest with the given
* capacity and flow
*/
public Edge (String source, String dest, int capacity, int flow){
this.source = source;
this.dest = dest;
this.capacity = capacity;
this.flow = flow;
}
/**
* @return a string representation of this edge as s->d (cap) flow
*/
public String toString() {
return this.source + "->"+ this.dest +
" (" + this.capacity +") " + this.flow;
}
}
// forward edge this should only be used in residual graphs
class EdgeF extends Edge {
public EdgeF (String source, String dest, int capacity, int flow){
super(source, dest, capacity, flow);
}
public String toString() {
return "E_F: "+ this.source + "->"+ this.dest + " " + this.flow;
}
}
// backward edge this should only be used in residual graphs
class EdgeB extends Edge {
public EdgeB (String source, String dest, int capacity, int flow){
super(source, dest, capacity, flow);
}
public String toString() {
return "E_B: "+ this.source + "->"+ this.dest + " " + this.flow;
}
}
FindFlow.java
import java.util.*;
import java.io.*; import java.util.logging.ErrorManager;
public class FindFlow {
public static void main (String [] args) throws FileNotFoundException {
Scanner sc = new Scanner(new File(args[0]));
// get the number of nodes in graph (first line of file)
int n = Integer.parseInt(sc.nextLine());
// construct new empty graph
Graph graph = new Graph();
// add nodes to this graph
String source = sc.nextLine();
graph.addNode(source);
for (int i = 1; i < n-1; i++) {
String node = sc.nextLine();
graph.addNode(node);
}
String dest = sc.nextLine();
graph.addNode(dest);
// add edges to this graph, each edge has source, dest, capacity
// and starts off with a flow of 0
while (sc.hasNextLine()) {
String [] tokens = sc.nextLine().split(" ");
String s = tokens[0]; //get edge source
String d = tokens[1]; // get edge dest
int capacity = Integer.parseInt(tokens[2]);
graph.addEdge(s, new Edge(s, d, capacity,0));
}
// right now the graph is G_0
ArrayList <Edge> path = new ArrayList<Edge>();
do {
// when printed, each graph prints its current flow
System.out.println(graph);
// get the residual graph
// the first residual graph will be G_0^R
ResGraph resGraph = graph.getResidual();
// when printed, each graph prints what graph it is the
// residual for
System.out.println(resGraph);
// find a path in the residual graph, use either DFS or BFS
// comment out the one you do not want
// path = resGraph.BFS(source,dest);
path = resGraph.DFS(source, dest);
//print the path
System.out.println("path = " + path + "\n");
// update (that is augment) the graph with the new path
// if the new path is empty, no augmentation happens
graph.augment(path);
//throw new Error();
//throw new Error();
} while (path.size() > 0);
}
}
Example Input
4
s
u
v
t
s u 20
s v 10
u t 10
u v 30
v t 20