答案集编程中的生成树

Question

对于下面描述的无向图，我试图得到它的生成树，然后将它的叶子与内部节点分开。你能帮我看看我的代码吗？

我希望在运行之后看到的代码类似于：

答案1：spanTree(1,2), spanTree(2,3), spanTree(3,4), leaf(1), leaf(4), internal(2), internal (3).

答案2：spanTree(1,2), spanTree(1,3), spanTree(3,4), leaf(2), leaf(4), internal(1), internal (3).

% undirected graph
edge(1,2).
edge(2,3).
edge(1,3).
edge(3,4).
vertex(X):- edge(X,Y).
vertex(X):- edge(Y,X).

%find spanning trees
spanTree(X,Y):- edge(X,Y).
spanTree(X,Y):- edge(Y,X).

start(1).

reached(X):-start(X).
reached(X):-reached(Y), spanTree(Y,X).
    
:-spanTree(X,Y), start(Y).
:-spanTree(X,Y), spanTree(X1,Y), X != X1.
:-vertex(X), not reached(X).

% degree of vertex
degree(X,D) :- vertex(X),D=#count {Y :spanTree(X,Y)}.

% leaves and internal vertices
{leaf(X):- spanTree(X,_),degree(X,D), D=1}:- vertex(X).
{internal(X):- spanTree(X,_),degree(X,D), D>1}:- vertex(X).

Answer 1

除非必要，否则我会避免计数。我在开始时镜像了边以实现无向图并且猜测 spanTree 也很重要。我在这里做了一个捷径：而不是说，边可能是一个 spantree-edge，当“构建”我说：对于每个节点（根除外）选择一个进入边作为 spantree-edge。
到达的部分几乎是复制和粘贴（这里做得很好），但我省略了前两个约束，因为它们已经被覆盖了。
internal/leaf分类也可以简化。派生内部节点很容易，叶子可以被非内部节点覆盖。

edge(1,2). edge(2,3). edge(1,3). edge(3,4).
% mirror edges
edge(Y,X) :- edge(X,Y).
vertex(X) :- edge(_,X).

% every node Y except root has exactly one ingoing edge
{ spanTree(X,Y) : edge(X,Y) } == 1:- vertex(Y), not root(Y).

root(1).
reached(X) :- root(X).
reached(X) :- reached(Y), spanTree(Y,X).
    
:- vertex(X), not reached(X).

% an internal node has an outgoing edge
internal(X) :- spanTree(X,_).
% a vertex which is not an internal is a leaf
leaf(X) :- vertex(X), not internal(X).

#show spanTree/2.
#show leaf/1.
#show internal/1.

输出

Answer: 1
internal(3) leaf(2) leaf(4) internal(1) spanTree(3,2) spanTree(1,3) spanTree(3,4)
Answer: 2
internal(3) leaf(2) leaf(4) internal(1) spanTree(1,2) spanTree(1,3) spanTree(3,4)
Answer: 3
internal(3) leaf(4) internal(1) spanTree(1,2) internal(2) spanTree(2,3) spanTree(3,4)
SATISFIABLE

答案集编程中的生成树

Spanning Trees in Answer Set Programming

graph

logic-programming

spanning-tree

answer-set-programming