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.

Constant Summary

STRATEGIES = 
[:edge_labeling, :node_labeling]

Instance Attribute Summary (collapse)

Class Method Summary (collapse)

Instance Method Summary (collapse)

Instance Attribute Details

- (Object) _options

Returns the value of attribute _options



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

def _options
  @_options
end

Class Method Details

+ (Object) included(base) 



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

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

Instance Method Details

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

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:

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

    Parameters:

    • i (node)
    • j (node)
    • l (Label)
  • - (RawTree) add_branch!(b)

    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



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

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

- (RawTree) add_node!(n) - (RawTree) add_node!(b)

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:

  • - (RawTree) add_node!(n)

    Parameters:

    • n (node)
  • - (RawTree) add_node!(b)

    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



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

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

- (Array(Branch)) branches

The branches of the tree in a 1D array.

Returns:



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

def branches
  edges
end

- (Boolean) empty?

Is the tree empty?

Returns:

  • (Boolean) 


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

def empty?
  nodes.empty?
end

- (Array(node)) nodes

The nodes of the tree in a 1D array.

Returns:



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

def nodes
  vertices
end

- (RawTree) remove_branch!(i, j) - (RawTree) remove_branch!(b)

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:

  • - (RawTree) remove_branch!(i, j)

    Parameters:

    • i (node)
    • j (node)
  • - (RawTree) remove_branch!(b)

    Parameters:

Returns:

  • (RawTree) —

    self



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

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

- (RawTree) remove_node!(u, force = false)

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



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

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

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

Is the node a terminal node?

Returns:

  • (Boolean)

Raises:



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

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

- (Array(node)) terminal_nodes 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).



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

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

- (Boolean) valid?

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

  • acyclic
  • connected

Returns:

  • (Boolean) 


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

def valid?
  acyclic? and connected?
end