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.

Constant Summary

Constants included from Shared

Shared::STRATEGIES

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 



11
12
13
14
15
16
17
 
# File 'lib/jumoku/builders/arborescence.rb', line 11

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:



49
50
51
 
# File 'lib/jumoku/builders/arborescence.rb', line 49

def children(parent)
  adjacent(parent)
end

#leaf?(node) ⇒ true, false

Check whether a node is a leaf.

Parameters:

  • (Node)

Returns:

  • (true, false) 


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

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

#leaves ⇒ Array<Node>

Return the list of leaf nodes.

Returns:



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

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) 


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

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:



119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
 
# File 'lib/jumoku/builders/arborescence.rb', line 119

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) 


149
150
151
 
# File 'lib/jumoku/builders/arborescence.rb', line 149

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!)



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

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 node is the parent of the latter node.

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) 


79
80
81
82
83
84
85
 
# File 'lib/jumoku/builders/arborescence.rb', line 79

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) 


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

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) 


40
41
42
 
# File 'lib/jumoku/builders/arborescence.rb', line 40

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:



32
33
34
 
# File 'lib/jumoku/builders/arborescence.rb', line 32

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



92
93
94
95
96
97
 
# File 'lib/jumoku/builders/arborescence.rb', line 92

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) 


106
107
108
 
# File 'lib/jumoku/builders/arborescence.rb', line 106

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