Ответ в теме: Поиск циклов и петель в графе

      Комментарии к записи Ответ в теме: Поиск циклов и петель в графе отключены
#2507

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

self_loop(Node):-
  edge(Node, Node).

Однако для поиска циклов граф удобнее преобразовать в список (не использовать записи базы данных), т.к. при поиске в ширину пройденные дуги удобно удалять, но при этом не хотелось бы испортить исходный граф. При этом если вы используете SWI Prolog, то записи базы данных могли бы быть такими – edge(From, To), однако при использовании Visual Prolog с этим могли бы возникнуть проблемы – чтобы получить набор дуг можно хранить в базе данных записи следующего вида: data(edge(From, To)). Формат записей не сильно скажется на функции сбора всех записей в список:

database_to_graph_list(Graph):-
  findall(Edge, data(Edge), Graph).

Теперь наш граф представлен в виде списка, для поиска элемента в котором можно применять функцию member, а для удаления – delete. Для поиска цикла (т.е. пути, начало и конец которого совпадают) из некоторой вершины мы можем:

  • постепенно (поиском в глубину) выбирать (и удалять) дуги, ведущие из текущей вершины, и помещать концы дуг в список пройденных вершин (ProcessedNodes) до тех пор пока очередная вершина не окажется в списке пройденных (цикл найден);
  • если из текущей вершины некуда пойти (из нее не выходит ни одна дуга) – выполняется откат (срабатывает механизм поиска в возвратами) и поиск другого (обходного) пути.

loop_graph(A, Graph, ProcessedNodes, [A|ProcessedNodes]):-
  member(edge(A, X), Graph),
  member(X, [A|ProcessedNodes]), !.
loop_graph(A, Graph, ProcessedNodes, [A|Loop]):-
  member(edge(A, X), Graph),
  delete(Graph, edge(A, X), NewGraph),
  loop_graph(X, NewGraph, [A|ProcessedNodes], Loop).

Данный фрагмент ищет не только циклы, но и петли благодаря тому, что к списку пройденных вершин в последнем вызове member в первом правиле добавляется исходный узел.
Приведенный фрагмент кода вернет все найденные циклы с началом в заданной вершине. Для того, чтобы получить все циклы в графе нужно оставить начальную вершину анонимной. При этом, если мы захотим проверить является ли граф деревом, мы должны будем использовать оператор NOT:
NOT(loop_graph(_X, Graph, [], _Loop))
Однако Visual Prolog при этом вернет ошибку, связанную с тем, что цель оператора NOT содержит анонимную переменную:

Free variable are not allowed in ‘not’ or ‘retractall’

Для решения проблемы достаточно написать вспомогательную функцию, выполняющую поиск любого цикла или петли в графе:

loop_graph(Graph):-
  loop_graph(_X, Graph, [], _Loop), !.

Вызов такой функции не содержит анонимных переменных, поэтому может использоваться совместно с оператором NOT.

На скриншоте показаны циклы, которые программа найдет для заданного Вами графа.