如何 - 图形着色在Prolog [英] How to - Graph Coloring in Prolog

问题描述

我试图在Prolog中创建简单的图形着色算法，但是我有点难以理解语言。我知道我想做什么 - 我想去一个顶点，找到所有其他顶点连接到它，检查我的顶点的颜色，并根据这一点，用不同的颜色着色其他顶点。我只是很难把它翻译成Prolog。如果它是一个C方言或Java，这将是一块蛋糕给我，但这是给我合适。

这是我到目前为止： / p>

  main： -  graph_coloring。 
 
％color_list（[蓝色，红色，绿色，黄色，白色]，颜色）。 
％vertex_list（[a，b，c，d]，vertices）。 
％edge_list（[（a，b），（b，c），（c，d）]，边缘）。 
 
％我们的图形
颜色（蓝色）。 
颜色（红色）。 
颜色（绿色）。 
颜色（黑色）。 
 color（white）。 
 
％graph（[a-b，b-c，b-d，c-d]）。 
 
 vertex（a）。 
 vertex（b）。 
 vertex（c）。 
 vertex（d）。 
 
％根据更改，因此在运行时被声明到侦听器中。 
 init_dynamic_facts： -  
 assertz（vertex_color（a，none）），
 assertz（vertex_color（b，none）），
 assertz b $ b assertz（vertex_color（d，none）），
 assertz（location（a））。 
 
 edge（a，b）。 
 edge（b，c）。 
 edge（b，d）。 
 edge（c，d）。 
 
 is_connect（A，B）： -  
 edge（A，B）。 
 is_connect（A，B）： -  
 edge（B，A）。 
 
连接（顶点）： -  
边缘（顶点，X）。 
连接（顶点）： -  
 edge（X，Vertex）。 
 
 move（Vertex）： -  
 retract（location（_）），
 asserta（location（Vertex））。 
 
 paint_vertex（Vertex，Color）： -  
 retract（vertex_color（Vertex，_）），
 asserta（vertex_color（Vertex，Color））。 
 
 find_vertex_color（Vertex）： -  
 vertex_color（Vertex，X）。 
 
 
 graph_coloring： -  
 
位置（Current_vertex），
 vertex_color（Current_vertex，Curr_color），
（Curr_color =：= > 
 connection（Current_vertex，Others），
 vertex_color（Others，Other_colors），
 paint_vertex（Current_vertex，
   
 
如何完成此算法？
 
 
 
（已编辑：graph_coloring下的更多代码）
解决方案
我认为你试图以一种对于Prolog程序不自然的方式来思考;也就是说，你不想使用递归）想到了以下是，但是可能不是完全正确的（它晚了，我没有一个良好的信誉，当试图想到这样的时候... :)）
 
 
 
让我们假设你有下面的事实描述的图：
  edge（a，b）。 
 edge（b，c）。 
 edge（b，d）。 
 edge（c，d）。 
  
，可用的颜色为
 颜色（蓝色）。 
颜色（红色）。 
颜色（绿色）。 
  
（你只需要3种颜色来绘制平面图，所以让我们在这里使用3）。让我们假设你想要的答案是作为一个[顶点 - 颜色]列表，其中列表将包含图形的每个顶点的颜色。我相信以下是一个正确的解决方案：
 着色（[VC]）： -  
 color 
 \ + edge（V，_）。 
 coloring（[VC，V1-C1 | Coloring]）： -  
 color（C），
 edge（V，V1），
 V \ == V1，
着色（[V1-C1 |着色]），
 C1 \ == C. 
  
 
 $ b b 
第一个子句说如果没有从V到任何其他顶点的边，只需尝试所有可能的颜色。第二节说明顶点V将获得颜色C，并且如果存在从V到V1的边缘，则顶点V1将获得颜色C1，其中V 1 = V1和C 1 = C1。 （我还假设你的图是连接的，即没有顶点没有连接到其他顶点）。
 
 
 
因为我们只想要解决方案，颜色，我们将只保留长度| V |的列表，其中V是您具有的顶点集。您可以通过各种方式实现此限制;我更喜欢使用findall / 3：
  colors（X）： -  
 coloring b $ b findall（V，edge（V，_），List），
 length（List，Len），
 length（X，Len）。 
  
现在，通过咨询此程序并询问 |？ 
 
 
 
如果任何人发现一个问题，我几乎可以肯定存在的图形顶点的所有可能的颜色分配。上述解决方案，请告诉我们：）
 
 
 
 Spyros 
 
I'm trying to make the simple graph coloring algorithm in Prolog, but I'm having a bit of a hard time understanding the language. I know what I want to do - I want to go to a vertex, find all the other vertices connected to it, check my vertex's color, and depending on that, color the other vertices with different colors. I'm just having a hard time translating this to Prolog. If it was a C dialect or Java, it would be a piece of cake for me, but this is giving me fits.

This is what I have so far:
main:- graph_coloring.

%color_list([blue, red, green, yellow, white], colors).
%vertex_list([a, b, c, d], vertices).
%edge_list([(a,b),(b,c),(c,d)], edges).

%Our graph
color(blue).
color(red).
color(green).
color(black).
color(white).

%graph([a-b, b-c, b-d, c-d]).

vertex(a).
vertex(b).
vertex(c).
vertex(d).

%Subject to changing, so are asserted into listener at runtime.
init_dynamic_facts:-
    assertz(vertex_color(a, none)),
    assertz(vertex_color(b, none)),
    assertz(vertex_color(c, none)),
    assertz(vertex_color(d, none)),
    assertz(location(a)).

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

is_connect(A,B):-
    edge(A,B).
is_connect(A,B):-
    edge(B,A).

connections(Vertex):-
    edge(Vertex,X).
connections(Vertex):-
    edge(X,Vertex).

move(Vertex):-
    retract(location(_)),
    asserta(location(Vertex)).

paint_vertex(Vertex, Color):-
    retract(vertex_color(Vertex,_)),
    asserta(vertex_color(Vertex, Color)).

find_vertex_color(Vertex):-
    vertex_color(Vertex, X).


graph_coloring:-

    location(Current_vertex),
    vertex_color(Current_vertex, Curr_color),
    ( Curr_color =:= none ->
        connections(Current_vertex, Others),
        vertex_color(Others, Other_colors),
        paint_vertex(Current_vertex, 
How can I complete this algorithm?

(edited: more code under graph_coloring)
解决方案
I think you are trying to think in a way that is not natural for Prolog programs; that is, you are trying not to use recursion :) What I've came up with is the following, which however may not be entirely correct (it's late, and I don't have a good reputation when trying to think at times like this...:) )

Let's assume that you have the graph described by the following facts:
edge(a,b).
edge(b,c).
edge(b,d).
edge(c,d).
and that the available colors are
color(blue).
color(red).
color(green).
(you only need 3 colors to color a planar graph, so let's just use 3 here). Let's also assume that you want the answer to be given as a [Vertex-Color] list, where the list will contain a color for every vertex of your graph. I believe the following is a correct solution:
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.
The first clause says that if there is no edge from V to any other vertex, just try all possible colors. The second clause says that vertex V will get color C, and vertex V1 will get color C1 if there is an edge from V to V1, where V != V1 and C != C1. (I also assumed that your graph is connected, i.e. there are no vertices which are not connected to other vertices).

And since we only want solutions where all the vertices have colors, we will only keep lists of length |V|, where V is the set of vertices you have. You can implement this restriction in various ways; I prefer to use "findall/3":
colors(X) :-
        coloring(X),
        findall(V,edge(V,_),List),
        length(List,Len),
        length(X,Len).
Now, by consulting this program and asking |?- colors(X). you will get all the possible color assignments for the vertices of your graph.

If anyone finds a problem I am almost sure there exists in the above solution, please, do let us know :)

Spyros

                        
这篇关于如何 - 图形着色在Prolog的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！