kruskal


Information

Created with NetLogo version NetLogo 4.0beta1
Running with NetLogoLite.jar version 404.


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.

Procedures

NetLogo Version: NetLogo 4.0beta1

;; 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-gui 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?
]

to startup setup end

to setup
   ca
   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
   let t timer + .5
   while [ timer < t ] [ layout-spanning-tree ]
end

to go
   ;; do the main kruskal thing
   vis-network-show-all
   kruskal-spanning-tree
   vis-network-show-all
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 .5
     setxy random-xcor random-ycor
     ;; 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 9)
           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 blue 3 .5 ]
end

to-report checkered [ 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 * ((pxcor + pycor) 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 [ [ 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
   [ ask ?
     [ ;; 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-by [ [ weight ] of ?1 < [ weight ] of ?2 ] 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 run-slowly? [ vis-network-spanning-tree-only ]
 
   foreach sorted-edges
   [ ;; 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 ?
       [ ;; 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 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 run-slowly? and in-tree?
         [ vis-display-edge false ; color the edge
           let t timer + .05
           while [ timer < t ]
           [
             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-and-scale
   ;; 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 ##
   stop
   let cx  mean [ xcor ] of vertices
   let cy  mean [ ycor ] of vertices
   ask vertices [ setxy (xcor - cx) (ycor - cy) ]
   let mxx min (list max-pxcor max [ pxcor ] of vertices)
   let mxy min (list max-pycor max [ pycor ] of vertices)
   let mnx max (list min-pxcor min [ pxcor ] of vertices)
   let mny max (list min-pycor min [ pycor ] of vertices)
   let xscale world-width  / (abs round (mxx - mnx))
   let yscale world-height / (abs round (mxy - mny))
   ask vertices 
   [ setxy limitx (xcor * xscale)
           limity (ycor * yscale)
   ]
end

to vis-display-edge [ show-only-tree? ]
   ;; modifies the display parameters of a single edge
   ifelse in-tree?
   [ set color green - 2  set label weight set hidden? false
   ]
   [ set color red - 2    set label weight set hidden? show-only-tree? 
   ]
   ifelse weight=thickness?
   [ set thickness .1 + .1 * weight
   ] 
   [ ifelse in-tree? [ set thickness .5 ] [ 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 ] display
   ask vertices [ set color gray set size 0.5 set label "" ]
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 ] display
   ask vertices [ set color gray set size 0.5 set label "" ]

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-and-scale
   
   ;; rotate 90 degrees
   ask vertices
   [ setxy ycor (- xcor) ]
   ;; 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
   ;; auto-layout the spanning tree
   layout-spring vertices (edges with [ in-tree? = true ]) layout-pull layout-length layout-push
end 

to layout-spanning-tree-button
   layout-spanning-tree
   monitor-mouse
   set gui-message ""
end

to-report real-time-monitor
   ;; run by a monitor, this procedure monitors some gui events
   ;; and handles them, even when no buttons are pressed
   monitor-push-pull
   ifelse gui-message = ""
   [ set gui-message "x" ]
   [ monitor-mouse
     layout-spanning-tree
   ]
   report ""
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 ] ]
     [ set dragged nobody ]
   ]
   [ if mouse-down?
     [ ask patch mouse-xcor mouse-ycor 
       [ set dragged one-of vertices-here ]
     ]
   ]
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 synch?
    [ifelse layout-push != oldpush
    [ set oldpush layout-push
      set layout-pull layout-push
      set oldpull layout-pull
    ][
    if 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 ]
   

                    


Download Link

View or download the complete model file (to download: right-click, save-link-as):
-- Download kruskal --