I am implementing a program to solve a matching problem by using the reduction from a matching problem to a maximum flow problem, which I am determined to solve using Edmond-Karp's algorithm.
I have looked through and taken impressions from different pseudo codes that are telling how to carry out the procedure to solve a maximum flow problem using the Edmond-Karp's algorithm and by mixing these impressions, I have produced an implementation that works for many small basic graphs. But by some reason, the implementation gives wrong answers for bigger graphs such as 50 nodes with 100 edges or even bigger than such graphs. So giving a input-output scenario example wouldn't help that much with highlighting the whole problem (if you insist although, I can post such a input-output scenario as you wish). When I say "wrong answers", the implementation does not actually give the maximal matching (or maximal flow value) given a graph to solve.
Down below you can have all the relevant classes that are being used in my implementation, that is in the MaxFlowSolver class (the method solveFlowProblem(...) is the method that uses the whole Edmond-Karp's algorithm):
MaxFlowSolver
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
public class MaxFlowSolver {
private Graph flowProblemSolution;
private int flowValue;
public MaxFlowSolver(Graph toBeSolved, int source, int sink) {
flowProblemSolution = solveFlowProblem(toBeSolved, source, sink);
}
private Graph solveFlowProblem(Graph toSolve, int source, int sink) {
Graph rGraph = toSolve;
Edge[] path;
while((path=BFS(rGraph, source, sink))!=null) {
int r = Integer.MAX_VALUE;
for(Edge e = path[sink]; e!=null; e = path[e.getStartVertex()])
r = Math.min(r, e.getCapacity()-e.getFlow());
for(Edge e = path[sink]; e!=null; e = path[e.getStartVertex()]) {
e.changeFlow(e.getFlow()+r);
Edge erev;
if((erev=getReversedEdge(e, rGraph))==null) {
erev = new Edge(e.getEndVertex(), e.getStartVertex(), 0);
rGraph.addEdge(erev);
}
erev.changeFlow(-e.getFlow());
e.changeResCap(e.getCapacity()-e.getFlow());
erev.changeResCap(erev.getCapacity()-erev.getFlow());
}
flowValue += r;
}
return rGraph;
}
private Edge getReversedEdge(Edge e, Graph graph) {
LinkedList<Edge> neighbours = graph.getEdges().get(e.getEndVertex());
if(neighbours==null)
return null;
for(Edge i : neighbours)
if(i.getEndVertex()==e.getStartVertex())
return i;
return null;
}
private Edge[] BFS(Graph resGraph, Integer source, Integer sink) {
Queue<Integer> q = new LinkedList<>();
q.add(source);
Edge[] pred = new Edge[resGraph.numVertices()+1];
while(!q.isEmpty()) {
Integer curr = q.poll();
LinkedList<Edge> neighbours1 = resGraph.getEdges().get(curr);
if(neighbours1!=null)
for(Edge someEdge : neighbours1) {
if(pred[someEdge.getEndVertex()]==null && someEdge.getEndVertex()!=source &&
someEdge.getCapacity()>someEdge.getFlow()) {
pred[someEdge.getEndVertex()] = someEdge;
q.add(someEdge.getEndVertex());
}
}
if(curr==sink) return pred;
}
return null;
}
public Graph getSolution() {
return flowProblemSolution;
}
public ArrayList<Edge> retrievePositiveEdges(Graph arg0, int source, int sink) {
ArrayList<Edge> res = new ArrayList<>();
Set<Integer> goThroughInts = flowProblemSolution.getEdges().keySet();
for(Integer i : goThroughInts)
for(Edge j : flowProblemSolution.getEdges().get(i)) {
int start = j.getStartVertex();
int end = j.getEndVertex();
if(!res.contains(j) && j.getFlow()>0 &&
start!=source && start!=sink && end!=source && end!=sink &&
arg0.getEdges().get(i).contains(j))
res.add(j);
}
return res;
}
public int getFlowValue() {
return flowValue;
}
}
Graph
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.HashMap;
public class Graph {
private HashMap<Integer, LinkedList<Edge>> edges;
private int firstVertices;
private int secondVertices;
private int size;
public Graph(int x, int y) {
firstVertices = x;
secondVertices = y;
edges = new HashMap<>();
size = 0;
}
public Graph(int size) {
firstVertices = size;
secondVertices = 0;
edges = new HashMap<>();
}
public boolean addEdge(int x, int y, boolean regularV) {
if(!(0<=x && x<=firstVertices && firstVertices<y && y<=firstVertices+secondVertices) && regularV) {
System.err.println("The graph is no longer bipartite. The execution is aborted.");
System.exit(1);
}
if(!edges.containsKey(x))
edges.put(Integer.valueOf(x), new LinkedList<Edge>());
Edge temp = new Edge(x,y);
if(!edges.get(x).add(temp))
return false;
size++;
return true;
}
public boolean addEdge(Edge newEdge) {
if(!edges.containsKey(newEdge.getStartVertex()))
edges.put(Integer.valueOf(newEdge.getStartVertex()), new LinkedList<Edge>());
if(!edges.get(newEdge.getStartVertex()).add(newEdge))
return false;
size++;
return true;
}
public void changeNumOfXs(int newVal) {
firstVertices = newVal;
}
public void changeNumOfYs(int newVal) {
secondVertices = newVal;
}
public int getNumOfXs() {
return firstVertices;
}
public int getNumOfYs() {
return secondVertices;
}
public int numOfEdges() {
return size;
}
public HashMap<Integer, LinkedList<Edge>> getEdges() {
return edges;
}
public void printGraph(Kattio io) {
printGraph(io, size-1, size);
}
public void printGraph(Kattio io, int source, int sink) {
io.println(firstVertices+secondVertices);
io.println(source + " " + sink);
io.println(size);
ArrayList<Edge> printed = new ArrayList<>();
for(LinkedList<Edge> i : edges.values())
for(Edge j : i)
if(!printed.contains(j)) {
printed.add(j);
io.println(j.getStartVertex() + " " + j.getEndVertex() + " " + j.getCapacity());
}
io.flush();
}
public int numVertices() {
return firstVertices+secondVertices;
}
public int numEdges() {
return size;
}
}
Edge
public class Edge {
private final int startVertex;
private final int endVertex;
private int flow;
private int rCapacity;
private final int capacity;
public Edge(int start, int end) {
startVertex = start;
endVertex = end;
flow = 0;
rCapacity = 1;
capacity = 1;
}
public Edge(int start, int end, int cap) {
startVertex = start;
endVertex = end;
flow = 0;
rCapacity = cap;
capacity = cap;
}
public void changeFlow(int newFlowVal) {
flow = newFlowVal;
}
public void changeResCap(int newResCapVal) {
rCapacity = newResCapVal;
}
public int getStartVertex() {
return startVertex;
}
public int getEndVertex() {
return endVertex;
}
public int getFlow() {
return flow;
}
public int getCapacity() {
return capacity;
}
public int getResCapacity() {
return rCapacity;
}
}
I have mainly followed the Wikipedia's description of the Edmond-Karp's algorith using adjacency nodes, but also a little from other sources but not that much. The link to the algorithm on wikipedia is down below:
https://en.wikipedia.org/wiki/Edmonds–Karp_algorithm#Pseudocode
Is there somewhere in my implementation where I have interpreted the pseudo code on the wikipedia wrong or is it something more specifically with my Java codes? I have been working with this program almost all the day without figuring out what causes the problem that the program for certain graphs does not output the maximal matching (or maximum flow) for some graph.
All help I can get from you will be highly appreciated.
Thank you all in advance!
