我正在尝试使用具有无限权重边但每个节点都有容量的图来解决最大流量问题。我使用福特富尔克森算法解决了这个问题，并将每个节点分成一个输入节点和一个输出节点，容量是两者之间的加权边。当我在边缘硬编码时，我的算法效果很好（请参阅代码中的注释块），但当我尝试从文本文件构建边缘时总是返回零。对于我的生活，我无法弄清楚为什么，我已经检查以确保所有边缘都被正确构建，并且无法弄清楚出了什么问题。
用于读取图形的文本文件（第 1 行是边，第 2 行是节点容量） (1 2) (2 3) (2 5) (3 4) (4 5) (3 5) (2 1500) (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;
}
}