Class: Turbine::Graph

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

Overview

Contains nodes and edges.

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Graph

Public: Creates a new graph.



6
7
8
 
# File 'lib/turbine/graph.rb', line 6

def initialize
  @nodes = {}
end

Instance Method Details

#add(node) ⇒ Object

Public: Adds the node to the graph.

node - The node to be added.

Raises a DuplicateNodeError if the graph already contains a node with the same key.

Returns the node.



18
19
20
21
22
23
24
 
# File 'lib/turbine/graph.rb', line 18

def add(node)
  if @nodes.key?(node.key)
    raise DuplicateNodeError.new(node.key)
  end

  @nodes[node.key] = node
end

#delete(node) ⇒ Object

Public: Removes the node from the graph and disconnects any nodes which have edges to the node.

node - The node to be deleted.

Raises a NoSuchNodeError if the graph does not contain the given node.

Returns the node.



34
35
36
37
38
39
40
41
42
43
44
45
 
# File 'lib/turbine/graph.rb', line 34

def delete(node)
  unless @nodes.key?(node.key)
    raise NoSuchNodeError.new(node.key)
  end

  (node.edges(:out) + node.edges(:in)).each do |edge|
    edge.from.disconnect_via(edge)
    edge.to.disconnect_via(edge)
  end

  @nodes.delete(node.key)
end

#inspect ⇒ Object

Public: A human-readable version of the graph.

Returns a string.



108
109
110
111
112
113
114
 
# File 'lib/turbine/graph.rb', line 108

def inspect
  edge_count = @nodes.values.each_with_object(Set.new) do |node, edges|
    edges.merge(node.edges(:out))
  end.length

  "#<#{self.class} (#{ @nodes.length } nodes, #{ edge_count } edges)>"
end

#node(key) ⇒ Object

Public: Retrieves the node whose key is key.

key - The key of the desired node.

Returns the node, or nil if no such node is known.



52
53
54
 
# File 'lib/turbine/graph.rb', line 52

def node(key)
  @nodes[key]
end

#nodes ⇒ Object

Public: All of the nodes in an array.

Generally speaking, the nodes will be returned in the same order as they were added to the graph, however this may very depending on your Ruby implementation.

Returns an array of nodes.



63
64
65
 
# File 'lib/turbine/graph.rb', line 63

def nodes
  @nodes.values
end

#strongly_connected_components(label = nil) ⇒ Object

Public: Uses Tarjan’s strongly-connected components algorithm to detect nodes which are interrelated.

label - An optional label used to limit the edges used when traversing

from one node to its outward nodes.

For example

graph.strongly_connected_components
# => [ [ #<Node key=one> ],
       [ #<Node key=two>, #<Node key=three>, #<Node key=four> ],
       [ #<Node key=five>, #<Node key=six ] ]

Returns an array.



101
102
103
 
# File 'lib/turbine/graph.rb', line 101

def strongly_connected_components(label = nil)
  Algorithms::Tarjan.new(self, label).strongly_connected_components
end

#tsort(label = nil, &edge_filter) ⇒ Object

Public: Topologically sorts the nodes in the graph so that nodes with no in edges appear at the beginning of the array, and those deeper within the graph are at the end.

label - An optional label used to limit the edges used when traversing

from one node to its outward nodes.

Raises CyclicError if the graph contains loops.

Returns an array.



77
78
79
80
81
82
83
84
85
 
# File 'lib/turbine/graph.rb', line 77

def tsort(label = nil, &edge_filter)
  if edge_filter
    Algorithms::FilteredTarjan.new(self, &edge_filter)
  else
    Algorithms::Tarjan.new(self, label)
  end.tsort
rescue TSort::Cyclic => exception
  raise CyclicError.new(exception)
end