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