class Packwerk::Graph

Public Class Methods

new(*edges) click to toggle source
# File lib/packwerk/graph.rb, line 6
def initialize(*edges)
  @edges = edges.uniq
  @cycles = Set.new
  process
end

Public Instance Methods

acyclic?() click to toggle source
# File lib/packwerk/graph.rb, line 16
def acyclic?
  @cycles.empty?
end
cycles() click to toggle source
# File lib/packwerk/graph.rb, line 12
def cycles
  @cycles.dup
end

Private Instance Methods

add_cycle(cycle) click to toggle source
# File lib/packwerk/graph.rb, line 66
def add_cycle(cycle)
  # Ensure that the lexicographically smallest item is the first one labeled in a cycle
  min_node = cycle.min
  cycle.rotate! until cycle.first == min_node

  @cycles << cycle
end
neighbours(node) click to toggle source
# File lib/packwerk/graph.rb, line 59
def neighbours(node)
  @edges
    .lazy
    .select { |src, _dst| src == node }
    .map { |_src, dst| dst }
end
nodes() click to toggle source
# File lib/packwerk/graph.rb, line 22
def nodes
  @edges.flatten.uniq
end
process() click to toggle source
# File lib/packwerk/graph.rb, line 26
def process
  # See https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search
  @processed ||= begin
    nodes.each { |node| visit(node) }
    true
  end
end
visit(node, visited_nodes: Set.new, path: []) click to toggle source
# File lib/packwerk/graph.rb, line 34
def visit(node, visited_nodes: Set.new, path: [])
  # Already visited, short circuit to avoid unnecessary processing
  return if visited_nodes.include?(node)

  # We've returned to a node that we've already visited, so we've found a cycle!
  if path.include?(node)
    # Filter out the part of the path that isn't a cycle. For example, with the following path:
    #
    #   a -> b -> c -> d -> b
    #
    # "a" isn't part of the cycle. The cycle should only appear once in the path, so we reject
    # everything from the beginning to the first instance of the current node.
    add_cycle(path.drop_while { |n| n != node })
    return
  end

  path << node
  neighbours(node).each do |neighbour|
    visit(neighbour, visited_nodes: visited_nodes, path: path)
  end
  path.pop
ensure
  visited_nodes << node
end