This page was automatically generated by NetLogo 5.0.3.
The applet requires Java 5 or higher. Java must be enabled in your browser settings. Mac users must have Mac OS X 10.4 or higher. Windows and Linux users may obtain the latest Java from Oracle's Java site.
In order for this to work, this file, your model file (DBS-gc-synch.nlogo), and the files NetLogoLite.jar and NetLogoLite.jar.pack.gz must all be in the same directory. (You can copy NetLogoLite.jar and NetLogoLite.jar.pack.gz from the directory where you installed NetLogo.)
On some systems, you can test the applet locally on your computer before uploading it to a web server. It doesn't work on all systems, though, so if it doesn't work from your hard drive, please try uploading it to a web server.
You don't need to include everything in this file in your page. If you want, you can just take the HTML code beginning with <applet> and ending with </applet>, and paste it into any HTML file you want. It's even OK to put multiple <applet> tags on a single page.
If the NetLogoLite files and your model are in different directories, you must modify the archive= and value= lines in the HTML code to point to their actual locations. (For example, if you have multiple applets in different directories on the same web server, you may want to put a single copy of the NetLogoLite files in one central place and change the archive= lines of all the HTML files to point to that one central copy. This will save disk space for you and download time for your users.)
powered by NetLogo
view/download model file: DBS-gc-synch.nlogo
Title: Graph Coloring using Distributed Bactracking with Sessions (DBS) algorithms
Author: Ionel Muscalagiu, Jose M. Vidal
Description:
This is the implementation of the Distributed Bactracking with Sessions (DBS) algorithms for the graph coloring problem.. We generate and solve the graph coloring problem using the Distributed Bactracking with Sessions (DBS) algorithms from
Unlike most DisCSP algorithms such as ABT, DBS priority does not consist in minimizing the number of exchanged messages but aims at minimizing the time required to process a message.
Another characteristic of DBS consists in using the concept of sessions to provide a context for each exchanged message. Moreover, these sessions allow the use of heuristics to remove obsolete messages containied in the inboxes (messages awaiting process) of each agent without eliminating possible solutions from the problem.
; Distributed Bactracking with Sessions (DBS) algorithms for the graph-coloring problem
; by Ionel Muscalagiu ( mionel@fih.upt.ro )
; and Jose Vidal
breed [ nodes ]
breed [ edges ]
breed [ 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 ]
weights-own [sw1 sw2]
;the-links list of neighbor nodes (but the-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.
;Agent_view is a list containing triple [[x0 v0 s0] [x1 v1 s1] ...] where vi =value, si= session.
;Current_session = Self's current session
;Current_value = Self's current value
;receivedBtVal is a list used to know values in Dself which have alredy received a backtrack request
;totalBtSet is a list containing triple [xi vi si] = this set allows self to transmit a backtrack message addressed to an agent in totalBtSet
;listeBT is a list containing triple [xi vi s] = is used to proceed a backtrack message to an agent contained in listeBT
;-1 = NULL in this implementation
;messages-recieved is the number of messages this vertice has received.
;nogood_list is the list of nogood received
nodes-own [the-links neighbors-list the-neighbors message-queue ChildrenA ParentA Current_value Current_session Agent_view
receivedBtVal totalBtSet propose
messages-received messages-received_ok messages-received_nogood nr_constraintc AgentC_Cost Forbidden_Pairs gt ]
globals [x-max y-max diam friction tot-edges filename tick1 stoptick init-power-edges domain-color-list
total-conflict-pairs no-more-messages done tmp nr_cicluri nn scris gata]
to setup-globals ; separate procedure for setting globals
let i 0
set diam 4
set tick1 0
set stoptick -2 ; set to some number to stop, generally for image collections
set x-max max-pxcor - (diam / 2) + 1; 0.5
set y-max max-pycor - (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 < number-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 setup ; Setup the model for a run, build a graph.
;; (for this model to work with NetLogo's new plotting features,
;; __clear-all-and-reset-ticks should be replaced with clear-all at
;; the beginning of your setup procedure and reset-ticks at the end
;; of the procedure.)
clear-all
file-close
clear-output
set-default-shape weights "none"
setup-globals
setup-patches
setup-turtles
setup-random-graph
graph-edges
end
to setup-patches
ask patches [set pcolor white]
end
to setup-turtles
create-nodes number-of-nodes [
set color one-of domain-color-list
;set color item (random-int-or-float num-colors) domain
set Current_value position color domain-color-list
set label-color black
set size diam
set the-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
let n 0
let prob 0
let p 0
let elist 0
let t1 0
let t2 0
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 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
let t 0
let t1 0
let g 0
set g (list turtle 1)
while [length g < number-of-nodes] [
set t1 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 one-of nodes
set t1 one-of nodes with [self != t and not member? t the-links]
if t1 != nobody [ask t1 [connect-edge t]]
]
end
to-report subgraph [n] ; report the complete connected subgraph containing n1
let stack 0
let graph 0
set graph (list n)
set stack (list n)
while [length stack > 0] [
foreach [the-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 [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 also click on a node and move it by hand.
to go
let t 0
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
]
]
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
;;;; 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 sw1 myself
ask sw1 [set wa-turtle self]
set label ([weight-a] of myself)]
hatch 1 [
set breed weights
;set ([wb-turtle] of myself) self
set sw2 myself
ask sw2 [set wb-turtle self]
set label ([weight-b] of myself)]
ask a [set the-links lput [b] of myself the-links]
ask b [set the-links lput [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-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
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 + 1
;set ([xcor] of wb-turtle) xcor
ask wb-turtle [ set xcor [xcor] of myself ]
;set ([ycor] of wb-turtle) ycor
ask wb-turtle [ set ycor [ycor] of myself ]
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
ask wa-turtle [ set xcor [xcor] of myself ]
;set ([ycor] of wa-turtle) ycor
ask wa-turtle [ set ycor [ycor] of myself ]
setxy [xcor] of a [ycor] of a
jump (size / 2) + (diam / 2)
end
to-report make-list [num element]
let i 0
let result 0
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]
let r 0
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]
let i 0
let lst 0
set i 0
set lst []
while [i < n] [
set lst fput el lst
set i i + 1]
report lst
end
to ComputeParentA_ChildrenA
let i 0
set ChildrenA []
set ParentA []
;show the-neighbors
foreach neighbors-list
[
if (? > who )
[set ChildrenA lput ? ChildrenA]
if (? < who )
[set ParentA lput ? ParentA]
]
end
to-report verifica_solutia
let good 0
let i 0
set good true
;without-interruption[
ask nodes
[
without-interruption[
foreach neighbors-list
[
if (? < who and Conflict who ? Current_value [Current_value] of turtle ? )
[
set good false
show (word "Conflict " who " cu " ?)
]
]
]
]
if good
[show "Good solution!"]
report good
end
to WriteSolution
show "Solution "
ask nodes [
write (word Current_value " ")
]
end
to WriteMasuratoriFisier
let tnogood 0
let tok 0
let tcc 0
let tcca 0
let nrcic 0
file-open "rez.txt"
set tnogood sum ([messages-received_nogood] of nodes)
set tok sum ([messages-received_ok] of nodes)
set tcc sum ( [nr_constraintc] of nodes)
set tcca max ( [AgentC_Cost] of nodes)
file-print (word tnogood " " tok " " tcc " " tcca " " nr_cicluri)
file-close
end
;get the next message from message-queue
to-report retrieve-message
let msg 0
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
;;;;;;;;;;
;;;DBS algorithm
;Initialize the DBS algorithm
to setup-DBS
ask nodes [
set the-neighbors nodes with [member? self ([the-links] of myself)]
set neighbors-list []
]
ask nodes[
ask the-neighbors
[
set neighbors-list lput [who] of myself neighbors-list
set neighbors-list sort neighbors-list
]
]
ask nodes [
set messages-received 0
set messages-received_ok 0
set messages-received_nogood 0
set nr_constraintc 0
set AgentC_Cost 0
set Agent_view get-list number-of-nodes []
set gt 0
set message-queue []
set receivedBtVal []
set Current_session 0
;set Current_value 0
set propose get-list number-colors false
set propose replace-item Current_value propose true
set TotalbtSet []
set-current-plot "Messages"
;set Current_value 0
;create-temporary-plot-pen (word "n-" who)
; set-plot-pen-color (who * 10 + 5) mod 140
]
ask nodes [
ComputeParentA_ChildrenA
initialize
;set childrenAExtended childrenA
]
set done false
set nr_cicluri 0
set gata false
set scris false
end
to go-DBS
set no-more-messages true
set nr_cicluri nr_cicluri + 1
ask-concurrent nodes [
;show message-queue
if (not empty? message-queue)[
set no-more-messages false]]
if (no-more-messages) [
if verifica_solutia
[WriteSolution
WriteMasuratoriFisier ]
stop
]
if (done)
[show "No solution"
stop]
ask-concurrent nodes [handle-message]
end
to initialize
let msg 0
foreach childrenA
[
set msg (list "ok" (list who Current_value Current_session) AgentC_Cost)
ask nodes with [who = ? ]
[receive-message msg]
]
end
;this is the messages process procedure
;set msg (list "ok" (list who Current_value Current_session) AgentC_Cost)
;set msg (list "nogood" (list who Current_value Current_session) BtSet AgentC_Cost)
to handle-message
let msg 0
let xj 0
let dj 0
let SenderC_Cost 0
if (empty? message-queue) [ set gt 1
stop]
if (not empty? message-queue)
[
set gt 0
set msg retrieve-message
;show msg
if (first msg = "stop")
[set done true
stop]
if (first msg = "ok")
[
set messages-received_ok messages-received_ok + 1
ProcessOk msg
]
if (first msg = "nogood")
[
set messages-received_nogood messages-received_nogood + 1
set SenderC_Cost item 3 msg
if SenderC_Cost > AgentC_Cost
[
set AgentC_Cost SenderC_Cost
]
ProcessNogood msg
]
]
end
;this is the Algorithm 1 from paper, when received msg "ok" (xj,dj,sj) SenderC_Cost from Aj
to ProcessOk [msg ]
let xj 0
let dj 0
let sj 0
let SenderC_Cost 0
set xj item 0 (item 1 msg)
set dj item 1 (item 1 msg)
set sj item 2 (item 1 msg)
set SenderC_Cost item 2 msg
if SenderC_Cost > AgentC_Cost
[
set AgentC_Cost SenderC_Cost
]
UpdateAgentView xj dj sj
Close_session
CheckAgentView xj "ok"
end
to ProcessOk1 [msg ]
let xj 0
let dj 0
let sj 0
let SenderC_Cost 0
let lsj 0
set xj item 0 (item 1 msg)
set dj item 1 (item 1 msg)
set sj item 2 (item 1 msg)
set SenderC_Cost item 2 msg
if SenderC_Cost > AgentC_Cost
[
set AgentC_Cost SenderC_Cost
]
if item xj agent_view != []
[set lsj item 2 (item xj agent_view)]
if sj >= lsj
[UpdateAgentView xj dj sj
Close_session
CheckAgentView xj "ok"
]
end
;this is the Algorithm 2 from paper, when received msg "nogood" (xj,dj,sj) BtSet SenderC_Cost
to ProcessNogood [msg ]
; show (word msg " si " receivedBtVal )
let xj 0
let dj 0
let sj 0
let BtSetR []
let SenderC_Cost 0
set xj item 0 (item 1 msg)
set dj item 1 (item 1 msg)
set sj item 2 (item 1 msg)
set SenderC_Cost item 3 msg
if SenderC_Cost > AgentC_Cost
[
set AgentC_Cost SenderC_Cost
]
;if it is not obsolete then receivedBtVal and totalBtSet are updated.
if ( (sj = Current_session) and (not member? dj receivedBtVal) )
[
;An accepted nogood is used to update receivedBtVal and totalBtSet
set receivedBtVal lput dj receivedBtVal
set BtSetR item 2 msg
set totalBtSet UpdateSet BtSetR totalBtSet
; show (word "s-a actualizat-" totalBtSet)
if dj = Current_value
[ set Current_value -1
]
CheckAgentView -1 "backtrack"
]
end
;The operator update from paper is implemented
to-report UpdateSet [AS BS]
let Rez []
let triple []
let xj 0
let ok 0
let xja 0
ifelse AS = []
[ report BS]
[if BS = []
[report AS]
]
set Rez AS
foreach BS
[
set triple ?
if triple != []
[
set xj item 0 triple
set ok 1
foreach AS
[
if ? != []
[
set xja item 0 ?
if (xja = xj )
[set ok 0]
]
]
if (ok = 1 )
[
set Rez lput triple Rez
]
]
]
;set Rez remove-duplicates Rez
report Rez
end
;The operator update from paper is implemented
to-report UpdateSet1 [Ag AS BS]
let Rez []
let triple []
let xj 0
let ok 0
let xja 0
set Rez AS
foreach AS
[
if ? != []
[
set xja item 0 ?
if (xja >= Ag )
[set Rez remove ? Rez ]
]
]
ifelse Rez = []
[ report BS]
[if BS = []
[report Rez]
]
foreach BS
[
set triple ?
if triple != []
[
set xj item 0 triple
set ok 1
foreach AS
[
if ? != []
[
set xja item 0 ?
if (xja = xj )
[set ok 0]
]
]
if (ok = 1 )
[
set Rez lput triple Rez
]
]
]
report Rez
end
to UpdateAgentView [Xj Vj Sj ]
;show (word " in" xj Agent_view)
set Agent_view replace-item Xj Agent_view (list Xj Vj Sj)
;show (word " dupa" xj Agent_view)
end
to Close_session
set current_value -1
set Current_session Current_session + 1
set receivedBtVal []
set propose get-list number-colors false
end
;this is the Submit_assign procedure (Algorithm 4) in the DBS algorithm
to Submit_assign [sd]
let ok 0
let msg []
;show (word d " ina- " ok)
let d 0
if ( sd = -1 )
[ set d 0
set ok 0
while [ d < number-colors and ok = 0]
[ if (item d propose = false)
[
if Is-Consistent d
[ set ok 1
set sd d
]
]
set d (d + 1)
]
]
Set Current_value sd
set propose replace-item sd propose true
set msg (list "ok" (list who Current_value Current_session) AgentC_Cost)
foreach childrenA
[
ask nodes with [who = ? ]
[receive-message msg]
]
end
to-report Is-Consistent [value_c ]
let i 0
let consistent 0
let triple []
let v 0
set consistent true
set i 0
while [ i < who ] ;for each agents < who
[
;set nr_constraintc nr_constraintc + 1
;set AgentC_Cost AgentC_Cost + 1
set triple item i Agent_view
if (triple != [] )
[
set v item 1 triple
]
if (triple != [] ) and (Conflict i who v Value_c)
[
set consistent false
]
set i i + 1
]
;show consistent
report consistent
end
to-report Is-Consistent1 [value_c Ag]
let i 0
let consistent 0
let triple []
set consistent true
let v 0
set i 0
while [ i <= Ag ] ;for each agents <= Ag
[
;set nr_constraintc nr_constraintc + 1
;set AgentC_Cost AgentC_Cost + 1
set triple item i Agent_view
if (triple != [] )
[
set v item 1 triple
]
if (triple != [] ) and (Conflict i who v Value_c)
[
set consistent false
]
set i i + 1
]
;show consistent
report consistent
end
to-report Conflict [who1 who2 value1 value2]
let result 0
let el 0
let pos 0
let element 0
set nr_constraintc nr_constraintc + 1
set AgentC_Cost AgentC_Cost + 1
if value1 = -1 or value2 = -1
[
show "Ha"
report true
]
set result false
if (neighbors? who1 who2) and (value1 = value2)
[
;show (word who1 "-" value1 "," who2 "-" value2 "," el " - " element)
set result true
]
report result
end
;this is the CheckAgentView procedure (Algorithm 5) in the DBS algorithm
to CheckAgentView [Ag msgt]
let d 0
let vd 0
let ok 1
if (Ag != -1)
[
set d 0
set ok 1
while [ d < number-colors and ok = 1]
[ if (item d propose = false)
[
if Is-Consistent1 d Ag = true
;if Is-Consistent d = true
[ set ok 0 ]
]
set d (d + 1)
]
]
ifelse (Ag != -1) and (ok = 1 )
[ Backtrack Ag msgt]
[ set d 0
set ok 1
while [ d < number-colors and ok = 1]
[if (item d propose = false)
[
if Is-Consistent d = true
[ set ok 0
set vd d
]
]
set d (d + 1)
]
ifelse ( ok = 0 )
[Submit_assign vd]
[Backtrack -1 msgt]
]
end
to-report CloseWho [S]
let i 0
set i who - 1
let triple item i S
while [triple = [] and i >= 0]
[
set i i - 1
set triple item i S
]
; show (word i "-Close" S)
report triple
end
to-report MaxSet [S]
let i 0
let maxa -1
let triple []
let t []
foreach S
[
set t ?
if t != [] and item 0 t >= maxa
[set maxa item 0 t
set triple t ]
]
;show (word triple "- Max " S)
report triple
end
;;this is the BackTrack procedure (Algorithm 6) in the DBS algorithm
to BackTrack [Ag msgt]
let msg 0
let xp 0
let vp 0
let Agn 0
let triple []
let BtSet []
let BtSet1 []
let tr []
let d 0
let ok 1
ifelse (Ag != -1)
[
set triple item Ag agent_view
;show (word "Caz Ag !=-1 " ag tr"-" triple " -" Agent_view)
set BtSet UpdateSet1 Ag Agent_view totalBtSet
set BtSet remove-duplicates BtSet
set BtSet remove [] BtSet
]
[
ifelse msgt ="ok"
[
set triple CloseWho Agent_view
;show (word "Caz Ag =-1 si ok " msg " " ag "-" triple " -" Agent_view)
set Agn item 0 triple
set BtSet UpdateSet1 Agn Agent_view totalBtSet
set BtSet remove-duplicates BtSet
set BtSet remove [] BtSet
]
[
set BtSet UpdateSet agent_view totalBtSet
set BtSet remove-duplicates BtSet
set BtSet remove [] BtSet
set triple MaxSet BtSet
;show (word "Caz Ag =-1 si backtrack " msg " " ag "-" triple " -" BtSet)
set BtSet remove triple BtSet
]
]
if triple = []
[
set done true
show "No solution"
set msg "stop"
receive-message msg
stop
]
set msg (list "nogood" triple BtSet AgentC_Cost who)
set AgN item 0 triple
ask nodes with [who = AgN ]
[receive-message msg]
set TotalBtSet remove triple TotalBtSet
foreach BtSet
[ set tr ?
if member? tr TotalBtSet
[ set TotalBtSet remove ? TotalBtSet]
]
set xp item 0 triple
ifelse item xp Agent_view != []
[set Agent_view replace-item xp Agent_view [] ]
[if msgt = "backtrack"
[ Close_Session
Submit_assign -1
]
]
end
to-report neighbors? [v1 v2]
report (member? v2 [neighbors-list] of turtle v1) or (member? v1 [neighbors-list] of turtle v2)
end