Как получить максимальный поток для каждой возможной пары «источник / сток», используя Edmonds Karp от JUNG? - PullRequest
Новая
       34

Как получить максимальный поток для каждой возможной пары «источник / сток», используя Edmonds Karp от JUNG?

0 голосов
/ 20 апреля 2020

У меня есть некоторый простой код Java / JUNG, который создает ориентированный граф, добавляет некоторые ребра с весами и значениями емкости и выполняет анализ максимального потока от узла-источника к узлу-приемнику.

Если у вас есть: A --- (емкость 2) -----> B ---- (емкость 5) ----> C и вы хотите найти максимальный поток от A- > C, это будет 2. 

import edu.uci.ics.jung.algorithms.flows.EdmondsKarpMaxFlow;
import edu.uci.ics.jung.graph.DirectedSparseMultigraph;
import edu.uci.ics.jung.graph.util.EdgeType;
import org.apache.commons.collections15.Factory;
import org.apache.commons.collections15.Transformer;

import java.util.HashMap;
import java.util.Map;

public class stack {
    static int edgeCount = 0;

    static class MyNode {
        int id;
        public MyNode(int id) {
            this.id = id;
        }
        public String toString() {
            return "V"+id;
        }
    }

    static class MyLink {

        double capacity;
        double weight;
        int id;

        public MyLink(double weight, double capacity) {
            this.id = edgeCount++;
            this.weight = weight;
            this.capacity = capacity;
        }
        public String toString() {
            return "E"+id;
        }

    }
    public static void main(String[] args){
        DirectedSparseMultigraph<MyNode, MyLink> g = new DirectedSparseMultigraph<MyNode, MyLink>();

        Transformer<MyLink, Double> capTransformer = new Transformer<MyLink, Double>(){
            public Double transform(MyLink link) {
                return link.capacity;
            }
        };

        Map<MyLink, Double> edgeFlowMap = new HashMap<MyLink, Double>();
        // This Factory produces new edges for use by the algorithm
        Factory<MyLink> edgeFactory = new Factory<MyLink>() {
            public MyLink create() {
                return new MyLink(1.0, 1.0);
            }
        };

        // Create some MyNode objects to use as vertices
        MyNode n1 = new MyNode(1);
        MyNode n2 = new MyNode(2);
        MyNode n3 = new MyNode(3);
        MyNode n4 = new MyNode(4);
        MyNode n5 = new MyNode(5);
        MyNode n6 = new MyNode(6);
        MyNode n7 = new MyNode(7);
        // Add some directed edges along with the vertices to the graph
        g.addEdge(new MyLink(2.0, 48),n1, n2, EdgeType.DIRECTED);
        g.addEdge(new MyLink(2.0, 58),n2, n3, EdgeType.DIRECTED);
        g.addEdge(new MyLink(3.0, 192), n3, n5, EdgeType.DIRECTED);
        g.addEdge(new MyLink(2.0, 48), n5, n4, EdgeType.DIRECTED);
        g.addEdge(new MyLink(2.0, 20), n6, n1, EdgeType.DIRECTED);
        g.addEdge(new MyLink(8, 24), n7, n4, EdgeType.DIRECTED);

        System.out.println("RUNNING EDMONDS KARP MAX FLOW FOR SOURCE " + n1.toString() + " TO SINK " + n2.toString());
        EdmondsKarpMaxFlow<MyNode, MyLink> edk = new EdmondsKarpMaxFlow(g, n1, n2, capTransformer, edgeFlowMap, edgeFactory);
        edk.evaluate();
        System.out.println("The max flow is: " + edk.getMaxFlow());
    }
}

Выполнение этого приведет к выводу:

РАБОТА С ЭДМОНДСОМ МАКСИМАЛЬНЫМ ПОТОКОМ KARP ДЛЯ ИСТОЧНИКА V1 НА МОЙК V2 Максимальный поток: 48

Как написать алгоритм, чтобы он работал на каждой возможной паре источника и приемника, чтобы я мог видеть максимальный поток всех путей в графе? Абсолютно новый для этого материала, так что все помогает!

1 Ответ

1 голос
/ 25 апреля 2020

Просто запустите алгоритм для каждой пары узлов. Не существует известного алгоритма, который более эффективен для ориентированных графов: Максимальный поток для всех пар

...