Module: Jumoku::ArborescenceBuilder

Includes:
Extended, RawDirectedTreeBuilder
Included in:
Arborescence
Defined in:
lib/jumoku/builders/arborescence.rb

Overview

This builder extends RawDirectedTreeBuilder implementation.

It provides a directed tree which acts as a hierarchical structure, known as an arborescence.

By default, it is ensured that new arcs remain in the same general flow direction, based on the first arc added (binding the node known as root to its first children, known as leaf). This constraint may be relaxed by passing the ‘:free_flow` option to true when initializing:

Arborescence.new(:free_flow => true)

This way, the tree remains directed (nodes are bound using arcs, not undirected edges), but a node may be either a pure source (only outing arcs), a pure target (only arcs pointing at it), or a mix.

Instance Attribute Summary

Attributes included from Shared

#_options

Instance Method Summary collapse

Methods included from Extended

#add_branch, #add_branches, #add_branches!, #add_consecutive_nodes, #add_consecutive_nodes!, #add_node, #add_nodes, #add_nodes!, #branch?, #branches?, #branches_among?, #node?, #nodes?, #nodes_among?, #num_branches, #num_nodes, #remove_branch, #remove_branches, #remove_branches!, #remove_node, #remove_nodes, #remove_nodes!

Methods included from RawDirectedTreeBuilder

#initialize, #valid?

Methods included from Shared

#add_node!, #branches, #empty?, included, #nodes, #remove_branch!, #remove_node!, #terminal?, #terminal_nodes, #valid?

Instance Method Details

#add_branch!(u, v = nil, l = nil) ⇒ Object 



22
23
24
25
26
27
28
 
# File 'lib/jumoku/builders/arborescence.rb', line 22

def add_branch!(u, v = nil, l = nil)
  return super(u,v,l) if @_options[:free_flow]
  return add_branch!(u.source, u.target, l) if u.is_a? _branch_type
  return super(u,v,l) if nodes.size < 2

  nodes.include?(u) ? super(u,v,l) : super(v,u,l)
end

#children(parent) ⇒ Array<Node> Also known as: children_of

Return the list of a node’s children.

Parameters:

  • node (Node)

Returns:



60
61
62
 
# File 'lib/jumoku/builders/arborescence.rb', line 60

def children(parent)
  adjacent(parent)
end

#leaf?(node) ⇒ true, false

Check whether a node is a leaf.

Parameters:

  • (Node)

Returns:

  • (true, false) 


179
180
181
 
# File 'lib/jumoku/builders/arborescence.rb', line 179

def leaf?(node)
  terminal?(node) && out_degree(node) == 0
end

#leaves ⇒ Array<Node>

Return the list of leaf nodes.

Returns:



168
169
170
171
172
 
# File 'lib/jumoku/builders/arborescence.rb', line 168

def leaves
  terminal_nodes.delete_if do |node|
    out_degree(node) > 0
  end
end

#leaves?(*nodes) ⇒ true, false

Check whether all nodes from a list are leaves.

Parameters:

  • nodes (#to_a)

Returns:

  • (true, false) 


188
189
190
 
# File 'lib/jumoku/builders/arborescence.rb', line 188

def leaves?(*nodes)
  nodes.to_a.flatten.all? { |node| leaf?(node) }
end

#neighbours(node, options = {:siblings => false}) ⇒ Array<Node> Also known as: cousins

Return the list of a node’s neighbours, that is, children of node’s parent siblings (cousins).

Parameters:

  • node (Node)
  • options (Hash) (defaults to: {:siblings => false})

Options Hash (options):

  • :siblings (true, false) —

    whether to include the node’s siblings in the list

Returns:



129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
 
# File 'lib/jumoku/builders/arborescence.rb', line 129

def neighbours(node, options = {:siblings => false})
  # special case when the node is the root
  return [] if root?(node)

  # special case when the node is a root's child
  if root?(parent(node))
    nghb = children(parent(node))
    nghb.delete_if { |child| child == node } unless options[:siblings]
    return nghb.map { |child| [child] }
  end

  # general case
  nghb = siblings(parent(node)).map do |sibling|
    children(sibling)
  end
  nghb << siblings(node) if options[:siblings]
  nghb
end

#neighbours?(node1, node2, options = {:siblings => false}) ⇒ true, false Also known as: cousins?

Check whether two nodes are neighbours. To include the node’s siblings in the matching candidates, pass the ‘:siblings` option to true.

Parameters:

  • node1 (Node)
  • node2 (Node)
  • options (Hash) (defaults to: {:siblings => false})

Options Hash (options):

  • :siblings (true, false) —

    whether to include the node’s siblings in the list

Returns:

  • (true, false) 


159
160
161
 
# File 'lib/jumoku/builders/arborescence.rb', line 159

def neighbours?(node1, node2, options = {:siblings => false})
  neighbours(node1, options).any? { |set| set.include? node2 }
end

#parent(node) ⇒ Node? Also known as: parent_of

Return the parent node of another.

Parameters:

  • node (Node)

Returns:

  • (Node, nil) —

    nil if the node is root

Raises:

  • if the node has more than one parent (should never occur!)



71
72
73
74
75
 
# File 'lib/jumoku/builders/arborescence.rb', line 71

def parent(node)
  parent = adjacent(node, :direction => :in)
  raise JumokuError, "Inconsistent directed tree (more than one parent for the node!)" if parent.size > 1
  parent.empty? ? nil : parent.first
end

#parent?(node) ⇒ true, false #parent?(node, maybe_child) ⇒ true, false

Check whether a node is a parent. If another node is provided as second parameter, check whether the former is the parent of the latter.

Overloads:

  • #parent?(node) ⇒ true, false

    Parameters:

    • node (Node)

    Returns:

    • (true, false)
  • #parent?(node, maybe_child) ⇒ true, false

    Parameters:

    • node (Node)
    • maybe_child (Node)

    Returns:

    • (true, false) 


89
90
91
92
93
94
95
 
# File 'lib/jumoku/builders/arborescence.rb', line 89

def parent?(node, maybe_child = nil)
  if maybe_child.nil?
    !children(node).empty?
  else
    children(node).include? maybe_child
  end
end

#root ⇒ Node

Find the root node.

Returns:

  • (Node) 


34
35
36
37
 
# File 'lib/jumoku/builders/arborescence.rb', line 34

def root
  return nodes.first if nodes.size == 1
  nodes.find { |node| root?(node) }
end

#root?(node) ⇒ true, false

Check whether a node is the root.

Returns:

  • (true, false) 


51
52
53
 
# File 'lib/jumoku/builders/arborescence.rb', line 51

def root?(node)
  in_degree(node) == 0 && out_degree(node) > 0
end

#root_edges ⇒ Array<Plexus::Arc>

Return the list of arcs branched out from the root node.

Returns:



43
44
45
 
# File 'lib/jumoku/builders/arborescence.rb', line 43

def root_edges
  adjacent(root, :type => :edges)
end

#siblings(node) ⇒ Array<Node> Also known as: siblings_of

Return the siblings for a node. Siblings are other node’s parent children.

Parameters:

  • node (Node)

Returns:

  • (Array<Node>) —

    empty list if the node is root



102
103
104
105
106
107
 
# File 'lib/jumoku/builders/arborescence.rb', line 102

def siblings(node)
  return [] if root?(node)
  siblings = children(parent(node))
  siblings.delete(node)
  siblings
end

#siblings?(node1, node2) ⇒ true, false

Check whether two nodes are siblings.

Parameters:

  • node1 (Node)
  • node2 (Node)

Returns:

  • (true, false) 


116
117
118
 
# File 'lib/jumoku/builders/arborescence.rb', line 116

def siblings?(node1, node2)
  siblings(node1).include?(node2)
end