Module: Rigor::ModuleGraph::CycleDetector

Defined in:
lib/rigor/module_graph/cycle_detector.rb

Overview

Finds dependency cycles in an Edge list.

Tarjan’s strongly-connected-components, sized ≥ 2 (a SCC of 1 is a single node with no self-loop and represents no cycle). We also surface single-node self-loops if any edge points a constant at itself.

Returns an array of Cycle, where each Cycle carries the list of node names in the cycle in a canonical rotation: smallest name first. The actual edge instances making up each cycle are not surfaced — for visualisation we only need the node set — but a kind filter is offered so callers can ask “do these edges form a cycle using only ‘include` / `inherits`?”

Defined Under Namespace

Classes: Cycle

Class Method Summary collapse

Class Method Details

.build_adjacency(edges, kinds) ⇒ Object 



46
47
48
49
50
51
52
53
54
55
56
 
# File 'lib/rigor/module_graph/cycle_detector.rb', line 46

def build_adjacency(edges, kinds)
  graph = Hash.new { |h, k| h[k] = [] }
  edges.each do |edge|
    next if kinds && !kinds.include?(edge.kind)

    graph[edge.from] << edge.to
    graph[edge.to] # ensure target appears even with no outgoing edges
  end
  graph.each_value(&:uniq!)
  graph
end

.canonicalize(scc, graph) ⇒ Object 



114
115
116
117
118
 
# File 'lib/rigor/module_graph/cycle_detector.rb', line 114

def canonicalize(scc, graph)
  nodes = walk_cycle(scc, graph)
  nodes = rotate_to_smallest(nodes)
  Cycle.new(nodes: nodes)
end

.collect_self_loops(graph) ⇒ Object 



147
148
149
150
151
 
# File 'lib/rigor/module_graph/cycle_detector.rb', line 147

def collect_self_loops(graph)
  graph.each_with_object([]) do |(node, targets), acc|
    acc << Cycle.new(nodes: [node]) if targets.include?(node)
  end
end

.detect(edges, kinds: nil) ⇒ Object

Parameters:

  • edges (Array<Edge>)
  • kinds (Array<String>, nil) (defaults to: nil) —

    when given, only edges whose ‘kind` is in the list participate in cycle detection.



38
39
40
41
42
43
44
 
# File 'lib/rigor/module_graph/cycle_detector.rb', line 38

def detect(edges, kinds: nil)
  graph = build_adjacency(edges, kinds)
  sccs = tarjan(graph)
  cycles = sccs.select { |scc| scc.size >= 2 }.map { |scc| canonicalize(scc, graph) }
  self_loops = collect_self_loops(graph)
  (cycles + self_loops).sort_by { |c| c.nodes.first }
end

.rotate_to_smallest(nodes) ⇒ Object 



142
143
144
145
 
# File 'lib/rigor/module_graph/cycle_detector.rb', line 142

def rotate_to_smallest(nodes)
  i = nodes.each_with_index.min_by { |name, _| name }[1]
  nodes.rotate(i)
end

.tarjan(graph) ⇒ Object

Iterative Tarjan to avoid blowing the Ruby stack on a wide graph. Returns SCCs as arrays of node names.



60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
 
# File 'lib/rigor/module_graph/cycle_detector.rb', line 60

def tarjan(graph)
  index = 0
  indices = {}
  lowlink = {}
  on_stack = {}
  stack = []
  sccs = []

  graph.each_key do |start|
    next if indices.key?(start)

    work = [[start, 0]]
    indices[start] = index
    lowlink[start] = index
    index += 1
    stack.push(start)
    on_stack[start] = true

    until work.empty?
      node, i = work.last
      neighbours = graph[node]
      if i < neighbours.size
        work[-1] = [node, i + 1]
        succ = neighbours[i]
        if !indices.key?(succ)
          indices[succ] = index
          lowlink[succ] = index
          index += 1
          stack.push(succ)
          on_stack[succ] = true
          work.push([succ, 0])
        elsif on_stack[succ]
          lowlink[node] = [lowlink[node], indices[succ]].min
        end
      else
        if lowlink[node] == indices[node]
          scc = []
          loop do
            w = stack.pop
            on_stack.delete(w)
            scc << w
            break if w == node
          end
          sccs << scc
        end
        work.pop
        parent = work.last&.first
        lowlink[parent] = [lowlink[parent], lowlink[node]].min if parent
      end
    end
  end
  sccs
end

.walk_cycle(scc, graph) ⇒ Object

Walk a single trip around the SCC starting from its smallest-named node, following outgoing edges that stay in the SCC. Falls back to sorted membership if the cycle is degenerate (should not happen for a real SCC ≥ 2).



124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
 
# File 'lib/rigor/module_graph/cycle_detector.rb', line 124

def walk_cycle(scc, graph)
  set = scc.to_set
  start = scc.min
  path = [start]
  current = start
  loop do
    next_node = graph[current].find { |n| set.include?(n) && !path.include?(n) }
    break unless next_node

    path << next_node
    current = next_node
  end
  # If we couldn't visit everyone (rare: SCC with parallel
  # branches), fall back to sorted order so output stays
  # deterministic.
  path.size == scc.size ? path : scc.sort
end