Class: HashGraph::UndirectedGraph

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

Overview

an undirected graph representation based on Hash, which ensures that h[b]==h[a]

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ UndirectedGraph

Returns a new instance of UndirectedGraph.



85
86
87
88
89
 
# File 'lib/hash_graph.rb', line 85

def initialize()
  super() do |h,a_vertex|
    UndirectedGraph::new_lower_hash(h,a_vertex)
  end
end

Class Method Details

.new_lower_hash(top_hash, a_vertex) ⇒ Object 



66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
 
# File 'lib/hash_graph.rb', line 66

def self.new_lower_hash(top_hash,a_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 |b_vertex,weight|
      top_hash[a_vertex]=tos if !top_hash.key?(a_vertex)
      uhg_store(b_vertex,weight)
      if top_hash.key?(b_vertex)
        top_hash[b_vertex]
      else
        top_hash[b_vertex]=UndirectedGraph::new_lower_hash(top_hash,b_vertex)
      end.uhg_store(a_vertex,weight) # ensure reverse link added too
    end
    ec.send(:alias_method, :[]=, :store)
  end
  tos
end

Instance Method Details

#components(&include_v) ⇒ Object

returns graph components



92
93
94
95
96
97
98
99
100
101
102
 
# File 'lib/hash_graph.rb', line 92

def components(&include_v)
  seen = Set.new
  comps = []
  keys.each do |vertex|
    if !seen.include?(vertex) && (!include_v || include_v.call(vertex))
      seen.add(vertex)
      comps << explore_component(seen, Set.new([vertex]), vertex, include_v).to_a
    end
  end
  comps
end

#explore_component(seen, component, vertex, include_v) ⇒ Object 



104
105
106
107
108
109
110
111
112
 
# File 'lib/hash_graph.rb', line 104

def explore_component(seen, component, vertex, include_v)
  self[vertex].keys.each do |conn_v|
    explore_component(seen.add(conn_v), 
                      component.add(conn_v), 
                      conn_v,
                      include_v) if !seen.include?(conn_v) && (!include_v || include_v.call(conn_v))
  end
  component
end