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.