Edmond-Karp のアルゴリズムを使用して解決することを決定した、マッチング問題から最大フロー問題への縮約を使用して、マッチング問題を解くプログラムを実装しています。
Edmond-Karp のアルゴリズムを使用して最大フロー問題を解決する手順を実行する方法を示すさまざまな疑似コードを調べて印象を取りました。これらの印象を組み合わせることで、多くの小さな基本グラフで機能する実装を作成しました。 . しかし、何らかの理由で、100 個のエッジを持つ 50 個のノード、またはそのようなグラフよりも大きなグラフなど、より大きなグラフに対して実装が間違った答えを返します。そのため、入出力シナリオの例を示しても、問題全体を強調するのにはあまり役立ちません (ただし、必要に応じて、そのような入出力シナリオを投稿できます)。私が「間違った答え」と言うとき、実装は実際には、解決するグラフが与えられたときに最大の一致 (または最大のフロー値) を与えません。
以下に、私の実装で使用されているすべての関連クラス、つまり MaxFlowSolver クラスがあります (メソッド solveFlowProblem(...) は、Edmond-Karp のアルゴリズム全体を使用するメソッドです)。
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;
}
}
グラフ
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;
}
}
角
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;
}
}
私は主に、隣接ノードを使用した Edmond-Karp のアルゴリズムに関するウィキペディアの説明に従いましたが、他の情報源からも少しは参考にしましたが、それほど多くはありませんでした。ウィキペディアのアルゴリズムへのリンクは以下のとおりです。
https://en.wikipedia.org/wiki/Edmonds –Karp_algorithm#Pseudocode
ウィキペディアの疑似コードを間違って解釈した実装のどこかにありますか、それとも私のJavaコードでより具体的なものですか? 特定のグラフのプログラムが特定のグラフの最大一致 (または最大フロー) を出力しないという問題の原因を突き止めることなく、ほぼ一日中このプログラムを使用してきました。
私があなたから得ることができるすべての助けは非常に高く評価されます.
よろしくお願いします！