Maximaler Fluss (maxflow) eines Netzwerkes in Java

Dieser Beitrag ist Teil 1 von 2 in der Serie Avaloqix Programmierwettbewerb

    MaxFlowUm im Avaloqix Wettbewerb einen einigermassen sinnvollen Agenten zustande zu kriegen, braucht es sehr wahrscheinlich eine Funktion, die den maximalen Fluss eines gegebenen Netzwerkes berechnet. Dafür gibt es eine Vielzahl von Algorithmen mit verschiedenen Aufwänden und in verschiedenen Komplexitätsstufen.

    Der erste, älteste und einfachste Algorithmus ist wohl derjenige von Ford und Fulkerson. Er ist aber relativ aufwändig in der Berechnung (O(#Kanten*#Knoten*Grösste-Kapazität)), da der maximale Fluss in den Aufwand hineinspielt. Etwas besser ist der Algorithmus von Tarjan und Goldberg. Er wird von der Uni Karlsruhe anschaulich erklärt und bei Google Code findet man auch eine Implementation davon.

    Für Graphen mit kleiner Kantendichte ist allerdings der Edmonds-Karp-Algorithmus schneller (laut Wikipedia).

    Wenn man die von der Avaloqix-Oberfläche unter Wettbewerbsbedingungen erzeugten Graphen anschaut, ergibt sich folgendes Bild:

    • Bei 20 Knoten werden 40-50 Kanten generiert, das ergibt eine Dichte von ungefähr 0,263
    • Bei 60 Knoten werden 160 Kanten generiert, das ergibt eine Dichte von ungefähr 0,090

    Das darf wohl mit Fug und Recht als undicht, ääh, geringe Dichte bezeichnet werden, also machen wir uns doch an Edmonds Karp!

    Implementation

    Bei der Implementation habe ich mich sehr nahe an die Beispielimplementation von Wikipedia gehalten. Die einzelnen Teile sind etwas aufgeräumter und kommentierter:

    /**
     * Edmonds-Karp algorithm with O(V³E) complexity
     *
     * This implementation is a slightliy modified source from Wikipedia. See
     * http://en.wikipedia.org/wiki/Edmonds_karp
     */

    class MaxFlow {

        public static final int UNVISITED = 0, VISITED = 1;

        private int[][] res_capacity; // Residual capacity
        private int[] parent; // Parent node in Breadth First Search (BFS)
        private int[] mark; // BFS: Already visited?
        private int[] min_capacity; // Minimal flow
        private int size; // Number of nodes
        private int sink;

        public MaxFlow() {
        }

        public int getMaxflow(int[][] graphMatrix, int source, int sink) {
            this.sink = sink;
            this.size = graphMatrix.length;

            int max_flow = 0; // THE max flow for which we are doing this
            // circus

            int[][] flow = new int[size][size]; // Our flow
            res_capacity = new int[size][size]; // Remaining capacity

            parent = new int[size];
            min_capacity = new int[size];
            mark = new int[size];

            // Before we start, all capacities are residual
            // System.arraycopy may be faster: see http://www.javaspecialists.eu/archive/Issue124.html
           
            // The following is wrong, as Feri in the comments has found out.
            // clone() is one-dimensional! *pats-head*
            // res_capacity=graphMatrix.clone();
            //
            //Faster:
            for (int i = 0; i < size; i++) {
                System.arraycopy(graphMatrix[i], 0, res_capacity[i], 0, size);
            }

            // Search in BFS manner through the graph, Path by Path
            while (BFS(source)) {
                max_flow += min_capacity[sink];
                int v = sink, u;
                while (v != source) {
                    u = parent[v];
                    flow[u][v] += min_capacity[sink];
                    flow[v][u] -= min_capacity[sink];
                    res_capacity[u][v] -= min_capacity[sink];
                    res_capacity[v][u] += min_capacity[sink];
                    v = u;
                }
            }
            return max_flow;
        }

        /**
         * Breadth First Search in O(V²)
         *
         * @param source
         *            The source node
         */

        private boolean BFS(int source) {
            int first, last; // Queue pointers
            int[] queue; // Queue pointers

            queue = new int[size];
            for (int i = 0; i < size; i++) {
                mark[i] = UNVISITED;
                min_capacity[i] = Integer.MAX_VALUE;
            }

            first = last = 0;
            queue[last++] = source;
            mark[source] = VISITED;

            while (first != last) { // While "queue" not empty.
                int v = queue[first++];
                for (int u = 0; u < size; u++)
                    if (mark[u] == UNVISITED && res_capacity[v][u] > 0) {
                        min_capacity[u] = Math.min(min_capacity[v],
                                res_capacity[v][u]);
                        parent[u] = v;
                        mark[u] = VISITED;
                        if (u == sink)
                            return true;
                        queue[last++] = u;
                    }
            }
            return false;
        }
    }

    Resultat

    Als innere Klasse angelegt, arbeitet diese Implementation wunderbar in einem Avaloqix-Agenten. Tests haben gezeigt, dass das Resultat nicht nur stimmt, sondern auch mit den Ausgaben der Spieloberfläche korrespondiert. Auch bei sehr grossen Netzwerken braucht sie auf meinem Schlaftop nur ein paar wenige Millisekunden.

    4 Gedanken zu “Maximaler Fluss (maxflow) eines Netzwerkes in Java

    1. Hallo skaldrom,

      danke für die Veröffentlichung Deiner Implementierung.
      Allerdings gibt es einen Schönheitsfehler: Während der Berechnung wird die übergebene graphMatrix zerstört. Kann leicht getestet werden, indem man mit der selben Matrix zwei mal maxFlow berechnen lässt. Der erste Aufruf liefert das korrekte Ergebnis, der zweite liefert dann nur noch „0“.

      Der Grund liegt in der flachen Hierarchie von clone(). Der clone des int[][] erzeugt nur für die erste Dimension eine Kopie, die zweite Dimension ist wiederum eine Referenz auf das Original-Array:

        res_capacity=graphMatrix.clone();

      Also: res_capacity != graphMatrix
      aber: res_capacity[0] == graphMatrix[0]

      Änderungen an res_capacity[0] wirken sich somit direkt auf graphMatrix aus!

      Lösung:

        res_capacity=cloneMatrix(graphMatrix);
        ...

      private int[][] cloneMatrix(int[][] matrix) {
        int[][] result = new int[matrix.length][];
        for (int i = 0; i < result.length; i++) {
          result[i] = matrix[i].clone();
        }
        return result;
      }

      Viele Grüße,

      feri

    2. @Feri: Ui ja, das stimmt! Intern habe ich das schon korrigiert, nicht aber hier im Blog.

      Vielen Dank!

      Man merke sich: Nur immer eine Dimension clonen!!!

    3. Auch von mir vielen Dank für diese Implementierung, aber

      //res_capacity = new int[size][size]; // Remaining capacity

      müsste auskommentiert sein.

    Schreibe einen Kommentar

    Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.