0
무제한의 가중치를 갖는 그래프로 최대 흐름 문제를 해결하려고하지만 각 노드에는 용량이 있습니다. 난 ford fulkerson 알고리즘을 사용하여 문제를 해결하고 각각의 노드를 in 노드와 out 노드로 나누었습니다.이 노드의 용량은 두 노드 사이의 가중치가됩니다. 내 알고리즘은 내가 하드 코드를 가장자리 (코드에서 주석 처리 된 부분 참조)에서 훌륭하게 작동하지만 텍스트 파일에서 가장자리를 만들 때 항상 0을 반환합니다. 내 인생에서 나는 왜 그 이유를 알아낼 수 없으며, 모든 경계가 올바르게 구성되었는지 확인하고 무엇이 잘못 되었는 지 파악할 수 없습니다. 그래프를 판독Java MaxFlow 알고리즘, 가장자리 생성 문제
텍스트 파일 (1 2) (2 3) (2-5) (3 4) (4 5) (3-5) (2 1,500 (첫번째 라인 에지이고, 둘째는 노드의 용량)) (3 천) (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;
}
}