Class: HashGraph::DirectedGraph

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

Overview

a simple directed graph representation for TSort, [ TSort implements tarjan’s algorithm for finding the

strongly connected components of a graph ]

DirectedGraph extends Hash, all nodes have a key in the top-level Hash, and a possibly empty child-hash of node to weight mappings, thus the structure is : from_v*=>{to_v*=>weight} and all keys used in the child hashes are guaranteed to also be present in the top-level hash

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ DirectedGraph

construct a DirectedGraph which ensures that all destination node keys are present in the top level Hash



33
34
35
36
37
 
# File 'lib/hash_graph.rb', line 33

def initialize()
  super() do |h,from_vertex|
    DirectedGraph::new_lower_hash(h,from_vertex)
  end
end

Class Method Details

.new_lower_hash(top_hash, from_vertex) ⇒ Object 



16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
# File 'lib/hash_graph.rb', line 16

def self.new_lower_hash(top_hash,from_vertex)
  tos = Hash.new()
  tos.instance_eval do
    ec = class << self ; self ; end
    ec.send(:alias_method, :uhg_store, :store)
    ec.send(:define_method, :store) do |to_vertex,weight|
      top_hash[from_vertex]=tos if !top_hash.key?(from_vertex)
      uhg_store(to_vertex,weight)
      top_hash[to_vertex]=DirectedGraph::new_lower_hash(top_hash,to_vertex) if !top_hash.key?(to_vertex)
    end
    ec.send(:alias_method, :[]=, :store)
  end
  tos
end

Instance Method Details

#to_undirected_graph(&proc) ⇒ Object

convert to an UndirectedGraph, with a proc which takes weights (a,b,weight_a_b,weight_b_a) as parameters [weights may be nil, indicating no edge], and returns weight_a_b or nil for the undirected graph edge [ which will be the same as weight_b_a ]



43
44
45
46
47
48
49
50
51
52
53
54
 
# File 'lib/hash_graph.rb', line 43

def to_undirected_graph(&proc)
  inject(UndirectedGraph.new()) do |ug,(a,targets)|
    targets.each do |(b,weight_a_b)|
      if !ug[a][b]
        weight_b_a = self[b][a]
        undw = proc.call(a,b,weight_a_b, weight_b_a)
        ug[a][b]=undw if undw
      end
    end
    ug
  end
end

#tsort_each_child(node, &block) ⇒ Object 



58
59
60
 
# File 'lib/hash_graph.rb', line 58

def tsort_each_child(node,&block)
  fetch(node).keys.each(&block)
end