Being Kevin Bacon NetLogo Model

Produced for the book series "Artificial Intelligence";

Author: W. J. Teahan; Publisher: Ventus Publishing Aps, Denmark.

powered by NetLogo

view/download model file: Being-Kevin-Bacon.nlogo

WHAT IS IT?

This model applies various algorithms to the problem of searching for a specific goal node in a network. The problem is that you do not know where the node is, or how the network is configured. To solve this problem, search needs to be employed to try out the different paths that might lead to the goal node. This model implements some multi-agent based solutions where knowledge is shared between agents in a dynamic way. These can be applied to this problem separately to see how they perform against each other.

The model uses "Kevin Bacon" in its title as Kevin Bacon has been chosen as the "centre" of the Hollywood Universe based on the catch-phrase "degrees of separation from Kevin Bacon". This catch-phrase is based on the related mathematical pastime of measuring the degrees of separation of mathematicians from Paul Erdos, a well-known Hungarian mathematician who was prolific at publishing papers. Paul Erdos has been chosen as the focal point for measuring how well connected a person is amongst the mathematical community. The degrees of separation measure is based on whether as person has published a paper with Paul Erdos (which equates to an Erdos number of 1), or if not then published a paper with someone who has published a paper with Paul Erdos (an Erdos number of 2), or if not then published a paper with someone who has published a paper with someone who has published a paper with Paul Erdos (an Erdos number of 3), and so on.

The model allows the user to select either Paul Erdos or Kevin Bacon as the "centre of the universe". Then it can measure the average degree of separation using Dijkstra's algorithm, or it can search for the node associated with these persons using various distributed algorithms for sharing of knowledge between agents, such as word-of-mouth.


WHAT IS ITS PURPOSE?

The purpose of this model is to demonstrate some important concepts in relation to communication amongst agents in a network such as the small world phenomenon, degrees of separation, super-nodes in peer to peer networks and communication via word-of-mouth.


HOW IT WORKS

The model implements the search algorithms in a novel way by making use of an agent-oriented approach which is relatively easy to implement in NetLogo. The model adopts a purely agent-oriented solution where the information is distributed amongst NetLogo agents. Unlike the traditional search algorithms (such as uninformed searches like Breadth-first Search, and Depth-first Search, or the informed searches such as Greedy Best-first Search and A* that are implemented in the Searching for Kevin Bacon model), these agents conduct the search by sharing knowledge with other agents that are concurrently conducting the search. In the word-of-mouth knowledge sharing method, if agents have found the goal, then they share their knowledge with other agents they meet while returning to their start destination. With the blackboard method, the agents share their knowledge by writing what they know into communal "blackboards" that are found at each node. This can then subsequently be read by agents who visit the node latter on. Two further knowledge sharing methods combine these two approaches - word-of-mouth and blackboard - in slightly different ways to create two new hybrid knowledge sharing schemes.

A breed of walker turtle agents is used for the agents that move throughout the maze trying to get to the goal. These searcher agents maintain information about the current state of the search such as the path they have taken. Each searcher agent expands the search by following the outgoing paths that lead out of the current node that were suggested as a result of the method of knowledge sharing they adopt.

A breed of dwalker agents are used to walk the network during the execution of Dijkstra's algorithm. This can be used to calculate the degree of separation for every node in the network from the goal node.


HOW TO USE IT

To initialise the search and create a random network (whose type is specified by the network-type chooser), press the setup-network button in the Interface. To setup a walker agent to search the network, first press the reset-blackboards and reset-walkers buttons to clear blackboards and remove any existing walkers, then press the setup-walkers button to create new ones. Several walker turtle agents (whose number is specified by the new-walkers-per-tick slider) will then be created and randomly located through the network. The setup-walkers button can be pressed multiple times if you wish more walkers to start the search.

To start the simulation, either press the go-walkers once button to make the search proceed one step at a time, or press the go-walkers button to make the search proceed continuously. The walkers will continue walking the network until they find the goal node or they expire without success if they have exceeded the time-to-live slider value. The links that the walker agents traverse across are briefly thickened to show the paths the agents are taking as they proceed in their search.

To plot the shortest path distances and find the average degree of separation from the goal node using Dijkstra's algorithm, press the go-dijkstra button.


THE INTERFACE

The model's Interface buttons are defined as follows:

- setup-network: This will clear the environment and all variables, and create a random network, whose type is specified by the network-type chooser. Its layout is specified by the layout-type chooser. The four sliders no-of-nodes, no-of-super-nodes, links-per-node and links-per-super-node control the number of nodes and super-nodes, and the number of links between them.

- change-layout: If the layout is of type spring, then this may help to remove some of the clutter.

- go-dijkstra: This plots the shortest path distances and find the average degree of separation from the goal node using Dijkstra's algorithm. The goal node is specified using the centre-of-the-universe chooser.

- reset-blackboards: This resets the blackboards that are associated with each node in the network. This is used by the Blackboard knowledge sharing mechanism.

- setup-walkers: This creates new walkers as specified by the number in the slider new-walkers-per-tick. These walkers will then start walking around the network trying to find the goal node.

- go-walkers-once: This will make the simulation proceed one step at a time.

- go-walkers-forever: This will make the simulation proceed continuously until it has reached the goal node or it gets stuck.

- reset-walkers: This kills off all existing searchers and creates new ones to restart the search as specified by the number in the slider new-walkers-per-tick.

- dump-blackboards: This will dump the contents of all the blackboards in the network (this can be used for debugging purposes).

- load-blackboards: This pre-loads the blackboards for each node using the shortest paths found using the Dijkstra algorithm. (This will improve the performance of the Blackboard knowledge sharing mechanism).

The model's Interface choosers, sliders, and switches are defined as follows:

- animate-dijkstra: This will animate the execution of Dijkstra's algorithm (that runs when the go-dijkstra button is pressed).

- revisits-allowed: If set to On, this will allow the agents to revisit already visited nodes.

- centre-of-the-universe: This sets the goal node that the agents are trying to find. It can be set to either Paul Erdos or Kevin Bacon. (These nodes are randomly created when the network is created).

- knowledge-sharing: This specifies the type of knowledge sharing the agents employ while walking around the network. The types of knowledge-sharing is as follows:
"None": The agents do not exchange any knowledge with other agents. As a result, the agents end up randomly walking around the network.
"Word-of-mouth": If the agents have found the goal, then they share their knowledge with other agents they meet while returning to their start destination.
"Blackboard": The agents share their knowledge by writing what they know into communal "blackboards" that are found at each node. This can then subsequently be read by agents who visit the node latter on.
"Combined 1" and "Combined 2": These combine the knowledge of the word-of-mouth and blackboard approaches in slightly different ways to create two new hybrid knowledge sharing schemes. The first scheme checks the blackboard first, then defaults to the word-of-mouth scheme if no knowledge exists in the blackboard. The second scheme does the reverse - it will apply word-of-mouth knowledge first before defaulting to the blackboard knowledge.

- network-type: This selects the type of network that is created when the setup-network button is pressed. The type of networks are as follows:
"P2P-no-super-nodes": This simulates a peer-to-peer network with no super-nodes.
"P2P-has-super-nodes": This simulates a peer-to-peer network with super-nodes.
"P2P-random-single-link": This simulates a peer-to-peer network where each node has only one link with another random node.
"P2P-incremental": This creates the simulated peer-to-peer network by incrementally building the links to other random nodes one at a time.
"P2P-incremental-1": This creates the simulated peer-to-peer network by incrementally building links to other random nodes.
"Star-central-hub": This creates a network with one node (the Kevin Bacon node; i.e. the goal node) as the central hub and all other nodes linked to it and not to any other node.
"Hierarchical": This creates a tree network with the Kevin Bacon goal node at the root.

- layout-type: This specifies how the network should be laid out when it is visualised.

- no-of-nodes: This is the number of nodes to place in the network.

- no-of-super-nodes: This is the number of super-nodes to place in the network. (These are nodes that usually will have significantly more links than standard nodes as specified by links-per-super-node slider).

- links-per-node: This specifies the maximum number of links a standard node will have. The actual number chosen for a particular node will be a random number between 1 and this number.

- links-per-super-node: This specifies the maximum number of links a super-node will have. The actual number chosen for a particular super-node will be a random number between 1 and this number.

- simulation-ticks: This specifies how long the simulation should run for.

- network-update: If non-zero, this will cause the network to be updated at an interval according to a random number from 0 up to the value of this slider.

- nodes-to-add: The number of nodes specified by this slider will be added to the network when the next update occurs according to the network-update slider.

- nodes-to-delete: The number of nodes specified by this slider will be deleted from the network when the next update occurs according to the network-update slider.

- new-walkers-per-tick: This sets the number of walker agents that are added each tick of the simulation.

- time-to-live: This sets how long the walker agents should remain active if they have not found the goal node before being killed off.

- new-walkers-per-node: This sets the number of walkers that are created to continue the search in multiple different directions when each walker visits each node. Setting this number higher than 1 will quickly flood the network in most circumstances.

- percent-in-both: When the network is created, a number of nodes will be created that are connected to the Paul Erdos node (i.e. a path exists that will eventually lead to Paul Erdos), and a number will be created that are connected to Kevin Bacon. This slider controls how many of the nodes will be doubly connected (i.e. paths exist from the node that will lead to both the Paul Erdos and Kevin Bacon nodes).

The model's Interface plots monitors (shown on the right) are defined as follows:

- Number of walkers: This plot shows the number of walkers per tick.

- Successful searches: This plot shows the number of successful searches (i.e. walkers that have found the goal node) per tick.

- Shortest path distances: This plot is plotted when the go-dijkstra button is pressed. It plots the shortest path distances from each node to the goal node.

- #Nodes: This monitor reports the number of nodes in the network. It will change if the network is updated when the network-update, nodes-to-add and nodes-to-delete sliders are all non-zero.

- #Walkers: This monitor reports the number of active walker agents in the network.

- #Visited: This monitor reports the number of nodes visited by the walker agents.

- %Success: This monitor reports the percentage of walker agents that have been successful in reaching the goal node.


THINGS TO NOTICE

Notice how well the agents perform at finding the goal node when the knowledge sharing method is set to None. Compare this with the other knowledge sharing methods.

Notice that the blackboard knowledge sharing mechanism usually outperforms the word of mouth mechanism in terms of the percentage of successful searches.

Notice that pre-loading the blackboards with shortest path information gained from execution of Dijkstra's algorithm can significantly improve the search.

Notice that when there is a learning effect due to the knowledge sharing mechanism, the Successful Searches plot will start to curve upwards rather then continue as a straight line. Why is this? What settings and type of networks does this occur for? Can you get the curve to bend downwards instead of upwards? (Hint: Try changing the value of one or two of the sliders mid-stream).

Notice how the effectiveness of the search deteriorates as the network changes when nodes are either added or deleted. Which type of knowledge sharing method seems to cope best with a dynamic network?

Notice the effect of turning the flag allow-revisited-states? On and Off. Why is turning it Off so effective at dramatically reducing the search for the different search behaviours?

Notice how the agents shown when the Dijkstra's algorithm is animated seem to jump all around the network. Why is this?


THINGS TO TRY

Which knowledge sharing behaviour seems to be the best at this problem? Which seems to be the worst? Try out each of the different knowledge sharing behaviours to see which one is the most effective.

Try setting low and high values for the time-to-live slider. How does this affect the percentage of successful searches and the number of nodes visited as a result?

Try pressing the setup-walkers button multiple times. This will start the search with more than one walker.

Try out all the different types of networks with different slider settings. Which types of network causes problems for the various knowledge sharing methods, and which do not? i.e. Which seem to be more difficult to search?

Try switching the knowledge sharing behaviour mid-stream to see if there is any noticeable effect. For example, try switching from a Word-of-Mouth sharing method to a Blackboard sharing method then back again.


EXTENDING THE MODEL

Try adding other knowledge sharing mechanisms, or adding your own variations to the ones implemented in the model.

Try adding your own type of network, either randomly created or with a correspondence to a network in real-life. You will need to add input routines to create the network layout for the latter.

Instead of having the walker agents searching for a single node in the network, try adding resources to each node so that the simulation is similar to the resource discovery problem where a resource (such as an MP3 file) might appear at multiple nodes throughout the network, and each node will have many resources (up to tens of 1000s). You will need to add a resources variable to the nodes-own field where the resources is a table that contains the names of the resources that the node holds locally.

Try turning off the visualisation of the network by using the hide-turtle command to hide all agents and links. This will allow you to run much larger simulations - up to 100,000s of nodes.


NETLOGO FEATURES

Note the use of the hatch and die commands to create new child walkers at each node and terminate all existing walkers. Note also how the next-locations-list parameter for the expand-walkers command determines the knowledge sharing strategy being used that defines the different searches.


RELATED MODELS

See the Searching for Kevin Bacon model.


CREDITS AND REFERENCES

This model was created by William John Teahan.

To refer to this model in publications, please use:

Being Kevin Bacon NetLogo model.
Teahan, W. J. (2010). Artificial Intelligence. Ventus Publishing Aps.


PROCEDURES

; Being Kevin Bacon model.
;
; Demonstrates communication in a network, Dijkstra's algorithm and the small world
; phenomenon.
;
; Copyright 2010 William John Teahan. All Rights Reserved.


extensions [ array table ]

breed [nodes node]
breed [walkers walker]
breed [dwalkers dwalker] ;; for performing the Dijkstra algorithm

nodes-own
[link-type    ;; link type: erdos, bacon and both
 blackboard   ;; table used when the knowledge-sharing of the walkers = "Blackboard"
 net-depth]   ;; used when building some of the networks  

walkers-own
[location     ;; the node where the walker is located
 path         ;; the path taken by the walker
 wom-path     ;; the path suggested by another walker by "word-of-mouth"
 goal         ;; the goal node that the walker wants to reach
 ticks-alive] ;; the number of ticks the walker has been alive

globals
[erdos-set              ;; nodes linked with Paul Erdos node
 bacon-set              ;; nodes linked with Kevin Bacon node
 paul-erdos             ;; node associated with Paul Erdos
 kevin-bacon            ;; node associated with Kevin Bacon
 paul-erdos-no          ;; node number associated with Paul Erdos node
 kevin-bacon-no         ;; node number associated with Kevin Bacon node
 network-update-count   ;; used for controlling when the network gets updated
 dijkstra-distances     ;; shortest path distance from initial node to all other nodes
 dijkstra-directions    ;; which direction to head in for shortest path
 nodes-visited          ;; total number of nodes visited by all walkers
 successful-searches    ;; number of successful searches completed by the walkers
 unsuccessful-searches  ;; number of unsuccessful searches not completed by the walkers
 max-distance ]         ;; a number that exceeds the maximum possible distance in the network

to reset-counts
;; Resets the counts used in some of the plots.
  set nodes-visited 0
  set successful-searches 0
  set unsuccessful-searches 0
end

to create-network [number-of-nodes]
;; Creates number-of-nodes new nodes in the network.
  create-nodes number-of-nodes
  [
    set blackboard table:make ;; used by walkers if applying the blackboard knowledge sharing method
    
    ifelse (random 100 < percent-in-both)
      [ set link-type 0 ;; both erdos and bacon node
        set color red
        set label (word "eb" who "    ") ]
   ;else
      [ ifelse (random 2 = 0)
          [ set link-type 1 ;; erdos node
            set color lime
            set label (word "e" who "    ") ]
          [ set link-type 2 ;; bacon-node
            set color blue
            set label (word "b" who "    ") ]]
  ]

  set erdos-set nodes with [link-type = 1 or link-type = 0] ;; erdos nodes
  set bacon-set nodes with [link-type = 2 or link-type = 0] ;; bacon nodes
end

to setup-network
  clear-all
  set-default-shape nodes "circle 2"
  set-default-shape dwalkers "person"
  ;; create a random network

  reset-counts
  
  set max-distance 9999999 ;; this number must be greater than maximum path length in the network
  
  if (network-update > 0) [ set network-update-count random network-update ]

  create-network no-of-nodes

  set paul-erdos min-one-of erdos-set [ who ]
  set kevin-bacon min-one-of bacon-set [ who ]
  ask paul-erdos [ set color magenta set paul-erdos-no who ]
  ask kevin-bacon [ set color orange set kevin-bacon-no who ]
  
  create-network-links
                
  reset-layout
end

to create-network-links
;; creates the network links for the nodes that have none
;; according to the network-type
  ifelse (network-type = "P2P-no-supernodes")
    [ create-network-P2P-no-super-nodes ]
    [ ifelse (network-type = "P2P-has-super-nodes")
      [ create-network-P2P-has-super-nodes ]
      [ ifelse (network-type = "P2P-random-single-link")
        [ create-network-P2P-random-single-link ]
        [ ifelse (network-type = "P2P-incremental")
          [ create-network-P2P-incremental ]
          [ ifelse (network-type = "P2P-incremental-1")
            [ create-network-P2P-incremental-1 ]
              [ ifelse (network-type = "Star-central-hub")
                [ create-network-star-central-hub ]
                [ create-network-hierarchical]]]]]]
end

to reset-layout
  clear-drawing
  
  layout
  
  ;; leave space around the edges
  ask nodes [ setxy 0.95 * xcor 0.95 * ycor ]
end

to change-layout
  ask walkers [ die ] ;; kill off all current walkers as where their current location may no longer be a correct node position 
  reset-layout
end

to layout
  ifelse layout-type = "spring"
    [ ifelse (network-type = "P2P-no-supernodes" or network-type = "P2P-has-super-nodes")
    ;;incremental" or network-type = "P2P-incremental-1" or network-type = "hierarchical")
      [ repeat 500 [ layout-spring nodes links 0.1 9 5 ]]
      [ repeat 500 [ layout-spring nodes links 0.5 2 1 ]]]

;;else
    [ ifelse layout-type = "circle"
      [ let radius ifelse-value (max-pxcor <= max-pycor) [max-pxcor - 1] [max-pycor - 1]
        layout-circle nodes radius ]
      [ ifelse (centre-of-the-universe = "Paul Erdos")
        [ layout-radial nodes links paul-erdos ]
        [ layout-radial nodes links kevin-bacon ]]
    ]
end

to update-network
;; updates the network by adding or deleting nodes
  if (network-update > 0)
  [
    ifelse (network-update-count > 0)
      [ set network-update-count network-update-count - 1 ] ;; count down to next update
      [ ;; delete some random nodes first
        if (nodes-to-delete > 0) and (nodes-to-delete < count nodes)
          [ ask n-of nodes-to-delete nodes
            [ if self != paul-erdos and self != kevin-bacon ;; don't delete Paul Erdos or Kevin Bacon
              [ ask my-links [ die ]
                ask walkers-here [ die ]
                die ]]]
        ;; now add in new nodes at random
        if (nodes-to-add > 0)
          [ create-network nodes-to-add
            create-network-links ]

        set network-update-count random network-update ;; reset count down to next update
      ]
  ]
end

to create-network-P2P-no-super-nodes
;; creates a P2P (peer-to-peer) layout without "super-nodes"
  let erdos-count count erdos-set
  let bacon-count count bacon-set
  let erdos-links ifelse-value (links-per-node < erdos-count) [links-per-node] [erdos-count]
  let bacon-links ifelse-value (links-per-node < bacon-count) [links-per-node] [bacon-count]

  let n 0
  ask erdos-set
  [ if count my-links = 0
    [ set n random (erdos-links - 1) + 1
      create-links-with n-of n other erdos-set ]];; create at least one link, but not to itself
  ask bacon-set
  [ if count my-links = 0
    [ set n random (bacon-links - 1) + 1
      create-links-with n-of n other bacon-set ]];; create at least one link, but not to itself
end

to create-network-P2P-has-super-nodes
;; creates a P2P (peer-to-peer) layout without "super-nodes"
  let erdos-count count erdos-set
  let bacon-count count bacon-set
  let erdos-links ifelse-value (links-per-node < erdos-count) [links-per-node] [erdos-count]
  let bacon-links ifelse-value (links-per-node < bacon-count) [links-per-node] [bacon-count]
  let erdos-slinks ifelse-value (links-per-super-node < erdos-count - 1) [links-per-super-node] [erdos-count - 1]
  let bacon-slinks ifelse-value (links-per-super-node < bacon-count - 1) [links-per-super-node] [bacon-count - 1]

  let n 0
  ask erdos-set
  [ if count my-links = 0
    [ set n random erdos-links + 1
      create-links-with n-of n other erdos-set ]];; create at least one link, but not to itself
  ask bacon-set
  [ if count my-links = 0
    [ set n random bacon-links + 1
      create-links-with n-of n other bacon-set ]];; create at least one link, but not to itself

  ;; now create super-nodes, making sure paul erdos and kevin bacon are included
  ask paul-erdos 
  [ if count my-links = 0
    [ set n random erdos-slinks + 1 ;; create at least one link
      create-links-with n-of n other erdos-set ]] ;; but not to itself
  ask kevin-bacon
  [ if count my-links = 0
    [ set n random bacon-slinks + 1 ;; create at least one link
      create-links-with n-of n other bacon-set ]] ;; but not to itself
  ask n-of (no-of-super-nodes - 1) erdos-set
  [ if count my-links = 0
    [ set n random erdos-slinks + 1 ;; create at least one link
      create-links-with n-of n other erdos-set ]] ;; but not to itself
  ask n-of (no-of-super-nodes - 1) bacon-set
  [ if count my-links = 0
    [ set n random bacon-slinks + 1 ;; create at least one link
      create-links-with n-of n other bacon-set ]] ;; but not to itself
end

to create-network-P2P-random-single-link
  ask erdos-set
      [ if count my-links = 0
        [ create-link-with one-of other erdos-set ]]
  ask bacon-set
      [ if count my-links = 0
        [ create-link-with one-of other bacon-set ]]
end

to create-network-P2P-incremental
  let erdos-set1 (list paul-erdos)
  let bacon-set1 (list kevin-bacon)
  
  foreach but-first sort erdos-set
  [ ask ?
      [ if count my-links = 0
        [ create-link-with one-of erdos-set1
          set erdos-set1 fput ? erdos-set1 ]]]
  foreach but-first sort bacon-set
  [ ask ?
      [ if count my-links = 0
        [ create-link-with one-of bacon-set1
          set bacon-set1 fput ? bacon-set1 ]]]
end

to create-network-P2P-incremental-1
  ask nodes [ set net-depth 0 ]

  ask paul-erdos
      [ create-link-with one-of other erdos-set
        ask link-neighbors [set net-depth 1 ]]
  ask erdos-set
      [ if (net-depth = 0) and (count my-links = 0)
        [
          create-link-with one-of erdos-set with [net-depth = 1]  
          set net-depth 1
        ]
      ]

  ask kevin-bacon
      [ create-link-with one-of other bacon-set
        ask link-neighbors [set net-depth 1 ]]
  ask bacon-set
      [ if (net-depth = 0) and (count my-links = 0)
        [
          create-link-with one-of bacon-set with [net-depth = 1]  
          set net-depth 1
        ]
      ]
end

to create-network-star-central-hub
  let erdos-count-1 count erdos-set - 1
  let bacon-count-1 count bacon-set - 1
  ask paul-erdos
      [ if count my-links = 0
        [ create-links-with n-of erdos-count-1 other erdos-set ]]
  ask kevin-bacon
      [ if count my-links = 0
        [ create-links-with n-of bacon-count-1 other bacon-set ]]
end

to create-network-hierarchical
  ask nodes [ set net-depth 0 ]

  ask paul-erdos ;; root of Paul Erdos sub-network
    [ set net-depth 1
      ifelse (count other erdos-set < links-per-node)
        [ create-links-with other erdos-set ]
        [ create-links-with n-of links-per-node other erdos-set ]
      ask link-neighbors [ set net-depth 2 ]]
  let depth 2
  let this-links 0
  let this-count 0
  while [count erdos-set with [net-depth = 0] > 0] ;; while still more nodes to place in network
      [ ask erdos-set with [net-depth = depth]
          [ set this-count count erdos-set with [net-depth = 0]
            set this-links ifelse-value (links-per-node < this-count) [links-per-node] [this-count]
            create-links-with n-of this-links erdos-set with [net-depth = 0]
            ask link-neighbors [ set net-depth depth + 1 ]]
        set depth depth + 1]
             
  ask nodes [ set net-depth 0 ]
  ask kevin-bacon ;; root of Kevin-Bacon sub-network
      [ set net-depth 1
        ifelse (count other bacon-set < links-per-node)
          [ create-links-with other bacon-set ]
          [ create-links-with n-of links-per-node other bacon-set ]
        ask link-neighbors [ set net-depth 2 ]]
  set depth 2
  set this-links 0
  set this-count 0
  while [count bacon-set with [net-depth = 0] > 0] ;; while still more nodes to place in network
      [ ask bacon-set with [net-depth = depth]
          [ set this-count count bacon-set with [net-depth = 0]
            set this-links ifelse-value (links-per-node < this-count) [links-per-node] [this-count]
            create-links-with n-of this-links bacon-set with [net-depth = 0]
            ask link-neighbors [ set net-depth depth + 1 ]]
        set depth depth + 1]

end

to reset-blackboards
;; resets the blackboards at each node
  ask nodes [ table:clear blackboard ]
end

to dump-blackboards
;; dumps out the blackboards at each node
  ask nodes [ type "Blackboard at " print self print table:to-list blackboard ]
end

to setup-walkers
;; creates some new walkers
  create-walkers new-walkers-per-tick
  [
    set color red
    set goal one-of nodes
    set location one-of nodes
    move-to location
    set path (list location)
    set wom-path []
    set ticks-alive 0
  ]
end

to reset-walkers
;; resets the walkers by first killing off all existing ones, then
;; creating new ones, and resetting related counts and plots
  ask walkers [ die ] ;; kill off existing walkers
  ask links [ set thickness 0 ] ;; reset all network links to uncrossed
  reset-counts
  setup-walkers
  set-current-plot "Number of walkers"
  clear-plot
  set-current-plot "Successful searches"
  clear-plot
  reset-ticks
end

to expand-walkers [new-locations-list]
  let new-walkers-count length new-locations-list
  let new-location 0

  hatch-walkers new-walkers-count
  [ ;; create a new walker at location to continue the search
    ;; and move to new location
    set ticks-alive ticks-alive + 1
    ; print ticks-alive
    set new-location first new-locations-list ;; pop off the next location to visit
    set new-locations-list but-first new-locations-list
    ifelse (not revisits-allowed and member? new-location path)
    [ die ] ;; don't revisit nodes already visited unless allowed to
    [
      if (new-location != nobody) and ([link-with new-location] of location != nobody)
      [  
        ask [link-with new-location] of location [ set thickness 0.4 ] ;; highlight link I am crossing
        face new-location  ;; not strictly necessary, but improves the visuals a bit
        move-to new-location
        set location new-location
        set path fput new-location path
        if new-location = goal ;; success - no need to hang around any longer
        [ set successful-searches successful-searches + 1
          update-along-path self "S" ;; update information along path if necessary; "S" means success
          die ] ;; die happy
      ]
    ]
  ]
end

to go-walkers
;; make the walkers continue the search
  if (simulation-ticks > 0) and (ticks > simulation-ticks)
    [ stop ]

  update-network

  setup-walkers
  ask links [ set thickness 0 ]
  ask walkers
  [
    set nodes-visited nodes-visited + 1
    ifelse (ticks-alive >= time-to-live) ;; lived too long without success - kill it off
    [ set unsuccessful-searches unsuccessful-searches + 1
      update-along-path self "F";; update information along path if necessary; "F" means failure
    ]
    [ ;; create new walkers to move to new location(s)
      expand-walkers (next-locations location)
    ]
    die ;; always die - the minions have already been sent out to continue the search for me
  ]

  plot-walkers
  tick
end

to-report next-locations [this-location]
;; find out the new locations to search for this-location
;; apply the search method using the knowledge sharing method or none e.g. choose randomly

  if (knowledge-sharing = "Word of mouth")
    [ ;; Word of mouth knowledge sharing method
      report next-locations-word-of-mouth this-location
    ]

  if (knowledge-sharing = "Blackboard")
    [ ;; Blackboard knowledge sharing method
      report next-locations-blackboard this-location
    ]

  if (knowledge-sharing = "Combined 1")
    [ ;; Blackboard knowledge sharing method
      report next-locations-combined-1 this-location
    ]
 
   if (knowledge-sharing = "Combined 2")
    [ ;; Blackboard knowledge sharing method
      report next-locations-combined-2 this-location
    ]

  ;; Default method is No knowledge sharing; i.e. knowledge-sharing = "None"
  report next-locations-no-knowledge-sharing this-location
end

to-report next-locations-no-knowledge-sharing [this-location]
;; returns the new locations to search for this location
;; uses random choices; no knowledge sharing
  let new-locations [link-neighbors] of this-location
  if count new-locations > new-walkers-per-node
    [ set new-locations n-of new-walkers-per-node new-locations ]

  report sort new-locations
end

to-report next-locations-word-of-mouth [this-location]
;; returns the new locations to search for this location
;; using the word-of-mouth knowledge sharing method
  if empty? wom-path
    [ ask walkers-here
      [ ;; does any of them know where the goal is?
        if (this-location = first path) and (member? [goal] of myself path)
          [ ask myself
            [ set wom-path but-first path ]
            ;; type "asked " type who type " goal = " type [goal] of myself type " this-loc = " type this-location type " path = " print path
            stop ]
      ]
    ]
  if not empty? wom-path
    [ ;; we have been told where to go
      ;; head back along the word of mouth path
      let this-loc first wom-path
      set wom-path but-first wom-path
      ;; type "found goal " type goal type " at " type this-loc type " in path " print wom-path
      report (list this-loc)
    ]

  ;; no word of mouth path; default to random choices (i.e. same as no knowledge sharing)
  report next-locations-no-knowledge-sharing this-location
end

to-report next-locations-blackboard [this-location]
;; returns the new locations to search for this location
;; using the blackboard knowledge sharing method

  ;;type "Blackboard for location " type this-location type " = " print [blackboard] of this-location

  let dist 0
  let this-path nobody
  let key-dist (word ([goal] of self) " dist")
  let key-path (word ([goal] of self) " path")

  ifelse (not table:has-key? [blackboard] of this-location key-path)
    [ set dist max-distance ] ;; no blackboard path
    [ set dist table:get [blackboard] of this-location key-dist
      set this-path table:get [blackboard] of this-location key-path ]

  ifelse (dist >= max-distance)
    [ ;; no blackboard path; default to random choices (i.e. same as no knowledge sharing)
      report next-locations-no-knowledge-sharing this-location ]
    [ ;; follow the blackboard path that has been found to be shortest
      report (list this-path) ]
  
end

to-report next-locations-combined-1 [this-location]
;; returns the new locations to search for this location
;; using the combined-1 knowledge sharing method
  let dist 0
  let this-path nobody
  let key-dist (word ([goal] of self) " dist")
  let key-path (word ([goal] of self) " path")

  ifelse (not table:has-key? [blackboard] of this-location key-path)
    [ set dist max-distance ] ;; no blackboard path
    [ set dist table:get [blackboard] of this-location key-dist
      set this-path table:get [blackboard] of this-location key-path ]

  ifelse (dist >= max-distance)
    [ ;; no blackboard path; default to word-of-mouth
      report next-locations-word-of-mouth this-location ]
    [ ;; follow the blackboard path that has been found to be shortest
      report (list this-path) ]
end

to-report next-locations-combined-2 [this-location]
;; returns the new locations to search for this location
;; using the combined-2 knowledge sharing method
  if empty? wom-path
    [ ask walkers-here
      [ ;; does any of them know where the goal is?
        if (this-location = first path) and (member? [goal] of myself path)
          [ ask myself
            [ set wom-path but-first path ]
            ;; type "asked " type who type " goal = " type [goal] of myself type " this-loc = " type this-location type " path = " print path
            stop ]
      ]
    ]
  if not empty? wom-path
    [ ;; we have been told where to go
      ;; head back along the word of mouth path
      let this-loc first wom-path
      set wom-path but-first wom-path
      ;; type "found goal " type goal type " at " type this-loc type " in path " print wom-path
      report (list this-loc)
    ]

  ;; no word of mouth path; default to blackboard
  report next-locations-blackboard this-location
end

to update-along-path [this-walker value]
;; updates information along the path when the knowledge sharing method
;; is "Blackboard" or combined

  let p 0
  let val 0
  let val1 0
  let key-dist ""
  let key-path ""
  
  if knowledge-sharing = "Blackboard" or
     knowledge-sharing = "Combined 1" or
     knowledge-sharing = "Combined 2"
  [
    ask this-walker
    [
      ;;type "goal = " type goal type " path = " show path
      let this-goal goal
      let prev first path
      foreach but-first path
      [
        set key-dist (word this-goal " dist")
        set key-path (word this-goal " path")

        ifelse (value = "F")
          [ set val max-distance ] ;; failure - node was not found
          [ set val p + 1 ] ;; calculate the position in the path
        ;;type "putting into blackboard for node " type ? type " : " type key-dist type " val: " print val
        
        if is-turtle? ? ;; does the node exist? (it may have been deleted)
        [
          ask ? ;; update blackboards along the path if path to goal is shorter
          [ ifelse (not table:has-key? blackboard key-dist)
              [ set val1 max-distance + 1 ] ;; no entry exists - make sure new entry is added
              [ set val1 table:get blackboard key-dist ]
            if (val < val1)
              [ table:put blackboard key-dist val
                table:put blackboard key-path prev ]]
        ]
        set prev ?
        set p p + 1
      ]
    ]
  ]
end

to plot-walkers
;; Reports results from data gathered by the walkers.

  set-current-plot "Successful searches"
  ;;let total successful-searches + unsuccessful-searches
  ;;let s ifelse-value (total = 0) [0] [100 * successful-searches / total]
  ;;plot s
  plotxy successful-searches + unsuccessful-searches successful-searches
    
  set-current-plot "Number of walkers"
  plot count walkers
end

to-report report-nodes
  report count nodes
end

to-report report-walkers
  report count walkers
end

to-report report-nodes-visited
  report nodes-visited
end

to-report report-success-rate
  report 100.0 * successful-searches / (successful-searches + unsuccessful-searches)
end 

to initialise-distances [initial-node]
;; initialises the shortest path distances between nodes in the network to 0
  let number-of-nodes max [who] of nodes + 1

  set dijkstra-distances array:from-list n-values number-of-nodes [number-of-nodes + 1] ;; "infinity"
  set dijkstra-directions array:from-list n-values number-of-nodes [nobody]
  array:set dijkstra-distances initial-node 0 ;; set distance to 0 for initial node
end

to perform-dijkstra [initial-node nodes-to-visit]
;; calculates the distance array for the Dijkstra algorithm using the initial node
;; as the focal point

  set nodes-visited 0
  
  initialise-distances [who] of initial-node
  
  let visited-set [] ;; this is the list of nodes that have been visited
  let unvisited-set nodes-to-visit ;; this is the list of nodes yet to have been visited

  let this-dwalker nobody
  if (animate-dijkstra)
    [ create-dwalkers 1 [ set color white set size 2 set this-dwalker who ]]
      
  let current-node initial-node
  while [count unvisited-set > 0]
  [
    if (animate-dijkstra)
      [ ask dwalker this-dwalker [ setxy [xcor] of current-node [ycor] of current-node display wait 0.1 ]]
   
    ask current-node
    [
      set nodes-visited nodes-visited + 1
      set visited-set fput who visited-set
      set unvisited-set other unvisited-set

      ask link-neighbors
      [
        let dist-thru-here (array:item dijkstra-distances [who] of current-node) + 1
        let dist-thru-to-there array:item dijkstra-distances who
        if (dist-thru-here < dist-thru-to-there)
          [ array:set dijkstra-distances who dist-thru-here
            array:set dijkstra-directions who [who] of current-node ]
      ]
      
      ;; set the current-node to the remaining unvisited node that has the smallest distance to the initial node      
      set current-node min-one-of unvisited-set [array:item dijkstra-distances who]
    ]
  ]
  
  ;; print array:to-list dijkstra-distances

  if (animate-dijkstra)
    [ wait 0.2 ask dwalker this-dwalker [ die ]]
end

to go-dijkstra
;; Run directly by the interface button - calculates the distance array for the Dijkstra algorithm

  let initial-node nobody
  ifelse (centre-of-the-universe = "Paul Erdos")
    [ set initial-node paul-erdos ]  ;; set the initial node to the node associated with Paul Erdos
    [ set initial-node kevin-bacon ] ;; set the initial node to the node associated with Kevin Bacon
  
  initialise-distances [who] of initial-node
  
  let nodes-to-visit [] ;; this is the list of nodes yet to have been visited
  ifelse (centre-of-the-universe = "Paul Erdos")
    [ set nodes-to-visit erdos-set ]
    [ set nodes-to-visit bacon-set ]

  perform-dijkstra initial-node nodes-to-visit

  dump-dijkstra-directions
      
  plot-dijkstra
end

to dump-dijkstra-directions
  let i 0
  foreach array:to-list dijkstra-directions
  [
    if (? != nobody) [ type " from: " type i type " thru: " type ? type " dist: " print array:item dijkstra-distances i ]
    set i i + 1
  ]
end

to plot-dijkstra
;; Reports results from data gathered by execution of the dijkstra
;; algorithm.
  set-current-plot "Shortest path distances"
  clear-plot
  let number-of-nodes report-nodes
  let d array:to-list dijkstra-distances
  let dmin number-of-nodes + 1
  let dmax 0
  let cnt 0
  let avg-total 0
  foreach d
  [ ;; find min and max of x and y ranges for the plot first
    ;; also calculate cumulative total for average
    if (? <= number-of-nodes)
      [
        set cnt cnt + 1
        set avg-total ? + avg-total
        if (? > dmax) [ set dmax ? ]
        if (? < dmin) [ set dmin ? ]
      ]
  ]
  set-plot-x-range 0 cnt
  set-plot-y-range dmin dmax
  foreach d
  [ ;; now plot it
    if (? <= number-of-nodes)
      [ plot ? ]
  ]
  user-message (word "The average path length to " centre-of-the-universe " is " (avg-total / cnt))
end

to load-blackboards-using-shortest-paths
;; pre-loads the blackboards for each node using the shortest paths
;; found using the Dijkstra algorithm

  let i 0
  let this-node nobody
  let key-dist ""
  let key-path ""
  
  foreach sort nodes
  [
    set this-node ?
    perform-dijkstra this-node nodes

    set i 0
    foreach array:to-list dijkstra-directions
    [
      if (? != nobody)
      [ ;; type "goal: " type this-node type " from: " type i type " thru: " type ? type " dist: " print array:item dijkstra-distances i

        set key-dist (word this-node " dist")
        set key-path (word this-node " path")
        table:put [blackboard] of node i key-dist (array:item dijkstra-distances i)
        table:put [blackboard] of node i key-path node ?
        ask node i
        [ 
        ]
      ]
      set i i + 1
    ]
  ] 
end
;
; Copyright 2010 by William John Teahan.  All rights reserved.
;
; Permission to use, modify or redistribute this model is hereby granted,
; provided that both of the following requirements are followed:
; a) this copyright notice is included.
; b) this model will not be redistributed for profit without permission
;    from William John Teahan.
; Contact William John Teahan for appropriate licenses for redistribution for
; profit.
;
; To refer to this model in publications, please use:
;
; Teahan, W. J. (2010).  Being Kevin Bacon NetLogo model.
;   Artificial Intelligence. Ventus Publishing Aps.
;