;Asynchronous weak-commitment search with nogood processor centralized for the graph-coloring problem ; by Ionel Muscalagiu ( mionel@fih.utt.ro ) ; Jose M. Vidal breeds [nodes edges weights] ;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 is done or not ;domain-color-list is the list of allowed colors ;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 colorn current-view messages-received_ok messages-received_nogood nr_constraintc messages-received nr nrn priorities_list ] globals [x-max y-max diam friction tot-edges filename tick stoptick init-power-edges domain-color-list no-more-messages done tmp nr_cicluri nn priorities_list_receive nogood_list_receive nr_nogood_store] to setup-globals ; separate procedure for setting globals locals [i] 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 tot-edges min list round (number-of-nodes * edge-ratio) ((number-of-nodes ^ 2 - number-of-nodes) / 2) set domain-color-list [] set i 0 while [i < num-colors][ 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 WriteGraphFile locals [sir i] ask nodes [ set the-neighbors nodes with [member? self (links-of myself)] ] file-close if (file-exists? "graf.txt" ) [file-delete "graf.txt"] file-open "graf.txt" file-print number-of-nodes + " " + edge-ratio + " " + number-of-nodes * edge-ratio ask nodes[ ask the-neighbors [ file-print who-of myself +" " + who ] ] file-close if (file-exists? "colors.txt" ) [file-delete "colors.txt"] file-open "colors.txt" ask nodes[ ask the-neighbors [ file-print who +" " + colorn ] ] file-close 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-graph graph-edges ;WriteGrafFisier set nr_nogood_store 0 end to setup-patches ask patches [set pcolor white] end to setup-turtles cct-nodes number-of-nodes [ set color random-one-of domain-color-list ;set color item (random-int-or-float num-colors) 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-power-graph ; Build a powerlaw graph locals [n prob p elist t1 t2] set prob (list turtle 0) repeat min list init-power-edges (floor number-of-nodes / 3) [ ask last prob [connect-edge turtle (length prob)] set prob lput turtle (length prob) prob ] set elist n-values (number-of-nodes - length prob) [1] while [reduce [?1 + ?2] elist < (tot-edges - count edges)] [ set n random length elist set elist replace-item n elist (1 + item n elist) ] while [length elist > 0] [ set t1 turtle (number-of-nodes - length elist) set p prob repeat min list who-of t1 first elist [ set t2 random-one-of p ask t1 [connect-edge t2] set p remove t2 p set prob lput t1 prob set prob lput t2 prob ] set elist but-first elist ] end to setup-random-graph ; Build a random graph locals [t t1 g] set g (list turtle 1) while [length g < number-of-nodes] [ 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]] ] 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 to graph-edges ; Make a simple edge histogram set-current-plot "edge-distribution" set-plot-x-range 1 1 + max values-from nodes [length links] histogram-from nodes [length links] 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-graphics 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 ;;;;;;;;;; ;;;awcs algorithm ;Initialize the awcs algorithm to setup-awcs 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 messages-received 0 set messages-received_ok 0 set messages-received_nogood 0 set nr_constraintc 0 set current-view make-list number-of-nodes [-1 -1] set priority 0 ;initial value is 0 for all. set nogood_list [] set nogood_sent_list [] set priorities_list [] set message-queue [] set-current-plot "Messages" create-temporary-plot-pen "n-" + who set-plot-pen-color (who * 10 + 5) mod 140 ] set nn nogood-number show nn set done false set nr_cicluri 0 set nogood_list_receive [] set priorities_list_receive [] ask nodes [ initialize set nrn 0 ] end to go-awcs 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) [ WriteSolution stop ] if (done) [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 WriteSolution ask nodes [ show colorn + " " ] end ;initialize the current-view's and start sending messages to initialize ask the-neighbors [set current-view (replace-item (who-of myself) current-view (list (colorn-of myself) (priority-of myself)) ) set message-queue lput (list "ok?" (sentence (list (who-of myself) (colorn-of myself)) (priority-of myself))) message-queue ] 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 ;Get the msg and dispatch it to the appropiate function to handle-message locals [msg] if (empty? message-queue) [stop] set msg retrieve-message ;set messages-received messages-received + 1 if (first msg = "ok?")[ set messages-received_ok messages-received_ok + 1 handle-ok-message item 1 msg] if (first msg = "nogood")[ set messages-received_nogood messages-received_nogood + 1 handle-nogood-message (first item 1 msg) (last item 1 msg)] end ;when received ok? messages to handle-ok-message [content] set current-view (replace-item (first content) current-view (but-first content)) check-agent-view end ;when received nogood messages to handle-nogood-message [content_colors content_priorities ] locals [i] without-interruption [ set nogood_list (lput content_colors nogood_list) set priorities_list (lput content_priorities priorities_list) if not member? content_colors nogood_list_receive [ set nogood_list_receive (lput content_colors nogood_list_receive) set priorities_list_receive (lput content_priorities priorities_list_receive) set nr_nogood_store nr_nogood_store + 1 ] ] set nrn nrn + 1 set i 0 while [i < number-of-nodes ] [ if (i != who) and (not member? turtle i links) and ((item i content_colors ) != -1) [ set current-view (replace-item i current-view (list item i content_colors item i content_priorities)) set links lput turtle i links set the-neighbors nodes with [member? self (links-of myself)] ] set i (i + 1) ] check-agent-view end to-report nogood-number locals [i nmr ] set i number-of-nodes - num-colors + 1 set nmr 1 while [i <= number-of-nodes] [ set nmr nmr * i set i i + 1 ] report nmr end ;reports a list with the values from current view (without the priorities) to-report current-view-values-only [color-value] locals [i result] set i 0 set result [] repeat (number-of-nodes) [ ifelse (i = who) [set result (lput color-value result)] [set result (lput (first (item i current-view)) result)] set i i + 1 ] report result end ;reports a list with the priorities from current view to-report current-view-priorities-only [priority-value] locals [i result] set i 0 set result [] repeat (number-of-nodes) [ ifelse (i = who) [set result (lput priority-value result)] [set result (lput (last (item i current-view)) result)] set i i + 1 ] report result end to-report conflict [who1 who2 colorn1 colorn2] locals [result] set result false set nr_constraintc nr_constraintc + 1 if (colorn1 = colorn2) and member? who1 neighbors-list-of turtle who2 [set result true] ;show result report result end ;report true if priority p2 of agent with who2=w2 is greater than that of agent with who=w1 to-report greater-priority [w1 p1 w2 p2] ifelse (p2 > p1) [report true] [ ifelse (p2 = p1) and (w2 > w1) [ report true] [report false] ] end ;reports true if the value color-value is inconsistent with the current view to-report inconsistent-view [color-value node-number] locals [i result] ifelse (node-number > -1) [ report conflict who node-number color-value first (item node-number current-view); colorn-of (one-of nodes with [who = node-number]) ] [ set i 0 set result false while [ i < number-of-nodes and result = false] [ if (i != who and (greater-priority who priority i (last (item i current-view)) ) and member? i neighbors-list ) [ if (conflict who i color-value first (item i current-view)) [ set result true ] ] set i i + 1 ] if (member? (current-view-values-only color-value) nogood_list) [set result true] ] report result end ;finds a value for the node that minimizes the number of ;constraints violations with lower priority nodes to-report findValue locals [i temp-val violations temp-violations result] set i 0 set temp-val 0 set violations number-of-nodes + 1 set temp-violations 0 set result -1 repeat (num-colors) [ if (temp-val != colorn) [ if not (inconsistent-view temp-val -1) and not inconsistent-nogood-processor temp-val [ repeat (number-of-nodes) [ if (i != who and (greater-priority i last (item i current-view) who priority) and member? i neighbors-list ) [ if (inconsistent-view temp-val i) [ set temp-violations temp-violations + 1 ] ] set i i + 1 ] if (temp-violations <= violations) [set violations temp-violations set result temp-val] ] ] set temp-val temp-val + 1 set i 0 set temp-violations 0 ] ;show result report result end ;sends msg to the-neighbors to send [msg] locals [i aux] ask the-neighbors [ set message-queue lput msg message-queue ] end ;reports a list with the priorities from current view to-report nogood-priorities-only [nogoods ] locals [i result] set i 0 set result [] repeat (number-of-nodes) [ ifelse (i = who) and (item i nogoods != -1) [set result (lput -1 result)] [set result (lput (last (item i current-view)) result)] set i i + 1 ] report result end to-report inconsistent-nogood-processor [color-value] locals [i result temp-nogood temp-priorities pos] set result true ifelse not empty? nogood_list_receive [foreach nogood_list_receive [ set pos position ? nogood_list_receive set temp-nogood ? set temp-priorities item pos priorities_list_receive set i 0 while [ i < number-of-nodes and result != false] [ if (i != who and (greater-priority who priority i (last (item i current-view)) )) [ ;set nr_comp nr_comp + 1 if (first (item i current-view) != item i temp-nogood ) and (first (item i current-view) != -1 ) and (item i temp-nogood != -1) [ set result false report result ] ] ;set nr_comp nr_comp + 1 if (item who temp-nogood != -1) and (item who temp-nogood != color-value) [set result false report result] set i i + 1 ] ;if (member? (current-view-values-only color-value) nogood_list) [set result true] ] report result ] [report false] end ;does a backtrack to backtrack locals [nogoods priorities msg newValue] set nogoods current-view-values-only colorn set priorities current-view-priorities-only priority if (nrn >= nn) [ show "no solution" set done true stop ] if not (member? nogoods nogood_sent_list) or (inconsistent-nogood-processor colorn) [ set msg list "nogood" (list nogoods priorities) send msg set nogood_list (lput nogoods nogood_list) set nogood_sent_list lput nogoods nogood_sent_list set priority (max priorities) + 1 set newValue findValue if (newValue != -1) [ set colorn newValue set color item colorn domain-color-list set current-view replace-item who current-view (list colorn priority) set msg list "ok?" (fput who (item who current-view)) send msg ] ] end to check-agent-view locals [newValue msg] if (inconsistent-view colorn -1) [ set newValue findValue ifelse (newValue = -1) [backtrack ] [ set colorn newValue set color item colorn domain-color-list set current-view replace-item who current-view (list colorn priority) set msg list "ok?" (fput who (item who current-view)) send msg ] ] end @#$#@#$#@ GRAPHICS-WINDOW 207 10 624 448 19 19 10.44 1 10 1 1 1 CC-WINDOW 624 288 976 626 Command Center BUTTON 7 64 62 97 NIL setup NIL 1 T OBSERVER T BUTTON 68 65 142 98 Layout go T 1 T OBSERVER NIL SLIDER 6 29 193 62 number-of-nodes number-of-nodes 2 100 17 1 1 NIL SLIDER 6 177 182 210 spring-force spring-force 0 2 0.2 0.1 1 NIL SLIDER 6 218 182 251 spring-length spring-length 0 10 8.75 0.25 1 NIL SLIDER 6 256 182 289 mutual-repulsion mutual-repulsion 0 10 4.0 0.25 1 NIL SLIDER 7 103 182 136 edge-ratio edge-ratio 0.8 5 1.5 0.1 1 NIL MONITOR 705 10 762 59 NIL tick 3 1 PLOT 8 294 180 414 edge-distribution edges/node count 1.0 1.0 0.0 1.0 true false PENS "default" 1.0 1 -16777216 true MONITOR 767 10 824 59 edges count edges 3 1 BUTTON 704 60 840 93 NIL setup-awcs NIL 1 T OBSERVER T BUTTON 704 94 814 127 NIL go-awcs NIL 1 T OBSERVER T BUTTON 704 128 820 161 NIL go-awcs T 1 T OBSERVER T TEXTBOX 716 175 927 286 1- setup\n2- Layout until it's pretty\n3- setup-awcs with nogood processor\n4- go-awcs with nogood processor PLOT 3 441 266 627 Messages NIL NIL 0.0 10.0 0.0 1.0 true false SLIDER 12 146 184 179 num-colors num-colors 0 10 3 1 1 NIL MONITOR 838 11 926 60 Msgs nogood sum (values-from nodes [messages-received_nogood]) 3 1 MONITOR 933 10 992 59 Msgs ok sum (values-from nodes [messages-received_ok]) 3 1 MONITOR 848 64 905 113 Cycles nr_cicluri 3 1 MONITOR 845 120 958 169 Constraint checks sum (values-from nodes [nr_constraintc]) 3 1 @#$#@#$#@ Title: Graph Coloring using Asynchronous Weak-Commitment with nogood processor centralized Author: Ionel Muscalagiu, Jose M. Vidal Description: This is the implementation of the Asynchronous Weak-Commitment Search with nogood processor for the graph coloring problem. We adapt the nogood processor technique from We solve the graph coloring problem using the AWCS algorithm (with nogood processor centralized) from

When a nogood is discovered, the variable assignments causing it and the IDs of the agents involved are sent to the no-good processor, which saves the nogood. Later, when an agent has found a tentative assignment for its variables, it consults the nogood processor to make sure that its assignment along with any known assignments of higher priority agents do not constitute a nogood.

@#$#@#$#@ default true 0 Polygon -7566196 true true 150 5 40 250 150 205 260 250 circle false 0 Circle -7566196 true true 35 35 230 line true 0 Line -7566196 true 150 0 150 301 none true 0 @#$#@#$#@ NetLogo 2.0.2 @#$#@#$#@ @#$#@#$#@ @#$#@#$#@