class Courgette::Graph

Attributes

adjacency_list[RW]
edges[R]
nodes[R]

Public Class Methods

new(nodes, edges) click to toggle source
# File lib/courgette/graph.rb, line 7
def initialize nodes, edges
  @nodes = nodes
  @edges = edges

  setup_graph
end

Public Instance Methods

dependency_count(node) click to toggle source
# File lib/courgette/graph.rb, line 14
def dependency_count node
  edges.select { |r| r.referrer == node }.count
end
depender_count(node) click to toggle source
# File lib/courgette/graph.rb, line 18
def depender_count node
  edges.select { |r| r.reference == node }.count
end
filter(roots) click to toggle source
# File lib/courgette/graph.rb, line 22
def filter roots
  return self if roots.nil?

  visited = Set.new

  roots.each do |r|
    dfs(r, visited)
  end

  filtered_edges = edges.select { |r| visited.include? r.referrer }

  Graph.new visited.to_a, filtered_edges
end

Private Instance Methods

dfs(v, visited) click to toggle source
# File lib/courgette/graph.rb, line 39
def dfs v, visited
  return if visited.include? v

  visited << v

  adjacency_list[v].each do |w|
    dfs(w, visited) unless visited.include? w
  end
end
setup_graph() click to toggle source
# File lib/courgette/graph.rb, line 49
def setup_graph
  self.adjacency_list = Hash.new { |h,k| h[k] = Set.new }

  edges.each do |e|
    self.adjacency_list[e.referrer] << e.reference
  end
end