Является ли граф деревом в прологе? - PullRequest
Новая
       24

Является ли граф деревом в прологе?

0 голосов
/ 18 апреля 2019

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

Мой вопрос: как мне получить решение?

Например, для этого графика?

График = [ab, bc, bd, cd] Я пытаюсь выяснить, как это работает.

stree(Graph,Tree):-
  subset(Graph, Tree),
  tree(Tree),
  covers(Tree, Graph).

tree(Tree):-
   connected(Tree),
   not hasacycle(Tree).

connected(Graph):-
   not(node(A, Graph),node(B,Graph), 
   not path(A,B,Graph,_)).

hasacycle(Graph):-
   adjacent(Node1,Node2,Graph), 
   path(Node1,Node2,Graph,[Node1,X,Y|_]).

covers(Tree,Graph):-
  not(node(Node,Graph),
  not node(Node,Tree)).

subset([],[]).
subset([X|Set],subset):-
 subset(Set,subset).
subset([X|Set],[X|subset]):-
 subset(Set, subset).

1 Ответ

0 голосов
/ 20 апреля 2019

Прямой ответ на ваш вопрос

Вы спросили, как проверить, является ли граф деревом в Прологе, специально для вашего примера графа:

test.pl: 

node(a,graph1).
node(b,graph1).
node(c,graph1).
node(d,graph1).

edge(a,b,graph1).
edge(b,c,graph1).
edge(b,d,graph1).
edge(c,d,graph1).

adjacent(X,Y,Graph) :-
  (edge(X,Y,Graph) ; edge(Y,X,Graph)).

travel(A,B,PathSuffix,Path,Graph) :-
  adjacent(A,B,Graph),
  Path = [B|PathSuffix].

travel(A,B,PathSuffix,Path,Graph) :-
  adjacent(A,C,Graph),
  C \== B,
  \+ member(C,PathSuffix),
  travel(C,B,[C|PathSuffix],Path,Graph).

path(A,B,Path,Graph) :-
  travel(A,B,[A],ReversedPath,Graph),
  reverse(ReversedPath,Path).

connected(Graph) :-
  not((
    node(A,Graph),
    node(B,Graph),
    not(path(A,B,_,Graph))
  )).

hascycle(Graph) :-
   node(A,Graph),
   node(B,Graph),
   adjacent(A,B,Graph), 
   path(A,B,[A,_,_|_],Graph).

tree(Graph) :-
   connected(Graph),
   not(hascycle(Graph)).

$ swipl
?- [test].
?- tree(graph1).
false.

Структура графика закодирована в атомах node и edge.

Правило path основано на этом этом примере .

Правила connected, hascycle и tree соответствуют правилам вашей программы.

Обратите внимание, что идентификаторы в верхнем регистре являются переменными: Graph является переменной, тогда как graph1 является константой.

Комментарии к вашему коду

Есть несколько проблем с кодом, который вы дали:

Не компилируется с SWI Prolog 8.0.1. Я должен был заменить использование без скобок not A на not(A). Также мне пришлось заменить использование формы not(A,B) на not((A,B)). Если ваша программа компилируется для вас, укажите, какой компилятор / интерпретатор Prolog вы используете.

Ваш код не содержит определения path, см. Приведенный выше пример.

Ваш код содержит дополнительное правило stree, предположительно проверяющее, является ли Tree связующим деревом из Graph, с правилами помощника cover и subset.

Определение subset полностью неверно: оно неудовлетворительно, кроме базового случая subset([],[]), поскольку subset, передаваемый в качестве аргумента, является константой, а не переменной. Я предполагаю, что вместо этого вам нужно правило subgraph(G1,G2), которое проверяет, что каждый узел G1 является узлом G2 и каждая пара смежных узлов в G1 также смежна в G2.

...