Deduplicate all_paths by reachable edge set

The Cartesian product over all nodes produces duplicate derivations when
edges differ only in nodes unreachable from the top. Walk reachable edges
from the top edge of each path and drop paths with identical reachable sets.

Co-Authored-By: Claude Opus 4.6 <noreply@anthropic.com>

1 files changed, 15 insertions, 1 deletions

diff --git a/prototype/hypergraph.rb b/prototype/hypergraph.rb
index fdaba5a..08d1a29 100644
--- a/prototype/hypergraph.rb
+++ b/prototype/hypergraph.rb
@@ -189,7 +189,21 @@ def HG::all_paths hypergraph, root
     paths = new_paths
   }
 
-  return paths
+  seen = Set.new
+  paths.select { |p|
+    reachable = Set.new
+    mark_reachable p, p.last, reachable
+    key = reachable.map(&:object_id).sort
+    !seen.include?(key) && seen.add(key)
+  }
+end
+
+def HG::mark_reachable path, edge, used
+  used << edge
+  edge.tails.each { |t|
+    child = path.find { |e| e.head == t }
+    mark_reachable path, child, used if child && !used.include?(child)
+  }
 end
 
 def HG::derive path, cur, carry