Dudas con parametros para este método

[GaudyG]

Buenas, necesito hacer funcionar el Algoritmo de Edmonds-Karp que encuentra el Flujo Maximo de un Grafo. Si bien me conseguí la implementacion en Java, pero me hace falta entender que parametros exactamente me pide el método.

Por cierto:
C: es la matriz de representacion del Grafo
E: ?
s: nodo de inicio
t: nodo destino

Mi dudas son:
Si fuera posible que alguien me explicara que es el E, se q es una matriz, pero no se de que. En el parametro me piden los nodos s y t, pero en ¿¿formato int??

Código (java) [Seleccionar] Expandir


import java.util.*;

/**
* Finds the maximum flow in a flow network.
* @param E neighbour lists
* @param C capacity matrix (must be n by n)
* @param s source
* @param t sink
* @return maximum flow
*/
public class EdmondsKarp {
    public static int edmondsKarp(int[][] E, int[][] C, int s, int t) {
        int n = C.length;
        // Residual capacity from u to v is C[u][v] - F[u][v]
        int[][] F = new int[n][n];
        while (true) {
            int[] P = new int[n]; // Parent table
            Arrays.fill(P, -1);
            P[s] = s;
            int[] M = new int[n]; // Capacity of path to node
            M[s] = Integer.MAX_VALUE;
            // BFS queue
            Queue<Integer> Q = new LinkedList<Integer>();
            Q.offer(s);
            LOOP:
            while (!Q.isEmpty()) {
                int u = Q.poll();
                for (int v : E[u]) {
                    // There is available capacity,
                    // and v is not seen before in search
                    if (C[u][v] - F[u][v] > 0 && P[v] == -1) {
                        P[v] = u;
                        M[v] = Math.min(M[u], C[u][v] - F[u][v]);
                        if (v != t)
                            Q.offer(v);
                        else {
                            // Backtrack search, and write flow
                            while (P[v] != v) {
                                u = P[v];
                                F[u][v] += M[t];
                                F[v][u] -= M[t];
                                v = u;
                            }
                            break LOOP;
                        }
                    }
                }
            }
            if (P[t] == -1) { // We did not find a path to t
                int sum = 0;
                for (int x : F[s])
                    sum += x;
                return sum;
            }
        }
    }
}

[Valkyr]

No estoy seguro porque nunca he utilizado este algoritmo, pero me imagino que si el grafo es de la forma:



la matriz C representa el peso de las aristas, y la matriz E representa si existe una arista de un nodo a otro.

Además en el javadoc pone: neighbour lists, que según el traductor de google es "las listas de vecinos" xD, lo cual me hace pensar que se refiere a una matriz de adyacencia, donde E[a] indicaría que existe una arista del nodo a al nodo b.

Espero haber acertado y haberte ayudado.

Saludos.