Найти все возможные пути из одной вершины в ориентированном циклическом графе в Эрланге

Я хотел бы реализовать функцию, которая находит все возможные пути ко всем возможным вершинам из исходной вершины V в ориентированном циклическом графе G.

Производительность не теперь неважно, я просто хотел бы понять алгоритм. Я прочитал определение алгоритма поиска в глубину, но не понимаю, что делать.

У меня нет завершенного фрагмента кода, который я мог бы предоставить здесь, потому что я не уверен, как:

• сохранить результаты (вместе с A-> B-> C-> мы также должны сохранить A-> B и A-> B-> C);
• представляют граф (орграф? Список кортежей?);
• сколько рекурсий использовать (работать с каждой смежной вершиной?).

Как мне найти все возможные пути из одной заданной исходной вершины в ориентированном циклическом графе в Erlang?

UPD: На основании полученных ответов я должен переопределить определение графа: это неациклический граф. Я знаю, что если моя рекурсивная функция попадает в цикл, это бесконечный цикл. Чтобы этого избежать, я могу просто проверить, находится ли текущая вершина в списке результирующего пути - если да, я прекращаю обход и возвращаю путь.

UPD2: Спасибо за наводящие на размышления комментарии! Да, мне нужно найти все простые пути, которые не имеют петель от одной исходной вершины ко всем остальным.

В таком графе:

с исходной вершиной A алгоритм должен найти следующие пути:

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

Следующий код выполняет свою работу, но его нельзя использовать с графами, имеющими более 20 вершин (я думаю, это что-то не так с рекурсией - занимает слишком много памяти, никогда не заканчивается):

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:

Проблема в том, что обычный алгоритм поиска в глубину сначала будет идти по одному из путей к: (A, B, C, D ) или (A, D, C, B) и никогда не пойдет по второму пути.

В любом случае это будет единственный путь - например, когда обычный DFS выполняет возврат от (A, B, C, D), он возвращается к A и проверяет, посещен ли D (второй сосед A). . А поскольку обычная DFS поддерживает глобальное состояние для каждой вершины, D будет «посещенным» состоянием.

Итак, мы должны ввести состояние, зависящее от рекурсии - если мы вернемся от (A, B, C, D) к A, мы должны иметь (A, B, C, D) в списке результатов и мы должны отметить D как непосещенный, как в самом начале алгоритма.

Я попытался оптимизировать решение до хвостовой рекурсии, но все же время работы алгоритма невыполнимо - требуется около 4 секунд, чтобы пройти крошечный граф из 16 вершин с 3 ребрами на вершину:

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).

Любой идеи запустить это в приемлемое время?