class Tree
Public Class Methods
# File lib/generic/tree.rb, line 2 def initialize @values = [] @edges = [] @parents = [] end
Public Instance Methods
# File lib/generic/tree.rb, line 59 def add_edge(from, to) register_edge(from, to) register_parent(to, from) end
# File lib/generic/tree.rb, line 48 def add_node(id, value) @values[id] = value end
# File lib/generic/tree.rb, line 68 def branch?(id) ! leaf?(id) end
# File lib/generic/tree.rb, line 44 def children(id) @edges[id] end
# File lib/generic/tree.rb, line 26 def depth(id) d = 0 i = id until( i==root_id ) i = parent(i) d += 1 end d end
# File lib/generic/tree.rb, line 64 def leaf?(id) @edges[id] == nil end
# File lib/generic/tree.rb, line 8 def list_depth_traverse(under) list = [] do_list_depth_traverse(under, list) return list end
NOTE: About Design. In current design, a link node that can not find the tag node it points to is treated as text node.
# File lib/rdtree.rb, line 10 def not_found_link2text! list_link_nodes.each do |id| if can_not_find_tag(id) modify_link2text(id) end end end
# File lib/generic/tree.rb, line 22 def parent(id) @parents[id] end
NOTE: Crazy Design Akira Hayakawa, Aug 23, 2011 This method must be called wherever it needs the rationalized state. For exmaple, a Link
node that can not find the tag in the tree should be altered to Text
node. But, this is innately a bad design. Because of my incapable of not coming up with a good idea to solve this issue elegantly. The version 2.0.2 scattered this method to to_csv
and to_dot. But I do not know if this is sufficient. To solve this issue theoritically, embed this method into every single mutate methods of the instance mattered.
If you embed this method, please leave comment “# CRAZY” there so that you can remove after I find a better solution.
A solution is to simplify the design that lets every paths through RDTree structure. Then call rationalize only one time before it is needed, case of conversion for example.
# File lib/rdtree.rb, line 33 def rationalize! not_found_link2text! end
# File lib/generic/tree.rb, line 36 def root_id 0 end
# File lib/generic/tree.rb, line 18 def size @values.size end
# File lib/rdtree.rb, line 37 def to_csv rationalize! # CRAZY m = tree2matrix(self) range = [ 0...m.m_size, 1...m.n_size] c = matrix2csv(m, range) do |n| s = nil if n == nil s = "" else s = n.to_csv end s end c end
# File lib/rdtree2dot.rb, line 5 def to_dot rationalize! # CRAZY elems = [] for i in 0...size unless link_node?(i) elems << dot_node_desc(i) end end linkmap = mk_id2id for i in 0...size if link_node?(i) to = linkmap[i] from = parent(i) elems << dot_edge_desc(from, to) next end if leaf?(i) next end children(i).each do |child| elems << dot_edge_desc(i, child) unless link_node?(child) end end # NOTE: The ratio of the output figure is 1 at default. # I/F to change the ratio is the future work. """ digraph graphname { graph [ratio = 1] #{elems.join("\n ")} } """ end
# File lib/rdtree2rd.rb, line 8 def to_rd nodes = list_depth_traverse(root_id) # NOTE: Eliminate the DummyRoot from rd file. nodes.delete(root_id) nodes.map do |node| value(node).to_rd end.join("\n") end
# File lib/generic/tree.rb, line 52 def update_value(id, value) # In current version, # update_value is just a wrapper of add_node. # but in future version, this may need modification. add_node(id, value) end
# File lib/generic/tree.rb, line 40 def value(id) @values[id] end
# File lib/generic/tree.rb, line 14 def values @values end
Private Instance Methods
# File lib/rdtree.rb, line 91 def can_not_find_tag(id) tag = mk_id2tag[id] ! mk_tag2id.include? tag end
# File lib/generic/tree.rb, line 74 def do_list_depth_traverse(under, list) list << under if leaf?(under) return end children(under).each do |id| do_list_depth_traverse(id, list) end end
# File lib/rdtree2dot.rb, line 44 def dot_edge_desc(from, to) "v#{from} -> v#{to};" end
# File lib/rdtree2dot.rb, line 40 def dot_node_desc(id) "v#{id} [label=\"#{value(id).to_desc}\"];" end
NOTE: Maybe Under-Engineering. id of node, tmp field are not copied but this time, I decided not because I considered unnessessary.
# File lib/rdtree.rb, line 67 def link2text(linknode) depth = linknode.depth text = linknode.dest Text.new(depth, text) end
# File lib/rdtree.rb, line 96 def link_node?(id) n = value(id) n.class == Link end
NOTE: Performance Issue The following methods call mk_xxx method everytime they need the information. Current version adopts lazy evaluation technique to always keep the state of RDTree new.
Now, my consideration is this is OK. Because the mk_xxx functions have complexity of O(N) where N is the number of nodes in the tree. Therefore, for small input, the performance will not go too bad.
If, performance is found bad, first consider lazy instantiation technique.
# File lib/rdtree.rb, line 87 def list_link_nodes mk_id2tag.keys end
# File lib/rdtree.rb, line 107 def mk_id2id id2tag = mk_id2tag tag2id = mk_tag2id id2id = {} id2tag.keys.each do |id| tag = id2tag[id] if tag2id.include?( tag) id2id[id] = tag2id[tag] end end id2id end
# File lib/rdtree.rb, line 131 def mk_id2tag id2tag = {} for i in 0...size n = value(i) if n.class == Link id2tag[i] = n.dest end end id2tag end
# File lib/rdtree.rb, line 101 def mk_linkmap # NOTE: is this use of warn method correct? warn "Warning: mk_linkmap should not be used. mk_id2id instead." mk_id2id end
# File lib/rdtree.rb, line 120 def mk_tag2id tag2id = {} for i in 0...size n = value(i) if n.class == Tag tag2id[n.tag] = i end end tag2id end
# File lib/rdtree.rb, line 58 def modify_link2text(id) linknode = value(id) textnode = link2text(linknode) update_value(id, textnode) end
# File lib/generic/tree.rb, line 84 def register_edge(from, to) if @edges[from] == nil @edges[from] = Array.new end @edges[from] << to end
# File lib/generic/tree.rb, line 91 def register_parent(from, to) @parents[from] = to end