Class: Turbine::Traversal::Base

Inherits:
Object
  • Object
show all
Defined in:
lib/turbine/traversal/base.rb

Overview

Provides the means for traversing through the graph.

Traversal classes do not themselves provide the methods commonly used for iterating through collections (each, map, etc), but act as a generator for the values in an Enumerator.

enumerator = DepthFirst.new(node, :in).to_enum
# => #<Enumerator: Node, Node, ...>

enumerator.each { |node| ... }
enumerator.map  { |node| ... }
# etc ...

The Base class should not be used directly, but instead you should use DepthFirst or BreadthFirst which define strategies for the order in which items are traversed.

Each unique item is traversed a maximum of once (loops are not repeatedly followed).

Traversals are normally used to iterate through nodes, however you may also use them to traverse edges by providing a fetcher argument which tells the traversal how to reach the next set of adjacent items:

DepthFirst.new(node, :in_edges, [], :out).to_enum
# => #<Enumerator: Edge, Edge, ...>

As an end-user, you should rarely have to instantiate a traversal class yourself; Node#ancestors and Node#descendants provide a more convenient short-cut.

Direct Known Subclasses

BreadthFirst, DepthFirst

Instance Method Summary collapse

Constructor Details

#initialize(start, method, args = nil, fetcher = nil) ⇒ Base

Creates a new graph traversal.

start - The node from which to start traversing. method - The method to be used to fetch the adjacent nodes (typically

+in+ or +out+).

args - Additional arguments to be used when calling method. fetcher - An optional method name to be called on each adjacent item

in order to fetch *its* adjacent items. Useful if traversing
edges instead of nodes.

Returns a new traversal.



45
46
47
48
49
50
 
# File 'lib/turbine/traversal/base.rb', line 45

def initialize(start, method, args = nil, fetcher = nil)
  @start   = start
  @method  = method
  @args    = args
  @fetcher = fetcher
end

Instance Method Details

#inspect ⇒ Object

Public: A human-readable version of the traversal.

Returns a string.



55
56
57
58
59
 
# File 'lib/turbine/traversal/base.rb', line 55

def inspect
  "#<#{ self.class.name } start=#{ @start.inspect } " \
    "method=#{ @method.inspect }" \
    "#{ @fetcher ? " fetcher=#{ @fetcher.inspect }" : '' }>"
end

#next ⇒ Object

Public: The next node in the traversal.

Raises a StopIteration if all reachable nodes have been visited.

For example

traversal.next # => #<Turbine::Node key=:one>
traversal.next # => #<Turbine::Node key=:two>
traversal.next # => ! StopIteration

Returns a Node.



72
73
74
 
# File 'lib/turbine/traversal/base.rb', line 72

def next
  @fiber.resume
end

#to_enum ⇒ Object

Public: The traversal as an enumerator. This is the main way to traverse since the enumerator implements each, map, with_index, etc.

Returns an Enumerator.



81
82
83
84
85
86
 
# File 'lib/turbine/traversal/base.rb', line 81

def to_enum
  Enumerator.new do |control|
    rewind
    loop { control.yield(self.next) }
  end
end