Module: Jumoku::Extended

Included in:
ArborescenceBuilder, TreeBuilder
Defined in:
lib/jumoku/builders/extended.rb

Overview

This module provides methods extending the core implementation. Most of those methods are cloning the receiver tree and perform their operation on the duplicated object. Some other are helpers adding reflexivity to trees. There are also a few in-place methods.

Instance Method Summary collapse

Instance Method Details

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

Non destructive version RawTreeBuilder#add_branch! (works on a copy of the tree).

Overloads:

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

    Parameters:

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

    Parameters:

    • b (Branch) —

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

Returns:

  • (Tree) —

    a modified copy of ‘self`

See Also:

  • RawTreeBuilder#add_branch!


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

def add_branch(i, j = nil, l = nil)
  _clone.add_branch!(i, j, l)
end

#add_branches(*a) ⇒ Tree

Same as add_branches! but works on a copy of the receiver.

Parameters:

  • *a (#each) —

    an Enumerable branches set

Returns:

  • (Tree) —

    a modified copy of ‘self`



158
159
160
 
# File 'lib/jumoku/builders/extended.rb', line 158

def add_branches(*a)
  _clone.add_branches!(*a)
end

#add_branches!(*a) ⇒ Tree

Adds all branches mentionned in the specified Enumerable to the branch set.

Elements of the Enumerable can be either two-element arrays or instances of Branch.

Parameters:

  • *a (#each) —

    an Enumerable branches set

Returns:

  • (Tree) —

    ‘self`



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

def add_branches!(*a)
  a.expand_branches!.each_nodes_pair { |pair| add_branch! pair[0], pair[1] }
  self
end

#add_consecutive_nodes(*a) ⇒ Tree

Same as add_consecutive_nodes! but works on a copy of the receiver.

Parameters:

  • *a (Array(nodes)) —

    flat array of unique nodes

Returns:

  • (Tree) —

    a modified copy of ‘self`



136
137
138
 
# File 'lib/jumoku/builders/extended.rb', line 136

def add_consecutive_nodes(*a)
  _clone.add_consecutive_nodes!(*a)
end

#add_consecutive_nodes!(*a) ⇒ Tree

Allows for adding consecutive nodes, each nodes being connected to their previous and next neighbours.

You may pass branches within the nodes list.

Tree.new.add_consecutive_nodes!(1, 2, 3, :four, Branch.new(:foo, "bar")).branches
# => (1=2, 2=3, 3=:four, :four=:foo, :foo="bar")

Parameters:

  • *a (Array(nodes)) —

    flat array of unique nodes

Returns:

  • (Tree) —

    ‘self`



122
123
124
125
126
127
128
 
# File 'lib/jumoku/builders/extended.rb', line 122

def add_consecutive_nodes!(*a)
  # FIXME: really this may not be as efficient as it could be.
  # We may get rid of nodes duplication (no expand_branches!)
  # and add nodes by pair, shifting one node at a time from the list.
  add_nodes!(a.expand_branches!.create_nodes_pairs_list)
  self
end

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

Non destructive version of RawTreeBuilder#add_node! (works on a copy of the tree).

Overloads:

  • #add_node!(n) ⇒ Tree

    Parameters:

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

    Parameters:

    • b (Branch) —

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

Returns:

  • (Tree) —

    a modified copy of ‘self`

See Also:

  • RawTreeBuilder#add_node!


17
18
19
 
# File 'lib/jumoku/builders/extended.rb', line 17

def add_node(n, l = nil)
  _clone.add_node!(n, l)
end

#add_nodes(*a) ⇒ Tree

Same as add_nodes! but works on a copy of the receiver.

Parameters:

  • *a (#each) —

    an Enumerable nodes set

Returns:

  • (Tree) —

    a modified copy of ‘self`



107
108
109
 
# File 'lib/jumoku/builders/extended.rb', line 107

def add_nodes(*a)
  _clone.add_nodes!(*a)
end

#add_nodes!(*a) ⇒ Tree Also known as: <<

Adds all specified nodes to the node set.

The nodes defines implicit branches, that is it is mandatory to provide an odd number of connected nodes which do not form cycles. You may specify Branch objects within the list, though.

Valid usage:

tree = Tree.new                # an empty tree
tree.add_nodes!(1,2, 2,3, 3,4) # tree.nodes => [1, 2, 3, 4]
                               # branches are (1-2), (2-3), (3-4)
tree.add_nodes!(1,2, 2,3, Branch.new(3,4), 10,1)
tree.add_nodes! [1,2, 2,3, 3,4]

Invalid usages:

tree = Tree.new                # an empty tree
tree.add_nodes!(1, 2, 3)       # even number of nodes
tree.add_nodes!(1,2, 2,3, 3,1) # cycle
tree.add_nodes!(1,2, 4,5)      # not connected

A helper exist to make it easy to add nodes in a suite. See add_consecutive_nodes!.

Parameters:

  • *a (#each) —

    an Enumerable nodes set

Returns:

  • (Tree) —

    ‘self`



87
88
89
90
91
92
93
94
95
96
97
98
99
 
# File 'lib/jumoku/builders/extended.rb', line 87

def add_nodes!(*a)
  a = a.flatten.expand_branches!
  if a.size == 1                                   # This allows for using << to add the root as well,
    if empty?                                      # so that you may write:
      add_node! a.only                             # Tree.new << :root << [:root, 1] << [1,2, 2,3, Branch.new(3,4)]...
    else
      raise RawTreeError, "Cannot add a node without a neighbour."
    end
  else
    a.expand_branches!.each_nodes_pair { |pair| add_branch! pair[0], pair[1] }
  end
  self
end

#branch?(a) ⇒ Boolean #branch?(i, j) ⇒ Boolean Also known as: has_branch?

Returns true if i or (i,j) is a branch of the tree.

Overloads:

  • #branch?(a) ⇒ Boolean

    Parameters:

  • #branch?(i, j) ⇒ Boolean

    Parameters:

    • i (node)
    • j (node)

Returns:

  • (Boolean) 


257
258
259
 
# File 'lib/jumoku/builders/extended.rb', line 257

def branch?(*args)
  branches.include?(edge_convert(*args))
end

#branches?(*maybe_branches) ⇒ Boolean Also known as: has_branches?

Returns true if the specified branches are a subset of or match exactly the branches set of the tree (no ordering criterion).

Labels are not part of the matching constraint: only connected nodes matter in defining branch equality.

Parameters:

  • *maybe_branches (*Branch, *nodes) —

    a list of branches, either as Branch objects or as nodes pairs

Returns:

  • (Boolean) 


272
273
274
275
276
277
278
 
# File 'lib/jumoku/builders/extended.rb', line 272

def branches?(*maybe_branches)
  maybe_branches.create_branches_list(_branch_type).all? do |maybe_branch|
    branches.any? do |branch|
      maybe_branch == branch
    end
  end
end

#branches_among?(*maybe_branches) ⇒ Boolean Also known as: has_branches_among?

Returns true if actual branches are included in the specified set of branches (no ordering criterion).

Labels are not part of the matching constraint: only connected nodes matter in defining equality.

Parameters:

  • *maybe_branches (*Branch, *nodes) —

    a list of branches, either as Branch objects or as nodes pairs

Returns:

  • (Boolean) 


291
292
293
294
295
296
297
298
 
# File 'lib/jumoku/builders/extended.rb', line 291

def branches_among?(*maybe_branches)
  list = maybe_branches.create_branches_list(_branch_type)
  branches.all? do |branch|
    list.any? do |maybe_branch|
      branch == maybe_branch
    end
  end
end

#node?(n) ⇒ Boolean Also known as: has_node?

Returns true if the specified node belongs to the tree.

This is a default implementation that is of O(n) average complexity. If a subclass uses a hash to store nodes, then this can be made into an O(1) average complexity operation.

Parameters:

  • n (node)

Returns:

  • (Boolean) 


221
222
223
 
# File 'lib/jumoku/builders/extended.rb', line 221

def node?(n)
  nodes.include?(n)
end

#nodes?(*maybe_nodes) ⇒ Boolean Also known as: has_nodes?

Returns true if all specified nodes belong to the tree.

Parameters:

  • (nodes)

Returns:

  • (Boolean) 


231
232
233
 
# File 'lib/jumoku/builders/extended.rb', line 231

def nodes?(*maybe_nodes)
  maybe_nodes.all? { |node| nodes.include? node }
end

#nodes_among?(*maybe_nodes) ⇒ Boolean Also known as: has_nodes_among?, has_node_among?

Returns true if any of the specified nodes belongs to the tree.

Parameters:

  • (nodes)

Returns:

  • (Boolean) 


241
242
243
 
# File 'lib/jumoku/builders/extended.rb', line 241

def nodes_among?(*maybe_nodes)
  maybe_nodes.any? { |node| nodes.include? node }
end

#num_branches ⇒ Integer Also known as: number_of_branches

Number of branches.

Returns:

  • (Integer) 


314
315
316
 
# File 'lib/jumoku/builders/extended.rb', line 314

def num_branches
  branches.size
end

#num_nodes ⇒ Integer Also known as: number_of_nodes

Number of nodes. Just ‘#nodes.size` really.

Returns:

  • (Integer) 


305
306
307
 
# File 'lib/jumoku/builders/extended.rb', line 305

def num_nodes
  nodes.size
end

#remove_branch(i, j = nil, *params) ⇒ Tree

Non destructive version RawTreeBuilder#remove_branch! (works on a copy of the tree).

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

Parameters:

  • i (node)
  • j (node) (defaults to: nil)

Returns:

  • (Tree) —

    a modified copy of ‘self`

See Also:

  • RawTreeBuilder#remove_branch!


56
57
58
 
# File 'lib/jumoku/builders/extended.rb', line 56

def remove_branch(i, j = nil, *params)
  _clone.remove_branch!(i, j)
end

#remove_branches(*a) ⇒ Tree Also known as: delete_branches

Same as remove_branches! but works on a copy of the receiver.

Parameters:

  • *a (#each) —

    an Enumerable branches set

Returns:

  • (Tree) —

    a modified copy of ‘self`

See Also:

  • RawTreeBuilder#remove_branch!


207
208
209
 
# File 'lib/jumoku/builders/extended.rb', line 207

def remove_branches(*a)
  _clone.remove_branches!(*a)
end

#remove_branches!(*a) ⇒ Tree Also known as: delete_branches!

Removes all branches mentionned in the specified Enumerable from the tree.

Parameters:

  • *a (#each) —

    an Enumerable branches set

Returns:

  • (Tree) —

    ‘self`



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

def remove_branches!(*a)
  a.expand_branches!.each_nodes_pair { |pair| remove_branch! pair[0], pair[1] }
  self
end

#remove_node(n) ⇒ Tree

Non destructive version of RawTreeBuilder#remove_node! (works on a copy of the tree).

Parameters:

  • n (node)

Returns:

  • (Tree) —

    a modified copy of ‘self`

See Also:

  • RawTreeBuilder#remove_node!


42
43
44
 
# File 'lib/jumoku/builders/extended.rb', line 42

def remove_node(n)
  _clone.remove_node!(n)
end

#remove_nodes(*a) ⇒ Tree Also known as: delete_nodes

Same as remove_nodes! but works on a copy of the receiver.

Parameters:

  • *a (#each) —

    a node Enumerable set

Returns:

  • (Tree) —

    a modified copy of ‘self`



185
186
187
 
# File 'lib/jumoku/builders/extended.rb', line 185

def remove_nodes(*a)
  _clone.remove_nodes!(*a)
end

#remove_nodes!(*nodes) ⇒ Tree Also known as: delete_nodes!

Removes all nodes mentionned in the specified Enumerable from the tree.

The process relies on remove_node!.

Examples:


remove_nodes! 1, 3..5

Parameters:

  • *nodes (#each) —

    an Enumerable nodes set; may contain Range

Returns:

  • (Tree) —

    ‘self`



173
174
175
176
177
 
# File 'lib/jumoku/builders/extended.rb', line 173

def remove_nodes!(*nodes)
  nodes = nodes.to_a.map { |i| i.is_a?(Range) ? i.to_a : i }.flatten
  nodes.each { |v| remove_node! v }
  self
end