fix(query): fallback BFS/DFS traversal omits relationships between visited nodes #4314

Summary

Cubic identified a correctness bug in Graphify's generated query instructions.

The inline NetworkX fallback for /graphify query records graph edges only when traversal discovers a previously unvisited node.

This can omit valid relationships between already visited nodes, producing incomplete answers even when the underlying graph contains the missing edges.

Affected file

graphify/skills/codex/references/query.md

Original downstream finding: .codex/skills/graphify/references/query.md, approximately line 133.

Priority: P2

Root cause

Both BFS and DFS couple edge recording to node discovery.

In BFS, an edge is appended only when the neighboring node is absent from subgraph_nodes.

DFS similarly appends an edge only when the neighbor has not yet been visited.

However, a graph can contain multiple relationships connecting nodes already discovered during traversal.

Node visitation should control whether traversal expands a node again, not whether an existing relationship is included in the result.

Minimal example

Consider a graph with three nodes:

• A
• B
• C

And three relationships:

• A → B
• B → C
• A → C

If A, B, and C are already selected as starting nodes, the BFS fallback records no edges between them because each target is already discovered.

The graph contains three valid relationships, but the traversal result can contain zero.

Expected behavior

The fallback traversal should preserve all relevant relationships between included nodes, within the configured traversal depth and output budget.

Actual behavior

Relationships to previously discovered nodes may be omitted, resulting in incomplete graph context.

Suggested fix

1. Separate edge collection from node-discovery logic.
2. Use the visited set only to control traversal expansion.
3. Record all relevant traversed relationships.
4. Preserve edge direction and relationship metadata.
5. Avoid duplicate edges.
6. Add regression coverage for BFS, DFS, seeded nodes, cycles, and cross-links.
7. Update the authoritative skill-generation source and regenerate the affected artifacts.

Verification

This issue was identified through static review of the generated workflow. The example above demonstrates the suspected failure mechanism; an automated regression test should confirm the behavior before implementing the fix.

I would be happy to contribute a PR addressing this issue.