; Asynchronous Backtracking Algorithm for the random binary CSPs
; by Ionel Muscalagiu ( mionel@fih.utt.ro )
; Jose M. Vidal and Hong Jiang
;The randomly generated (binary) CSPs are characterised by the 4-tuple (n, m,p1,p2),
;where n is the number of variables, m is the uniform domain size, p1 is the portion of
;the n * (n - 1) /2 possible constraints in the graph, and p2 is the portion of the m*m  value
;pairs in each constraint that are disallowed by the constraint. That is, p1 may be thought
;of as the density of the constraint graph, and p2 as the tightness of constraints.
;In generating a CSP (n, m,pl ,p2) exactly p1 * n * (n - 1)/2 constraints are randomly
;selected (rounded to the nearest integer), and for each constraint selected exactly p2 * m*m conflicting pairs of values are selected (again, rounded to the nearest integer). 

;
breeds [nodes edges weights]
;nodes = agents
;each undirected edge goes from a to b
edges-own [a b weight-a weight-b wa-turtle wb-turtle  number-of-edges ]

;links list of neighbor nodes (but links is a list of the 'who' of all nodes that have a constraint with me)
;the-neighbors the same but as an agentset
;neighbors-list is a list of the initial neighbors nodes 
;done boolean that says if node (agent) is done or not

;message-queue contains the incoming messages. We take new ones out from the head.
;current-view is a list indexed by node number [[color0 priority0] [color1 priority1] ...] colorl = -1 and priority = -1 if unknown.
;nogoods is a list of inconsistent colors [color0 color11 ... ] 
;messages-recieved is the number of messages this vertice has received.
;nogood_list is the list of nogood received
;nogood_sent_list is the list of nogood sent

nodes-own [links neighbors-list the-neighbors message-queue priority nogood_list nogood_sent_list
             extendend-neighbors colorn current-view nogoods messages-received_ok messages-received_nogood nr_constraintc 
             AgentC_Cost agent_nogood messages-received messages-received_nogoodold FlagList Forbidden_Pairs]

globals [x-max y-max diam friction tot-edges filename tick stoptick init-power-edges domain-color-list 
         total-conflict-pairs no-more-messages done tmp nr_cicluri nn] 

to setup-globals  ; separate procedure for setting globals
  locals [i max-edges]
  set diam 4
  set tick 0
  set stoptick -2  ; set to some number to stop, generally for image collections
  set x-max screen-edge-x - (diam / 2) + 1; 0.5
  set y-max screen-edge-y - (diam / 2) + 1; 0.5
  set filename "" ; change to collect images (or just use command center after setup)
  
  set-default-shape nodes "circle"
  set-default-shape edges "line"
  set friction .25
  set init-power-edges 2
  set max-edges round (number-of-variables * (number-of-variables - 1 ) / 2)
  set tot-edges round (max-edges * p1-network-connectivity) 
                         
  set domain-color-list []
  set i 0
  while [i < number-of-values][
        set domain-color-list lput item i [15 105 64 125 45 85 35 55 5] domain-color-list
        set i i + 1
    ]
end

 
to setup  ; Setup the model for a run, build a graph.
  ca
  file-close
  clear-output
  set-default-shape weights "none"
  setup-globals
  setup-patches
  setup-turtles
  setup-random-binary-problems
  ;LoadGrafFisier
  ;WriteGrafFisier    
end

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

to setup-turtles
  cct-nodes number-of-variables [
    set color random-one-of domain-color-list
    ;set color item (random-int-or-float number-of-values) domain
    set colorn position color domain-color-list
    set label-color black
    set size diam
    set links []
    set label who
    setxy random-float (x-max) * (2 * (random 2) - 1)
          random-float (y-max) * (2 * (random 2) - 1)
   ]
end


to setup-random-binary-problems  ; Build a random binary CSP

  locals [t t1 g p1 p2 el i pos temp]
  set g (list turtle 1)
  while [length g < number-of-variables] [
    set t1 random-one-of nodes with [not member? self g]
    set t item random length g g
    ask t1 [connect-edge t]
    set g subgraph turtle 1
  ]
  while [count edges < tot-edges] [
    set t  random-one-of nodes
    set t1 random-one-of nodes with [self != t and not member? t links]
    if t1 != nobody [ask t1 [connect-edge t]]
  ]
  ask nodes [
    set the-neighbors nodes with [member? self (links-of myself)]
    
    set neighbors-list []
    ask  the-neighbors
    [
     set neighbors-list lput who-of myself neighbors-list
     set neighbors-list sort  neighbors-list
    ]
    ]
     
    set total-conflict-pairs round(p2-constraint-tightness * (number-of-values + 1 ) * (number-of-values + 1 ))
    show "Total-conflict-pairs  " + total-conflict-pairs
    ask nodes 
    [
    without-interruption[
     set Forbidden_Pairs get-list length(neighbors-list) []
     set pos  0
     foreach neighbors-list 
     [
     if ? < who
     [ set i 0
      while [i < total-conflict-pairs]
      [
        set p1 random-int-or-float number-of-values 
        set p2 random-int-or-float number-of-values
        set el list p1 p2
        if not member? el item pos Forbidden_Pairs
        [
         set temp lput el (item pos Forbidden_Pairs )
         set Forbidden_Pairs  replace-item pos Forbidden_Pairs temp
         set i i + 1 ]
        ]
      show  item pos Forbidden_Pairs + " confict with the agent " + ?
      set pos pos + 1       
     ]
     ]
     ]
    ]  
end


to-report subgraph [n]  ; report the complete connected subgraph containing n1
  locals[stack graph]
  set graph (list n)
  set stack (list n)
  while [length stack > 0] [
    foreach links-of first stack [
      if not member? ? graph [
        set graph lput ? graph
        set stack lput ? stack
      ]
    ]
    set stack but-first stack
  ]
  report graph
end



; The run procedure which makes the model take one step.
; It moves the nodes so that we get a better layout. You can also click on a node and move it by hand.
to go  
  locals[t]
  if filename = 0 [setup] ; an attempt to work even tho user forgets setup
  if stoptick = -1 [stop]
  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
    ]
  ]
  check-movie
  if stoptick = tick [stop]
end

to step  ; Adjust the edges and nodes for one step of the model
  locals[delta]
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 check-movie  ; if filename is non-empty, make another snapshot
  if length filename > 0 [
    export-view filename + substring "0000" (int log tick 10) 3 + tick + ".png"
  ]
end


;;;; Edge & Node utilities
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
    set weight-a 1
    set weight-b 1
    hatch 1 [
      set breed weights
      set (wa-turtle-of myself) self
      set label (weight-a-of myself)]
    hatch 1 [
      set breed weights
      set (wb-turtle-of myself) self
      set label (weight-b-of myself)]
    ask a [set links lput b-of myself links]
    ask b [set links lput a-of myself links]
    set color black
    set label no-label
    adjust-edge
  ]
end

to-report sign [num]
  ifelse num < 0 [report -1][report 1]
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 jump-nowrap [dist] ; turtle proc: jump but don't wrap, bounce w/ friction instead
  locals [x y]
  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 + 1
  set (xcor-of wb-turtle) xcor
  set (ycor-of wb-turtle) ycor
  
  setxy xcor-of a ycor-of a
  set size distance-nowrap b - diam
  set heading towards-nowrap b
  
  fd diam / 2 + 1
  set (xcor-of wa-turtle) xcor
  set (ycor-of wa-turtle) ycor
  
  setxy xcor-of a ycor-of a
  jump (size / 2) + (diam / 2)
end

to-report make-list [num element]
  locals [i result]
  set i 0
  set result []
  while [i < num] [
    set result lput element result
    set i i + 1
    ]
  report result
end

to-report copy-list [l]
  locals [r]
  set r []
  foreach l [
    set r lput ? r]
  report r
end

; n is length of list
; el is the element
to-report get-list [n el]
  locals [i lst]
  set i 0
  set lst []
  while [i < n] [
    set lst fput el lst
    set i i + 1]
  report lst
end
;;;;;;;;;;
;;;Asynchrounous Backtracking  algorithm

;Initialize the Asynchrounous Backtracking algorithm
to setup-ABT
  ask nodes [
     set messages-received 0
    set messages-received_ok 0
    set messages-received_nogood 0
    set messages-received_nogoodold 0
    set nr_constraintc 0
    set AgentC_Cost 0
    set current-view get-list number-of-variables -1
    set nogoods get-list number-of-variables 0
    set message-queue []
    set-current-plot "Messages"
    create-temporary-plot-pen "n-" + who
    set-plot-pen-color (who * 10 + 5) mod 140
    ]
  ask nodes [
    initialize
    set extendend-neighbors neighbors-list
  ]
  set done false
  set nr_cicluri 0
 WriteColors
end


to WriteColors
file-close
  if (file-exists? "culorit.txt" )
   [file-delete "culorit.txt"]
  file-open "culorit.txt"
  ask nodes[
  ;ask  the-neighbors
  ; [
     file-print who +" " + colorn 
  ; ]
   ]  
file-close  
end

to WriteSolution
show "Solution "
ask nodes [
write colorn + " "
]
end

to-report verifica_solutia
locals [good i]
set good true
;without-interruption[ 
ask nodes
[

 without-interruption[
 foreach neighbors-list 
  [
  if (? < who and Conflict who  ?  colorn colorn-of turtle ? )
  [
  set good false
  show "Conflict " + who + " cu " + ?
  ]
 ]
 ]
 ]
if good 
[show "Good solution!"]
report good
end

to go-ABT
  set no-more-messages true
  set nr_cicluri nr_cicluri + 1
  ask nodes [
    if (not empty? message-queue)[
      set no-more-messages false]]
  if (no-more-messages) [
    ifelse verifica_solutia
    [WriteSolution]
    [WriteSolution]
    stop
   ]
  if (done)
  [show "No solution"
   stop]
  ask nodes [handle-message]
  ask nodes [
    set-current-plot "Messages"
    create-temporary-plot-pen "q" + who
    plot messages-received_nogood + messages-received_ok
   ]
 
end


to initialize
 locals [msg]
   foreach neighbors-list
    [
     set msg (list "ok" (list who colorn) AgentC_Cost)
     ask turtles with [who = ? ]
         [receive-message msg]
    ] 
end

;get the next message from message-queue
to-report retrieve-message
  locals [msg]
  without-interruption [
    set msg first message-queue
    set message-queue butfirst message-queue]
  report msg
end

to receive-message [msg]
  without-interruption [
    set message-queue lput msg message-queue]
end

to send-message [receiver msg]
  without-interruption [ set message-queue-of (turtle receiver) lput msg (message-queue-of (turtle receiver))
  ]
 
end


;Get the msg and dispatch it to the appropiate function
to handle-message
  locals [msg xj dj sender msgnog SenderC_Cost]
  if (empty? message-queue) [stop]
  set msg retrieve-message
  ;set messages-received messages-received + 1
  if (first msg = "ok")
  [
      set xj item 0 (item 1 msg)
      set dj item 1 (item 1 msg)
      set messages-received_ok messages-received_ok + 1
      set SenderC_Cost item 2 msg
      if SenderC_Cost > AgentC_Cost
      [ 
        set AgentC_Cost SenderC_Cost
      ]
      ok xj dj 
   ]
   if (first msg = "nogood")
   [
     set SenderC_Cost item 3 msg
     if SenderC_Cost > AgentC_Cost
     [ 
      set AgentC_Cost SenderC_Cost
     ]
     set sender item 1 msg
     set msgnog item 2 msg 
     nogood sender msgnog 
     set messages-received_nogood messages-received_nogood + 1
    ]
   if (first msg = "addl")
    [ 
    SetLink item 1 msg 
    ]      
end



; this is the Ok? procedure in the paper where Qj = Xj and Vj = dj
to ok [Qj Vj ]
    set current-view replace-item Qj current-view Vj
    check-agent-view 
end

to-report agents-in-context [cont]
    locals [i res]
    set i 0
    set res []
    while [i < number-of-variables][
        if (item i cont != -1) 
        [
           set res lput i res
        ]
        set i i + 1
    ]
    report res 
end

to-report locate-who-nogood [ n ]
locals [whon gasit lagent]
 set lagent agents-in-context current-view
 set whon n - 1
 set gasit false 
 while [not gasit ]
  [
   ifelse ( member? whon lagent ) 
     [set gasit true]
   [set whon whon - 1] 
   ]  
  report whon
end


to SetLink [ Sender]
  locals [msg]
  if not member? Sender extendend-neighbors
   [ 
    set extendend-neighbors lput Sender extendend-neighbors 
    set extendend-neighbors sort extendend-neighbors
    set msg (list "ok" (list who colorn) AgentC_Cost)
    send-message Sender msg
   ]
end

to-report Is_oldnogood [beef whosend]
locals [i]
  set i 0
   while [i < who ]
     [
     if  ( (item i beef) != (item i current-view) and (item i beef) != -1  and (item i current-view) != -1 and member? i extendend-neighbors) 
      [report true]            
      set i (i + 1)
    ] 
  if  ((item who beef) != (colorn) and (item who beef) != -1)  
    [report true] 
  report false
end    
   
; this is the nogood procedure from the paper
to nogood [whosend beef ]
    locals [ i j msg whonog oldvalue  k]
   ;does this nogood apply to my current view? 
   if (Is_oldnogood beef whosend )
     [
       if  (item who beef = colorn) ;and (member? whosend extendend-neighbors) 
       [
         set msg (list "ok" (list who colorn) AgentC_Cost) 
         send-message whosend msg
        ]
       stop
     ] 
    ;mark current position as no good 
    ;set nogoods replace-item colorn nogoods 1
    
    set i 0
    while [i < who ]
     [
     if (not member? i extendend-neighbors)  and ((item i beef ) != -1) 
     [
      set msg (list "addl" who )
      send-message i msg
      set current-view (replace-item i current-view (item i beef))
      set extendend-neighbors lput i extendend-neighbors
      set extendend-neighbors sort extendend-neighbors  
      set extendend-neighbors remove-duplicates extendend-neighbors  
     ]
     set i (i + 1)
     ]
    set oldvalue colorn
    set nogoods replace-item colorn nogoods 1
    Check-agent-view1 
    if ( oldvalue = colorn )
     [
       set msg (list "ok" (list who colorn) AgentC_Cost) 
       send-message whosend msg
     ]
end

to-report Conflict [who1 who2 value1 value2]
    locals [result el pos element]
    set result false
    if (neighbors?  who1  who2)
    [
     set nr_constraintc nr_constraintc + 1 
     set AgentC_Cost AgentC_Cost + 1 
     set el list value2 value1
     set pos position who2 neighbors-list
     ;show "Pozitia " + pos 
     ;show item pos Forbidden_Pairs
     set element item pos Forbidden_Pairs
     if  (member? el element )
        [set result true]
     ]    
    report result
end

to check-agent-view 
    locals [ i j msg whonog consistent k col]
    set i 0
    set consistent true
    while [ i < who ] ;for each vertices
    [
     ;set nr_constraintc nr_constraintc + 1 
     ;set AgentC_Cost AgentC_Cost + 1 
     if Conflict who  i  colorn  item i current-view
      [ set consistent false 
      ]
     set i i + 1 
    ]
    
    UpdateNogood
    if ( not consistent )
    [    
     set col 0
     set k 0
     while [ col < number-of-values and k = 0]
     [
      if ( item Col nogoods  = 0 )
      [
        set i 0
        set consistent true
        while [ i < who ] ;for each vertices
        [
         ;set nr_constraintc nr_constraintc + 1 
         ;set AgentC_Cost AgentC_Cost + 1 
         if (Conflict who i  col  item i current-view) 
          [ set consistent false]
         set i i + 1 
        ]
        
       if consistent
        [ set colorn col
             ;setxy (colorn - screen-edge-x) (screen-edge-y - who)
          set color item colorn domain-color-list
          set msg (list "ok" (list who colorn) AgentC_Cost)
          foreach extendend-neighbors 
           [ 
           if (? > who )  
                 [send-message ? msg] 
           ]
          set k 1
        ]
       ; [ set nogoods replace-item col nogoods 1] 
      ] 
      set col  (col + 1)
     ]
  if (k = 0 ) 
   [BackTrack]
  ]
  
end

to check-agent-view1 
    locals [ i j msg whonog consistent k col]
    
     set col 0
     set k 0
     while [ col < number-of-values and k = 0]
     [
      if ( item Col nogoods  = 0 )
      [
        set i 0
        set consistent true
        while [ i < who ] ;for each vertices
        [
         ;set nr_constraintc nr_constraintc + 1 
         ;set AgentC_Cost AgentC_Cost + 1 
         if (Conflict who i col item i current-view) 
          [ set consistent false]
         set i i + 1 
        ]
      if consistent
        [ set colorn col
             ;setxy (colorn - screen-edge-x) (screen-edge-y - who)
          set color item colorn domain-color-list
          set msg (list "ok" (list who colorn) AgentC_Cost)
          foreach extendend-neighbors 
           [ 
           if (? > who )  
                 [send-message ? msg] 
           ]
          set k 1
        ]
      ] 
      set col  (col + 1)
     ]
         
    if (k = 0 ) 
    [BackTrack  ]
end
    
    
 to BackTrack 
 locals [msg whonog]
 if (who = 0);no consistent colors and I'm highest priority
 [
   show "No solution"
   set done true
   stop
 ]
 set msg (list "nogood" who current-view AgentC_Cost )
 set whonog locate-who-nogood who
 send-message whonog msg
 set current-view (replace-item whonog current-view -1)
 UpdateNogood
 check-agent-view1
     
end


to  UpdateNogood
locals [i j]
 set nogoods get-list number-of-values  0
  set i 0
     while [ i < who ] ;for each vertices
      [ 
        set j 0
        while [ j < number-of-values ] ;for each color
            [
            ;set nr_constraintc nr_constraintc + 1
            ;set AgentC_Cost AgentC_Cost + 1  
            if (Conflict who i j item i current-view) and (item i current-view != -1 )             
                   [set nogoods replace-item j nogoods 1]              
             set j (j + 1)]
         set i (i + 1)
      ]
end


to-report neighbors? [v1 v2]
     report (member? v2 neighbors-list-of turtle v1) or (member? v1 neighbors-list-of turtle v2)
end



@#$#@#$#@
GRAPHICS-WINDOW
209
10
697
430
21
17
11.12
1
10
1
1
1
0
1
1
1

CC-WINDOW
5
469
1005
564
Command Center
0

BUTTON
1
11
56
44
NIL
setup
NIL
1
T
OBSERVER
T
NIL

BUTTON
62
12
136
45
Layout
go
T
1
T
OBSERVER
NIL
NIL

SLIDER
6
50
193
83
number-of-variables
number-of-variables
2
30
12
1
1
NIL

SLIDER
5
223
97
256
spring-force
spring-force
0
2
0.2
0.1
1
NIL

SLIDER
99
223
191
256
spring-length
spring-length
0
10
8.5
0.25
1
NIL

SLIDER
7
259
190
292
mutual-repulsion
mutual-repulsion
0
10
4.25
0.25
1
NIL

SLIDER
4
125
192
158
p1-network-connectivity
p1-network-connectivity
0.1
1
0.3
0.1
1
NIL

MONITOR
705
10
762
59
NIL
tick
3
1

MONITOR
767
10
824
59
edges
count edges
3
1

BUTTON
704
60
861
93
setup-ABT 
setup-ABT 
NIL
1
T
OBSERVER
T
NIL

BUTTON
704
94
836
127
go ABT
go-ABT
NIL
1
T
OBSERVER
T
NIL

BUTTON
704
128
836
161
go ABT
go-ABT
T
1
T
OBSERVER
T
NIL

TEXTBOX
716
175
862
286
1- setup\n2- Layout until it's pretty\n3- setup-ABT \n4- go-ABT 

SLIDER
5
87
192
120
number-of-values
number-of-values
0
10
6
1
1
NIL

MONITOR
827
10
915
59
Msgs nogood
sum (values-from nodes [messages-received_nogood])
3
1

MONITOR
920
10
979
59
Msgs ok
sum (values-from nodes [messages-received_ok])  
3
1

MONITOR
863
61
920
110
Cycles
nr_cicluri
3
1

MONITOR
842
110
955
159
Constraint checks
sum (values-from nodes [nr_constraintc])
3
1

MONITOR
834
165
985
214
Concurrent constraint checks
max (values-from nodes [AgentC_Cost])
3
1

SLIDER
5
164
191
197
p2-constraint-tightness
p2-constraint-tightness
0.1
1
0.3
0.1
1
NIL

PLOT
1
297
191
432
Messages
NIL
NIL
0.0
100.0
0.0
10.0
true
false

TEXTBOX
705
242
996
455
The randomly generated (binary) CSPs are characterised by the 4-tuple (n, m,p1,p2),\nwhere:\n- n is the number of variables;\n- m is the uniform domain size; \n- p1 is the portion of the n * (n - 1) /2 possible\n  constraints in the graph; \n- p2 is the portion of the m*m  value pairs in each constraint that are disallowed by the  constraint. \n\nThat is, p1 may be thought of as the density of the constraint graph, and p2 as the tightness of constraints.

@#$#@#$#@
Title: Random binary CSPs using Asynchronous Backtracking
Author: Ionel Muscalagiu, Jose M. Vidal and Hong Jiang
Description:
This is the implementation of the Asynchronous Backtracking for the random binary problems. We generate and solve the random binary problem using the Asynchronous Backtracking  algorithm from 
<ul>
<li>Makoto Yokoo and Katsutoshi Hirayama. <a href="http://jmvidal.cse.sc.edu/library/yokoo00a.pdf">Algorithms for Distributed Constraint Satisfaction: A Review</a>. <i>Autonomous Agents and Multi-Agent Systems,</i> 3(2):185--207, 2000. <a href="http://dx.doi.org/10.1023/A:1010078712316">doi:10.1023/A:1010078712316</a>
</li>
</ul>
The randomly generated (binary) CSPs are characterised by the 4-tuple (n, m,p1,p2),
where n is the number of variables, m is the uniform domain size, p1 is the portion of
the n * (n - 1) /2 possible constraints in the graph, and p2 is the portion of the m*m  value pairs in each constraint that are disallowed by the constraint. That is, p1 may be thought of as the density of the constraint graph, and p2 as the tightness of constraints.

In generating a CSP (n, m,pl ,p2) exactly p1 * n * (n - 1)/2 constraints are randomly
selected (rounded to the nearest integer), and for each constraint selected exactly p2 * m*m conflicting pairs of values are selected (again, rounded to the nearest integer). 

@#$#@#$#@
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 3.0
@#$#@#$#@
@#$#@#$#@
@#$#@#$#@
@#$#@#$#@