CODEWITHSUNDEEP
prologgraph-coloring
user2585677
user2585677

Reputation: 149

How to color a graph

I have a question described below:

Write a prolog program that colors a graph. The colors are defined by the color/1 predicate and the graph by the clauses edge/2. You must write the predicate coloring(Coloring) that finds a coloring of the nodes node_1,..., node_n of the graph. A coloring is list [node_1/color_1,..., node_n/color_m] where color_1, ..., color_m are colors, that satisfies the property that the nodes of every edge have different colors.

Let us look at an example. Let color and edge be the predicates below.

% 2 colors
color(blue).
color(red).
% the edges
edge(1,2).
edge(1,3).
edge(2,4).
edge(5,2).

For this data, coloring(C) is satisfied. One solution is

C = [ 1/blue, 2/red, 3/red, 4/blue, 5/blue].

Write the predicate color below.

Actually, I just begin to do this practice. So I have no idea. I think four colors will be enough to color a graph. Maybe someone has asked the similar question. When I have some ideas I will post it quickly.

Upvotes: 1

Views: 1643

Answers (1)

joel76
joel76

Reputation: 5675

You need to know the names of the nodes. One way to do that is to use setof/3 :

setof(Node,X^Y^(edge(Node, X); edge(Y,Node)), LN)

X^Y means that X and Y must be used in the search but not for the result.

Now we built the list of the associations Node/Color using a predicate set_color(List_of_nodes, List_of_association).

An empty list of nodes gives an empty list of association !

set_color([], [])

Now, the process :

% we work with the current element of the list of nodes
set_color([H | T], [H/C | TC]) :-
    % we create the association for the rest of the list
    set_color(T, TC),
    % we choose the color
    color(C),
    % we check that two adjacent nodes of different colors
    forall(member(Node/Color, TC),
           (   (edge(Node, H) -> Color \= C; true),
           ( edge(H, Node) -> Color \= C; true))).

So you get :

% 2 colors
color(blue).
color(red).
% the edges
edge(1,2).
edge(1,3).
edge(2,4).
edge(5,2).

coloring(L) :-
    setof(Node,X^Y^(edge(Node, X); edge(Y,Node)), LN),
    set_color(LN, L).


set_color([], []).

set_color([H | T], [H/C | TC]) :-
    set_color(T, TC),
    color(C),
    forall(member(Node/Color, TC),
           (   (edge(Node, H) -> Color \= C; true),
           ( edge(H, Node) -> Color \= C; true))).

I forgot to say that Prolog with its backtrack does the job !

Upvotes: 2

Related Questions