Geek asks and answers

How to - colorize a graph in Prolog

I'm trying to make a simple graph coloring algorithm in Prolog, but it's a little difficult for me to understand the language. I know what I want to do - I want to go to the vertex, find all the other vertices associated with it, check the color of the vertices and, depending on this, color the other vertices with different colors. It’s just hard for me to translate this to Prolog. If it was a dialect of C or Java, for me it would be a piece of cake, but it gives me the opportunity.

This is what I still have:

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 execute this algorithm?

(edited: more code under graph_coloring)

+3
source share
2 answers

, , Prolog; :) , , : (, , ...:))

, , :

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


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

( 3 , , 3 ). , , [Vertex-Color], . , :

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.

, V , . , V C, V1 C1, V V1, V!= V1 C!= C1. ( , , .. , ).

, , | V |, V - , . ; "findall/3":

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

, |?- colors(X)., .

- , , , , :)

+2

, CSP SWI-Prolog. :

:- use_module(library(clpfd)). 

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

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

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


colorGraph(ColorList) :- 
  findall((X, Y), edge(X, Y), Edges),
  findall(X, vertex(X), Vertexes),
  findall(hasColor(X, _), member(X, Vertexes), ColorList),
  createConstraint(Edges,ColorList),
  colorNodes(ColorList).

createConstraint([],_).
createConstraint([(V1,V2)|RL],ColorList):-
  member(hasColor(V1,C1),ColorList),
  member(hasColor(V2,C2),ColorList),
  dif(C1,C2),
  createConstraint(RL,ColorList).

colorNodes([]).
colorNodes([hasColor(_,C)|Nodes]) :-
  color(C),
  colorNodes(Nodes).

color/1 , vertex/1 , edge/2 . , colorGraph(?List) , List - hasColor(Vertex, Color), Vertex - Color.

, , .

:- use_module(library(clpfd)).

SWI-Prolog , .

colorGraph(ColorList) :- 
  findall((X, Y), edge(X, Y), Edges),
  findall(X, vertex(X), Vertexes),
  findall(hasColor(X, _), member(X, Vertexes), ColorList),
  createConstraint(Edges,ColorList),
  colorNodes(ColorList).

colorGraph/1 . / , ColorList, , , ( ).

createConstraint([],_).
createConstraint([(V1,V2)|RL],ColorList):-
  member(hasColor(V1,C1),ColorList),
  member(hasColor(V2,C2),ColorList),
  dif(C1,C2),
  createConstraint(RL,ColorList).

createConstraint/2 , . , dif/2 CSP.

colorNodes([]).
colorNodes([hasColor(_,C)|Nodes]) :-
  color(C),
  colorNodes(Nodes).

colorNodes/1 . Prolog , .

, , colorGraph/1, :

?- colorGraph(L).
L = [hasColor(a, red), hasColor(b, blue), hasColor(c, green), hasColor(d, red), hasColor(e, red)] ;
L = [hasColor(a, red), hasColor(b, blue), hasColor(c, green), hasColor(d, red), hasColor(e, blue)] ;
L = [hasColor(a, red), hasColor(b, blue), hasColor(c, green), hasColor(d, red), hasColor(e, green)] ;
L = [hasColor(a, red), hasColor(b, green), hasColor(c, blue), hasColor(d, red), hasColor(e, red)] ;
L = [hasColor(a, red), hasColor(b, green), hasColor(c, blue), hasColor(d, red), hasColor(e, blue)] ;
L = [hasColor(a, red), hasColor(b, green), hasColor(c, blue), hasColor(d, red), hasColor(e, green)] ;
L = [hasColor(a, blue), hasColor(b, red), hasColor(c, green), hasColor(d, blue), hasColor(e, red)] ;
L = [hasColor(a, blue), hasColor(b, red), hasColor(c, green), hasColor(d, blue), hasColor(e, blue)] ;
L = [hasColor(a, blue), hasColor(b, red), hasColor(c, green), hasColor(d, blue), hasColor(e, green)] ;
L = [hasColor(a, blue), hasColor(b, green), hasColor(c, red), hasColor(d, blue), hasColor(e, red)] ;
L = [hasColor(a, blue), hasColor(b, green), hasColor(c, red), hasColor(d, blue), hasColor(e, blue)] ;
L = [hasColor(a, blue), hasColor(b, green), hasColor(c, red), hasColor(d, blue), hasColor(e, green)] ;
L = [hasColor(a, green), hasColor(b, red), hasColor(c, blue), hasColor(d, green), hasColor(e, red)] ;
L = [hasColor(a, green), hasColor(b, red), hasColor(c, blue), hasColor(d, green), hasColor(e, blue)] ;
L = [hasColor(a, green), hasColor(b, red), hasColor(c, blue), hasColor(d, green), hasColor(e, green)] ;
L = [hasColor(a, green), hasColor(b, blue), hasColor(c, red), hasColor(d, green), hasColor(e, red)] ;
L = [hasColor(a, green), hasColor(b, blue), hasColor(c, red), hasColor(d, green), hasColor(e, blue)] ;
L = [hasColor(a, green), hasColor(b, blue), hasColor(c, red), hasColor(d, green), hasColor(e, green)] ;
+1

More articles:


All Articles