Prolog ,找到一个图的邻居
Prolog , find neighbors of a graph
给定一张图
G = [1 - 5, 2 - 4, 2 - 6, 3 - 4, 3 - 6, 3 - 9, 4 - 7, 5 - 7, 6 - 7, 6 - 8, 6 - 9]
我必须找到每个节点的所有邻居,并用这种形式创建一个列表
Graph = [(1, [5]), (2, [4, 6]), (3, [4, 6, 9]), (4, [2, 3, 7]), (5, [1, 7]), (6, [2, 3, 7, 8, 9]), (7, [4, 5, 6]), (8, [6]), (9, [3, 6])].
这是我的方法:
search_for_neighbors(Ne,V,Ne,V).
search_for_neighbors(V,V,Ne,Ne).
search_for_neighbors(_,_,_,0).
neigh(_,[],_).
neigh(N,[(V - Ne)|T],Graph) :-
neigh(N,T,Graph1),
search_for_neighbors(N,V,Ne,Result),
add_first(Result,Graph1,Graph).
allneigh(0,_,_).
allneigh(N,G,L) :-
N1 is N - 1,
allneigh(N1,G,L1),
neigh(N,G,L2),
add_last((N,L2),L1,L).
add_first(0, L, L).
add_first(X, L, [X|L]).
add_last(X, [], [X]).
add_last(X, [Y|L1], [Y|L2]):- add_last(X,L1,L2).
我运行我的序言代码:
?- allneigh(9,[1 - 5, 2 - 4, 2 - 6, 3 - 4, 3 - 6, 3 - 9, 4 - 7, 5 - 7, 6 - 7, 6 - 8, 6 - 9],G).
这是我的结果,
G = [(1, [5|_464]), (2, [4, 6|_508]), (3, [4, 6, 9|_556]), (4, [2, 3, 7|_606]), (5, [1, 7|_658]), (6, [2, 3, 7, 8, 9|_712]), (7, [4, 5, 6|_769]), (8, [6|_827]), (9, [3, 6|_883])]
为什么我会有这种行为?
简答:因为neigh/3
第一行第二个下划线(_
):
neigh(_,[],_).
% ^ culprint
由于您对该部分进行了递归,因此您生成的所有列表都是 开放式:
?- neigh(N,[1 - 5, 2 - 4, 2 - 6, 3 - 4, 3 - 6, 3 - 9, 4 - 7, 5 - 7, 6 - 7, 6 - 8, 6 - 9],L).
N = 9,
L = [3, 6|_G4581] ;
N = 9,
L = [0, 3, 6|_G4581] ;
N = 9,
L = [0, 3, 6|_G4581] ;
N = 9,
L = [0, 0, 3, 6|_G4581] ;
您可以使用空列表进行快速修复,例如:
neigh(_,[],[]).
但还有更多问题:
add_first/3
即使添加 0
也会回溯,因为 add_first/3
的第二行确实 not 排除了 X
0
.
- 你为什么要生成一个
0
?
总的来说,我会说代码并不多 "declarative" 并且使用了很多约定(比如使用 0
)来过滤掉极端情况和边缘情况。您还使用 add_last/3
等,这通常是您想避免的,因为它效率很低。
使用内置的解决方案
让我们首先定义一个辅助函数 range(N,L).
,它针对给定的 N
,生成一个列表 L=[1,2,...,N]
:
range(N,L) :-
range(1,N,L).
range(I,N,[]) :-
I > N.
range(I,N,[I|L]) :-
I =< N,
I1 is I+1,
range(I1,N,L).
现在我们可以使用一个复杂的one-liner来构造这样一个图:
allneigh(N,G,L) :-
range(N,Vs),
findall((X,Ys),
setof(Y,(member(X,Vs),(member(X-Y,G);member(Y-X,G))),Ys),
L).
给出:
?- allneigh(9,[1 - 5, 2 - 4, 2 - 6, 3 - 4, 3 - 6, 3 - 9, 4 - 7, 5 - 7, 6 - 7, 6 - 8, 6 - 9],G).
G = [ (1, [5]), (2, [4, 6]), (3, [4, 6, 9]), (4, [2, 3, 7]), (5, [1, 7]), (6, [2, 3|...]), (7, [4|...]), (8, [...]), (..., ...)] [write]
G = [ (1, [5]), (2, [4, 6]), (3, [4, 6, 9]), (4, [2, 3, 7]), (5, [1, 7]), (6, [2, 3, 7, 8, 9]), (7, [4, 5, 6]), (8, [6]), (9, [3, 6])] ;
(第二行只是全写的输出)
另一种方法是使用 foldl :
:- use_module(library(lambda)).
all_neighbors(G, N) :-
foldl(\X^Y^Z^(X = A - B,
( select((A,V), Y, Y1)
-> append(V, [B], V1),
sort([(A,V1) | Y1], Y2)
; sort([(A,[B])| Y], Y2)),
( select((B,W), Y2, Y3)
-> append(W, [A], V2),
sort([(B,V2)|Y3], Z)
; sort([(B,[A]) | Y2], Z))),
G, [], N).
结果
?- all_neighbors( [1-5,2-4,2-6,3-4,3-6,3-9,4-7,5-7,6-7,6-8,6-9], N).
N = [(1,[5]),(2,[4,6]),(3,[4,6,9]),(4,[2,3,7]),(5,[1,7]),(6,[2,3,7,8,9]),(7,[4,5,6]),(8,[6]),(9,[3,6])].
给定一张图
G = [1 - 5, 2 - 4, 2 - 6, 3 - 4, 3 - 6, 3 - 9, 4 - 7, 5 - 7, 6 - 7, 6 - 8, 6 - 9]
我必须找到每个节点的所有邻居,并用这种形式创建一个列表
Graph = [(1, [5]), (2, [4, 6]), (3, [4, 6, 9]), (4, [2, 3, 7]), (5, [1, 7]), (6, [2, 3, 7, 8, 9]), (7, [4, 5, 6]), (8, [6]), (9, [3, 6])].
这是我的方法:
search_for_neighbors(Ne,V,Ne,V).
search_for_neighbors(V,V,Ne,Ne).
search_for_neighbors(_,_,_,0).
neigh(_,[],_).
neigh(N,[(V - Ne)|T],Graph) :-
neigh(N,T,Graph1),
search_for_neighbors(N,V,Ne,Result),
add_first(Result,Graph1,Graph).
allneigh(0,_,_).
allneigh(N,G,L) :-
N1 is N - 1,
allneigh(N1,G,L1),
neigh(N,G,L2),
add_last((N,L2),L1,L).
add_first(0, L, L).
add_first(X, L, [X|L]).
add_last(X, [], [X]).
add_last(X, [Y|L1], [Y|L2]):- add_last(X,L1,L2).
我运行我的序言代码:
?- allneigh(9,[1 - 5, 2 - 4, 2 - 6, 3 - 4, 3 - 6, 3 - 9, 4 - 7, 5 - 7, 6 - 7, 6 - 8, 6 - 9],G).
这是我的结果,
G = [(1, [5|_464]), (2, [4, 6|_508]), (3, [4, 6, 9|_556]), (4, [2, 3, 7|_606]), (5, [1, 7|_658]), (6, [2, 3, 7, 8, 9|_712]), (7, [4, 5, 6|_769]), (8, [6|_827]), (9, [3, 6|_883])]
为什么我会有这种行为?
简答:因为neigh/3
第一行第二个下划线(_
):
neigh(_,[],_).
% ^ culprint
由于您对该部分进行了递归,因此您生成的所有列表都是 开放式:
?- neigh(N,[1 - 5, 2 - 4, 2 - 6, 3 - 4, 3 - 6, 3 - 9, 4 - 7, 5 - 7, 6 - 7, 6 - 8, 6 - 9],L).
N = 9,
L = [3, 6|_G4581] ;
N = 9,
L = [0, 3, 6|_G4581] ;
N = 9,
L = [0, 3, 6|_G4581] ;
N = 9,
L = [0, 0, 3, 6|_G4581] ;
您可以使用空列表进行快速修复,例如:
neigh(_,[],[]).
但还有更多问题:
add_first/3
即使添加0
也会回溯,因为add_first/3
的第二行确实 not 排除了X
0
.- 你为什么要生成一个
0
?
总的来说,我会说代码并不多 "declarative" 并且使用了很多约定(比如使用 0
)来过滤掉极端情况和边缘情况。您还使用 add_last/3
等,这通常是您想避免的,因为它效率很低。
使用内置的解决方案
让我们首先定义一个辅助函数 range(N,L).
,它针对给定的 N
,生成一个列表 L=[1,2,...,N]
:
range(N,L) :-
range(1,N,L).
range(I,N,[]) :-
I > N.
range(I,N,[I|L]) :-
I =< N,
I1 is I+1,
range(I1,N,L).
现在我们可以使用一个复杂的one-liner来构造这样一个图:
allneigh(N,G,L) :-
range(N,Vs),
findall((X,Ys),
setof(Y,(member(X,Vs),(member(X-Y,G);member(Y-X,G))),Ys),
L).
给出:
?- allneigh(9,[1 - 5, 2 - 4, 2 - 6, 3 - 4, 3 - 6, 3 - 9, 4 - 7, 5 - 7, 6 - 7, 6 - 8, 6 - 9],G).
G = [ (1, [5]), (2, [4, 6]), (3, [4, 6, 9]), (4, [2, 3, 7]), (5, [1, 7]), (6, [2, 3|...]), (7, [4|...]), (8, [...]), (..., ...)] [write]
G = [ (1, [5]), (2, [4, 6]), (3, [4, 6, 9]), (4, [2, 3, 7]), (5, [1, 7]), (6, [2, 3, 7, 8, 9]), (7, [4, 5, 6]), (8, [6]), (9, [3, 6])] ;
(第二行只是全写的输出)
另一种方法是使用 foldl :
:- use_module(library(lambda)).
all_neighbors(G, N) :-
foldl(\X^Y^Z^(X = A - B,
( select((A,V), Y, Y1)
-> append(V, [B], V1),
sort([(A,V1) | Y1], Y2)
; sort([(A,[B])| Y], Y2)),
( select((B,W), Y2, Y3)
-> append(W, [A], V2),
sort([(B,V2)|Y3], Z)
; sort([(B,[A]) | Y2], Z))),
G, [], N).
结果
?- all_neighbors( [1-5,2-4,2-6,3-4,3-6,3-9,4-7,5-7,6-7,6-8,6-9], N).
N = [(1,[5]),(2,[4,6]),(3,[4,6,9]),(4,[2,3,7]),(5,[1,7]),(6,[2,3,7,8,9]),(7,[4,5,6]),(8,[6]),(9,[3,6])].