Module: Autonoma::Graph

Defined in:
lib/autonoma/graph.rb

Class Method Summary collapse

Class Method Details

.find_deferrable_edge(cycle, edges) ⇒ Object

Find a nullable FK edge in a cycle that can be deferred.



82
83
84
85
86
87
88
89
90
 
# File 'lib/autonoma/graph.rb', line 82

def self.find_deferrable_edge(cycle, edges)
  cycle_set = cycle.to_set
  edges.find do |e|
    cycle_set.include?(e["from"]) &&
      cycle_set.include?(e["to"]) &&
      e["from"] != e["to"] &&
      e["nullable"] == true
  end
end

.topo_sort(nodes, edges) ⇒ Object

Topological sort of nodes by FK dependency edges. Returns => […], “cycles” => [[…]].



9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
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
70
71
72
73
74
75
76
77
78
79
 
# File 'lib/autonoma/graph.rb', line 9

def self.topo_sort(nodes, edges)
  node_set = nodes.to_set

  # Filter to only edges between known nodes, skip self-referential
  relevant_edges = edges.select do |e|
    e["from"] != e["to"] && node_set.include?(e["from"]) && node_set.include?(e["to"])
  end

  # Build in-degree map and adjacency list
  in_degree = nodes.each_with_object({}) { |n, h| h[n] = 0 }
  adj = Hash.new { |h, k| h[k] = [] }

  relevant_edges.each do |e|
    # e["from"] depends on e["to"] (from has the FK pointing to to)
    adj[e["to"]] << e["from"]
    in_degree[e["from"]] = (in_degree[e["from"]] || 0) + 1
  end

  # First pass: standard Kahn's
  queue = in_degree.select { |_, d| d == 0 }.keys.sort
  sorted_nodes = []

  until queue.empty?
    node = queue.shift
    sorted_nodes << node
    (adj[node] || []).each do |neighbor|
      in_degree[neighbor] -= 1
      queue << neighbor if in_degree[neighbor] == 0
    end
    queue.sort!
  end

  # Find unsorted nodes
  unsorted = nodes.reject { |n| sorted_nodes.include?(n) }

  return { "sorted" => sorted_nodes, "cycles" => [] } if unsorted.empty?

  cycles = find_sccs(unsorted, relevant_edges)

  return { "sorted" => sorted_nodes, "cycles" => [] } if cycles.empty?

  # Second pass: treat cycle nodes as resolved and re-sort remaining
  cycle_nodes = cycles.flatten.to_set
  still_unsorted = unsorted.reject { |n| cycle_nodes.include?(n) }

  if still_unsorted.any?
    still_set = still_unsorted.to_set
    in_deg2 = still_unsorted.each_with_object({}) { |n, h| h[n] = 0 }
    adj2 = Hash.new { |h, k| h[k] = [] }

    relevant_edges.each do |e|
      if still_set.include?(e["from"]) && still_set.include?(e["to"])
        adj2[e["to"]] << e["from"]
        in_deg2[e["from"]] = (in_deg2[e["from"]] || 0) + 1
      end
    end

    queue2 = in_deg2.select { |_, d| d == 0 }.keys.sort
    until queue2.empty?
      node = queue2.shift
      sorted_nodes << node
      (adj2[node] || []).each do |neighbor|
        in_deg2[neighbor] -= 1
        queue2 << neighbor if in_deg2[neighbor] == 0
      end
      queue2.sort!
    end
  end

  { "sorted" => sorted_nodes, "cycles" => cycles }
end