Struct PathGraph 

pub struct PathGraph { /* private fields */ }

A multigraph: token IDs are nodes, liquidity pools are edges.

Stored as a compact adjacency list (Vec<Vec<CompactEdge>>) indexed by remapped contiguous token indices. External token IDs (u64) are mapped to compact indices (u32) via token_index, so the hot DFS loop does direct array indexing instead of hashing. Parallel edges (multiple pools connecting the same token pair) are naturally supported and preserve insertion order for deterministic traversal.

Pools are also remapped to compact indices; the pools table maps each compact pool index back to its (pool_id, PoolKind) for yielding, and the visited set is an O(1) Vec<bool> indexed by pool index.

Implementations

impl PathGraph

pub fn from_edges(edges: Vec<(u64, u64, u64, PoolKind)>) -> Self

Build from a flat list of (token0, token1, pool_id, pool_kind) edges.

Each edge is added in both directions (the graph is undirected, like the networkx.MultiGraph it replaces). Edge insertion order within each node’s adjacency list is preserved for deterministic traversal. External token IDs are remapped to compact contiguous indices.

Panics

Panics if the number of distinct pools or tokens exceeds u32::MAX (compact index overflow). This is an architectural bound of the compact-index representation and unreachable in practice.

pub fn contains_node(&self, node: u64) -> bool

Returns true if the node exists in the graph.

pub fn node_count(&self) -> usize

The number of nodes (tokens) in the graph.

pub fn degree(&self, token: u64) -> Option<usize>

The number of pool edges incident to a token (its degree).

pub fn prune_dead_ends(&mut self)

Remove nodes with degree ≤ 1, repeating until no such nodes remain.

This mirrors the Python _prepare_graph dead-end pruning loop: while tokens_to_prune := tuple(t for t, d in graph.degree() if d <= 1): graph.remove_nodes_from(tokens_to_prune)

Pruning a node removes all its incident edges, which may reduce other nodes’ degrees below 2 — hence the iterative fixpoint. Removed nodes are dropped from token_index (so contains_node returns false) and their adjacencies are cleared. Their compact indices are not recycled (would require reindexing), but this only wastes a slot — it never affects correctness or the hot DFS path.

Panics

Panics if the number of nodes exceeds u32::MAX when mapping a compact index (architectural bound of the index type; unreachable in practice).

pub fn compute_node_valid_depths( &self, pool_type_per_depth: &[Option<Vec<PoolKind>>], ) -> Vec<Vec<bool>>

Precompute valid depth positions per node, for lookahead pruning.

For each node, determine which depth positions its edges satisfy. A node can appear at depth d if it has at least one incident edge whose pool_kind is in the allowed set at depth d (or allowed[d] is None, meaning all kinds are allowed).

Returns a Vec indexed by compact token index, where entry i is a Vec<bool> whose index d is true if token i can participate at depth d.

impl PathGraph

pub fn find_paths_iter<'a>( &'a self, start: u64, end: u64, min_depth: usize, max_depth: Option<usize>, include_reverse: bool, pool_type_per_depth: Option<&'a [Option<Vec<PoolKind>>]>, node_valid_depths: Option<&'a [Vec<bool>]>, ) -> PathFinder<'a>

Create a lazy iterator over all valid paths from start back to end.

This is a stateful, resumable version of the DFS. The iterator yields one path at a time, avoiding the memory cost of collecting all results into a Vec. Use this when the graph may produce a large number of paths.

pub fn find_paths( &self, start: u64, end: u64, min_depth: usize, max_depth: Option<usize>, include_reverse: bool, pool_type_per_depth: Option<&[Option<Vec<PoolKind>>]>, node_valid_depths: Option<&[Vec<bool>]>, ) -> Vec<Vec<EdgeKey>>

Depth-first search for all valid paths from start back to end.

This is an eager version that collects all results. For large graphs that may produce millions of paths, use PathGraph::find_paths_iter instead to avoid excessive memory usage.

Arguments

• start — The token ID where the search begins.
• end — The token ID the path must return to.
• min_depth — Minimum number of hops in a completed path.
• max_depth — Maximum number of hops, or None for no limit.
• include_reverse — If true, yield each found path again reversed.
• pool_type_per_depth — Optional per-depth allowed pool kinds. A None entry allows all kinds at that depth. Implicitly caps max depth at its length.
• node_valid_depths — Optional precomputed valid-depth sets (from compute_node_valid_depths) for lookahead pruning.

Returns

A Vec of paths, each a Vec of (pool_id, PoolKind) hops.