% P89 (**) Bipartite graphs % Write a predicate that finds out whether a given graph is bipartite. :- ensure_loaded(p80). % conversions :- ensure_loaded(p88). % connected_components/2 % is_bipartite(G) :- the graph G is bipartite is_bipartite(G) :- connected_components(G,Gs), checklist(is_bi,Gs). is_bi(graph(Ns,Es)) :- Ns = [N|_], alist_gterm(_,Alist,graph(Ns,Es)), paint(Alist,[],red,N). % paint(Alist,ColoredNodes,Color,ActualNode) % (+,+,+,+) paint(_,CNs,Color,N) :- memberchk(c(N,Color),CNs), !. paint(Alist,CNs,Color,N) :- \+ memberchk(c(N,_),CNs), other_color(Color,OtherColor), memberchk(n(N,AdjNodes),Alist), Pred =.. [paint,Alist,[c(N,Color)|CNs],OtherColor], checklist(Pred,AdjNodes). other_color(red,blue). other_color(blue,red).