Module: Jumoku::Shared

Included in:
RawDirectedTreeBuilder, RawUndirectedTreeBuilder
Defined in:
lib/jumoku/builders/shared.rb

Overview

This module provides the basic routines needed to implement the specialized builders: RawUndirectedTreeBuilder and RawDirectedTreeBuilder.

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Instance Attribute Details

#_options ⇒ Object

Returns the value of attribute _options.



14
15
16
 
# File 'lib/jumoku/builders/shared.rb', line 14

def _options
  @_options
end

Class Method Details

.included(base) ⇒ Object 



6
7
8
9
10
11
12
 
# File 'lib/jumoku/builders/shared.rb', line 6

def self.included(base)
  base.class_eval do
    # Late aliasing as it references methods provided by Plexus modules.
    alias has_node? has_vertex?
    include Jumoku::Strategies
  end
end

Instance Method Details

#add_branch!(i, j, l = nil) ⇒ RawTree #add_branch!(b) ⇒ RawTree

Adds a new branch to the tree.

As a tree is an undirected structure, the order of the parameters is of no importance, that is: ‘add_branch!(u,v) == add_branch!(v,u)`.



53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
 
# File 'lib/jumoku/builders/shared.rb', line 53

def add_branch! u, v = nil, l = nil
  if has_node? u and has_node? v
    unless has_branch? u, v
      # Ensure the acyclic constraint.
      raise ForbiddenCycle, "Can't form a cycle within a tree."
    end
  end

  # TODO: DRY this up.
  if u.is_a? _branch_type
    v = u.target
    u = u.source
  end

  if has_node? u or has_node? v or nodes.empty?
    add_edge! u, v, l
  else
    # Ensure the connected constraint.
    raise RawTreeError, "Can't add a dead branch to a tree."
  end
end

#add_node!(n) ⇒ RawTree #add_node!(b) ⇒ RawTree

Adds the node to the tree.

For convenience, you may pass a branch as the parameter, which one node already exists in the tree and the other is to be added.



27
28
29
30
31
32
33
34
35
36
37
38
 
# File 'lib/jumoku/builders/shared.rb', line 27

def add_node! u, v = nil, l = nil
  if nodes.empty?
    add_vertex! u, l
  elsif u.is_a? _branch_type
    add_branch! u, nil, l
  elsif not v.nil?
    add_branch! u, v, l
  else
    # Ensure the connected constraint.
    raise RawTreeError, "In order to add a node to the tree, you must specify another node to attach to."
  end
end

#branches ⇒ Array(Branch)

The branches of the tree in a 1D array.



163
164
165
 
# File 'lib/jumoku/builders/shared.rb', line 163

def branches
  edges
end

#empty? ⇒ Boolean

Is the tree empty?



194
195
196
 
# File 'lib/jumoku/builders/shared.rb', line 194

def empty?
  nodes.empty?
end

#nodes ⇒ Array(node)

The nodes of the tree in a 1D array.



144
145
146
 
# File 'lib/jumoku/builders/shared.rb', line 144

def nodes
  vertices
end

#remove_branch!(i, j) ⇒ RawTree #remove_branch!(b) ⇒ RawTree

Removes a branch from the tree.

You cannot remove non terminal branches as it would break the connectivity constraint of the tree.

I may add an option which would allow to force removal of internal nodes and return two new trees from this destructive operation.



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
 
# File 'lib/jumoku/builders/shared.rb', line 110

def remove_branch! u, v = nil
  if u.is_a? _branch_type
    v = u.target
    u = u.source
  end

  if has_node? u and has_node? v
    if terminal? u and terminal? v
      remove_edge! u, v
      # empty the tree if u and v are the last two nodes, for they're
      # not connected anymore
      if [u, v].all? { |node| nodes.include? node } and nodes.size == 2
        remove_node! u, true
        remove_node! v, true
      end
    elsif terminal? u and not terminal? v
      remove_node! u
    elsif terminal? v and not terminal? u
      remove_node! v
    else
      raise RawTreeError, "Can't remove a non terminal branch in a tree."
    end
  else
    raise RawTreeError, "Can't remove a branch which does not exist."
  end
end

#remove_node!(u, force = false) ⇒ RawTree

Removes a node from the tree.

You cannot remove non terminal nodes as it would break the connectivity constraint of the tree.

I may add an option which would allow to force removal of internal nodes and return two new trees from this destructive operation.



86
87
88
89
90
91
92
93
 
# File 'lib/jumoku/builders/shared.rb', line 86

def remove_node!(u, force = false)
  if force || terminal?(u)
    remove_vertex! u
  else
    # Ensure the connected constraint.
    raise UndefinedNode, "Can't remove a non terminal node in a tree"
  end
end

#terminal?(u) ⇒ Boolean Also known as: has_terminal_node?, leaf?

Is the node a terminal node?

Raises:



183
184
185
186
187
 
# File 'lib/jumoku/builders/shared.rb', line 183

def terminal? u
  raise UndefinedNode, "Not a node of this tree." unless has_node? u
  return true if (1..2).include? nodes.size
  degree(u) == 1
end

#terminal_nodes ⇒ Array(node) Also known as: boundaries

The terminal nodes of the tree in a 1D array.



152
153
154
155
156
157
 
# File 'lib/jumoku/builders/shared.rb', line 152

def terminal_nodes
  nodes.inject([]) do |terminals, node|
    terminals << node if terminal?(node)
    terminals
  end
end

#valid? ⇒ Boolean

Checks whether the tree is a valid tree (directed or undirected), that is if the following conditions are fulfilled:

  • acyclic

  • connected



176
177
178
 
# File 'lib/jumoku/builders/shared.rb', line 176

def valid?
  acyclic? and connected?
end