; Asynchronous Backtracking for the graph-coloring problem with message manager
; Version 1.4, Oct.,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 num-ok-msg num-nogood-msg];nogoodset okset]
;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 initial-value n-adds test 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
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 [? * 10 + 5]
  set num-cycle 0
  set n-adds 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;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;initial constraints, nodes proc
to setconstraints
  let i 0
  let j 0
  let tmp 0
  
    set my-constraints []
    set i 0
    without-interruption [ 
    while [i < number-of-color] [
      set tmp []
      set j 0
      while [j < length the-links] [
        set tmp lput (list (list item j the-links i)) tmp
        set j j + 1
      ]
      set my-constraints lput tmp my-constraints
       set i i + 1
    ]]
end

;initialize
to initialize
  ;locals [i j tmp]
  clear-output
  set failure false
  set num-cycle 0
  clear-plot
  set initial-value (make-list number-of-nodes -1)
  set n-adds 0
  ask nodes [
    set color one-of color-list
    set initial-value replace-item who initial-value color
    set the-neighbors the-links 
    setconstraints
    ;show my-constraints
    set nogoods []
    set message-queue []
    ;for new algorithm
    ;set okset []
    ;set nogoodset []
    
    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
    
    ;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)]
    graph-edges

    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

;reset
to reset
  clear-output
  set failure false
  set num-cycle 0
  set n-adds 0
  clear-plot
  ask nodes [
    set color item who initial-value
    set the-neighbors the-links 
    setconstraints
    set nogoods []
    set message-queue []
    ;for new algorithm
    ;set okset []
    ;set nogoodset []

    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
    
    ;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"
    set test 0
    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 message-manage message
;	If message is an ok message
;If message content source is in the ok-message set
;Update ok-message set;
;		Else add the content to ok-message set;
;	Else if message is a nogood message		
;		Add content to nogood-message set
;	End if;

;Procedure handle-message
;	If message-queue empty then stop;
;If ok-message set not empty
;		Update local-view;
;	End if;
;	If nogood-message set not empty
;		Record non-neighbor nodes to local-view;
;		Record new constaints
;	End if;
;Check-local-view;

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
    if (item source agent-view != scolor) [
    set agent-view (replace-item (source) agent-view scolor)
    check-agent-view]
end

;update my-constraints; nodes proc
to updateConstraints [nogoodlist] ;tested
  let i 0
  let index 0
  let tmp 0
  let c-set 0
  
  without-interruption [
  foreach nogoodlist [
    ;set tmp remove-duplicates ?
    set index first filter [first ? = who] ? 
    set tmp remove index ?
    ;if (empty? tmp) [set tmp [[]]]
    set c-set item (last index) my-constraints
    set i 0
    while [i < length c-set] [
      ifelse (isSubset item i c-set tmp) [
        set i length c-set 
        set tmp [[]];tmp shouldn't be added
      ][
      ifelse (isSubset tmp item i c-set) [
        set c-set remove item i c-set c-set
      ][set i i + 1]]
    ]
    if (tmp != [[]]) [set c-set lput tmp c-set];and not empty? c-set
    set my-constraints replace-item last index my-constraints c-set
  ]]
end

;is A subset of B
to-report isSubset [aset bset]
  let a-b 0
  
  set a-b filter [not member? ? bset] aset
  ifelse (a-b = []) [report true][report false]
end

;update local view; nodes proc
to updateLocalView [nogoodlist] ;tested
  let index 0
  let tmp 0
  let c-set 0
  
  while [nogoodlist != []][
    set c-set first nogoodlist
    set nogoodlist butfirst nogoodlist
    set index filter [first ? = who] c-set 
    set tmp remove index c-set
    foreach tmp [
      if (addNeighbor and (not member? first ? the-neighbors)) [
        set n-adds n-adds + 1
        set the-neighbors lput first ? the-neighbors]
      set agent-view replace-item first ? agent-view item last ? color-list
    ]
  ]
end

;when received nogood messages
to handle-nogood-message [source nogoods-list] ;nodes prc
  let oldvalue 0
  let i 0
  
  updateConstraints nogoods-list
  updateLocalView nogoods-list
  
  ;set parent source
  set oldvalue color 
  ;show oldvalue
  check-agent-view
  if (oldvalue =  color ) [
    ;send turtle source (list "ok?" (who-of myself) oldvalue)
    ask turtle source [
      set message-queue lput (list "ok?" ([who] of myself) oldvalue) message-queue
    ]
  ]  
end

to-report isConsistent [cons i]
  let nogood 0
  let cs 0
  
  set nogood item i cons
  ifelse (empty? nogood) [report true] [report false]
end

to check-agent-view ;nodes proc
   let fl 0
  let availablelist 0
  let i 0
  let tmp 0
     
   
   set fl filterConstraints
   ;check agent-view and current-value
   ifelse (isConsistent fl (position color color-list)) [
   ;print "safa"
   ;show fl
   ] [
   ;print "hi"
   set availablelist []
   set i 0
   while [i < number-of-color][
     if (isConsistent fl i) [
       set availablelist lput i availablelist
       set i number-of-color
     ]
     set i i + 1
   ]
   
;   without-interruption [
;   set i 0
;   while [i < length the-links] [ 
;     set tmp (item (item i the-links) agent-view)
;     if ( tmp != -1 )
;       [set availablelist remove tmp availablelist
;       ];color-of turtle i
;     set i i + 1
;   ]
   ifelse (empty? availablelist) [
     backtracking
   ][
;     ifelse (not member? color availablelist) [
      set color item first availablelist color-list
      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]
      ]
;      ][
      ;print "consistent"
      ;show who
    ]
    ]
;   ]]
end

;filter constraints based on agent-view
to-report filterConstraints; need my-constraints and agent-view
  let cons 0
  let tmp 0
  let i 0
  let j 0
  let cl 0
  
  set i 0
  set cons []
  while [i < number-of-color] [
    set tmp item i my-constraints
    without-interruption [
    foreach tmp [ 
      set j 0 ; ? could be []
      while [j < length ?] [
      set cl item j ?
      ifelse (item (first cl) agent-view = -1 or (item (first cl) agent-view != item (last cl) color-list)) [
        set tmp remove ? tmp
        set j length ?
      ][
        set j j + 1
      ]]
    ]]
    set cons lput tmp cons
    set i i + 1
  ]
  report cons
end

to-report check-duplicate [nogood]
  let tmp 0
  let ttmp 0
  let maxl 0
  let l 0
  
  set tmp remove-duplicates nogood
  set maxl 1
  without-interruption [
  foreach tmp [
    set ttmp ?
    set l length filter [first ? = first ttmp] tmp
    if (l > maxl) [set maxl l]
  ]]
  ifelse (maxl > 1) [report []][report tmp] 
end

to-report gNogoods [newnogoods nogood cons l];node proc
  if (l = length cons) [   
    ;show check-duplicate nogood
    if (not empty? check-duplicate nogood) [
      set newnogoods lput check-duplicate nogood newnogoods
    ]
    report newnogoods
  ]
  without-interruption [
    ifelse (item l cons = [[]]) [set newnogoods gNogoods newnogoods (sentence nogood) cons (l + 1)]
    [foreach item l cons [
      set newnogoods gNogoods newnogoods (sentence ? nogood) cons (l + 1)
    ]]    
  ] 
  report newnogoods
end 

to backtracking ;nodes proc
  let newnogoods 0
  let tmp 0
  let i 0
  let xj 0
  let oldnogoods 0
  

  ;generate nogoods
  ;print "cons"
  ;show filterConstraints

  set newnogoods gNogoods [] [] filterConstraints 0
  ;print "newnogoods"
  ;show newnogoods
    
  if (newnogoods = []) [
      show "no solution"
      set failure true
      stop
  ]
  
  without-interruption [
    foreach newnogoods [
      set tmp sort-by [first ?1 > first ?2] ?
      ;show tmp
      set xj turtle first (first tmp)
      ;show xj
      ask xj [
       set message-queue lput (list "nogood" ([who] of myself) (list tmp)) message-queue
      ]
      set agent-view replace-item [who] of xj agent-view -1;     
    ]]
    
    check-agent-view 
end

;;;;;;;;;;;;;;;;;;;;;;;
;; Message Mechanism ;;
;;;;;;;;;;;;;;;;;;;;;;;

to MUpdate
  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"
    set test 0
    stop
  ]
  ask nodes [message-manage message-size]
  ask nodes [
    set-current-plot "Messages"
    create-temporary-plot-pen (word "q" who)
    plot num-ok-msg + num-nogood-msg    
  ]
  if (trace) [
    showtrace 
    ;showOkset
    ;showNogoodset
  ]  
end

to message-manage [ msize ] ; nodes proc
  let n 0
  let msg 0
  let nogoodset 0
  let source 0
  let oldvalue 0
  
  set n 0
  set nogoodset []
  set source []
  while [not empty? message-queue and n < msize][
    set msg retrieve-message
    if (first msg = "ok?") [
      set num-ok-msg num-ok-msg + 1
      set msg butfirst msg
      set agent-view (replace-item (first msg) agent-view (item 1 msg))
    ]
    if (first msg = "nogood") [
      set num-nogood-msg num-nogood-msg + 1
      set msg butfirst msg
      ;show msg
      set source lput first msg source
      set nogoodset (sentence nogoodset last msg)
    ]
    set n n + 1
  ]
  if (not empty? nogoodset) [
    updateLocalView nogoodset
    updateConstraints nogoodset
  ]
  set oldvalue color
  check-agent-view  
  if (oldvalue = color and not empty? source) [
    ask nodes with [member? who source] [
      set message-queue lput (list "ok?" ([who] of myself) oldvalue) message-queue
    ]
  ]      
end

to testing
  let m 0
  let c 0
  let cyc 0
  let ok 0
  let nogood 0
  let ncyc 0
  let nok 0
  let nnogood 0
  
  set c 0
  file-open "20.txt"
  while [c < 100] [
    setup
    initialize
    set m 0
    set test 1
    while [m = 0] [
      ifelse (num-cycle <= 200) [
        ifelse (test = 0) [
          set cyc num-cycle
          set ok sum ([num-ok-msg] of nodes)
          set nogood sum ([num-nogood-msg] of nodes)
          set m 1
        ]
        [update]]
      [initialize]
    ]
    set test 1
    reset
    while [m = 1] [
      ifelse (num-cycle <= 200) [
        ifelse (test = 0) [
          set ncyc num-cycle
          set nok sum ([num-ok-msg] of nodes)
          set nnogood sum ([num-nogood-msg] of nodes)
          ask turtle 0 [file-write cyc file-write ok file-write nogood file-write ncyc file-write nok file-type " " file-print nnogood]
          set c c + 1
          set m 0
        ]
        [MUpdate]]
      [set m 0]
    ]
  ]
  file-close
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
383
741
478
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
20
1
1
NIL
HORIZONTAL

SLIDER
1
76
138
109
edge-ratio
edge-ratio
0.8
5
2
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
608
43
Initialize
initialize
NIL
1
T
OBSERVER
NIL
NIL
NIL
NIL

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

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

TEXTBOX
543
125
695
236
1- setup\n2- Layout by using mouse\n3- Initialize\n4- Update
13
0.0
0

PLOT
532
190
732
369
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
13
3
1
1
NIL
HORIZONTAL

MONITOR
125
315
188
368
num-ok-msg
sum ([num-ok-msg] of nodes)
3
1
13

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

SWITCH
1
269
91
302
trace
trace
1
1
-1000

MONITOR
1
315
63
368
NIL
num-cycle
3
1
13

SWITCH
622
156
732
189
addNeighbor
addNeighbor
1
1
-1000

BUTTON
632
10
712
43
Reset
reset
NIL
1
T
OBSERVER
NIL
NIL
NIL
NIL

BUTTON
632
44
712
77
NIL
MUpdate
NIL
1
T
OBSERVER
NIL
NIL
NIL
NIL

BUTTON
632
78
712
111
NIL
MUpdate
T
1
T
OBSERVER
NIL
NIL
NIL
NIL

SLIDER
621
111
731
144
message-size
message-size
1
100
100
1
1
NIL
HORIZONTAL

MONITOR
63
315
125
368
NIL
n-adds
3
1
13

@#$#@#$#@
Title: Graph Coloring using Asychronous Backtracking with Message Manager
Author: Hong Jiang, Jose M. Vidal
Description:
An implementation of the Asynchronous Backtracking algorithm with Message Manager (MMABT) from
<ul>
<li>Hong Jiang and Jose M. Vidal. <a href="http://jmvidal.cse.sc.edu/lib/jiang05a.html">Reducing Redundant Messages in the Asynchronous Backtracking Algorithm</a>. In <i>Proceedings of the Sixth International Workshop on Distributed Constraint Reasoning,</i> 2005.</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

@#$#@#$#@