Advertisement
Guest User

Untitled

a guest
Jan 23rd, 2020
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.99 KB | None | 0 0
  1. %
  2. % Let V(G) be a set of vertices of the graph G, let N(v)
  3. % be a set of all neighbours of the vertex v in V, and
  4. % let a coloring be any assignment of the form V -> Colors,
  5. % where Colors = {1,2,3,...}. Find a coloring, which uses
  6. % a minimal number of colors, such that all sums of colors
  7. % of N(v) for every vertex v are pairvise distinct.
  8. % coloring([[2,3,4,5],[1,3],[1,2,4],[1,3,5],[1,4]],L).
  9. %
  10.  
  11. :- use_module(library(clpfd)).
  12.  
  13. coloring2(Graph,Coloring) :-
  14. length(Graph,N),
  15. length(Coloring,N),
  16. length(Tints,N),
  17. Cn in 1..N,
  18. labeling([ff], [Cn]),
  19. Coloring ins 1..Cn,
  20. constr(Graph,Coloring,Tints),
  21. all_different(Tints),
  22. labeling([ff], Tints).
  23.  
  24. constr(Graph,Coloring,Tints) :-
  25. maplist(vert_sum(Coloring),Graph,Tints).
  26.  
  27. vert_sum(VertexColoring,VertNeighInds, VertSum) :-
  28. maplist(ind_to_vert(VertexColoring),VertNeighInds,VertNeighs),
  29. sum(VertNeighs, #=, VertSum).
  30.  
  31. ind_to_vert(VertexColoring,VertI,Vert) :-
  32. nth1(VertI,VertexColoring,Vert).
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement