Обнаружение графического цикла с помощью Prolog

Question

Я пытаюсь написать программу пролога, которая обнаруживает цикл в неориентированном графе. Я уже проконсультировался с этим вопросом: первый поиск по глубине графа пролога

и попытался изменить алгоритм dfs, представленный там, для обнаружения циклов. Вот мой прогресс:

findCycle(Node, NextNode, Visited) :-
      ( member(NextNode, Visited), isNotParent(Node, NextNode) )
    ->
      writeln("found a cycle"), saveCycle(Node, NextNode), !
    ;
      writeln("end of findCycle").
   
saveCycle(Node, NextNode) :-
    % save to structure
 
dfs(Graph, StartNode) :-
    dfs(Graph, StartNode, []).

dfs(Graph, Node, Visited) :-
    writeln(Visited),
    \+ member(Node, Visited),
    write("visiting node "),
    write(Node), nl,
    member(NextNode, Graph.get(Node)),
    % \+ findCycle(Node, NextNode, Visited),
    dfs(Graph, NextNode, [Node|Visited]).

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

• Мне нужно сохранить «родительский элемент» каждой вершины в структуре данных, чтобы его можно было использовать для обнаружения цикла. Я не знаю, как это сделать. До сих пор я тестировал программу на примере графа, ребра которого я ввожу вручную с отдельными терминами. Однако это не моя конечная цель.

• Мне также нужно исправить алгоритм dfs, потому что, как и сейчас, он вызывает переполнение стека из-за того, что список посещенных не сохраняет все вершины настойчиво. В идеале Visited должен быть словарем, а не списком, чтобы к нему можно было получить более эффективный доступ.

• Наконец, если обнаружен цикл, я хотел бы сохранить все вершины, участвующие в в другую структуру данных.

Хотя я знаю программирование и писал эту программу на C ++ в прошлом, мой gr asp пролога в лучшем случае является элементарным, поэтому любая помощь будет оценена. Спасибо!

Answer 1

Вы несколько перегибаете палку ...

Просто упростите свой код до минимума, и вы получите то, что вам нужно ... например:

find_cycle(G,Vs) :-
  member(V-_Edges,G), % don't care about starting point
  find_cycle(G,V,[],Vs).

find_cycle(_G,V,SeenVs,[V|SeenVs]) :-
  memberchk(V,SeenVs).
find_cycle(G,V,SeenVs,Cycle) :-
  \+memberchk(V,SeenVs),
  member(V-Es,G),
  member(Ve,Es),
  find_cycle(G,Ve,[V|SeenVs],Cycle).

?- G=[a-[b,c],b-[a,c],c-[]],find_cycle(G,C).
G = [a-[b, c], b-[a, c], c-[]],
C = [a, b, a] ;
G = [a-[b, c], b-[a, c], c-[]],
C = [b, a, b] ;
false.

Или, чтобы избежать дублирования поиска в списке посещенных ребер:

find_cycle(G,V,SeenVs,Cycle) :-
  (   memberchk(V,SeenVs)
  ->  Cycle=[V|SeenVs]
  ;   member(V-Es,G),
      member(Ve,Es),
      find_cycle(G,Ve,[V|SeenVs],Cycle)
  ).

редактировать после комментария ...

Для эффективности, обратите внимание, я использовал memberchk / 2 в тест, а не член / 2. Реализация в SWI-Prolog очень быстрая, так как использует низкоуровневое представление списков (skip list), выполненное в C. Итак, у вас должны быть очень длинные списки, прежде чем вы начнете наблюдать некоторые улучшения с использованием какой-либо другой структуры данных (есть такие ... как rbtrees, avltrees, ...). Но если ваши списки такие большие, то нужно улучшить весь алгоритм. Опять же, они есть, вы можете начать поиск в библиотеке ( ugraph ).