elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: (TUTORIAL) Aprende a emular Sentinel Dongle By Yapis


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  Java
| | | |-+  Dudas con parametros para este método
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Dudas con parametros para este método  (Leído 3,157 veces)
GaudyG

Desconectado Desconectado

Mensajes: 23


Ver Perfil
Dudas con parametros para este método
« en: 3 Julio 2011, 23:45 pm »

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
  1. import java.util.*;
  2.  
  3. /**
  4.  * Finds the maximum flow in a flow network.
  5.  * @param E neighbour lists
  6.  * @param C capacity matrix (must be n by n)
  7.  * @param s source
  8.  * @param t sink
  9.  * @return maximum flow
  10.  */
  11. public class EdmondsKarp {
  12.    public static int edmondsKarp(int[][] E, int[][] C, int s, int t) {
  13.        int n = C.length;
  14.        // Residual capacity from u to v is C[u][v] - F[u][v]
  15.        int[][] F = new int[n][n];
  16.        while (true) {
  17.            int[] P = new int[n]; // Parent table
  18.            Arrays.fill(P, -1);
  19.            P[s] = s;
  20.            int[] M = new int[n]; // Capacity of path to node
  21.            M[s] = Integer.MAX_VALUE;
  22.            // BFS queue
  23.            Queue<Integer> Q = new LinkedList<Integer>();
  24.            Q.offer(s);
  25.            LOOP:
  26.            while (!Q.isEmpty()) {
  27.                int u = Q.poll();
  28.                for (int v : E[u]) {
  29.                    // There is available capacity,
  30.                    // and v is not seen before in search
  31.                    if (C[u][v] - F[u][v] > 0 && P[v] == -1) {
  32.                        P[v] = u;
  33.                        M[v] = Math.min(M[u], C[u][v] - F[u][v]);
  34.                        if (v != t)
  35.                            Q.offer(v);
  36.                        else {
  37.                            // Backtrack search, and write flow
  38.                            while (P[v] != v) {
  39.                                u = P[v];
  40.                                F[u][v] += M[t];
  41.                                F[v][u] -= M[t];
  42.                                v = u;
  43.                            }
  44.                            break LOOP;
  45.                        }
  46.                    }
  47.                }
  48.            }
  49.            if (P[t] == -1) { // We did not find a path to t
  50.                int sum = 0;
  51.                for (int x : F[s])
  52.                    sum += x;
  53.                return sum;
  54.            }
  55.        }
  56.    }
  57. }


En línea

Valkyr


Desconectado Desconectado

Mensajes: 646


Divide y vencerás


Ver Perfil
Re: Dudas con parametros para este método
« Respuesta #1 en: 4 Julio 2011, 02:38 am »

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.


En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Dudas con MySQL, SP con multiples parametros y PHP
PHP
Anteros 0 1,612 Último mensaje 5 Diciembre 2008, 15:24 pm
por Anteros
C/C++ Dudas parámetros « 1 2 3 4 »
Programación C/C++
h0oke 30 12,857 Último mensaje 24 Mayo 2010, 04:17 am
por h0oke
parametros x e y en metodo POST
Desarrollo Web
lord mick 8 6,084 Último mensaje 19 Agosto 2010, 22:54 pm
por w4r10
Dudas: Parametros remplazables | Programación Batch
Scripting
miguel_s777 1 4,041 Último mensaje 8 Octubre 2011, 18:17 pm
por leogtz
¿Se pueden tener parámetros de distinto tipo en un método?
Programación General
Jprogramer 1 2,653 Último mensaje 26 Mayo 2020, 16:42 pm
por Serapis
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines