Class: Interdependence::Graph

Inherits:
Hash
  • Object
show all
Includes:
TSort
Defined in:
lib/interdependence/graph.rb

Overview

Graph data structure - Topologically sortable

  • Accessing any key will initialize that key to a new empty set.

  • Topologically sortable using ‘tsort`

Examples:

Usage


dependencies = Interdependence::Graph.new # => {}
dependencies['foo'] # => #<Set: {}>
dependencies['foo'] << 1 # => # => #<Set: {1}>

Direct Known Subclasses

DependencySetGraph

Instance Method Summary collapse

Constructor Details

#initialize ⇒ undefined

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Create a new graph utilizing Hash#default_proc

#default_proc usage initializes new keys to #default_value



27
28
29
30
31
 
# File 'lib/interdependence/graph.rb', line 27

def initialize
  super do |hash, key|
    hash[key] = default_value
  end
end

Instance Method Details

#tsort_each_child(node) { ... } ⇒ undefined

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Iterate over each child in the graph for TSort

Parameters:

  • node —

    key to fetch

Yields:

  • children of ‘node`

Returns:

  • (undefined) 


67
68
69
 
# File 'lib/interdependence/graph.rb', line 67

def tsort_each_child(node, &block)
  tsort_fetch(node).each(&block)
end

#tsort_fetch(key) ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Fetch a key for tsort and fallback to #default_value

‘tsort_fetch` returns a new #default_value like `#[]` when `key` is not found. The fallback value is not added to the graph though since we do not want to mutate the graph during iteration

Parameters:

  • key —

    key being looked up

Returns:

  • value stored at self.fetch(key) if key exists

  • (#default_value) —

    otherwise

See Also:

  • Hash#fetch
  • #default_value


87
88
89
 
# File 'lib/interdependence/graph.rb', line 87

def tsort_fetch(key)
  fetch(key) { default_value }
end