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)`.

Overloads:

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

    Parameters:

    • i (node)
    • j (node)
    • l (Label) (defaults to: nil)
  • #add_branch!(b) ⇒ RawTree

    Parameters:

    • b (Branch) —

      Branch[node i, node j, label l = nil]; if i (j) already exists, then j (i) must not exist

Returns:

  • (RawTree) —

    self



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.

Overloads:

  • #add_node!(n) ⇒ RawTree

    Parameters:

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

    Parameters:

    • b (Branch) —

      Branch[node i, node j, label l = nil]; if i (j) already exists, then j (i) must not exist

Returns:

  • (RawTree) —

    self



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.

Returns:



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

def branches
  edges
end

#empty? ⇒ Boolean

Is the tree empty?

Returns:

  • (Boolean) 


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.

Returns:



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.

Overloads:

  • #remove_branch!(i, j) ⇒ RawTree

    Parameters:

    • i (node)
    • j (node)
  • #remove_branch!(b) ⇒ RawTree

    Parameters:

Returns:

  • (RawTree) —

    self



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.

Parameters:

  • u (node)

Returns:

  • (RawTree) —

    self



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?

Returns:

  • (Boolean)

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.

Returns:

  • (Array(node)) —

    only terminal nodes (empty array if no terminal nodes, but should never happen in a tree).



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

Returns:

  • (Boolean) 


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

def valid?
  acyclic? and connected?
end