0
我试图解决最大流量问题，图中有无限的加权边，但每个节点都有一个容量。我使用ford fulkerson算法解决了这个问题，并将每个节点分成一个in节点和out节点，容量是两者之间的加权边。当我在边缘进行硬编码时（请参阅代码中的注释块），我的算法效果很好，但是当我尝试从文本文件构建边缘时总是返回零。对于我的生活，我无法弄清楚为什么，我已经检查过，以确保所有的边缘都正确构造，并且不知道什么是错的。 （1 5）（3 5）（3 5） （2 1500）（2 3） ）（3 1000）（4 800）Java MaxFlow算法，产生边缘故障
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;
}
}