Печать всех циклов графика для указанного узла графика, Пролог

Question

Я новичок в мире Пролога. Я пытаюсь написать предикат для печати всех циклов графика для указанного узла графика, который является элементом данного узла. Мой график выглядит так.

edge(a,e). 
edge(e,d). 
edge(d,c). 
edge(c,b). 
edge(b,a). 
edge(d,a). 
edge(e,c). 
edge(f,b). 

cycle(X) :- 
    cycle(X, []). 

cycle(Curr, Visited) :- 
    member(Curr, Visited), 
    !. 
cycle(Curr, Visited) :- 
    edge(Curr, Next), 
    cycle(Next, [Curr|Visited]). 

К сожалению, сейчас я не могу найти цикл для конкретного узла. Например, я ищу все циклы для узла d.

Answer 1

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

Циклы, которые происходят от узла

Это не так сложно, вы уже используете аккумулятор, вы просто нужен механизм, который когда-то цикл найден, верните аккумулятор в качестве цикла. Вы можете сделать это, предоставляя дополнительный параметр cycle:

cycle(Node,Cycle) :- 
    cycle(Node,[],Cycle). 

cycle(Curr,Visited,Cycle) :- 
    member(Curr,Visited), 
    !, 
    reverse([Curr|Visited],Cycle). 
cycle(Curr,Visited,Cycle) :- 
    edge(Curr,Next), 
    cycle(Next,[Curr|Visited],Cycle). 

В этой реализации я использовал reverse/2, так как это даст вам правильный порядок узлов (краевой-накрест). Если вы не заинтересованы в этом (например, вы только хотите, чтобы проанализировать цикл, и вы можете проанализировать в обратном направлении, вы можете просто заменить Cycle в первом пункте cycle/3 с [Curr|Visited].

Проблема заключается в том, однако, что если вы вызываете этот предикат, он возвращает:.

?- cycle(d,Cycle). 
Cycle = [d, c, b, a, e, d] ; 
Cycle = [d, c, b, a, e, c] ; 
Cycle = [d, a, e, d] ; 
Cycle = [d, a, e, c, b, a]. 

Таким образом, она не ищет циклы где d является частью цикла самих по себе, он ищет для всех циклов, которые могут происходящих из d Это, вероятно, не то, что вы хотите.

Циклы с данным узлом

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

cycle(Node,Cycle) :- 
    edge(Node,Next), 
    cycle(Node,Next,[Node],Cycle). 

Так вот мы смотрим на каждый edge/2 происходящий из Node и мы вызываем cycle/4 с начальным Node (чтобы проверить, когда мы нашли цикл), узел Next, список посещенных [Node] s и параметр Cycle для возврата найденных циклов.

В настоящее время существует три возможных варианта cycle/4:

• Приходим исходный узел, в этом случае мы нашли цикл, где Node является частью из, мы обработка аналогична первой версии:

  cycle(Curr,Curr,Visited,Cycle) :- 
      !, 
      reverse([Curr|Visited],Cycle). 
  

• мы прибываем в узле мы уже посетили: Curr элемент Visited, в этом случае мы должны прекращаться поиск: в противном случае мы будем цикл двутавровой nfinite количество раз:

  cycle(_,Curr,Visited,_) :- 
      member(Curr,Visited), 
      !, 
      fail. 
  

  fail предикат, который гласит ветвь терпит неудачу. Это может быть полезно, потому что теперь мы указываем, как это может произойти.

• Наконец, мы просто посетили другой край и попытаться найти следующий узел:

  cycle(Node,Curr,Visited,Cycle) :- 
      edge(Curr,Next), 
      cycle(Node,Next,[Curr|Visited],Cycle). 
  

Полная версия:

cycle(Node,Cycle) :- 
    edge(Node,Next), 
    cycle(Node,Next,[Node],Cycle). 

cycle(Curr,Curr,Visited,Cycle) :- 
    !, 
    reverse([Curr|Visited],Cycle). 
cycle(_,Curr,Visited,_) :- 
    member(Curr,Visited), 
    !, 
    fail. 
cycle(Node,Curr,Visited,Cycle) :- 
    edge(Curr,Next), 
    cycle(Node,Next,[Curr|Visited],Cycle). 

, который генерирует:

?- cycle(d,Cycle). 
Cycle = [d, c, b, a, e, d] ; 
Cycle = [d, a, e, d] ; 

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

cycle(Node,Cycle) :- 
    edge(Node,Next), 
    cycle(Node,Next,[Node],Cycle). 

cycle(Curr,Curr,Visited,Cycle) :- 
    !, 
    reverse([Curr|Visited],Cycle). 
cycle(Node,Curr,Visited,Cycle) :- 
    \+ member(Curr,Visited), 
    edge(Curr,Next), 
    cycle(Node,Next,[Curr|Visited],Cycle). 

Где \+ означает не.

Answer 2

Что вы ищете, например, transitive-closure ... нет необходимости изобретать велосипед!

Просто опираться на проверенные и проверенный код, показанный в "Definition of a path/trail/walk" и определить:

 
in_cycle(R_2, AZ, Path) :-     % cf. " simple cycle " 
    First  = AZ, 
    Last  = AZ, 
    path (R_2, Path, First, ButLast),   % all "hops" but the last one ... 
    call (R_2, ButLast, Last).    % ... and here comes the last one 

Пример запроса # 1 с помощью SICStus Prolog 4.3.2:

 
| ?- in_cycle(edge, d, Path). 
Path = [d,c,b,a,e] ? ; 
Path = [d,a,e] ? ; 
no 

В образце запроса # 2 , мы смотрим на транзитивное замыкание symmetric closure от edge/2:

 
| ?- in_cycle(symm (edge), d, Path). 
Path = [d,c] ? ; 
Path = [d,c,b,a] ? ; 
Path = [d,c,b,a,e] ? ; 
Path = [d,c,e] ? ; 
Path = [d,c,e,a] ? ; 
Path = [d,a] ? ; 
Path = [d,a,e] ? ; 
Path = [d,a,e,c] ? ; 
Path = [d,a,b,c] ? ; 
Path = [d,a,b,c,e] ? ; 
Path = [d,e] ? ; 
Path = [d,e,c] ? ; 
Path = [d,e,c,b,a] ? ; 
Path = [d,e,a] ? ; 
Path = [d,e,a,b,c] ? ; 
no 

Все решения запроса # 1 также выполнить более общий запрос # 2 — монотонной Пролог ^{1, 2, 3} на работе :)