graph - profundidad - recorrido de grafos en c++

Encuentra todas las rutas 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 posibles vértices desde un vértice de origen 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 aquí, porque no estoy seguro de cómo hacerlo:

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

¿Cómo puedo encontrar todas las rutas posibles desde un vértice fuente dado 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, solo puedo verificar si un vértice actual está en la lista de la ruta resultante; si es así, dejo de atravesar y regreso la ruta.

UPD2: ¡ Gracias por los comentarios que provocan la reflexión! Sí, necesito encontrar todas las rutas simples que no tienen 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
• ANUNCIO
• 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 algo está mal con la recursión; requiere 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 de búsqueda regular de profundidad primero irá primero a uno de los caminos: (A, B, C, D) o (A, D, C, B) y nunca irá al segundo camino.

En cualquier caso, será la única ruta, por ejemplo, cuando el DFS normal retrocede desde (A, B, C, D) regresa a A y verifica si D (el segundo vecino de A) es visitado. Y dado que el DFS regular mantiene un estado global para cada vértice, D tendría el 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 han marcado D como no visitado como al comienzo del algoritmo.

He tratado de optimizar la solución a la recursiva de la cola, pero aún así el tiempo de ejecución del algoritmo es inviable: lleva unos 4 segundos atravesar un pequeño gráfico de 16 vértices con 3 bordes 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

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 todos los caminos posibles para cualquier vértice en un gráfico cíclico?

Editar:

¿Intentó calcular o adivinar el crecimiento de posibles caminos para algunos gráficos? Si tienes un gráfico completamente conectado, obtendrás

• 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ás seguro de que te gustaría encontrar todas las rutas para todos los nodos? Significa que si se calculan miliones de caminos en un segundo, se necesitarían 10750 años para calcular todas las rutas a todos los nodos en un gráfico totalmente conectado con 20 nodos. Es un límite superior para su tarea, así que creo que no le gustaría hacerlo. Creo que quieres algo más.

Answer 2

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

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

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

Answer 3

Editar: Bien, ahora lo entiendo, quiere 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 uno que hayas visitado) y seguir hasta llegar a un callejón sin salida. Luego regresa al último vértice en el que estuviste y elige un vecino diferente, etc. Debes obtener las partes más complicadas, pero no debería ser demasiado difícil. Por ejemplo, en cada paso debe etiquetar los vértices "explorados" o "inexplorados" dependiendo de si ya los ha visitado anteriormente. El rendimiento no debería ser un problema, un algoritmo implementado correctamente debería tomar quizás O (n ^ 2) tiempo. Entonces, no sé lo que estás haciendo mal, ¿quizás estás visitando a demasiados vecinos? Por ejemplo, tal vez estés visitando vecinos que ya has visitado y dando vueltas en bucles o algo así.

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

Editar: Sí, lo siento, tienes razón, la búsqueda DFS estándar no funcionará tal como está, debes ajustarla ligeramente para que vuelva a visitar los vértices que ha visitado anteriormente. Así que puedes visitar cualquier vértice, excepto los que ya has almacenado en tu ruta actual. Esto, por supuesto, significa que mi tiempo de ejecución fue completamente incorrecto, la complejidad de su algoritmo estará por las nubes. Si la complejidad promedio de su gráfica 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 se obtienen más de 20 vértices. No hay forma de evitarlo realmente, porque si quieres que tu programa muestre todos los caminos posibles, entonces de hecho tendrás que sacar todos los d ^ n de ellos.

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