Proyecto de Estructura de datos.... GRAFOS!!! :c

[axel19]

Hola comunidad!!!

Publico esto para pedir su ayuda

Necesito realizar un programa que me de las diferentes rutas posibles dentro de un grafo

Entiendo que esto lo puedo realizar con una matriz de Adyacencia con 1 y 0

Como podría realizar este procedimiento???
     L
    /
C ---B----D
|\            |
| \           |
A---F------H     

Por ejemplo en este grafo me las rutas para ir de A a L
A->C->L   ,    A->F->C->L    ,    A->F->H->D->B->C->L

[anubisdark]

Lo que puedes hacer es una clase Grafo, en los cuales tenga solo 3 nodos, si son grafos supuestamente vas a tener dos apuntadores el izquierdo y el derecho, si es un diagrama de Hasse, si no es ese caso, entonces vas a tener más nodos, después de crear ese insert, lo que haces es un backtracking, en el que le pasas un contador por referencia, y vas probando... Yo la verdad lo que haría es que en cada nodo guardo un contador que me diga cuantos saltos tengo que hacer de un nodo A a un nodo B, como sale en tu ejemplo, por ejemplo sería, que en el nodo F, guardo en una variable cuantos saltos tengo que hacer para llegar a L, y cual es su camino en un string.

[Serapis]

Antes que nada, debes decidir/indicar, si es admisible que se revisite un nodo dos ó x veces, ó solo una como máximo... sino, por ejemplo sería valido la ruta:
A->C, B, D, H, F, C, L  ...Que, como se puede ver, revisita el nodo C dos veces...

Una vez decidido, y dando por supuesto que no se admitite revisitar nodos, puede tratarse como un automata finito determinista (AFD), donde el alfabeto es el conjunto de nodos (A, B, C, D, F, H, L) donde el estado inicial es A y el estado final es L, entonces puede establecerse el resto de nodos como estados de transición entre uno y otro.

Así desde A solo puede accederse a F y a C, lo que por ejemplo tratado como un autómata finito determinista , se señalaría en BNF como:
A = C|F
y desde C, se puede acceder a los nodos
C = A|F|B|L
El resto d eproducciones:
F = A|H
H = F|D
D = H|B
B = C|D
L = C  <--- esta no interesa, se trata de llegar a L, no pasar po él (es el estado final, no un estadode transición)
Como se puede ver, las producciones BNF, son las adyacencias de un nodo, la cantidad de nodos a los que se accede (por ejemplo A|F|B|L) son las aristas que salen de dicho nodo (en el ejemplo del nodo C, en C = A|F|B|L).

Entonces una vez en el estado inicial (A, pongamos estado 1), solo puede transitar hacia un estado 2, y desde un estado 2 a otro estado 2 o al estado de transición 3, si no tiene otro nodo que sea visitable que uno ya visitado, va al estado de error y por tanto ese camino no tiene solución, debe volverse un paso atrás cada vez que esto suceda... el estado de transición 3 (L), es el estado final, y señal de que admite ese 'token', para la gramática del alfabeto propuesto...
Puede tratarse como un automata de pila, porque un nodo no puede visitarse más de una vez...

A diferencia claro, de por ejemplo cuando se hace un compilador que en la entrada viene un texto y se trata de ver si un token pertenerce o no a la gramática, en tu caso haces algo distinto, la entrada es nula y tratas de averguar todas las salidas válidas (para una gramática libre de contexto serían incontables), pero para el caso de un grafo como el del ejemplo, es finito... ...de entrada se sabe que como máximo la longitud de palabra es la del alfabeto (ó menor)...
Por cuestiones de rendimiento, la pila realmente puede ser remplazada por un array de bytes donde cada letra del alfabeto tenga un valor true (no visitado ún, esto es, es Visitable), y una vez usado (pop si fuera una pila) su valor se ponga a false (nodo visitado, no visitable ya)... la velocidad de usar el array sobre una pila, está en el acceso aleatorio. al no exigir tener que extraer lo de encima de la pila... para acceder a un nodo.


Aquí un pseudocódigo casi completo... la función donde ba todo el trabajo lo dejo a tu esfuerzo...

Código [Seleccionar] Expandir


funcion TodasLasRutasDeUnGrafo(string alfabeto) // sin repetir nodo.
   array bytes pila()  // realmente no es una pila, pero acomoda llamarlo así.
   array string prod= GetProducciones  //las producciones BNF, como un array de strings.

   // Albabeto = ABCDFHL  la primera letra debe ser el estado inicial
   Bucle k desde 2letra de alfabeto hasta última-1 //y la última debe ser el estado final.
       x = alfabeto(k)  //letra enésima del alfabeto
       c= caracter kesimo en alfabeto
       Hacer  
           pila = LlenarPila(alfabeto)   //vuelve visitable todos sus nodos.
           //pila(ASCII(c)) = FALSE // excepto la letra inicial de la que partimos esta vez,
           // pero esto mejor se traslada a la función invocada.            
           token = SiguienteToken(prod, pila, c)
           Si token <> ""
               imprimir "A --> " + token
           sino
               salir del bucle interno    
           fin si
       Repetir //mientras token distinto de nulo
   Siguiente


Código [Seleccionar] Expandir


// el array es fijo según el grafo, y tal como se indico en las producciones.
// al caso se 'montan' en un array de strings,
array de String = Funcion GetProducciones  
   array de string p(0 a 255)

   //Cada valor está en la casilla cuyo ASCII representa y su contenido son la representación de cada nodo al que se accede desde él,
   // cada letra representa un nodo, al caso se han ordenado alfabéticamente, pero puede seguirse el orden en que aparecen sobre el grafo girando en uno u otro sentido, no importa...
   p(ASCII(A)) = CF
   p(ASCII(B)) = CD
   p(ASCII(C)) = ABLF
   p(ASCII(D)) = BH
   p(ASCII(F)) = AH
   p(ASCII(H)) = DF
   //p(ASCII(L))  
   
   devolver p
fin funcion

Código [Seleccionar] Expandir


array de bytes = funcion LlenarPila(string alfabeto)
   array de bytes x(0 a 255)
   byte k

   Por cada letra en Alfabeto
       x(ASCII(letra)) = TRUE   //por ejemplo si letra es A: x(65) = TRUE, porque A es el carácter ASCII 65
   siguiente
   devolver X
fin funcion

Y la función final que lleva todo el trabajo, la dejo a tu esfuerzo... pero con algunas anotaciones.

Código [Seleccionar] Expandir


enumeracion Estados
   ESTADO_ERROR = 0
   ESTADO_INICIAL = 1
   ESTADO_TRANSICION = 2
   ESTADO_FINAL = 3
fin enumeracion

// de entrada sabemos que el estado inicial es 1, y el primer carácter-nodo es A, que puede obviarse.
string = funcion SiguienteToken(array string P(),  array bytes Pila(), char letra)
  Estados  e= ESTADO_INICIAL
  string t = letra // la letra inicial, para esta vez.
 
  letra = siguiente letra en p(ASCII(letra)) // esto exige recursión ya que una producción engloba a otra.
  // Si pila(ASCII(letra)) = TRUE si el nodo de dicha letra es visitable
  //     t += letra
  //     Si letra = "L"
  //         e = ESTADO_FINAL
  //         devolver t
  //     sino
  //         e = ESTADO_TRANSICION
  //         marcar letra no visitable  pila(ASCII(letra)) = False
  //     fin si
  // sino
  //     volver atras, si es recursivo, implica devolver
  // fin si  
 
  // Si un nodo no es visitable, volver atrás, y si ya no quedan más nodos hacia adelante devolver false.  
fin funcion


Finalmente decirte que casi siempre verás una solución con un cuerpo más matemático, tirando de árboles... , la solución (incompleta) que te aporto, es... no más cercana, sino íntima a la programación... pués entra en la parte de la teoría de compiladores. Aunque al caso ha habido una discreta variación... a medias entre un análisis léxico y sintáctico.

Otra solución es recurrir a la combinatoria... generar (ir generando y probando sobre la marcha cada una si es un camino, esto es si el siguiente nodo es accesible desde el actual) todas las permutaciones sin repetición de largo máximo el alfabeto ABCDFHL (menos la letra inicial).
Como algoritmo es mucho más simple, pero es más lento en ejecución, especialmente si el alfabeto fuera mucho más largo, para este cortito, todavía no es significativo.

Código [Seleccionar] Expandir


   string permutacion, ruta
   array de string p()  // el array de producciones que se generó el en otro pseudocódigo... traer la función aquí.
   por cada permutacion sobre el alfabeto //BCDFHL, nota que retiramos la A, pués siempre es el nodo inicial
     
       ruta = Substring(permutacion, hasta "L")  // obtenemos la subcadena hasta L, lo que tenga detrás sobra
       si EsCamino(ruta, p ) = TRUE
           imprimir "A" + ruta
       fin si
   siguiente

buleano = EsCamino(string ruta, array strings p)  // p son el array de las producciones generadas en el otro pseudocódigo
  char c = ruta(0)
  char n
   //... recorrer todo el string, viendo si desde la letra actual, hay conexión al otro nodo (siguiente letra)
   bucle para k desde 1 hasta largo de ruta
       n = ruta(k)
       si p(ASCII(c)) contiene n
           c = n
       sino
           devolver false
       fin si
   siguiente
   devolver TRUE   // c = "L"
fin funcion

// OJO: Alfabeto aquí deja fuera la letra A, no queremos que cambie de posición porque sabemos que siempre ha de ser el primero, no cabe en otra posición.
// alfabeto = "BCDFHL"
string = SiguientePermutacion(string alfabeto , string permutacion)
  ... calcula y devuelve la siguiente permutacion a la recibida. inicialmente permutacion = alfabeto
fin funcion
 

[Serapis]

mmmm... es típico que alguien venga preguntando algo, y luego nunca comparezca, ni siquiera para ver si han respondido...

Si lo que sucede es que te asusta la respuesta, te aclaro que se puede simplificar, pero (resulta conveniente) que antes haya algún "feedback", que demuestre que tienes interés en aprender y no solo en tener una tarea lista.

De todos modos, como va a resultar en incomparecencia, no dejaré a otros en la intriga.



Del mismo modo, que por ejemplo, cuando intentamos trazar un área dados unos  segmentos (medida y ángulo), que delimitan el perímetro... que si sucede, como en el siguiente ejemplo que:

A-------B-------------C----D
AB mide 8, angulo = g
BC mide 13, angulo = g
CD mide 4, angulo = g

Teniendo todos ellos el mismo ángulo y yendo uno a continuación del otro, se puede simplificar los 3 como un único segmento del mismo ángulo pero de longitud la suma de todos ellos:

A-------------------------D
AD mide AB + BC + CD = 25, angulo = g
No necsitamos nada más de dicho ejemplo...

(un ejemplo sencillo de entender por todo el mundo). Del mismo modo cuando hay grafos que son antecedidos por solo un nodo y seguido de también un solo nodo, un tramo así igualmente puede ser resumido en uno equivalente... en tu caso, entonces:
F-H-D-B-C, puede ser resumido como uno nuevo E = HDB  que los remplace. Y por tanto considerar, solo las producciones
A = C|F
y desde C, se puede acceder a los nodos
C = A|F|E|L
F = A|C|E
E = C|F   <---- el nuevo nodo que remplaza (para simplificar) a los 3 intermedios.

H = F|D
D = H|B
B = C|D
L = C <--- esta no interesa, ya dijimos que L es el nodo del estado final, no un estado intermedio.


Si lo montas en un árbol sintáctico (que corresponde al algoritmo, señalado más arriba)... se obtiene esto... debajo lo explico por encima, aunque es autoexplicativo, si lo observas el suficiente tiempo...


La raíz es la producción general, la solución.
Debajo se ponen como hijos cada uno de las alternativas que salen desde "A" (el nodo padre).
De igual modo debajo de cada nodo, se pone las alternativas de esa producción.
De esa manera se va completando el árbol...
Los nodos pintados de verde, son los rechazados. y se rechazan, porque ya han sido visitados... toma un nodo verde, revisa sus ancentros, y verás que ya consta en esa ruta.
Una vez que un nodo es tachado, ya no cabe más descencia de él.
Finalmente (en alguno) se llega al estado terminal, "L"...
Todas las rutas de la raíz "A" a cada una de los nodos terminales "L", son las soluciones que buscas (las he marcado con nodos rojos y caminos en amarillo).
Finalmente se ponen todas, juntas debajo y habiendo recordado deshacer "E", que lo hemos tenido simplificado durante el proceso.