---layout.nlogo

NETLOGO

breeds [nodes edges]
edges-own [a b]
nodes-own [links]
globals [x-max y-max diam friction tot-edges filename tick stoptick init-power-edges]

to setup-globals  ; separate procedure for setting globals
  set diam 4
  set x-max screen-edge-x - (diam / 2) + 1; 0.5
  set y-max screen-edge-y - (diam / 2) + 1; 0.5
  set filename "" ; change to collect images (or just use command center after setup)
  set tick 0
  set stoptick 0  ; set to some number to stop, generally for image collections
  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)
end

to setup  ; Setup the model for a run, build a graph.
  ca
  setup-globals
  setup-patches
  setup-turtles
  ifelse powerlaw? [setup-power-graph] [setup-random-graph]
  graph-edges
end

to setup-patches
  ask patches [set pcolor white]
  ask patches with [pxcor = 0 or pycor = 0][set pcolor gray]
end

to setup-turtles
  cct-nodes number-of-nodes [
    set color yellow
    set label-color black
    set size diam
    set links []
    set label who
    setxy random-float (x-max) * (2 * (random 2) - 1)
          random-float (y-max) * (2 * (random 2) - 1)
  ]
end

to setup-power-graph  ; Build a powerlaw graph
  locals [n prob p elist t1 t2]
  set prob (list turtle 0)
  repeat min list init-power-edges (floor number-of-nodes / 3) [
    ask last prob [connect-edge turtle (length prob)]
    set prob lput turtle (length prob) prob
  ]

  set elist n-values (number-of-nodes - length prob) [1]
  while [reduce [?1 + ?2] elist < (tot-edges - count edges)] [
      set n random length elist
      set elist replace-item n elist (1 + item n elist)
  ]
  while [length elist > 0] [
    set t1 turtle (number-of-nodes - length elist)
    set p prob
    repeat min list who-of t1 first elist [
      set t2 random-one-of p
      ask t1 [connect-edge t2]
      set p remove t2 p
      set prob lput t1 prob
      set prob lput t2 prob
    ]
    set elist but-first elist
  ]
end

to setup-random-graph  ; Build a random graph
  locals [t t1 g]
  set g (list turtle 1)
  while [length g < number-of-nodes] [
    set t1 random-one-of nodes with [not member? self g]
    set t item random length g g
    ask t1 [connect-edge t]
    set g subgraph turtle 1
  ]
  while [count edges < tot-edges] [
    set t  random-one-of nodes
    set t1 random-one-of nodes with [self != t and not member? t links]
    if t1 != nobody [ask t1 [connect-edge t]]
  ]
end

to-report subgraph [n]  ; report the complete connected subgraph containing n1
  locals[stack graph]
  set graph (list n)
  set stack (list n)
  while [length stack > 0] [
    foreach links-of first stack [
      if not member? ? graph [
        set graph lput ? graph
        set stack lput ? stack
      ]
    ]
    set stack but-first stack
  ]
  report graph
end

to go  ; The run procedure which makes the model take one step
  locals[t]
  if filename = 0 [setup] ; an attempt to work even tho user forgets setup
  if stoptick = -1 [stop]
  ;no-display
  set tick tick + 1
  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]
      display
    ]
  ]
  check-movie
  if stoptick = tick [stop]
end

to step  ; Adjust the edges and nodes for one step of the model
  locals[delta]
without-interruption [
  ask edges [
    set delta (spring-force * (size - spring-length)) / 2.0
    ask a [set heading towards-nowrap b-of myself jump-nowrap delta]
    ask b [set heading towards-nowrap a-of myself jump-nowrap delta]
  ]
  ask nodes [
    ask nodes with [self != myself] [
      set delta distance-nowrap myself
      set delta mutual-repulsion / (delta * delta)
      set heading towards-nowrap myself
      jump-nowrap (- delta)
    ]
  ]
  ask edges [adjust-edge]
]
end

to graph-edges  ; Make a simple edge histogram
  set-plot-x-range 1  1 + max values-from nodes [length links]
  histogram-from nodes [length links]
end

to check-movie  ; if filename is non-empty, make another snapshot
  if length filename > 0 [
    export-graphics filename + substring "0000" (int log tick 10) 3 + tick + ".png"
  ]
end

;;;; Edge & Node utilities
to connect-edge [other-node] ; node proc: attach an edge between self and other
  hatch 1 [
    set breed edges
    set a myself
    set b other-node
    ask a [set links lput b-of myself links]
    ask b [set links lput a-of myself links]
    set color red
    adjust-edge
  ]
end

to adjust-edge ; edge proc: reattach to a & b nodes
  setxy xcor-of a ycor-of a
  set size distance-nowrap b
  set heading towards-nowrap b
  set label precision size 0 ; who + ": " + precision size 2
  jump size / 2
end

;;;; Utilities
to-report sign [num]
  ifelse num < 0 [report -1][report 1]
end
to-report closest-xy [x y agent-set]  ; Return closest agent to x, y
  report min-one-of agent-set [distancexy-nowrap x y]
end
to jump-nowrap [dist] ; turtle proc: jump but don't wrap, bounce w/ friction instead
  locals [x y]
  set x xcor + dist * dx
  set y ycor + dist * dy
  if (abs x) > x-max [set x sign x * (x-max - (1 - friction) * ((abs x) - x-max))]
  if (abs y) > y-max [set y sign y * (y-max - (1 - friction) * ((abs y) - y-max))]
  setxy x y
end
@#$#@#$#@
GRAPHICS-WINDOW
204
10
565
392
19
19
9.0
1
10
1
1
1

CC-WINDOW
4
417
635
536
Command Center

BUTTON
7
64
62
97
NIL
setup
NIL
1
T
OBSERVER
T

BUTTON
68
65
123
98
NIL
go
T
1
T
OBSERVER
NIL

BUTTON
129
65
184
98
step
go
NIL
1
T
OBSERVER
T

SLIDER
6
29
184
62
number-of-nodes
number-of-nodes
2
40
20
1
1
NIL

SLIDER
2
281
178
314
spring-force
spring-force
0
2
0.2
0.1
1
NIL

SLIDER
2
317
178
350
spring-length
spring-length
0
10
4.0
0.25
1
NIL

TEXTBOX
10
10
182
28
Setup Parameters and Controls.

TEXTBOX
6
248
161
279
Runtime Parameters.\nCan change while running!

SLIDER
2
353
178
386
mutual-repulsion
mutual-repulsion
0
10
4.0
0.25
1
NIL

TEXTBOX
8
104
196
140
Use mouse to grab and move nearest node while "go" is active.

SLIDER
7
136
182
169
edge-ratio
edge-ratio
0.8
2.5
1.2
0.1
1
NIL

SWITCH
7
173
181
206
powerlaw?
powerlaw?
0
1
-1000

MONITOR
573
13
630
62
NIL
tick
3
1

PLOT
573
67
733
187
edge-distribution
edges/node
count
1.0
1.0
0.0
1.0
true
false
PENS
"default" 1.0 1 -16777216 true

MONITOR
632
13
689
62
edges
count edges
3
1

@#$#@#$#@
WHAT IS IT?
-----------
This is a dynamic graph layout model using springs and repulsion forces to create a pleasing layout.

HOW IT WORKS
------------
The model uses two parameters (number-of-nodes and edge-ratio) to create the graph. For example, if the number of nodes is 10 and the edge ratio is 1.2, then the target graph would have 10 nodes and 12 edges.  

We currently provide two graph types: random and power-law.  The random graph simply connects random pairs of nodes together until the graph is fully connected and the number of edges is equal to or greater than the desired number.

Three parameters are used to adjust the layout while the model runs.  The spring-force is how strongly the spring pushes/pulls the nodes.  The spring-length is the 0-force length of the spring.  Greater lengths attract, lesser repel.  The total force is the spring-force times the amount the spring differs from its spring-length.  Finally, there is a general repulsion between all nodes, specified by the mutual-repulsion parameter.  It uses an inverse-square calculation rather than the spring's linear one.

HOW TO USE IT
-------------
Click on setup to initialize the graph.  Click on go to start the model.  While the model is running, you can change the three spring/repulsion parameters.  You also can grab a node with the mouse and move it around to help untangle the graph.

THINGS TO NOTICE
----------------
This is a fairly simple model.  The main thing to notice is that such a simple layout algorithm does a reasonable job of making the graph untangled.

The power-law graph uses the Barab噑i method (Google for his group's papers) which creates fairly "bush-y" power-law graphs.  His work helped us understand why web and internet graphs are often power-law by noting that these nets grow 1) progressively from small networks, and 2) link probabilistically to nodes according to "popularity" .. i.e. by number of links.

THINGS TO TRY
-------------
Try various settings for number of nodes and edge ratio. Grab nodes with the mouse while the model is running. Change the spring and repulsion settings while the model is running. Try changing the graph type (power-law switch) between random and power-law.  What are the differences that you see?

Try this: set the number of nodes to max and the edge ratio to 1.2 or so.  Click setup several times in succession, first with powerlaw? on, then off.  What differences does the edge histogram show?

Movies: (Use this with local models, not via the web) You can make a sequence of images for creating a movie of the model.  To do this, type 'set filename "movie"' in the command center immediately after clicking "setup".  When the model sees the filename has been set to a non-null value while running ("go"), it will take a picture every step of the model.  The filenames will look like movie0001.png movie0002.png ... etc.  You can stop the process by clicking on "go" when you have enough images.  Alternatively, the model can be stopped by "set stoptick 100" or some similar value, again using the command center.

UI Changes: The size of the graph world can be changed by editing the graphics window.  Try changing the patch size to a smaller number (5, say) and making the graph larger (35 x 35).  Just click the "more" button on the graphics window.  You can change the max number of nodes too by selecting its slider and editing it.  I've tried 100, with small edge ratio and it worked fine.

Programming changes: You could modify or replace the two graph construction algorithms, or add additional ones.  It would be interesting to see how a small world cluster would evolve under springs and repulsion.  The "go" procedure can be modified to use other layout algorithms.

Research: Modify the step procedure to periodically look for edge crossings and try to eliminate them.

EXTENDING THE MODEL
-------------------
Other kinds of graphs would be interesting to add.  See
	http://backspaces.net/PLaw/index.html
for a discussion on creating and exploring power-law and small worlds graphs and their searching properties.

NETLOGO FEATURES
----------------
This uses the generalizations NetLogo introduced which allow agents to be of any size and to use fractional coordinates.  Amazingly enough, the edges in the model are really a breed of turtle whose shape is a line, whose heading is the direction of the edge and whose midpoint is halfway between the nodes.  This is genius and works beautifully with the NetLogo concept of agents and patches.  I never would have thought this could have worked, especially with such outstanding ease of programming and good performance.

RELATED MODELS
--------------
The PLaw work above prompted my looking into NetLogo implementations like this.  And the models Seth Tisue showed me while the edge/node development was underway were essential.  The GraphVis graph drawing suite from ATT were used extensively in the power law study, for example:
	http://backspaces.net/PLaw/html/graphs-TdS+.html
Their site is: http://www.graphviz.org/

The pioneering work by Caida (http://www.caida.org/) and kc claffy (http://www.caida.org/home/seniorstaff/kclaffy.xml) to study the web's "shape" are central to any interesting computer graph investigations.

The Santa Fe Institute's graph theoretic work is fascinating, including models of the internet, virus propagation, small worlds.  This work has spawned a huge diversity of investigations world wide.  Contact me ([e-mail]) if you are interested in further pointers and potential projects.


CREDITS AND REFERENCES
----------------------
Seth Tisue showed me the basic ideas behind how to use fractional coordinates and arbitrary shapes for creating nodes and edges.  Thanks!  Arthur VonHoff created a similar layout demo for the Java SDK.  Steve Guerin suggested the repulsive force idea. See his Redfish.com site for great demos of this and other visualization and modeling ideas.
@#$#@#$#@
default
true
0
Polygon -7566196 true true 150 5 40 250 150 205 260 250

circle
false
0
Circle -7566196 true true 35 35 230

line
true
0
Line -7566196 true 150 0 150 301

@#$#@#$#@
NetLogo 2.0.1
@#$#@#$#@
@#$#@#$#@
@#$#@#$#@