Sha256: e78a497c0754958ae8ae8c9ba943c00525cecc07a6607286ad2814ca1c408fe8
Contents?: true
Size: 1.97 KB
Versions: 8
Compression:
Stored size: 1.97 KB
Contents
# typed: true
# frozen_string_literal: true
module Packwerk
# A general implementation of a graph data structure with the ability to check for - and list - cycles.
class Graph
# @param [Array<Array>] edges The edges of the graph; An edge being represented as an Array of two nodes.
def initialize(*edges)
@edges = edges.uniq
@cycles = Set.new
process
end
def cycles
@cycles.dup
end
def acyclic?
@cycles.empty?
end
private
def nodes
@edges.flatten.uniq
end
def process
# See https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search
@processed ||= begin
nodes.each { |node| visit(node) }
true
end
end
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
def neighbours(node)
@edges
.lazy
.select { |src, _dst| src == node }
.map { |_src, dst| dst }
end
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
end
end
Version data entries
8 entries across 8 versions & 1 rubygems