I'm implementing the Ford-Fulkerson algorithm but i have some problem in updating the graph after augmenting phase. My data structure doesn't make this easy i guess.
To represent the graph i use this:
private Map<Vertex, ArrayList<Edge>> outgoingEdges;
That is, i associate at each Vertex its list of outgoing edges.
To manage the backward edges, i associated a "opposite" edge for each edge in the graph.
Any kind of suggestion is appreciated.
public class FF {
/**
* Associates each Vertex with his list of outgoing edges
*/
private Map<Vertex, ArrayList<Edge>> outgoingEdges;
public FF() {
outgoingEdges = new HashMap<Vertex, ArrayList<Edge>>();
}
/**
* Returns the nodes of the graph
*/
public Collection<Vertex> getNodes() {
return outgoingEdges.keySet();
}
/**
* Returns the outgoing edges of a node
*/
public Collection<Edge> getIncidentEdges(Vertex v) {
return outgoingEdges.get(v);
}
/**
* Adds a new edge to the graph
*/
public void insertEdge(Vertex source, Vertex destination, float capacity) throws Exception {
if (!(outgoingEdges.containsKey(source) && outgoingEdges.containsKey(destination)))
throw new Exception("Unable to add the edge");
Edge e = new Edge(source, destination, capacity);
Edge opposite = new Edge(destination, source, capacity);
outgoingEdges.get(source).add(e);
outgoingEdges.get(destination).add(opposite);
e.setOpposite(opposite);
opposite.setOpposite(e);
}
/**
* Adds a new node to the graph
*/
public void insertNode(Vertex v) {
if (!outgoingEdges.containsKey(v))
outgoingEdges.put(v, new ArrayList<Edge>());
}
/**
* Ford-Fulkerson algorithm
*
* @return max flow
*/
public int fordFulkerson(Vertex source, Vertex destination) {
List<Edge> path = new ArrayList<Edge>();
int maxFlow = 0;
while(bfs(source, destination, path)) {
// finds the bottleneck
float minCap = bottleneck(path);
// updates the maxFlow
maxFlow += minCap;
// updates the graph <-- this updates only the local list path, not the graph!
for(Edge e : path) {
try {
e.addFlow(minCap);
e.getOpposite().addFlow(-minCap);
} catch (Exception e1) {
e1.printStackTrace();
}
}
path.clear();
}
return maxFlow;
}
/**
* @param Path of which we have to find the bottleneck
* @return bottleneck of the path
*/
private float bottleneck(List<Edge> path) {
float min = Integer.MAX_VALUE;
for(Edge e : path) {
float capacity = e.getCapacity();
if(capacity <= min) {
min = capacity;
}
}
return min;
}
/**
* BFS to obtain a path from the source to the destination
*
* @param source
* @param destination
* @param path
* @return
*/
private boolean bfs(Vertex source, Vertex destination, List<Edge> path) {
Queue<Vertex> queue = new LinkedList<Vertex>();
List<Vertex> visited = new ArrayList<Vertex>(); // list of visited vertexes
queue.add(source);
//source.setVisited(true);
visited.add(source);
while(!queue.isEmpty()) {
Vertex d = queue.remove();
if(!d.equals(destination)) {
ArrayList<Edge> d_outgoingEdges = outgoingEdges.get(d);
for(Edge e : d_outgoingEdges) {
if(e.getCapacity() - e.getFlow() > 0) { // there is still available flow
Vertex u = e.getDestination();
if(!visited.contains(u)) {
//u.setVisited(true);
visited.add(u);
queue.add(u);
path.add(e);
}
}
}
}
}
if(visited.contains(destination)) {
return true;
}
return false;
}
}
Edge
public class Edge {
private Vertex source;
private Vertex destination;
private float flow;
private final float capacity;
private Edge opposite;
public Edge(Vertex source, Vertex destination, float capacity) {
this.source = source;
this.destination = destination;
this.capacity = capacity;
}
public Edge getOpposite() {
return opposite;
}
public void setOpposite(Edge e) {
opposite = e;
}
public void setSource(Vertex v) {
source = v;
}
public void setDestination(Vertex v) {
destination = v;
}
public void addFlow(float f) throws Exception {
if(flow == capacity) {
throw new Exception("Unable to add flow");
}
flow += f;
}
public Vertex getSource() {
return source;
}
public Vertex getDestination() {
return destination;
}
public float getFlow() {
return flow;
}
public float getCapacity() {
return capacity;
}
public boolean equals(Object o) {
Edge e = (Edge)o;
return e.getSource().equals(this.getSource()) && e.getDestination().equals(this.getDestination());
}
}
Vertex
public class Vertex {
private String label;
public Vertex(String label) {
this.label = label;
}
public boolean isVisited() {
return visited;
}
public String getLabel() {
return label;
}
public boolean equals(Object o) {
Vertex v = (Vertex)o;
return v.getLabel().equals(this.getLabel());
}
}
Although, strictly speaking, the question could be considered as being "Off topic" (since you're mainly looking for debugging help), this is one of your first questions, so some general hints:
When you post a question here, consider that people here a volunteers. Make it easy for them to answer the question. In this particular case: You should create a MCVE, so that people can quickly copy & paste your code (preferably, in a single code block) and run the program without any effort. For example, you should include a test class, inculding a
mainmethod, like this one:(You should already have created such a test class when you write the question, anyhow!)
You should make clear that you are NOT using StackOverflow as a "magic problem solving machine". In this case: I already mentioned that you should include debug outputs. If you had extended your
FFclass with methods like these....which can be called in the main loop like this:
then you would already have noticed the main problem with your code: ...
The
bfsmethod is wrong! You are not properly reconstructing the path that led you to the destination vertex. Instead, you are adding every visited vertex to the path. You have to track which edge was used for reaching a particular node, and when you reached the destination vertex, have to go backward.A quick-and-dirty approach could roughly(!) look like this:
(You should always test such a central method independently. You could have easily created a small test program that computes several paths, and you would quickly have noticed that these paths are wrong - and thus, that the Ford Fulkerson can't work properly at all).
Further remarks:
Whenever you override the
equalsmethod, you must also override thehashCodemethod. Some rules apply here, you should definitely refer to the documentation ofObject#equalsandObject#hashCode.It is often beneficial to additionally override the
toStringmethod, so that you may easily print the objects to the console.In your case, these methods could be implemented like this, for
VertexAnd for
EdgeThe capacities of the edges are
floatvalues, so the resulting flow should also be afloatvalue.With the modifications mentioned above, the program runs and prints a "plausible" result. I have NOT verified it for correctness. But this is your task, and it should be much easier now.
P.S: No, io sono tedesco.