; Asynchronous Backtracking for the graph-coloring problem
; Version 1.3, Septemper,2004.
; by Hong Jiang
; Jose M. Vidal

breed [ nodes ]
breed [ edges ]


edges-own [a b]
;each directed edge goes from a to b, for undirect edge a and b have no different

nodes-own [the-links the-neighbors message-queue agent-view my-constraints nogoods parent num-ok-msg num-nogood-msg ]
;the-links: list of linked neighbor nodes
;the-neighbors: list of neighbor nodes for sending message
;message-queue: message queue. New messages are added at the tail end.
;agent-view: agent's beliefs about others' color. A list indexed by their 'who'.
;my-constraints: color constraint
;nogoods: nogoods information
;parent: record the nogood message source
;num-ok-msg: number of ok? messages
;num-nogood-msg: number of nogood messages
;Instead of current-value we use 'color'.

globals [x-max y-max diam tot-edges color-list no-more-messages num-cycle failure spring-force spring-length mutual-repulsion friction] 
;color-list: list of colors to be used
;num-cycle: record the times of the update run
;failure: record the failure information

to setup  ; Setup the model for a run, build a graph.
  ca
  clear-output
  setup-globals
  setup-patches 
  setup-turtles 
  setup-random-graph
  graph-edges
  set spring-force .2
  set spring-length 5
  set mutual-repulsion 4
  set friction .25
end

;
to setup-globals  ; separate procedure for setting globals
  set diam 4
  set x-max max-pxcor - (diam / 2) + 1; 0.5
  set y-max max-pycor - (diam / 2) + 1; 0.5
  set-default-shape nodes "circle"
  set-default-shape edges "line"
  set tot-edges min list round (number-of-nodes * edge-ratio) 
                         ((number-of-nodes ^ 2 - number-of-nodes) / 2)
  set color-list n-values number-of-color [? * round (14 / (? + 1)) * 10 + 5]
  set num-cycle 0
  set failure false
end

to setup-patches
  ask patches [set pcolor white]
end

to setup-turtles
  create-nodes number-of-nodes [
    set color one-of color-list
    set label-color black
    set label who
    set size diam
    set the-links []
    set message-queue []
    set nogoods []
    setxy random-float (x-max) * (2 * (random 2) - 1)
          random-float (y-max) * (2 * (random 2) - 1)
    set num-ok-msg 0
    set num-nogood-msg 0
  ]
end

to setup-random-graph; Build a random graph without conflict
  let t 0
  let t1 0
  let g 0
  let tries 0
  
  set g (list turtle 1)
  while [length g < number-of-nodes] [
    set t item random length g g
    set t1 one-of nodes with [not member? self g and color != [color] of t]
    if (t1 != nobody) [
      ask t1 [connect-edge t]
      set g lput t1 g]
  ]
  set tries number-of-nodes * 10
  while [count edges < tot-edges and tries > 0] [
    set t  one-of nodes
    set t1 one-of nodes with [self != t and not member? [who] of t the-links and color != [color] of t]
    if t1 != nobody [ask t1 [connect-edge t]]
    set tries tries - 1
  ]
  if tries = 0 [
    show "Oops, I suppose to have higher edge density. :("
  ]
end

to graph-edges  ; Make a simple edge histogram
  set-current-plot "edge-distribution"
  set-plot-x-range 1  1 + max [length the-links] of nodes
  histogram [length the-links] of nodes
end

; The run procedure which makes the model take one step.
; It moves the nodes so that we get a better layout. You can click on a node and move it by hand.
;to layout 
;  locals[t]
;  if mouse-down? [
;    set t closest-xy mouse-xcor mouse-ycor nodes ;
;    while [mouse-down?] [
;      ask t [setxy mouse-xcor mouse-ycor]
;      no-display
;      ask edges with [a = t or b = t][adjust-edge]
;      display
;    ]
;  ]
;end

to layout 
  let t 0
  
  no-display
  step
  display
  if mouse-down? [
    set t closest-xy mouse-xcor mouse-ycor nodes ;
    while [mouse-down?] [
      ask t [setxy mouse-xcor mouse-ycor]
      no-display
      ask edges with [a = t or b = t][adjust-edge]
      step
      display
    ]
  ]
end

to step  ; Adjust the edges and nodes for one step of the model
  let delta 0
  
without-interruption [
  ask edges [
    set delta (spring-force * (size - spring-length)) / 2.0
    ask a [set heading towards-nowrap [b] of myself jump-nowrap delta]
    ask b [set heading towards-nowrap [a] of myself jump-nowrap delta]
  ]
  ask nodes [
    ask nodes with [self != myself] [
      set delta distance-nowrap myself
      set delta mutual-repulsion / (delta * delta)
      set heading towards-nowrap myself
      jump-nowrap (- delta)
    ]
  ]
  ask edges [adjust-edge]
]
end

to-report closest-xy [x y agent-set]  ; Return closest agent to x, y
  report min-one-of agent-set [distancexy-nowrap x y]
end

to connect-edge [other-node] ; node proc: attach an edge between self and other
  hatch 1 [
    set breed edges
    set a myself
    set b other-node
    ask a [set the-links lput [who] of [b] of myself the-links]
    ask b [set the-links lput [who] of [a] of myself the-links]
    set color black
    set label ""
    adjust-edge
  ]
end

to-report sign [num]
  ifelse num < 0 [report -1][report 1]
end

to jump-nowrap [dist] ; turtle proc: jump but don't wrap, bounce w/ friction instead
  let x 0
  let y 0
  
  set x xcor + dist * dx
  set y ycor + dist * dy
  if (abs x) > x-max [set x sign x * (x-max - (1 - friction) * ((abs x) - x-max))]
  if (abs y) > y-max [set y sign y * (y-max - (1 - friction) * ((abs y) - y-max))]
  setxy x y
end

to adjust-edge ; edge proc: reattach to a & b nodes
  setxy [xcor] of b [ycor] of b
  set heading towards-nowrap a
  fd diam / 2 
  
  setxy [xcor] of a [ycor] of a
  set size distance-nowrap b - diam
  set heading towards-nowrap b
  fd diam / 2 
  
  setxy [xcor] of a [ycor] of a
  jump (size / 2) + (diam / 2)
end

to-report make-list [n element]
  let i 0
  let lst 0
  
  set i 0
  set lst []
  while [i < n] [
    set lst fput element lst
    set i i + 1]
  report lst
end

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Asynchronous backtracking agorithm;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;initialize
to initialize
  clear-output
  set failure false
  set num-cycle 0
  clear-plot
  ask nodes [
    set color one-of color-list
    set the-neighbors the-links 
    set my-constraints []
    set nogoods []
    set message-queue []
    set num-ok-msg 0
    set num-nogood-msg 0
    set agent-view (make-list number-of-nodes -1) ;-1 means "I don't know".
    set agent-view replace-item who agent-view color
    set parent -1; means none
    
    ;drow message number
    set-current-plot "Messages"
    create-temporary-plot-pen (word "n-" who)
    set-plot-pen-color (who * 10 + 5) mod 140
    if trace [show (word "ok? " who " " color)]
    
    ask nodes with [member? who [the-neighbors] of myself and who > [who] of myself] [
      without-interruption [   
      set message-queue remove-duplicates lput (list "ok?" ([who] of myself) [color] of myself) message-queue]
    ] 
  ] 
  if trace [
    showtrace
    showmsg
  ]     
end

to update
  if (failure) [stop]
  set no-more-messages true
  set num-cycle num-cycle + 1
  ask nodes [
    if (not empty? message-queue)[
      set no-more-messages false]
  ]
  if (no-more-messages) [
    ask nodes [show (word who " " color)]
    print "Succeed"
    stop
  ]
  ask nodes [handle-message]
  ask nodes [
    set-current-plot "Messages"
    create-temporary-plot-pen (word "q"  who)
    plot num-ok-msg + num-nogood-msg    
  ]
  if (trace) [
    showtrace 
    showmsg
  ]  
end

to showtrace
    print "================"
    ask nodes [
      show (word "agent-view: " agent-view)
      show (word "nogood: "  nogoods)
    ]
end

to showmsg
  ask nodes [show message-queue]
end

to handle-message ;nodes proc
  let msg 0
  let tmp 0
  
  if (empty? message-queue) [stop]
  set msg retrieve-message
  if (first msg = "nogood")[
    set num-nogood-msg num-nogood-msg + 1
    handle-nogood-message (item 1 msg) (item 2 msg)
  ]
  if (first msg = "ok?") [
    set num-ok-msg num-ok-msg + 1
    handle-ok-message item 1 msg item 2 msg
    ]
end

to-report retrieve-message ;nodes proc
  let msg 0
  
  without-interruption [
    set msg first message-queue
    set message-queue butfirst message-queue]
  report msg
end

;when received ok? messages
to handle-ok-message [source scolor] ;nodes proc
    set agent-view (replace-item (source) agent-view scolor)
    set my-constraints []
    check-agent-view
end

;when received nogood messages
to handle-nogood-message [source nogoods-list] ;nodes prc
  let oldvalue 0
  let i 0
  
  set my-constraints (list item who nogoods-list);record myself as a constraints
  set i 0
  while [i < number-of-nodes][
    if (item i nogoods-list != -1 and (not member? i the-neighbors)) [
      if (i != who) [
        set agent-view replace-item i agent-view item i nogoods-list
        set the-neighbors lput i the-neighbors]]
    set i i + 1
  ]
  
  set parent source
  set oldvalue color
  check-agent-view
  if (oldvalue = color) [
    ask turtle source [
      without-interruption [ set message-queue lput (list "ok?" ([who] of myself) oldvalue) message-queue]
    ]
  ]  
end

to check-agent-view ;nodes proc
   let availablelist 0
  let i 0
  
   
   ;check agent-view and current-value
   without-interruption [
   set i 0
   while [i < length the-links] [ 
     if (((item (item i the-links) agent-view) != -1) );and (item i the-links) != parent
       [set my-constraints lput (item (item i the-links) agent-view) my-constraints
       ];color-of turtle i
     set i i + 1
   ]
   set parent -1
   if (member? color my-constraints)
   [
       set availablelist filter [not member? ? my-constraints] color-list
       ifelse (empty? availablelist) 
       [backtracking]
       [           
           set color min availablelist 
           set agent-view replace-item who agent-view color
           ask nodes with [member? who [the-neighbors] of myself and who > [who] of myself] [
             without-interruption [ 
             set message-queue lput (list "ok?" ([who] of myself) [color] of myself) message-queue]]
       ]
   ]]
   
end

to backtracking ;nodes proc
    let xj 0
  let newnogoods 0
  let i 0
  
    ;generate nogoods
    set newnogoods agent-view
    set newnogoods replace-item who newnogoods -1
    
    set i number-of-nodes - 1
    while [member? newnogoods nogoods] [
      while [i > 0 and item i newnogoods = -1 ][ set i i - 1]
      if (item i newnogoods = -1) ;nogoods is empty
      [
        set failure true
        show "no solution"
        stop
      ]
      set newnogoods replace-item i newnogoods -1
    ]

    ;find out target to send nogoods
    while [i > 0 and item i newnogoods = -1 ][ set i i - 1]
    if (item i newnogoods = -1) ;nogoods is empty
      [
        set failure true
        show "no solution"
        stop
      ]
    set nogoods lput newnogoods nogoods
    set xj turtle i
    ask xj [
       without-interruption [set message-queue lput (list "nogood" ([who] of myself) newnogoods) message-queue]
    ]
    set agent-view replace-item [who] of xj agent-view -1;
    set my-constraints []
    check-agent-view 
end

@#$#@#$#@
GRAPHICS-WINDOW
191
10
529
369
19
19
8.4103
1
10
1
1
1
0
1
1
1
-19
19
-19
19
0
1
1
ticks

CC-WINDOW
5
387
802
482
Command Center
0

BUTTON
1
112
65
145
Setup
setup
NIL
1
T
OBSERVER
NIL
NIL
NIL
NIL

BUTTON
70
112
135
145
Layout
layout
T
1
T
OBSERVER
NIL
NIL
NIL
NIL

SLIDER
1
10
188
43
number-of-nodes
number-of-nodes
2
100
24
1
1
NIL
HORIZONTAL

SLIDER
1
76
138
109
edge-ratio
edge-ratio
0.8
5
1.5
0.1
1
NIL
HORIZONTAL

PLOT
1
147
188
267
edge-distribution
edges/node
count
1.0
1.0
0.0
1.0
true
false
PENS
"default" 1.0 1 -16777216 true

MONITOR
138
76
188
129
edges
count edges
3
1
13

BUTTON
531
10
667
43
Initialize
initialize
NIL
1
T
OBSERVER
NIL
NIL
NIL
NIL

BUTTON
531
44
667
77
Update
update
NIL
1
T
OBSERVER
NIL
NIL
NIL
NIL

BUTTON
531
78
667
111
Update
update
T
1
T
OBSERVER
NIL
NIL
NIL
NIL

TEXTBOX
543
125
793
222
1- setup\n2- Layout until pretty\n3- Initialize\n4- Update
13
0.0
0

PLOT
532
187
732
366
Messages
NIL
NIL
0.0
10.0
0.0
1.0
true
false
PENS
"default" 1.0 0 -16777216 true

SLIDER
1
43
188
76
number-of-color
number-of-color
1
14
5
1
1
NIL
HORIZONTAL

MONITOR
107
269
188
322
num-ok-msg
sum ([num-ok-msg] of nodes)
3
1
13

MONITOR
78
320
188
373
num-nogood-msg
sum ([num-nogood-msg] of nodes)
3
1
13

SWITCH
1
269
104
302
trace
trace
1
1
-1000

MONITOR
2
320
73
373
NIL
num-cycle
3
1
13

@#$#@#$#@
Title: Graph Coloring using Asychronous Backtracking
Author: Hong Jiang, Jose M. Vidal
Description:
An implementation of the Asynchronous Backtracking algorithm from
<ul>
<li>Makoto Yokoo and Katsutoshi Hirayama. <a href="http://jmvidal.cse.sc.edu/lib/yokoo00a.html">Algorithms for Distributed Constraint Satisfaction: A Review</a>. <i>Autonomous Agents and Multi-Agent Systems,</i> 3(2):185--207, 2000.
</li>
</ul>
@#$#@#$#@
default
true
0
Polygon -7500403 true true 150 5 40 250 150 205 260 250

circle
false
0
Circle -7500403 true true 35 35 230

line
true
0
Line -7500403 true 150 0 150 301

none
true
0

@#$#@#$#@
NetLogo 4.0beta3
@#$#@#$#@
@#$#@#$#@
@#$#@#$#@
@#$#@#$#@
@#$#@#$#@
default
0.0
-0.2 0 0.0 1.0
0.0 1 1.0 0.0
0.2 0 0.0 1.0
link direction
true
0
Line -7500403 true 150 150 90 180
Line -7500403 true 150 150 210 180

@#$#@#$#@