0
私は無制限のウェイトエッジを持つグラフで最大フローの問題を解決しようとしていますが、各ノードには容量があります。私はこの問題をford fulkersonアルゴリズムを使って解決し、各ノードをinノードとoutノードに分割しました。その容量は2つの間の重み付きエッジです。私のアルゴリズムは、私はハードコードのエッジで（コード内のブロックを参照してください）が、テキストファイルからエッジを構築しようとすると常にゼロを返します。私の人生のために、私はなぜ、私はすべてのエッジが正しく構築されていることを確認するためにチェックし、ちょうど何が間違っているか把握することができません。Java MaxFlowアルゴリズム、エッジを生成するトラブル
グラフを読み取るためのテキストファイル（1行目はエッジ、2番目はノードの容量） （1 2）（2 3）（2 5）（3 4）（4 5）（3 5） ）（3 1000）（4 800）
import java.util.*;
import java.io.*;
public class Main {
//Add Node to Graph
public static void make_node(Map<String, List<Edge>> graph, String node_v) {
List<Edge> empty = new ArrayList<>();
if(!graph.containsKey(node_v)) {
graph.put(node_v, empty);
}
}
//Create Edge
public static void make_edge(Map<String, List<Edge>> graph, Map<Edge, Integer> flow_graph, String node_u, String node_v, int weight) {
Edge edge = new Edge(node_u, node_v, weight);
Edge residual_flow = new Edge(node_v, node_u, 0);
edge.setRisedge(residual_flow);
residual_flow.setRisedge(edge);
if (graph.containsKey(node_u)) {
List<Edge> edge_list = graph.get(node_u);
edge_list.add(edge);
graph.put(node_u, edge_list);
}
if (graph.containsKey(node_v)) {
List<Edge> edge_list = graph.get(node_v);
edge_list.add(residual_flow);
graph.put(node_v, edge_list);
}
flow_graph.put(edge, 0);
flow_graph.put(residual_flow, 0);
}
//Find valid path to Sink
public static List<Edge> get_path(Map<String, List<Edge>> graph, Map<Edge, Integer> flow_graph, String source, String sink, List<Edge> path) {
if (source == sink)
return path;
int residual;
List<Edge> result;
for (Edge edge : graph.get(source)) {
residual = edge.getCapacity() - flow_graph.get(edge);
if (residual > 0 && !path.contains(edge) && !path.contains(edge.getRisedge())) {
path.add(edge);
result = get_path(graph, flow_graph, edge.getSink(), sink, path);
if (result != null) {
return result;
}
}
}
return null;
}
//Find Max Flow
public static int find_max_flow(Map<String, List<Edge>> graph, Map<Edge, Integer> flow_graph, String source, String sink) {
List<Edge> path = new ArrayList<>();
path = get_path(graph, flow_graph, source, sink, path);
List<Integer> residuals = new ArrayList<>();
int min_path_flow;
while (path != null) {
for (Edge edge : path) {
residuals.add(edge.getCapacity() - flow_graph.get(edge));
}
min_path_flow = Collections.min(residuals);
for (Edge edge : path) {
flow_graph.put(edge, flow_graph.get(edge) + min_path_flow);
flow_graph.put(edge.getRisedge(), flow_graph.get(edge.getRisedge()) - min_path_flow);
}
List<Edge> empty = new ArrayList<>();
path = get_path(graph, flow_graph, source, sink, empty);
}
int max_flow = 0;
for (Edge edge : graph.get(source)) {
max_flow += flow_graph.get(edge);
}
return max_flow;
}
public static void main(String[] args) throws IOException {
Map<String, List<Edge>> graph = new HashMap<>();
Map<Edge, Integer> flow_graph = new HashMap<>();
Map<String, Integer> capacity_dict = new HashMap<>();
List<String> in_out_nodes = new ArrayList<>();
//Get file name
Scanner scan = new Scanner(System.in);
System.out.println("Enter file name:");
String filename = scan.nextLine();
File file = new File(filename);
BufferedReader reader = new BufferedReader(new FileReader(file));
String graph_text = reader.readLine();
String capacity_text = reader.readLine();
//Parse Capacity
capacity_text = capacity_text.replace(")", "");
capacity_text = capacity_text.replace("(", "");
String[] split_capacity = capacity_text.split("\\s");
//Parse Graph
graph_text = graph_text.replace(")", "");
graph_text = graph_text.replace("(", "");
String[] split_graph = graph_text.split("\\s");
//Parse Capacity
for (int i = 0; i < split_capacity.length; i++){
if(!capacity_dict.containsKey(split_capacity[i])){
capacity_dict.put(split_capacity[i],Integer.valueOf(split_capacity[i+1]));
in_out_nodes.add(split_capacity[i]);
i = i+1;
}
}
//Make nodes
for (String s : split_graph){
make_node(graph, s + "out");
make_node(graph, s + "in");
}
//Make edges
for (int i = 0; i < split_graph.length; i ++){
String u = split_graph[i] + "out";
String ui = split_graph[i] + "in";
String v = split_graph[i + 1] + "in";
if(in_out_nodes.contains(split_graph[i])){
in_out_nodes.remove(split_graph[i]);
make_edge(graph,flow_graph,u,ui, capacity_dict.get(split_graph[i]));
}
if(capacity_dict.containsKey(split_graph[i])){
make_edge(graph,flow_graph,u,v, capacity_dict.get(split_graph[i]));
}else{
make_edge(graph,flow_graph,u,v, capacity_dict.get(split_graph[i + 1]));
}
i += 1;
}
//Code works when i comment out my generated edges and use these
//make_edge(graph,flow_graph, "1out","2in",1500);
//make_edge(graph,flow_graph, "2out","3in",1500);
//make_edge(graph,flow_graph, "2out","5in",1500);
//make_edge(graph,flow_graph, "3out","4in",1000);
//make_edge(graph,flow_graph, "4out","5in",800);
//make_edge(graph,flow_graph, "3out","5in",1000);
//make_edge(graph,flow_graph, "2in","2out",1500);
//make_edge(graph,flow_graph, "3in","3out",1000);
//make_edge(graph,flow_graph, "4in","4out",800);
System.out.print(find_max_flow(graph, flow_graph, "1out", "5in"));
}
}
エッジクラスまあ
public class Edge {
public Edge(String source, String sink, int capacity) {
this.source = source;
this.sink = sink;
this.capacity = capacity;
}
private String source;
private String sink;
private int capacity;
private Edge risedge;
public String getSource() {
return source;
}
public void setSource(String source) {
this.source = source;
}
public String getSink() {
return sink;
}
public void setSink(String sink) {
this.sink = sink;
}
public int getCapacity() {
return capacity;
}
public void setCapacity(int capacity) {
this.capacity = capacity;
}
public Edge getRisedge() {
return risedge;
}
public void setRisedge(Edge risedge) {
this.risedge = risedge;
}
}