Encuentre todos los caminos posibles desde un vértice en un gráfico cíclico dirigido en Erlang

Question

Me gustaría implementar una función que encuentre todas las rutas posibles a todos los vértices posibles desde un vértice fuente V en un gráfico cíclico dirigido G.

El rendimiento no importa ahora, solo me gustaría entender el algoritmo. He leído la definición del algoritmo de búsqueda en profundidad, pero no tengo una comprensión completa de qué hacer.

No tengo ningún fragmento de código completo para proporcionar aquí porque no estoy seguro de cómo:

• almacenar los resultados (junto con A-> B-> C-> también debemos almacenar A-> B y A-> B-> C);
• representar el gráfico (¿dígrafo? ¿lista de tuplas?);
• cuántas recursiones usar (¿trabajar con cada vértice adyacente?).

¿Cómo puedo encontrar todas las rutas posibles desde un vértice de origen determinado en un gráfico cíclico dirigido en Erlang?

UPD: Basado en las respuestas hasta ahora tengo que redefinir la definición del gráfico: es un gráfico no acíclico. Sé que si mi función recursiva golpea un ciclo, es un ciclo indefinido. Para evitar eso, puedo verificar si un vértice actual está en la lista de la ruta resultante; si es así, dejo de atravesar y devuelvo la ruta.

---

UPD2: ¡Gracias por los comentarios que invitan a la reflexión! Sí, necesito encontrar todas las rutas simples que no tengan bucles desde un vértice de origen a todos los demás.

En un gráfico como este:

con el vértice de origen A, el algoritmo debería encontrar las siguientes rutas:

• A, B
• A, B, C
• A, B, C, D
• A, D
• A, D, C
• A, D, C, B

El siguiente código hace el trabajo, pero no se puede usar con gráficos que tienen más de 20 vértices (supongo que hay algo mal con la recursividad - toma demasiada memoria, nunca termina):

dfs(Graph,Source) ->
    ?DBG("Started to traverse graph~n", []),
            Neighbours = digraph:out_neighbours(Graph,Source),
    ?DBG("Entering recursion for source vertex ~w~n", [Source]),
            dfs(Neighbours,[Source],[],Graph,Source),
ok.


dfs([],Paths,Result,_Graph,Source) ->
    ?DBG("There are no more neighbours left for vertex ~w~n", [Source]),
    Result;

dfs([Neighbour|Other_neighbours],Paths,Result,Graph,Source) ->
    ?DBG("///The neighbour to check is ~w, other neighbours are: ~w~n",[Neighbour,Other_neighbours]),
    ?DBG("***Current result: ~w~n",[Result]),
    New_result = relax_neighbours(Neighbour,Paths,Result,Graph,Source),

        dfs(Other_neighbours,Paths,New_result,Graph,Source).


relax_neighbours(Neighbour,Paths,Result,Graph,Source) ->
     case lists:member(Neighbour,Paths) of 
        false ->
            ?DBG("Found an unvisited neighbour ~w, path is: ~w~n",[Neighbour,Paths]),
            Neighbours = digraph:out_neighbours(Graph,Neighbour),
            ?DBG("The neighbours of the unvisited vertex ~w are ~w, path is:
                ~w~n",[Neighbour,Neighbours,[Neighbour|Paths]]),
                dfs(Neighbours,[Neighbour|Paths],Result,Graph,Source);
            true ->
                [Paths|Result]

        end.

---

<×UPD3:

El problema es que el algoritmo regular de búsqueda en profundidad primero irá primero a una de las rutas a: (A, B, C, D) o (A, D, C, B) y nunca irá a la segunda ruta.

En cualquier caso, será la única ruta; por ejemplo, cuando el DFS normal retrocede desde (A, B, C, D) vuelve a A y comprueba si se visita D (el segundo vecino de A) . Y dado que el DFS regular mantiene un estado global para cada vértice, D habría estado 'visitado'.

Entonces, tenemos que introducir un estado dependiente de la recursividad: si retrocedemos desde (A, B, C, D) hasta A, deberíamos tener (A, B, C, D) en la lista de resultados y deberíamos tener D marcado como no visitado como al principio del algoritmo.

He intentado optimizar la solución a la cola recursiva, pero aún así el tiempo de ejecución del algoritmo es inviable: se necesitan unos 4 segundos para atravesar un pequeño gráfico de 16 vértices con 3 aristas por vértice:

dfs(Graph,Source) ->
    ?DBG("Started to traverse graph~n", []),
            Neighbours = digraph:out_neighbours(Graph,Source),
    ?DBG("Entering recursion for source vertex ~w~n", [Source]),
    Result = ets:new(resulting_paths, [bag]),
Root = Source,
            dfs(Neighbours,[Source],Result,Graph,Source,[],Root).


dfs([],Paths,Result,_Graph,Source,_,_) ->
    ?DBG("There are no more neighbours left for vertex ~w, paths are ~w, result is ~w~n", [Source,Paths,Result]),
    Result;

dfs([Neighbour|Other_neighbours],Paths,Result,Graph,Source,Recursion_list,Root) ->
    ?DBG("~w *Current source is ~w~n",[Recursion_list,Source]),
    ?DBG("~w Checking neighbour _~w_ of _~w_, other neighbours are: ~w~n",[Recursion_list,Neighbour,Source,Other_neighbours]),



?    DBG("~w Ready to check for visited: ~w~n",[Recursion_list,Neighbour]),

 case lists:member(Neighbour,Paths) of 
        false ->
            ?DBG("~w Found an unvisited neighbour ~w, path is: ~w~n",[Recursion_list,Neighbour,Paths]),
New_paths = [Neighbour|Paths],
?DBG("~w Added neighbour to paths: ~w~n",[Recursion_list,New_paths]),
ets:insert(Result,{Root,Paths}),

            Neighbours = digraph:out_neighbours(Graph,Neighbour),
            ?DBG("~w The neighbours of the unvisited vertex ~w are ~w, path is: ~w, recursion:~n",[Recursion_list,Neighbour,Neighbours,[Neighbour|Paths]]),
                dfs(Neighbours,New_paths,Result,Graph,Neighbour,[[[]]|Recursion_list],Root);
            true -> 
            ?DBG("~w The neighbour ~w is: already visited, paths: ~w, backtracking to other neighbours:~n",[Recursion_list,Neighbour,Paths]),
ets:insert(Result,{Root,Paths})

end,

        dfs(Other_neighbours,Paths,Result,Graph,Source,Recursion_list,Root).

¿Alguna idea para ejecutar esto en un tiempo aceptable?

Answer 1

Editar: Bien, ahora lo entiendo, desea encontrar todas las rutas simples desde un vértice en un gráfico dirigido. Por lo tanto, una búsqueda en profundidad con retroceso sería adecuada, como se habrá dado cuenta. La idea general es ir a un vecino, luego ir a otro (no a uno que hayas visitado) y seguir hasta llegar a un callejón sin salida. Luego retrocede hasta el último vértice en el que estabas y elige un vecino diferente, etc. Necesita hacer bien los detalles complicados, pero no debería ser demasiado difícil. P.ej. en cada paso debe etiquetar los vértices como 'explorados' o 'inexplorados' dependiendo de si ya los ha visitado antes. El rendimiento no debería ser un problema, un algoritmo implementado correctamente debería llevar tal vez O (n ^ 2) tiempo. Entonces no sé qué estás haciendo mal, ¿tal vez estás visitando a demasiados vecinos? P.ej. tal vez esté visitando vecinos que ya ha visitado y dando vueltas o algo así.

Realmente no he leído su programa, pero la página Wiki en la búsqueda en profundidad tiene un programa de pseudocódigo simple y corto que puede intentar copiar en su idioma. Guarde los gráficos como listas de adyacencia para que sea más fácil.

Editar: Sí, lo siento, tiene razón, la búsqueda DFS estándar no funcionará como está, debe ajustarla ligeramente para que vuelva a visitar los vértices que ha visitado antes. Por lo tanto, puede visitar cualquier vértice, excepto los que ya ha almacenado en su ruta actual. Esto, por supuesto, significa que mi tiempo de ejecución fue completamente incorrecto, la complejidad de su algoritmo será por las nubes. Si la complejidad promedio de su gráfico es d + 1, entonces habrá aproximadamente d * d * d * ... * d= d ^ n caminos posibles. Entonces, incluso si cada vértice tiene solo 3 vecinos, todavía hay bastantes caminos cuando superas los 20 vértices. Realmente no hay forma de evitarlo, porque si desea que su programa muestre todas las rutas posibles, entonces tendrá que generar todas las d ^ n.

Me interesa saber si lo necesita para una tarea específica o simplemente está intentando programarlo por interés. Si es lo último, solo tendrá que estar contento con gráficos pequeños y escasamente conectados.

Answer 2

No entiendo la pregunta. Si tengo el gráfico G= (V, E)= ({A, B}, {(A, B), (B, A)}), hay infinitos caminos de A a B {[A, B], [ A, B, A, B], [A, B, A, B, A, B], ...}. ¿Cómo puedo encontrar todas las rutas posibles a cualquier vértice en un gráfico cíclico?

Editar:

¿Intentaste calcular o adivinar el crecimiento de posibles rutas para algunos gráficos? Si tiene un gráfico completamente conectado, obtendrá

• 2 - 1
• 3 - 4
• 4 - 15
• 5 - 64
• 6 - 325
• 7 - 1956
• 8-13699
• 9 - 109600
• 10 - 986409
• 11 - 9864100
• 12 - 108505111
• 13 - 1302061344
• 14 - 16926797485
• 15 - 236975164804
• 16 - 3554627472075
• 17 - 56874039553216
• 18 - 966858672404689
• 19-17403456103284420
• 20 - 330665665962403999

¿Está seguro de que le gustaría encontrar todas las rutas para todos los nodos? Significa que si calcula un millón de rutas en un segundo, tomaría 10750 años calcular todas las rutas a todos los nodos en un gráfico completamente conectado con 20 nodos. Es el límite superior para su tarea, así que creo que no le gustaría hacerlo. Creo que quieres algo más.

Answer 3

No es una solución algorítmica mejorada de ninguna manera, pero a menudo puede mejorar el rendimiento generando múltiples hilos de trabajo, potencialmente aquí uno para cada nodo de primer nivel y luego agregando los resultados.Esto a menudo puede mejorar los algoritmos de fuerza bruta ingenuos con relativa facilidad.

Puede ver un ejemplo aquí: Algunas funciones de matriz de Erlang , en la función maximise_assignment (comentarios que comienzan en la línea 191 a partir de hoy).De nuevo, el algoritmo subyacente es bastante ingenuo y de fuerza bruta, pero la paralelización lo acelera bastante bien para muchas formas de matrices.

He usado un enfoque similar en el pasado para encontrar el número de caminos hamiltonianos en un gráfico.