class Ogr::ConnectedComponents
ConnectedComponents
class finds graph components
Attributes
counter[R]
graph[R]
stack[R]
visited[R]
Public Class Methods
new(graph)
click to toggle source
# File lib/ogr/connected_components.rb, line 7 def initialize(graph) @graph = graph @visited = {} @counter = 0 find_components end
Public Instance Methods
component(v)
click to toggle source
# File lib/ogr/connected_components.rb, line 18 def component(v) visited[v] end
components()
click to toggle source
# File lib/ogr/connected_components.rb, line 22 def components visited end
connected?(v, u)
click to toggle source
# File lib/ogr/connected_components.rb, line 14 def connected?(v, u) visited[v] == visited[u] end
count()
click to toggle source
# File lib/ogr/connected_components.rb, line 26 def count counter end
Private Instance Methods
dfs(v)
click to toggle source
# File lib/ogr/connected_components.rb, line 41 def dfs(v) @stack = [v] while u = stack.pop visit(u) end end
find_components()
click to toggle source
# File lib/ogr/connected_components.rb, line 32 def find_components vertexes.each do |v| unless visited[v] dfs(v) @counter += 1 end end end
vertexes()
click to toggle source
# File lib/ogr/connected_components.rb, line 54 def vertexes @vertexes ||= graph.vertexes end
visit(v)
click to toggle source
# File lib/ogr/connected_components.rb, line 48 def visit(v) return if visited[v] visited[v] = counter stack.concat(graph.neighbors(v)) end