Алгоритм Java MaxFlow, края, генерирующие проблемы

Question

Алгоритм Java MaxFlow, края, генерирующие проблемы

Я пытаюсь решить проблему максимального потока с графом, имеющим неограниченные весовые ребра, но у каждого узла есть емкость. Я решил проблему с помощью алгоритма Форда Фулкерсона и разделил каждый узел на входной и выходной узлы с емкостью, являющейся взвешенным фронтом между ними. Мой алгоритм прекрасно работает, когда я жестко кодирую по краям (см. Закомментированный блок в коде), но всегда возвращает ноль, когда я пытаюсь построить ребра из текстового файла. Что касается жизни, я не могу понять, почему, я проверил, чтобы убедиться, что все ребра строятся правильно, и просто не могу понять, что не так.

Текстовый файл для чтения графика (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"));
}
}

Edge Class

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;
}

}

0

java graph max-flow

Источник

user6275576 23 фев '17 в 23:11

1 ответ

Другие вопросы по тегам java graph max-flow

user3217378 24 фев '17 в 02:30 2017-02-24 02:30 · Answer 1 · 2017-02-24 02:30

Ну, если честно, твой код беспорядок. Я не могу сказать, какова ваша точка неудачи. Так как ваша программа работает для жестко закодированных ребер, с вашим графиком что-то не так. И действительно, я создал несколько выходных данных для сравнения обоих графиков.

Ваши жестко закодированные графики выглядят следующим образом. Край представлен

name_of_source -> name_of_sink (capacity)

1in: []
2in: [2in -> 1out (0), 2in -> 2out (0)]
3in: [3in -> 2out (0), 3in -> 3out (0)]
4in: [4in -> 3out (0), 4in -> 4out (0)]
5in: [5in -> 2out (0), 5in -> 4out (0), 5in -> 3out (0)]
1out: [1out -> 2in (1500)]
2out: [2out -> 2in (1500), 2out -> 3in (1500), 2out -> 5in (1500)]
3out: [3out -> 3in (1000), 3out -> 4in (1000), 3out -> 5in (1000)]
4out: [4out -> 4in (800), 4out -> 5in (800)]
5out: []

Но когда вы строите тот же график без жесткого кодирования, вы получаете:

1in: []
2in: [2in -> 1out (0), 2in -> 2out (1500)]
3in: [3in -> 2out (0), 3in -> 3out (1000)]
4in: [4in -> 3out (0), 4in -> 4out (800)]
5in: [5in -> 2out (0), 5in -> 4out (0), 5in -> 3out (0)]
1out: [1out -> 2in (1500)]
2out: [2out -> 3in (1500), 2out -> 5in (1500), 2out -> 2in (0)]
3out: [3out -> 4in (1000), 3out -> 5in (1000), 3out -> 3in (0)]
4out: [4out -> 5in (800), 4out -> 4in (0)]
5out: []

Чтобы определить строковое представление любого класса, вы должны переопределить метод toString() из Object. Я добавил следующий метод в ваш класс Edge для получения этого вывода.

@Override
public String toString(){
    return source + " -> " + sink + " (" + capacity + ")";
}

И следующий код производит вывод вашей графовой переменной:

for ( String k : graph.keySet() )
    System.out.println( k + ": " + graph.get(k));

Я уверен, что этого достаточно, чтобы помочь вам решить проблему.