Clarify path identity for parallel relations in NetworkX graph traversal

[DivyamTalwar]

@haolpku

Summary

The NetworkX provider stores relation- and origin-distinct edges in a MultiDiGraph, but traverse deduplicates paths using only the node sequence. Parallel relations between the same nodes are therefore suppressed according to insertion order.

Evidence

At the current main baseline (96e49f9e006f1f5a44f9838bdfbb74f27885363a), two edges A -> B with relations authored and reviewed produce the same path key (A, B). The first edge survives and the second is skipped before its relation, weight, or provenance can be returned. Reversing insertion order changes which relation is visible.

This is a deterministic reduced identity witness; the public traversal contract still needs confirmation.

Decision requested

Should path identity be:

• node sequence only, with a documented deterministic representative policy; or
• relation sequence / exact edge identity, so relation- and origin-distinct alternatives are returned?

Any implementation must preserve relation_filter, max_hops, and max_results, keep cycle control, and bound combinatorial growth. A focused regression should cover parallel relations, same relation from different origins, insertion-order reversal, filters, caps, cycles, and reload from persisted graph.

No implementation PR is opened until the path-identity contract is confirmed.

[haolpku]

Thanks for identifying this. The intended contract is exact stored edge-sequence identity, rather than node-sequence identity. DataMind uses traversal results as evidence, so different relations or different stored origins between the same nodes must remain distinguishable. Re-upserting the same edge identity should still replace it, not create a duplicate.

I reproduced the suppression on main and implemented the fix in #15. It retains relation filtering at every hop, node-simple cycle control, and hop/result limits. Traversal expands in deterministic target/relation/edge-key order, stops as soon as the result budget is reached, and sorts the selected paths by score. This preserves bounded enumeration; it does not claim globally optimal top-k paths.

Regression coverage includes parallel relations and multihop extensions, the same relation from different origins (including profile/runtime origins), repeated upserts, reversed insertion order, filters, caps, cycles, and persistence/reload. Five focused cases fail before the fix; all ten pass afterward. Full suite: 235 passed, 5 skipped.

The contract is also documented in docs/STABLE_API.md. The fix is submitted for review in #15; this issue will close when that PR is merged.