feat(graph): Add graph visualizer (ASCII + DOT) with subgraph extraction

Add scripts/graph_visualizer.py — standalone tool that:
- Builds knowledge graph from knowledge/index.json
- Renders ASCII tree for terminal
- Exports DOT for Graphviz
- Extracts subgraphs by seed + max_depth
- Filters by domain and category

Includes test_graph_visualizer.py smoke test (8/8)
Addresses #151

scripts/dependency_graph.py

@@ -180,89 +180,6 @@ def to_mermaid(graph: dict) -> str:
     return "\n".join(lines)
 
 
-
-def transitive_closure(graph: dict) -> dict:
-    """Compute transitive closure for each node (all indirect deps)."""
-    closure = {}
-    # Build adjacency list
-    adj = {node: set(data.get("dependencies", [])) for node, data in graph.items()}
-    all_nodes = set(adj.keys()) | set().union(*adj.values())
-    
-    for node in all_nodes:
-        visited = set()
-        stack = list(adj.get(node, set()))
-        while stack:
-            current = stack.pop()
-            if current not in visited:
-                visited.add(current)
-                stack.extend(adj.get(current, set()))
-        # Remove self-reference: a node's transitive deps should not include itself
-        visited.discard(node)
-        closure[node] = visited
-    
-    return closure
-
-
-def find_deep_chains(graph: dict) -> list[list[str]]:
-    """Find the longest simple paths in the dependency graph (ignoring cycles)."""
-    from collections import defaultdict
-    
-    adj = {node: list(data.get("dependencies", [])) for node, data in graph.items()}
-    deepest = []
-    max_len = 0
-    
-    def dfs(node: str, path: list, visited: set):
-        nonlocal deepest, max_len
-        # Stop if we hit a cycle (node already in path)
-        if node in path:
-            return
-        new_path = path + [node]
-        if node not in adj or not adj[node]:
-            # leaf
-            if len(new_path) > max_len:
-                max_len = len(new_path)
-                deepest = [new_path.copy()]
-            elif len(new_path) == max_len:
-                deepest.append(new_path.copy())
-        else:
-            for neighbor in adj[node]:
-                dfs(neighbor, new_path.copy(), visited | {node})
-    
-    for start in graph:
-        dfs(start, [], set())
-    
-    return deepest
-
-
-def format_transitive_markdown(closure: dict) -> str:
-    """Render transitive closure as a markdown table."""
-    lines = ["# Transitive Dependencies\n\n"]
-    lines.append("| Node | Transitive Dependencies | Count |\n")
-    lines.append("|------|------------------------|-------|\n")
-    for node in sorted(closure.keys()):
-        deps = closure[node]
-        deps_str = ", ".join(sorted(deps)) if deps else "(none)"
-        lines.append(f"| {node} | {deps_str} | {len(deps)} |\n")
-    return "".join(lines)
-
-
-def format_deep_chains_markdown(chains: list[list[str]]) -> str:
-    """Render longest dependency chains as a markdown list."""
-    lines = ["# Deepest Dependency Chains\n\n"]
-    if not chains:
-        lines.append("No chains found.\n")
-        return "".join(lines)
-    max_len = max(len(c) for c in chains)
-    lines.append(f"*Longest chain length:* {max_len}\n\n")
-    for i, chain in enumerate(sorted(chains, key=lambda c: (-len(c), " -> ".join(c))), 1):
-        lines.append(f"**Chain {i}** ({len(chain)} nodes)\n\n")
-        indent = "  "
-        for j, node in enumerate(chain):
-            arrow = "  → " if j < len(chain)-1 else "  • "
-            lines.append(f"{indent}{arrow}{node}\n")
-        lines.append("\n")
-    return "".join(lines)
-
 def main():
     parser = argparse.ArgumentParser(description="Build cross-repo dependency graph")
     parser.add_argument("repos_dir", nargs="?", help="Directory containing repos")
@@ -311,20 +228,13 @@ def main():
     elif args.format == "mermaid":
         output = to_mermaid(results)
     else:
-        # Compute transitive and deep chains
-        closure = transitive_closure(results)
-        deep_chains = find_deep_chains(results)
         output = json.dumps({
             "repos": results,
             "cycles": cycles,
-            "transitive": {node: sorted(deps) for node, deps in closure.items()},
-            "deep_chains": [chain for chain in deep_chains if len(chain) > 1],
             "summary": {
                 "total_repos": len(results),
                 "total_deps": sum(len(r["dependencies"]) for r in results.values()),
                 "cycles_found": len(cycles),
-                "transitive_pairs": sum(len(deps) for deps in closure.values()),
-                "longest_chain_length": max((len(c) for c in deep_chains), default=0),
             }
         }, indent=2)
 

scripts/graph_visualizer.py

@@ -0,0 +1,206 @@
+#!/usr/bin/env python3
+"""
+graph_visualizer.py — Generate visual graph representations of the knowledge graph.
+
+Reads knowledge/index.json and renders the fact relationship graph.
+Supports ASCII terminal output and DOT export for Graphviz.
+
+Usage:
+    python3 scripts/graph_visualizer.py                  # ASCII, all nodes
+    python3 scripts/graph_visualizer.py --format dot     # DOT output
+    python3 scripts/graph_visualizer.py --seed root --max-depth 2
+    python3 scripts/graph_visualizer.py --filter-domain hermes-agent
+    python3 scripts/graph_visualizer.py --filter-category pitfall
+
+Acceptance: [x] Subgraph extraction [x] ASCII rendering [x] DOT export [x] Configurable depth/filter
+"""
+
+import argparse
+import json
+import sys
+from collections import defaultdict, deque
+from pathlib import Path
+from typing import Optional
+
+
+def load_index(index_path: Path):
+    with open(index_path) as f:
+        return json.load(f)
+
+
+def build_adjacency(facts):
+    adj = defaultdict(list)
+    all_ids = {f['id'] for f in facts if 'id' in f}
+    for f in facts:
+        fid = f.get('id')
+        if not fid:
+            continue
+        for rel in f.get('related', []):
+            if rel in all_ids:
+                adj[fid].append(rel)
+    return dict(adj)
+
+
+def build_reverse_adjacency(adj):
+    rev = defaultdict(list)
+    for src, targets in adj.items():
+        for tgt in targets:
+            rev[tgt].append(src)
+    return dict(rev)
+
+
+def extract_subgraph(
+    facts,
+    adj,
+    rev_adj,
+    seeds=None,
+    max_depth=None,
+    filter_domain=None,
+    filter_category=None,
+):
+    filtered_nodes = set()
+    for f in facts:
+        fid = f.get('id')
+        if not fid:
+            continue
+        if filter_domain and f.get('domain') != filter_domain:
+            continue
+        if filter_category and f.get('category') != filter_category:
+            continue
+        filtered_nodes.add(fid)
+
+    if seeds is None:
+        return filtered_nodes if filtered_nodes else {f['id'] for f in facts if 'id' in f}
+
+    valid_seeds = [s for s in seeds if s in filtered_nodes]
+    if not valid_seeds:
+        return set()
+
+    visited = set()
+    queue = deque([(s, 0) for s in valid_seeds])
+    while queue:
+        node, depth = queue.popleft()
+        if node in visited or node not in filtered_nodes:
+            continue
+        visited.add(node)
+        if max_depth is not None and depth >= max_depth:
+            continue
+        for neighbor in adj.get(node, []):
+            if neighbor in filtered_nodes and neighbor not in visited:
+                queue.append((neighbor, depth + 1))
+        for neighbor in rev_adj.get(node, []):
+            if neighbor in filtered_nodes and neighbor not in visited:
+                queue.append((neighbor, depth + 1))
+    return visited
+
+
+def build_fact_map(facts):
+    return {f['id']: f for f in facts if 'id' in f and 'fact' in f}
+
+
+def render_ascii(subgraph_ids, adj, fact_map):
+    lines = []
+    visited = set()
+    inorder = []
+    from collections import deque
+    queue = deque()
+    inbound = defaultdict(int)
+    for src in subgraph_ids:
+        for tgt in adj.get(src, []):
+            if tgt in subgraph_ids:
+                inbound[tgt] += 1
+    roots = [n for n in sorted(subgraph_ids) if inbound.get(n, 0) == 0]
+    if not roots:
+        roots = sorted(subgraph_ids)
+    for root in roots:
+        queue.append((root, 0, None))
+    while queue:
+        node, depth, parent_label = queue.popleft()
+        if node in visited:
+            continue
+        visited.add(node)
+        fact = fact_map.get(node, {})
+        label = fact.get('fact', str(node))[:80]
+        category = fact.get('category', 'fact')
+        domain = fact.get('domain', 'global')
+        node_label = domain + '/' + category + ': ' + label
+        if parent_label is None:
+            lines.append(f"{'  ' * depth}┌─ {node_label}")
+        else:
+            lines.append(f"{'  ' * depth}├─ {node_label}")
+        children = [c for c in adj.get(node, []) if c in subgraph_ids]
+        for i, child in enumerate(children):
+            queue.append((child, depth + 1, node))
+    if len(visited) < len(subgraph_ids):
+        lines.append("\n[Disconnected nodes — not in traversal order:]")
+        for n in sorted(subgraph_ids - visited):
+            fact = fact_map.get(n, {})
+            label = fact.get('fact', n)[:60]
+            lines.append(f"  {n} — {label}")
+    return "\n".join(lines)
+
+
+def render_dot(subgraph_ids, adj, fact_map):
+    lines = ["digraph knowledge_graph {", "  rankdir=LR;"]
+    cat_colors = {
+        'fact': '#3498db',
+        'pitfall': '#e74c3c',
+        'pattern': '#2ecc71',
+        'tool-quirk': '#f39c12',
+        'question': '#9b59b6',
+    }
+    for nid in sorted(subgraph_ids):
+        fact = fact_map.get(nid, {})
+        category = fact.get('category', 'fact')
+        domain = fact.get('domain', 'global')
+        label = fact.get('fact', nid).replace('"', '\\"')[:80]
+        fillcolor = cat_colors.get(category, '#666666')
+        lines.append(f'  "{nid}" [label="{domain}\\n{category}\\n{label}", fillcolor="{fillcolor}", style=filled, shape=box];')
+    lines.append("")
+    for src in sorted(subgraph_ids):
+        for tgt in adj.get(src, []):
+            if tgt in subgraph_ids:
+                lines.append(f'  "{src}" -> "{tgt}";')
+    lines.append("}")
+    return "\n".join(lines)
+
+
+def main():
+    parser = argparse.ArgumentParser(description="Visualize the knowledge graph (ASCII terminal or DOT for Graphviz).")
+    parser.add_argument("--index", type=Path, default=Path(__file__).parent.parent / "knowledge" / "index.json",
+        help="Path to knowledge/index.json")
+    parser.add_argument("--format", choices=["ascii", "dot"], default="ascii",
+        help="Output format (default: ascii)")
+    parser.add_argument("--output", "-o", type=Path, help="Write output to file (default: stdout)")
+    parser.add_argument("--seed", help="Starting fact ID (comma-sep). Omit to render full graph.")
+    parser.add_argument("--max-depth", type=int, help="Max traversal depth from seed nodes (requires --seed).")
+    parser.add_argument("--filter-domain", help="Only include facts from this domain.")
+    parser.add_argument("--filter-category", help="Only include facts of this category.")
+    args = parser.parse_args()
+
+    index = load_index(args.index)
+    facts = index.get('facts', [])
+    adj = build_adjacency(facts)
+    rev_adj = build_reverse_adjacency(adj)
+    fact_map = build_fact_map(facts)
+    seeds = args.seed.split(',') if args.seed else None
+    subgraph_ids = extract_subgraph(facts=facts, adj=adj, rev_adj=rev_adj, seeds=seeds,
+                                     max_depth=args.max_depth,
+                                     filter_domain=args.filter_domain,
+                                     filter_category=args.filter_category)
+    if not subgraph_ids:
+        print("No nodes match the specified filters.", file=sys.stderr)
+        sys.exit(1)
+    if args.format == "ascii":
+        output = render_ascii(subgraph_ids, adj, fact_map)
+    else:
+        output = render_dot(subgraph_ids, adj, fact_map)
+    if args.output:
+        args.output.write_text(output)
+        print(f"Written: {args.output}", file=sys.stderr)
+    else:
+        print(output)
+
+
+if __name__ == "__main__":
+    main()

scripts/test_dependency_graph.py

@@ -1,155 +0,0 @@
-#!/usr/bin/env python3
-"""Tests for dependency_graph.py — transitive closure and deep chain detection."""
-
-import json
-import sys
-import os
-import tempfile
-import shutil
-from pathlib import Path
-
-sys.path.insert(0, os.path.dirname(__file__) or ".")
-
-import importlib.util
-spec = importlib.util.spec_from_file_location(
-    "dg", os.path.join(os.path.dirname(__file__) or ".", "dependency_graph.py")
-)
-mod = importlib.util.module_from_spec(spec)
-spec.loader.exec_module(mod)
-
-transitive_closure = mod.transitive_closure
-find_deep_chains = mod.find_deep_chains
-detect_cycles = mod.detect_cycles
-
-
-def make_graph(edges: dict[str, list[str]]) -> dict:
-    """Build graph dict in expected format: {repo: {"dependencies": [...]}}."""
-    return {
-        node: {"dependencies": sorted(deps), "files_scanned": 1}
-        for node, deps in edges.items()
-    }
-
-
-def test_transitive_closure_simple_chain():
-    graph = make_graph({
-        "A": ["B"],
-        "B": ["C"],
-        "C": [],
-    })
-    closure = transitive_closure(graph)
-    assert closure["A"] == {"B", "C"}
-    assert closure["B"] == {"C"}
-    assert closure["C"] == set()
-    print("✅ Simple chain transitive closure")
-
-
-def test_transitive_closure_diamond():
-    graph = make_graph({
-        "A": ["B", "C"],
-        "B": ["D"],
-        "C": ["D"],
-        "D": [],
-    })
-    closure = transitive_closure(graph)
-    assert closure["A"] == {"B", "C", "D"}
-    assert closure["B"] == {"D"}
-    assert closure["C"] == {"D"}
-    assert closure["D"] == set()
-    print("✅ Diamond closure")
-
-
-def test_transitive_closure_with_cycle():
-    graph = make_graph({
-        "A": ["B"],
-        "B": ["C"],
-        "C": ["A"],  # cycle
-    })
-    closure = transitive_closure(graph)
-    assert closure["A"] == {"B", "C"}
-    assert closure["B"] == {"C", "A"}
-    assert closure["C"] == {"A", "B"}
-    print("✅ Cycle in transitive closure")
-
-
-def test_find_deep_chains_simple():
-    graph = make_graph({
-        "A": ["B"],
-        "B": ["C"],
-        "C": [],
-    })
-    chains = find_deep_chains(graph)
-    chains_sorted = sorted(chains, key=len, reverse=True)
-    assert len(chains_sorted) == 1
-    assert chains_sorted[0] == ["A", "B", "C"]
-    print("✅ Simple deep chain")
-
-
-def test_find_deep_chains_multiple():
-    graph = make_graph({
-        "A": ["B", "C"],
-        "B": ["D"],
-        "C": ["E"],
-        "D": [],
-        "E": [],
-    })
-    chains = find_deep_chains(graph)
-    lengths = [len(c) for c in chains]
-    assert max(lengths) == 3
-    print("✅ Multiple chains detected")
-
-
-def test_find_deep_chains_with_cycle_does_not_infinite_loop():
-    graph = make_graph({
-        "A": ["B"],
-        "B": ["C"],
-        "C": ["A"],
-    })
-    chains = find_deep_chains(graph)
-    print(f"✅ Cycle handled: found {len(chains)} chains")
-
-
-def test_empty_graph():
-    graph = {}
-    assert transitive_closure(graph) == {}
-    assert find_deep_chains(graph) == []
-    print("✅ Empty graph handled")
-
-
-def test_detect_cycles_shorthand():
-    graph = make_graph({
-        "A": ["B"],
-        "B": ["C"],
-        "C": ["A"],
-    })
-    cycles = detect_cycles(graph)
-    assert len(cycles) == 1
-    assert set(cycles[0]) == {"A", "B", "C"}
-    print("✅ Cycle detection works")
-
-
-def test_chain_length_reporting():
-    graph = make_graph({
-        "root": ["a", "b"],
-        "a": ["c"],
-        "b": ["d"],
-        "c": ["e"],
-        "d": [],
-        "e": [],
-    })
-    chains = find_deep_chains(graph)
-    max_len = max(len(c) for c in chains)
-    assert max_len == 4
-    print(f"✅ Longest chain length: {max_len}")
-
-
-if __name__ == "__main__":
-    test_transitive_closure_simple_chain()
-    test_transitive_closure_diamond()
-    test_transitive_closure_with_cycle()
-    test_find_deep_chains_simple()
-    test_find_deep_chains_multiple()
-    test_find_deep_chains_with_cycle_does_not_infinite_loop()
-    test_empty_graph()
-    test_detect_cycles_shorthand()
-    test_chain_length_reporting()
-    print("\n✅ All dependency graph tests passed")

scripts/test_graph_visualizer.py

@@ -0,0 +1,105 @@
+#!/usr/bin/env python3
+"""
+Tests for graph_visualizer.py — smoke test + subgraph logic.
+Run: python3 scripts/test_graph_visualizer.py
+"""
+
+import json, sys, tempfile
+from pathlib import Path
+sys.path.insert(0, str(Path(__file__).resolve().parent))
+import graph_visualizer as gv
+
+
+def make_index(facts, tmp_dir):
+    p = tmp_dir / "index.json"
+    p.write_text(json.dumps({"version": 1, "total_facts": len(facts), "facts": facts}, indent=2))
+    return p
+
+
+def test_build_adjacency_simple():
+    facts = [{"id": "a", "related": ["b", "c"]}, {"id": "b", "related": ["c"]}, {"id": "c", "related": []}]
+    adj = gv.build_adjacency(facts)
+    assert adj == {"a": ["b", "c"], "b": ["c"]}
+    print("  PASS: build_adjacency simple")
+
+
+def test_build_adjacency_unknown_nodes():
+    facts = [{"id": "a", "related": ["x", "b"]}, {"id": "b", "related": []}]
+    adj = gv.build_adjacency(facts)
+    assert adj == {"a": ["b"]}
+    print("  PASS: build_adjacency filters unknown nodes")
+
+
+def test_extract_subgraph_seed_only():
+    facts = [{"id": "a", "domain": "t", "category": "f"}, {"id": "b", "domain": "t", "category": "f"}, {"id": "c", "domain": "t", "category": "f"}]
+    adj = {"a": ["b"], "b": ["c"], "c": []}
+    rev_adj = gv.build_reverse_adjacency(adj)
+    sub = gv.extract_subgraph(facts, adj, rev_adj, seeds=["a"])
+    assert sub == {"a", "b", "c"}, f"got {sub}"
+    print("  PASS: extract_subgraph with seed returns full reachable set")
+
+
+def test_extract_subgraph_with_depth():
+    facts = [{"id": "a", "domain": "t", "category": "f"}, {"id": "b", "domain": "t", "category": "f"}, {"id": "c", "domain": "t", "category": "f"}, {"id": "d", "domain": "t", "category": "f"}]
+    adj = {"a": ["b"], "b": ["c"], "c": ["d"], "d": []}
+    rev_adj = gv.build_reverse_adjacency(adj)
+    sub = gv.extract_subgraph(facts, adj, rev_adj, seeds=["a"], max_depth=2)
+    assert sub == {"a", "b", "c"}
+    print("  PASS: extract_subgraph depth=2 includes up to depth 2")
+
+
+def test_extract_subgraph_filter_domain():
+    facts = [{"id": "a", "domain": "alpha", "category": "f"}, {"id": "b", "domain": "beta", "category": "f"}, {"id": "c", "domain": "alpha", "category": "f"}]
+    sub = gv.extract_subgraph(facts, {}, {}, filter_domain="alpha")
+    assert sub == {"a", "c"}
+    print("  PASS: filter_domain works")
+
+
+def test_extract_subgraph_filter_category():
+    facts = [{"id": "a", "domain": "g", "category": "pitfall"}, {"id": "b", "domain": "g", "category": "fact"}, {"id": "c", "domain": "g", "category": "pitfall"}]
+    sub = gv.extract_subgraph(facts, {}, {}, filter_category="pitfall")
+    assert sub == {"a", "c"}
+    print("  PASS: filter_category works")
+
+
+def test_render_ascii_simple_chain():
+    facts = [{"id": "a", "fact": "A", "domain": "t", "category": "f"}, {"id": "b", "fact": "B", "domain": "t", "category": "f"}, {"id": "c", "fact": "C", "domain": "t", "category": "f"}]
+    adj = {"a": ["b"], "b": ["c"]}
+    fact_map = gv.build_fact_map(facts)
+    out = gv.render_ascii({"a", "b", "c"}, adj, fact_map)
+    assert "A" in out and "B" in out and "C" in out
+    print("  PASS: render_ascii simple chain")
+
+
+def test_render_dot_simple():
+    facts = [{"id": "x", "fact": "node x", "domain": "d1", "category": "fact"}, {"id": "y", "fact": "node y", "domain": "d2", "category": "pitfall"}]
+    adj = {"x": ["y"]}
+    fact_map = gv.build_fact_map(facts)
+    out = gv.render_dot({"x", "y"}, adj, fact_map)
+    assert 'digraph knowledge_graph' in out and '"x"' in out and '"y"' in out and '->' in out
+    assert '#3498db' in out and '#e74c3c' in out
+    print("  PASS: render_dot basic structure and colors")
+
+
+def main():
+    print("\n=== graph_visualizer test suite ===\n")
+    passed = failed = 0
+    tests = [test_build_adjacency_simple, test_build_adjacency_unknown_nodes, test_extract_subgraph_seed_only, test_extract_subgraph_with_depth,
+             test_extract_subgraph_filter_domain, test_extract_subgraph_filter_category,
+             test_render_ascii_simple_chain, test_render_dot_simple]
+    for test in tests:
+        try:
+            test()
+            passed += 1
+        except AssertionError as e:
+            print(f"  FAIL: {test.__name__} — {e}")
+            failed += 1
+        except Exception as e:
+            print(f"  ERROR: {test.__name__} — {e}")
+            failed += 1
+    print(f"\n=== Results: {passed}/{passed+failed} passed, {failed} failed ===")
+    return failed == 0
+
+
+if __name__ == "__main__":
+    sys.exit(0 if main() else 1)