Prolog 中无向平面图的着色

Question

我有一个用 3 种颜色为图形着色的程序，相邻节点需要有不同的颜色。

我的问题是，它仅适用于有向图，当我使用无向图时，它会因堆栈溢出而失败。我知道有一些错误，你能帮忙吗我让它适用于非定向图？

最后的findall/3也有问题。我需要将其更改为查找所有节点，而不仅仅是带有 edge(V,_) 的节点，但我不知道该怎么做。我是初学者，我需要简单的解决方案。谢谢

edge(1,2).
edge(2,3).
edge(2,4).
edge(3,4).

%for making the non-oriented graph I tried to use nonedge(X, Y) :- edge(X, Y).
%                                                 nonedge(X, Y) :- edge(Y, X).

color(blue).                                
color(red).
color(green).

coloring([V-C]) :-
   color(C),
   \+ edge(V,_).
coloring([V-C,V1-C1|Coloring]) :-
   color(C),
   edge(V, V1),
   V \== V1,
   coloring([V1-C1|Coloring]),
   C1 \== C.

colors(X) :-                      
   coloring(X),
   findall(V, edge(V,_), List),
   length(List, Len),
   length(X, Len).

Answer 1

该代码也不适用于循环。它只检查前一个是否不一样。但是在你的例子中 2 -> 3 -> 4 -> 2 -> .. 永远不会结束。

此外，如果您的图表断开连接，它永远不会 return 整个图表。

出于这两个原因，我建议采用完全不同的方法，首先找到所有唯一的顶点。然后给它们分配一个颜色，并检查之前设置的颜色是否与设置的颜色冲突。

colors(Colored) :-
        findall(U,edge(U,_),Vertices), 
        list_to_set(Vertices, UniqueVertices), %% find all unique vertices
        coloring(UniqueVertices,[], Colored). %% color them

着色谓词如下所示：

coloring([],Acc,Acc). %% base case for empty list
coloring([H|T],Acc,AccRes) :-
    color(C), %% pick a valid color
    not((edge(H, V), member(V-C,Acc))), %% No linked vertex should have the same color
    coloring(T,[H-C|Acc],AccRes). %% Color the rest of the vertices

此代码使用了一个 accumulator 来保存先前设置的 vertex-color 组合。

Answer 2

在这个答案中，我们表示图形数据的方式与 OP 描述的方式不同。

相反，图是 Id-Neibs 对的列表，其中 Neibs 是相邻节点 Id 的列表，如 type-check 谓词所定义 is_graph/1（显示在答案末尾）。

要为图表着色，我们使用 clpfd:

:- use_module(library(clpfd)).

graph_coloring(G0, Zs) :-
   (  is_graph(G0)
   -> maplist(node_augmented_color, G0, G, Zs),
      maplist(agraph_coloring_outer(G), G)
   ;  throw(error(domain_error(graph,G0),_))
   ).

node_augmented_color(ID-Neibs, t(ID,Color,Neibs), Color).

agraph_coloring_outer(G, t(_,Color_v,Neibs_v)) :-
   maplist(agraph_coloring_inner(G,Color_v), Neibs_v).

agraph_coloring_inner(G, Color_x, Id_y) :-
   member(t(Id_y,Color_y,_), G),
   Color_x #\= Color_y.

示例查询使用 SWI-Prolog 8.0.0:

?- graph_coloring([1-[2],2-[1,3,4],3-[2,4],4-[2,3]], Zs),
   Zs ins 1..3,
   labeling([], Zs).
Zs = [1,2,1,3] ;
Zs = [1,2,3,1] ;
Zs = [1,3,1,2] ;
Zs = [1,3,2,1] ;
Zs = [2,1,2,3] ;
Zs = [2,1,3,2] ;
Zs = [2,3,1,2] ;
Zs = [2,3,2,1] ;
Zs = [3,1,2,3] ;
Zs = [3,1,3,2] ;
Zs = [3,2,1,3] ;
Zs = [3,2,3,1] ;
false.

定义type-check is_graph/1（基于 and distinct/1）写：

is_graph(G) :-
   iwhen(ground(G), is_graph_aux(G)).

is_graph_aux(G) :-
   maplist(pair_key, G, Nodes),
   distinct(Nodes),
   maplist(is_graph_aux_outer(G), G).

pair_key(K-_, K).

is_graph_aux_outer(G, E-Xs) :-
   distinct(Xs),
   maplist(is_graph_aux_inner(G,E), Xs).

is_graph_aux_inner(G, E, X) :-
   member(X-Ys, G),
   member(E, Ys).

Prolog 中无向平面图的着色

Coloring of a non-oriented planar graph in Prolog

graph-theory

prolog

graph-coloring