Kruskals Spanning Tree

No preview image

2 collaborators

Turtlezero2-white-048 James Steiner (Author)
Head-shot Jim Lyons (Domain expert)

Tags

computer science 

Tagged by Ali Akhtari almost 2 years ago

mouse 

Tagged by James Steiner about 12 years ago

networks 

Tagged by James Steiner about 12 years ago

realtime 

Tagged by James Steiner about 2 years ago

Visible to everyone | Changeable by the author
Model was written in NetLogo 6.2.2 • Viewed 905 times • Downloaded 56 times • Run 0 times
Download the 'Kruskals Spanning Tree' modelDownload this modelEmbed this model

Do you have questions or comments about this model? Ask them here! (You'll first need to log in.)


WHAT IS IT?

A model to demonstrate a method of constructing a minumum (or maximum) spanning tree for a network using Kruskal's algorithm.

HOW TO USE IT

Press RESET (this is done automatically when the model first loads) to generate a random network graph. Then graph is constructed using a method that guarantees the network will be one giant component, with a fair number of loops and such. Each edge in the graph is assigned a random weight in the range 1 to 100.

You can create multiple components by clicking "SPLIT"

Press find-spanning-tree to find the minimum-weight spanning tree of the graph. (if INVERT? is On, the maximum-weight spanning tree is found)

HOW DOES IT WORK?

In typical NetLogo idiom, the network is contructed using turtles of breed "vertices" connected by an undirected-link-breed "edges"

find-spanning-tree uses Kruskal's Algorithm, with some enhancements to allow early exit from the algorithm as soon as all vertexes in the graph have been processed.

To use Kruskal's algorithm:

First the vertices are assigned to sub-trees. Each vertice begins assigned to its own unique subtree. The who number is used to provide sub-tree id numbers.

Next the edges are sorted by weight.

Then, for each edge, in order:

If end1 and end2 of the current edge are not already in the same sub-tree, then the edge belongs in the spanning tree. The edge is so marked (IN-TREE? is set to true). Now, end2 and all other vertices in the same subtree as end2 are assigned to the subtree of end1. The unique count of vertice touched by edges added to the spanning tree is kept.

If there is another edges to process, and not every vertex has been touched, the next edge is processed.

SPECIAL TRICKS

This model features an in-view gui that is active even if no button is pressed. A monitor control (sort of hiding under the synch? switch) runs a procedure that updates the layout and detects mouse dragging and layout-properties sliders moving. Since monitors always run, and since NetLogo 4 updates the view if needed when only monitor code is running (prior NetLogos did not), we can have models that can start running (albeit in a slow mode) as soon as they load.

This could be useful for displaying instructions, displaying an "attract" mode to entice users to begin using the model, or, as in this case, to provide a more-or-less full-time in-view gui.

CREDITS

Thanks to Jim Lyons for his very clean implementation of Kruskal's algorithm, as described in [[ http://en.wikipedia.org/wiki/Kruskal's_algorithm ]], and dirted-up by me.

Quote:

 * create a forest F (a set of trees),
   where each vertex in the graph is a separate tree
 * create a set S containing all the edges in the graph
 * while S is nonempty
   o remove an edge with minimum weight from S
   o if that edge connects two different trees, then add it to the forest,
     combining two trees into a single tree
   o otherwise discard that edge

Of course, I had to go clutter it up, but the essense is there. I just didn't get the combining the forests and trees thing, that makes the whole thing so elegent and zippy.

Comments and Questions

Please start the discussion about this model! (You'll first need to log in.)

Click to Run Model

;; summary: A minimal spanning tree is not a narrow evergreen.
;; copyright: Copyright � 2007, James P. Steiner

globals
[ dragged ;; used by mouse-gui code
  oldpull ;; used to synch the layout properties sliders
  oldpush ;; used to synch the layout properties sliders
  gui-message ;; used by the mouse and animate code
]

undirected-link-breed [ edges edge ]
edges-own
[ weight   ;; the weight of this edge
  in-tree? ;; in this edge in the spanning tree?
]

breed [ vertices vertex ]
vertices-own
[ subtree ;; the ID of the component that this vertex belongs to
  tested? ;; in the current detection, has this vertex been tested yet?
  old-avg-link-len
  new-avg-link-len
  old-x
  old-y
]

to startup setup end

to setup
   ;; (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

  setup-patches
  ; no-display
  setup-network
  ; display
  ;; now that the network is created,
  ;; auto-layout the network for a short time
  ;; hopefully to make is more attractive
  layout-for-seconds 1
  reset-ticks
end 

to layout-for-seconds [ $seconds ]
   let t timer + $seconds
   while [ timer < t ] [ layout-spanning-tree ]
end 

to go
   ;; do the main kruskal thing
   vis-network-spanning-tree-only
   kruskal-spanning-tree
   vis-network-show-all
   layout-for-seconds 1
end 

to setup-network
   ;; create a number of vertices
   ;; connect them into a single component
   ;; apply weights to the edges
   set-default-shape vertices "circle"
   create-vertices vertex-count
   [ set size 1.0
     setxy random-xcor random-ycor
     set color 15 + 10 * (who mod 12)
     ;; apply default value for subtree id
     set subtree who
     ;; apply default value for spanning tree flag
     set tested? false
     if who > 0
     [ ;; get the set of vertices that this vertex might link with
       let candidates vertices with [ who < [ who ] of myself ]
       ;; pick a number of edges to make
       let edge-count 2 + random 3
       ;; can't make more edges than there are vertices
       ;; so fix number of edges so that it does not exceed
       ;; available number of vertices
       ;; (in this simple implementation,
       ;; vertices are created first, so
       ;; are numbered from 0 - up, and bear
       ;; consecutive numbers, so
       ;; (who - 1) is the number of vertices available
       ;; to make edges with this vertex.
       set edge-count min (list edge-count (who - 1) )

       ;; address the desired quantity of randomly selected vertexes
       ;; and make them make links with this vertex
       ask n-of edge-count candidates
       [ create-edge-with myself
         [ ;; apply default value for spanning tree flag
           set in-tree? false
           ;; apply weight to the edge
           set weight (1 + random 100)
           set thickness 0
           set label weight
           set label-color black
         ]
       ]
     ]
   ]
end 

to setup-patches
   ;; color the background in an attractive pattern
   ask patches [ set pcolor checkered 5 blue 3 .5 ]
end 

to-report checkered [ $size $hue $tint $diff] ;; patch / turtle reporter
   ;; report a color to the calling patch
   ;; this formula produces a checker-board (chess-board) pattern
   ;; of light and tints of the given color
   ;; hue = base color
   ;; tint = base tint of that color (-5...4.9)
   ;; diff = difference between the base tint and the lighter shade
   report ( $hue + $tint + $diff * (((floor(pxcor / $size)  + floor(pycor / $size) )) mod 2 ) )
end 

to JPS-spanning-tree-not-really-kruksal
   ; no-display
   ask edges [ set in-tree? false ]
   ask vertices [ set tested? false ]
   let sorted-edges sort-by [ [?1 ?2] -> [ weight ] of ?1 > [ weight ] of ?2 ] edges
   if invert? [ set sorted-edges reverse sorted-edges ]

   let verts-to-test vertices with [ any? my-edges ]

   foreach sorted-edges
   [ ?1 -> ask ?1
     [ ;; does this edge make a loop in the tree-so-far?
       ;; i.e. are both of its vertices already in the tree?
       ifelse ( in-loop? nobody end1 end2 )
       [ ;; yes. skip it.
       ]
       [ ;; no. add it to the tree
         set in-tree? true
         ask both-ends with [ not tested? ]
         [ set tested? true
           set verts-to-test verts-to-test - 1
         ]
       ]
     ]
     ;; once all vertices have been tested once, we are done.
     ;; remaining untested edges must form loops
     if verts-to-test <= 0 [ stop ]
   ]
end 

to kruskal-spanning-tree
   ;; identifies the vertices that compose the minimum (or max, if inverted) spanning tree(s)
   ;; for the network made of up the vertices and edges currently in existence

   ;; Note that if graph is not a single component,
   ;; then the results will be all the spanning trees for each component.

   ;; edges in the spanning tree are marked with in-tree? = true
   ;; vertices that have been processed and placed in a tree are marked in-tree? = true
   ;;

   ; no-display

   ;; reset the testing flag for the vertices
   ;; place each vertex in its own sub-tree
   ask vertices
   [ set tested? false
     set subtree who
   ]

   ;; reset the in-tree flag for the edges
   ask edges
   [ set in-tree? false
   ]

   let sorted-edges []

   ;; sort low to high
   set sorted-edges sort-on [ weight ] edges
   if invert? [ set sorted-edges reverse sorted-edges ]

   ;; store the number of vertices with edges
   let verts-to-test count ( vertices with [ any? my-edges ] )

   if slow? and not netlogo-web? [ vis-network-spanning-tree-only ]

   foreach sorted-edges
   [ ?1 -> ;; once all verts with edges have been placed in trees (and thus subtrees merged, as needed),
     ;; ...this loop is done.
     ;; any remaining edges are (by definition) loops, since they must connect
     ;; vertices that are already in the same tree

     ;; are there any connected vertices not accounted for?
     if verts-to-test >= 0
     [ ;; yes. so lets process this edge
       ask ?1
       [ ;; get subtrees of the endpoints
         let subtree-1 [subtree] of end1
         let subtree-2 [subtree] of end2
         ;; compare them. are they in different sub-trees?
         if subtree-1 != subtree-2
         [ ;; yes! (no loop is formed)
           ;; this edge in in the spanning tree--mark it
           set in-tree? true
           ;; mark one or both verts (which ever is not already in a spanning tree)
           ;; as being in a tree and
           ;; decrement the counter of connected vertices yet to be discovered
           ask both-ends with [ tested? = false ]
           [ set tested? true
             set verts-to-test verts-to-test - 1
           ]
           ;; "merge the forests"
           ;; i.e. connect the entire set of vertices in subtree 2 to subtree 1.
           ;; this is accomplished by assiging subtree 1 to the subtree variable
           ;; of all vertices in subtree 2.
           ;; # one way to do that is to use a one-line with-clause:
           ;; ----  ask vertices with [ subtree = subtree-2 ][set subtree subtree-1 ]
           ;; but that address all the vertices, every time we merge a subtree.
           ;; whether we are adding 1 vertice to the subtree or a hundred.
           ;; in a large network, that seems like a lot of extra work.
           ;; # another way to do it is to start with the subtree 2 end-point,
           ;; and traverse the spanning sub-tree away from the subtree 1 end-point
           ;; putting the vertices into the subtree as we go along
           ;; this is a lot more code, even if done recursively.
           ;; this is a non-recursive implementation.
           ;; for smaller networks, its not very efficient,
           ;; but luckily, that doesn't seem to matter as much
           ;; for larger networks, I think it is more efficient.

           ;; flow through the vertices in subtree-2, assigning them to subtree 1
           ;; ## need to test speed ##
           ask vertices with [ subtree = subtree-2 ][set subtree subtree-1 ]
           ;ask end2
           ;[ ;; assign to subtree 1
           ;  set subtree subtree-1
           ;  ;; get set of subtree 2 vertices
           ;  let connected-vertices edge-neighbors with [ subtree = subtree-2 ]
           ;  ;; if any, assign them to subtree 1, get next set
           ;  while [ any? connected-vertices ]
           ;  [ ask connected-vertices [ set subtree subtree-1 ]
           ;    set connected-vertices (turtle-set [ edge-neighbors with [ subtree = subtree-2 ] ] of connected-vertices)
           ;  ]
           ; ]
         ]

         ;; run-slowly mode is eye-candy to show the edges
         ;; being connected to the spanning-tree one by one

         if slow? and not netlogo-web? and in-tree?
         [ vis-display-edge false ; color the edge
          repeat 100 [ layout-spanning-tree  display ]
         ]
       ]
     ]
   ]
end 

to-report in-loop? [ a b c]
   ;; a recursive procedure to detect if an edge between node B and C
   ;; will form a loop in the network that contains A B and C.
   ;; Node A starts out as nobody, and B is passed as A in recursive calls.
   ;; this lets us remember the direction B is coming from as we recursively
   ;; traverse the network, and prevents the traversal from backing up.

   let result false
   ask b
   [ ;; get set of b's edges that are in the tree
     let tree-edges my-edges with [ in-tree? ]
     ifelse not any? tree-edges
     [ ;; if no edges from b in the tree, no loop!
       set result false ]
     [ ;; get set of b's vertices attached to b's in-tree edges,
       ;; that are NOT edges back the way we came (back to a)
       ;; these may be routes futher along the tree
       let tree-verts (turtle-set [ other-end ] of tree-edges) with [ self != a ]
       ifelse not any? tree-verts
       [ ;; if no way out of here, no loop!
         set result false
       ]
       [ ;; are any of these vertices that might be routes out of here
         ;; actually C?
         ifelse any? tree-verts with [ self = c ]
         [ ;; yes! egad! we've found a loop back to C!
           set result true
         ]
         [ ;; search further along these routes
           ;; see if any of them lead to c
           ifelse any? tree-verts with [ in-loop? b self c ]
           [ set result true ]
           [ set result false ]
         ]
       ]
     ]
   ]
   report result
end 

to vis-network-center
   ;; attempts to center the network in the view
   ;; then scale the graph to fill the view.
   ;; doesn't work as expected...
   ;; ## abandoned pending further work ##
   let cx  mean [ xcor ] of vertices
   let cy  mean [ ycor ] of vertices
   ask vertices [ carefully [ setxy (xcor - cx) (ycor - cy) ][]]
end 

to vis-network-scale
   stop
  let max-x  max [ abs xcor ] of vertices
   let max-y  max [ abs ycor ] of vertices
   let max-v  max list max-x max-y
   let scale  max-pxcor / max-v
   ask vertices [ carefully [ setxy xcor * scale ycor * scale ][]]
end 

to vis-network-rotate
  stop
  ask vertices
   [ facexy 0 0
     lt 90
     let d .1 * patch-size * distancexy 0 0 / world-width
     if can-move? d [ jump d ]
   ]
end 

to vis-display-edge [ show-only-tree? ]
   let pixel 1 / patch-size
   ;; modifies the display parameters of a single edge
   ifelse in-tree?
   [ set color green - 2  set label weight set hidden? false
   ]
  [ set color [ 128 0 0 50 ] ;
    set label weight set hidden? show-only-tree?
   ]
   ifelse in-tree? [ set thickness 2 * pixel ] [ set thickness 0 ]
end 

to vis-network-show-all
   ;; modifies edge and vertice display parameters
   ;; to show all the edges
   ask edges [ vis-display-edge false ]
   ask vertices [ set label "" hide-turtle ]
end 

to vis-network-spanning-tree-only
   ;; modifies edge and vertice display parameters
   ;; to show only the discovered spanning tree
   ;; if no spanning tree has been found yet,
   ;; all the edges are hidden
   ask edges [ vis-display-edge true ]
   ask vertices [ set color 15 + 10 * (who mod 12) set size 2 set label "" show-turtle ]
end 

to split-network-on-y-axis
   ;; delete edges along the y axis, thus turning a giant component
   ;; into at least 2 smaller component.
   ;; depending on the topology of the current network
   ;; may create 2 or more components,
   ;; as well as any number of unconnected vertices

   ;; first, scale and center the graph
   vis-network-center
   vis-network-scale

   ;; find edges that have one vertex to the left of y-axis (x < 0)
   ;; and the other vertex on or to the right of y-axis (x >= 0)
   ;; kill those vertices.
   ;; this will split the network into at least two components
   ;; and may create orphan vertices
   ask edges with [     first sort ([ xcor] of both-ends) < 0
                    and last sort ([ xcor] of both-ends) >= 0 ]
   [ die ]
end 

to-report limitx [ xx ]
   ;; report an xcor, making sure it is within the view limits
   report ( max ( list min-pxcor min ( list max-pxcor xx ) ) )
end 

to-report limity [ yy ]
   ;; report a ycor, making sure it is within the view limits
   report ( max ( list min-pycor min ( list max-pycor yy ) ) )
end 

to vis-network-color
   ;; does two things
   ;; pretty-colors the graph,
   ;; but also does a thing where it finds two endpoints with the largest possible number of hops between them.
   ;; more than one longest route can exist--this procedure finds one of them, and
   ;; will randomly select among them
   if not any? edges with [ in-tree? = true ]
   [ go ]
   let depth 1
   ask vertices [ set color 0 ]
   ask edges [ set color 0 ]
   ask one-of (vertices with [ count my-edges with [ in-tree?] = 1 ]);  [ who ]
   [ trav-set-color depth ]

   let bus-end-1 max-one-of vertices [ label ]
   let max-depth-1 [ label ] of bus-end-1


   set depth 1
   ask vertices [ set color 0 set size .5 ]
   ask edges [ set color 0 ]
   ask bus-end-1 [ trav-set-color depth ]

   let bus-end-2 max-one-of vertices [ label ]
   let max-depth-2 [ label ] of bus-end-2

   set depth 1
   ask vertices [ set color 0 set size .5 ]
   ask edges [ set color 0 ]
   ask bus-end-2 [ trav-set-color depth ]

   set bus-end-1 max-one-of vertices [ label ]
   set max-depth-1 [ label ] of bus-end-2


   ask bus-end-1 [ set size 3 ]
   ask bus-end-2 [ set size 3 ]
end 

to trav-set-color [ depth ]
   ;; traverse the graph, setting colors and incrementing a counter as we go.
   set color 5 + 10 * depth
   set label depth
   ask my-edges with [ in-tree? and color = 0 ]
   [ set color 5 + 10 * depth
     set label depth
     ask other-end
     [ if color = 0
       [ trav-set-color depth + 1 ]
     ]
   ]
end 

to layout-spanning-tree
  layout-spanning-tree-basic
end 

to layout-spanning-tree-basic
   let $rod layout-length
   ;; auto-layout the spanning tree
   ifelse not any? edges with [ in-tree? = true ]
   [
     layout-spring vertices (edges) layout-pull $rod layout-push
   ]
   [
     layout-spring vertices (edges with [ in-tree? = true ]) layout-pull $rod layout-push
   ]
   vis-network-center
   vis-network-scale
   vis-network-rotate
end 

to layout-spanning-tree-button
  if netlogo-web? [ stop ]
   layout-spanning-tree
   monitor-mouse
   set gui-message ""
end 

to-report background-animate
   monitor-push-pull
   ifelse ( background-animate? )
   [
     ;; run by a monitor, this procedure monitors some gui events
     ;; and handles them, even when no buttons are pressed
     ifelse gui-message = ""
     [ set gui-message "idle" ]
     [ layout-spanning-tree
       display
       monitor-mouse
       display
       set gui-message "active"
       display
     ]
     report gui-message
   ]
  [ report "idle" ]
end 

to monitor-mouse
   ;; detect and perform dragging of vertice in the view with the mouse
   ifelse is-vertex? dragged
   [ ifelse mouse-down?
     [ ask dragged [ setxy mouse-xcor mouse-ycor ask link-neighbors [ set color white ] ]
     ]
     [ ask dragged [ setxy mouse-xcor mouse-ycor ask link-neighbors [ set color 15 + 10 * (who mod 12) ] ]
       set dragged nobody
     ]
   ]
   [ if mouse-down?
     [ ask patch mouse-xcor mouse-ycor
      [ set dragged one-of vertices in-radius ( 20 / patch-size) ]
     ]
   ]
end 

to monitor-push-pull
   ;; if in synch mode, watch the layout push and pull sliders for changes
   ;; if either slider changes, change the other slider to match
   ( if-else
     ( synch? and layout-push != oldpush )
     [ set oldpush layout-push
       set layout-pull layout-push
       set oldpull layout-pull
     ]
     ( synch? and layout-pull != oldpull )
     [ set oldpull layout-pull
       set layout-push layout-pull
       set oldpush layout-push
     ]
   )
end 

; ask vertices [ let x (sum [ weight ] of my-edges with [ in-tree? ]) set size min (list 3 (x * .5)) set label precision x 2 ]

There are 6 versions of this model.

Uploaded by When Description Download
James Steiner about 2 years ago web-specific fixes Download this version
James Steiner about 2 years ago change default values Download this version
James Steiner about 2 years ago controls fix Download this version
James Steiner about 2 years ago newest version Download this version
James Steiner about 2 years ago updated to 6.2.2, w/ more features Download this version
James Steiner about 12 years ago Initial upload Download this version

Attached files

File Type Description Last updated
6906.png png model thumbnail about 2 years ago, by James Steiner Download

This model does not have any ancestors.

This model does not have any descendants.