I have a program for coloring graphs with 3 colors, neighbouring nodes need to have different colors.
My problem is, it is working only for directed graph, when I use non-directed graph it fails on stack overflow. I know there are some mistakes, could you help me to make it work for non-directed graph?
There is also problem with that findall/3 at the end. I need to change it to finding all nodes, not only nodes with edge(V,_) but I don't know exactly how to do that.
I'm beginner and I need the solution to be simple. Thanks.
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).
The code does not work with loops as well. It only checks if the previous is not the same. But in your example 2 -> 3 -> 4 -> 2 -> .. will never end.
Also if your graph is disconnected it will never return the entire graph.
For both reasons I would suggest a totally different approach, first find all unique vertices. Then assign them a color and check if no previously set colors conflict with the set colors.
colors(Colored) :-
findall(U,edge(U,_),Vertices),
list_to_set(Vertices, UniqueVertices), %% find all unique vertices
coloring(UniqueVertices,[], Colored). %% color them
The coloring predicate will look like:
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
This code uses an accumulator which hold the previously set vertex-color combinations.