Module: Rigor::ModuleGraph::Reachability

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

Overview

Restricts an edge list to the subgraph reachable from a set of root nodes within a hop limit.

Used by the --from / --depth CLI flags to make a graph focused on one or a few constants tractable to look at on a large project (where dumping every edge produces 1000+-node Mermaid output that browsers refuse to render).

Direction is configurable:

:out

follow edges in the natural direction (depends-on)

:in

follow edges backwards (depended-on-by)

:both

union of the two (the default — usually what “what’s around Article?” means)

Constant Summary collapse

VALID_DIRECTIONS = 
%i[out in both].freeze
VALID_EDGE_SCOPES = 
%i[cluster walk].freeze

Class Method Summary collapse

Class Method Details

.build_adjacency(edges, direction) ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future. 



125
126
127
128
129
130
131
132
133
134
135
 
# File 'lib/rigor/module_graph/reachability.rb', line 125

def build_adjacency(edges, direction)
  # Build only the adjacency tables we actually need. The
  # caller asking for +:out+ never touches +backward+ etc.
  forward = direction == :in ? nil : Hash.new { |h, k| h[k] = [] }
  backward = direction == :out ? nil : Hash.new { |h, k| h[k] = [] }
  edges.each do |edge|
    forward[edge.from] << edge.to if forward
    backward[edge.to] << edge.from if backward
  end
  [forward, backward]
end

.build_indexed_adjacencies(edges) ⇒ Object 



160
161
162
163
164
165
166
167
168
 
# File 'lib/rigor/module_graph/reachability.rb', line 160

def build_indexed_adjacencies(edges)
  forward = Hash.new { |h, k| h[k] = [] }
  backward = Hash.new { |h, k| h[k] = [] }
  edges.each_with_index do |edge, i|
    forward[edge.from] << [edge.to, i]
    backward[edge.to] << [edge.from, i]
  end
  [forward, backward]
end

.build_indexed_adjacency(edges, direction) ⇒ Object 



149
150
151
152
153
154
155
156
157
158
 
# File 'lib/rigor/module_graph/reachability.rb', line 149

def build_indexed_adjacency(edges, direction)
  adjacency = Hash.new { |h, k| h[k] = [] }
  edges.each_with_index do |edge, i|
    case direction
    when :out then adjacency[edge.from] << [edge.to, i]
    when :in then adjacency[edge.to] << [edge.from, i]
    end
  end
  adjacency
end

.each_neighbour(node, forward, backward, direction, &block) ⇒ Object 



137
138
139
140
141
142
143
144
145
146
147
 
# File 'lib/rigor/module_graph/reachability.rb', line 137

def each_neighbour(node, forward, backward, direction, &block)
  case direction
  when :out
    forward.fetch(node, EMPTY).each(&block)
  when :in
    backward.fetch(node, EMPTY).each(&block)
  when :both
    forward.fetch(node, EMPTY).each(&block)
    backward.fetch(node, EMPTY).each(&block)
  end
end

.filter(edges, roots:, depth: nil, direction: :both, edge_scope: :cluster) ⇒ Array<Edge>

Returns filtered edges with original order preserved.

Parameters:

  • edges (Array<Edge>)
  • roots (Array<String>) —

    node names to start from

  • depth (Integer, nil) (defaults to: nil) —

    hop limit, nil for unlimited

  • direction (Symbol) (defaults to: :both) —

    one of VALID_DIRECTIONS

  • edge_scope (Symbol) (defaults to: :cluster) —

    one of VALID_EDGE_SCOPES. :cluster (default) keeps every edge whose endpoints both fall in the reachable node set — useful when you want the neighbourhood as a cluster. :walk keeps only the edges the BFS itself traverses, so a depth=1 –direction out walk from Article returns exactly the edges whose from is Article, never the sibling inherits ApplicationRecord rows from the reached set.

Returns:

  • (Array<Edge>) —

    filtered edges with original order preserved.



44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
 
# File 'lib/rigor/module_graph/reachability.rb', line 44

def filter(edges, roots:, depth: nil, direction: :both, edge_scope: :cluster)
  roots = Array(roots).map(&:to_s).reject(&:empty?)
  return edges if roots.empty?

  unless VALID_DIRECTIONS.include?(direction)
    raise ArgumentError, "unknown direction #{direction.inspect}; expected one of #{VALID_DIRECTIONS.inspect}"
  end
  unless VALID_EDGE_SCOPES.include?(edge_scope)
    raise ArgumentError, "unknown edge_scope #{edge_scope.inspect}; expected one of #{VALID_EDGE_SCOPES.inspect}"
  end

  case edge_scope
  when :cluster
    reachable = walk(edges, roots, depth, direction)
    edges.select { |e| reachable.key?(e.from) && reachable.key?(e.to) }
  when :walk
    indexes = walked_edge_indexes(edges, roots, depth, direction)
    # `walked` is a Hash<edge_index, true>; filter by
    # membership keeping the original edge order.
    out = []
    edges.each_with_index do |e, i|
      out << e if indexes.key?(i)
    end
    out
  end
end

.run_indexed_walk(adjacency, roots, depth, walked) ⇒ Object 



170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
 
# File 'lib/rigor/module_graph/reachability.rb', line 170

def run_indexed_walk(adjacency, roots, depth, walked)
  visited = {}
  frontier = []
  roots.each do |r|
    visited[r] = true
    frontier << r
  end
  hops = 0
  until frontier.empty?
    break if depth && hops >= depth

    next_frontier = []
    frontier.each do |node|
      adjacency.fetch(node, EMPTY).each do |neighbour, edge_index|
        walked[edge_index] = true
        next if visited.key?(neighbour)

        visited[neighbour] = true
        next_frontier << neighbour
      end
    end
    frontier = next_frontier
    hops += 1
  end
end

.walk(edges, roots, depth, direction) ⇒ Object

BFS over the edge graph; returns a Hash<node_name, true> whose keys are the reachable nodes. We use a Hash instead of Set because Hash key lookup is faster on Ruby 4 and we don’t need Set’s union/intersection methods here.



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
 
# File 'lib/rigor/module_graph/reachability.rb', line 75

def walk(edges, roots, depth, direction)
  forward, backward = build_adjacency(edges, direction)

  visited = {}
  frontier = []
  roots.each do |r|
    visited[r] = true
    frontier << r
  end
  hops = 0

  until frontier.empty?
    break if depth && hops >= depth

    next_frontier = []
    frontier.each do |node|
      each_neighbour(node, forward, backward, direction) do |n|
        next if visited.key?(n)

        visited[n] = true
        next_frontier << n
      end
    end
    frontier = next_frontier
    hops += 1
  end
  visited
end

.walked_edge_indexes(edges, roots, depth, direction) ⇒ Object

Returns a Hash<edge_index, true> for the edges actually traversed by the BFS. ‘direction=both` runs the out-walk and in-walk against separate adjacency tables so the zigzag chain (+A <- X -> Y+ whose X -> Y isn’t on any genuine path from the roots) stays excluded.



109
110
111
112
113
114
115
116
117
118
119
120
121
122
 
# File 'lib/rigor/module_graph/reachability.rb', line 109

def walked_edge_indexes(edges, roots, depth, direction)
  if direction == :both
    forward, backward = build_indexed_adjacencies(edges)
    walked = {}
    run_indexed_walk(forward, roots, depth, walked)
    run_indexed_walk(backward, roots, depth, walked)
    return walked
  end

  adjacency = build_indexed_adjacency(edges, direction)
  walked = {}
  run_indexed_walk(adjacency, roots, depth, walked)
  walked
end