Class: Rubyvis::Layout::Tree

Inherits:
Hierarchy show all
Defined in:
lib/rubyvis/layout/tree.rb

Overview

Implements a node-link tree diagram using the Reingold-Tilford “tidy” tree layout algorithm. The specific algorithm used by this layout is based on <a href=“citeseer.ist.psu.edu/buchheim02improving.html”>“Improving Walker’s Algorithm to Run in Linear Time”</A> by C. Buchheim, M. J&uuml;nger &amp; S. Leipert, Graph Drawing 2002. This layout supports both cartesian and radial orientations orientations for node-link diagrams.

<p>The tree layout supports a “group” property, which if true causes siblings to be positioned closer together than unrelated nodes at the same depth. The layout can be configured using the depth and breadth properties, which control the increments in pixel space between nodes in both dimensions, similar to the indent layout.

<p>For more details on how to use this layout, see Rubyvis::Layout::Hierarchy

Instance Attribute Summary

Attributes inherited from Network

#_id, #link, #node, #node_label

Attributes inherited from Panel

#_canvas, #children, #root

Attributes inherited from Mark

#_properties, #binds, #child_index, #parent, #proto, #root, #scale, #scene, #target

Class Method Summary collapse

Instance Method Summary collapse

Methods inherited from Hierarchy

#hierarchy_build_implied, #links

Methods inherited from Network

#_link, #_node, #_node_label, #build_properties, #network_build_implied, #nodes, #reset

Methods inherited from Rubyvis::Layout

Arc, Cluster, Grid, Hierarchy, Horizon, Indent, Matrix, Network, Pack, Partition, Stack, Tree, Treemap, attr_accessor_dsl, #build_properties, #layout_build_implied, #layout_build_properties

Methods inherited from Panel

#add, #anchor, #bind, #build_instance, #children_inspect, #panel_build_implied, #to_svg, #type

Methods inherited from Bar

#type, #width

Methods inherited from Mark

#add, #anchor, #area, attr_accessor_dsl, #bar, #bind, #build, #build_instance, #build_properties, #context, #context_apply, #context_clear, #cousin, #delete_index, #dot, #event, #execute, #first, #image, index, #index, index=, #index=, #index_defined?, #instance, #instances, #label, #last, #layout_arc, #layout_cluster, #layout_grid, #layout_horizon, #layout_indent, #layout_matrix, #layout_pack, #layout_partition, #layout_partition_fill, #layout_stack, #layout_tree, #layout_treemap, #line, #margin, #mark_anchor, #mark_bind, #mark_build_implied, #mark_build_instance, #mark_build_properties, #mark_extend, mark_method, #panel, #properties, properties, property_method, #property_value, #render, #rule, scene, scene=, #sibling, stack, stack=, #type, #wedge

Constructor Details

#initialize ⇒ Tree

Returns a new instance of Tree.



24
25
26
 
# File 'lib/rubyvis/layout/tree.rb', line 24

def initialize
  super
end

Class Method Details

.defaults ⇒ Object

Default properties for tree layouts. The default orientation is “top”, the default group parameter is 1, and the default breadth and depth offsets are 15 and 60 respectively.



62
63
64
65
66
67
68
 
# File 'lib/rubyvis/layout/tree.rb', line 62

def self.defaults
  Rubyvis::Layout::Tree.new.mark_extend(Rubyvis::Layout::Hierarchy.defaults).
  group(1).
  breadth(15).
  depth(60).
  orient("top")
end

Instance Method Details

#ancestor(vim, v, a) ⇒ Object 



175
176
177
 
# File 'lib/rubyvis/layout/tree.rb', line 175

def ancestor(vim, v, a) 
  (vim.ancestor.parent_node == v.parent_node) ? vim.ancestor : a
end

#apportion(v, a) ⇒ Object 



101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
 
# File 'lib/rubyvis/layout/tree.rb', line 101

def apportion(v,a)
  w = v.previous_sibling
  if w
    vip = v
    vop = v
    vim = w
    vom = v.parent_node.first_child
    sip = vip.mod
    sop = vop.mod
    sim = vim.mod
    som = vom.mod
    nr = next_right(vim)
    nl = next_left(vip)
    while (nr and nl) do
      vim = nr
      vip = nl
      vom = next_left(vom)
      vop = next_right(vop)
      vop.ancestor = v
      shift = (vim.prelim + sim) - (vip.prelim + sip) + distance(vim.depth, false)
      if (shift > 0)
        move_subtree(ancestor(vim, v, a), v, shift)
        sip += shift
        sop += shift
      end
      sim += vim.mod
      sip += vip.mod
      som += vom.mod
      sop += vop.mod
      nr = next_right(vim)
      nl = next_left(vip)
    end
    
    if (nr and !next_right(vop))
      vop.thread = nr
      vop.mod += sim - sop
    end
    if (nl and !next_left(vom))
      vom.thread = nl
      vom.mod += sip - som
      a = v
    end
  end
  a
end

#build_implied(s) ⇒ Object 



222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
 
# File 'lib/rubyvis/layout/tree.rb', line 222

def build_implied(s)
  return nil if hierarchy_build_implied(s)        
  @_nodes = s.nodes
  @_orient = s.orient
  @_depth = s.depth
  @_breadth = s.breadth
  @_group = s.group
  @_w = s.width
  @_h = s.height
  root=@_nodes[0]
  root.visit_after {|v,i|
    v.ancestor = v
    v.prelim = 0
    v.mod = 0
    v.change = 0
    v.shift = 0
    v.number = v.previous_sibling ? (v.previous_sibling.number + 1) : 0
    v.depth = i
  }
  #/* Compute the layout using Buchheim et al.'s algorithm. */
  first_walk(root)
  second_walk(root, -root.prelim, 0)
  
  root.visit_after {|v,i|
    v.breadth *= breadth
    v.depth *= depth
    v.mid_angle = mid_angle(v)
    v.x = x(v)
    v.y = y(v)
    v.mid_angle += Math::PI if (v.first_child)
    v.breadth=nil
    v.depth=nil
    v.ancestor=nil
    v.prelim=nil
    v.mod=nil
    v.change=nil
    v.shift=nil
    v.number=nil
    v.thread=nil
  }
  
  
end

#distance(depth, siblings) ⇒ Object 



179
180
181
 
# File 'lib/rubyvis/layout/tree.rb', line 179

def distance(depth, siblings) 
  (siblings ? 1 : (@_group + 1)).to_f / ((@_orient == "radial") ? depth : 1)
end

#execute_shifts(v) ⇒ Object 



163
164
165
166
167
168
169
170
171
172
173
174
 
# File 'lib/rubyvis/layout/tree.rb', line 163

def execute_shifts(v) 
  shift = 0
  change = 0
  c=v.last_child
  while c        
    c.prelim += shift
    c.mod += shift
    change += c.change
    shift += c.shift + change
    c = c.previous_sibling          
  end
end

#first_walk(v) ⇒ Object 



70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
 
# File 'lib/rubyvis/layout/tree.rb', line 70

def first_walk(v)
  l,r,a=nil,nil,nil
  if (!v.first_child)
    l= v.previous_sibling
    v.prelim = l.prelim + distance(v.depth, true)  if l
  else    
    l = v.first_child
    r = v.last_child
    a = l # default ancestor
    v.each_child {|c| 
      first_walk(c)
      a = apportion(c, a)
    }
    execute_shifts(v)
    midpoint = 0.5 * (l.prelim + r.prelim)
    l = v.previous_sibling
    if l
      v.prelim = l.prelim + distance(v.depth, true)
      v.mod = v.prelim - midpoint
    else
      v.prelim = midpoint
    end
  end
end

#group ⇒ Object

:group: The sibling grouping, i.e., whether differentiating space is placed between sibling groups. The default is 1 (or true), causing sibling leaves to be separated by one breadth offset. Setting this to false (or 0) causes non-siblings to be adjacent.



57
 
# File 'lib/rubyvis/layout/tree.rb', line 57

attr_accessor_dsl :group, :breadth, :depth, :orient

#mid_angle(n) ⇒ Object 



184
185
186
 
# File 'lib/rubyvis/layout/tree.rb', line 184

def mid_angle(n)
  (@_orient == "radial") ? n.breadth.to_f / depth : 0;
end

#move_subtree(wm, wp, shift) ⇒ Object 



154
155
156
157
158
159
160
161
 
# File 'lib/rubyvis/layout/tree.rb', line 154

def move_subtree(wm, wp, shift) 
  subtrees = wp.number - wm.number
  wp.change -= shift / subtrees.to_f
  wp.shift += shift
  wm.change += shift / subtrees.to_f
  wp.prelim += shift
  wp.mod += shift
end

#next_left(v) ⇒ Object 



147
148
149
 
# File 'lib/rubyvis/layout/tree.rb', line 147

def next_left(v)
  v.first_child ? v.first_child : v.thread
end

#next_right(v) ⇒ Object 



150
151
152
 
# File 'lib/rubyvis/layout/tree.rb', line 150

def next_right(v)
  v.last_child ? v.last_child : v.thread
end

#second_walk(v, m, depth) ⇒ Object 



94
95
96
97
98
99
100
 
# File 'lib/rubyvis/layout/tree.rb', line 94

def second_walk(v,m,depth)
  v.breadth = v.prelim + m
  m += v.mod
  v.each_child {|c|
    second_walk(c, m, depth)
  }
end

#x(n) ⇒ Object

/** @private */



189
190
191
192
193
194
195
196
197
198
199
200
201
202
 
# File 'lib/rubyvis/layout/tree.rb', line 189

def x(n)
  case @_orient
    when "left"
      n.depth;
    when "right"
      @_w - n.depth;
    when "top"
      n.breadth + @_w / 2.0
    when "bottom"
      n.breadth + @_w / 2.0
    when "radial"
      @_w / 2.0 + n.depth * Math.cos(mid_angle(n))
  end
end

#y(n) ⇒ Object

/** @private */



205
206
207
208
209
210
211
212
213
214
215
216
217
218
 
# File 'lib/rubyvis/layout/tree.rb', line 205

def y(n)
  case @_orient
    when "left"
      n.breadth + @_h / 2.0
    when "right"
      n.breadth + @_h / 2.0
    when "top"
      n.depth;
    when "bottom"
      @_h - n.depth
    when "radial"
      @_h / 2.0 + n.depth * Math.sin(mid_angle(n))
  end
end