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