Обнаружение цикла в графике

Question

Нам дан график со следующими фактами:

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

И нас просят определить правило cycle(X), которое определяет, существует ли цикл, начинающийся с узла X.

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

Answer 1

Идея Арчи является хорошей отправной точкой, но она создаст бесконечный цикл, если при поиске пути найдет другой цикл.

Я также не использовал пролог годами, но вам понадобится что-то вроде path(X,Y,Visited), где вы будете отслеживать посещенные узлы, предотвращая бесконечные циклы.

Answer 2

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

cycle(X):- cycleh(X,[X]).
cycleh(X,Visited) :- edge(X,Y), (member(Y,Visited) -> !,true; cycleh(Y,[Y|Visited])).

Answer 3

Это должно сработать:

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

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

Хотя это, похоже, решение, подобное @ Gökhan Uras - великие умы думают одинаково! Или что-то B ^)

Основная логика в том, что у вас есть цикл, если текущий узел уже был посещен (первое предложение в предикате хелпера cycle/2. В этот момент мы сокращаем (!) И объявляем успех. Причина сокращения ( !) заключается в том, что без него возврат в исходное состояние приведет к повторному посещению уже посещенного узла и, следовательно, к бесконечному набору циклов.

Если текущий узел не был посещен, мы берем ребро, привязанное к текущему узлу, и посещаем его. Возвращение ко второму предложению cycle/2 переходит к следующему ребру, поэтому, когда определенный путь исчерпан, cycle/2 возвращается и пробует другой путь.

Answer 4

Если ваша система Prolog имеет прямой цепной преобразователь, вы можете использовать его для определения циклов. Но будьте осторожны, он может съесть довольно много памяти, поскольку он будет генерировать и хранить path/2 факты.

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

:- forward edge/2.
:- forward path/2.

path(X,Y) :- edge(X,Y), \+ path(X,Y).
path(X,Y) :- edge(X,Z), path(Z,Y), \+ path(X,Y).
cycle(X) :- path(X,X).

Чтобы сделать пример немного более интересным в отношении результата, я опустил edge(d,d). Вот примерный прогон:

?- postulate(edge(a,b)), postulate(edge(a,c)), postulate(edge(b,a)),    
postulate(edge(c,d)), postulate(edge(d,e)), postulate(edge(e,f)), 
postulate(edge(f,g)), postulate(edge(g,e)), cycle(X).
X = a ;
X = b ;
X = e ;
X = f ;
X = g

Предикат postulate/1 здесь публикует событие и поддерживает работу пропагатора прямого цепочника. Порядок написания ваших форвардных правил зависит от используемой вами библиотеки Prolog.

П.С .: По-прежнему проводятся исследования:
http://x10.sourceforge.net/documentation/papers/X10Workshop2011/elton_slides.pdf

Answer 5

Я не использовал Пролог в течение некоторого времени, но вот мой подход к этой проблеме.

Вы можете создать правило path(X,Y), которое проверяет, существует ли путь от узла X до Y.Путь - это одно ребро или ребро, ведущее к пути.Имея это, легко найти цикл, начинающийся с узла X - это будет просто path(X,X).Вот моя реализация (взята из макушки головы и не обязательно правильная, но дает идею):

path(X,Y) :- edge(X,Y).
path(X,Y) :- edge(X,Z), path(Z,Y).

cycle(X) :- path(X,X).

Answer 6

Прошло много времени с тех пор, как я использовал Prolog, но, возможно, этот подход будет работать: A path - это последовательность ребер, где каждое ребро начинается на узле, на котором закончилось предыдущее ребро (например, a -> b , б -> в, в -> г). Тривиальный путь - это одно ребро, и более сложные пути можно сформировать, взяв существующий путь и добавив к нему ребро. Цикл - это путь, который начинается и заканчивается в одном и том же узле. Можете ли вы использовать эти определения для построения ваших правил Пролога?