Class: Turbine::Algorithms::Tarjan

Inherits:

Object

• Object
• Turbine::Algorithms::Tarjan

Includes:

TSort

Defined in:

lib/turbine/algorithms/tarjan.rb

Overview

Internal: A wrapper around the Ruby stdlib implementation of Tarjan’s strongly connected components and topological sort algorithms.

Direct Known Subclasses

FilteredTarjan

Instance Method Summary

• #initialize(graph, label = nil) ⇒ Tarjan constructor

  Public: Creates a new Tarjan instance used for topologically sorting graphs.

Constructor Details

#initialize(graph, label = nil) ⇒ Tarjan

Public: Creates a new Tarjan instance used for topologically sorting graphs.

graph - A Turbine graph whose nodes are to be sorted. label - An optional label which will be used when traversing from a

node to its +out+ nodes.

For example

Turbine::Algorithms::Tarjan.new(graph).tsort
# => [ [ #<Node key=one>, #<Node key=two>, #<Node key=three> ],
       [ #<Node key=five> ],
       [ #<Node key=six>, #<Node key=seven> ] ]

Turbine::Algorithms::Tarjan.new(graph, :spouse).tsort
# => [ ... ]

Returns a Tarjan.

# File 'lib/turbine/algorithms/tarjan.rb', line 26

def initialize(graph, label = nil)
  @nodes = graph.nodes
  @label = label
end