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 (per-node cursor fill over the edge list = insertion order). External token IDs are remapped to compact contiguous indices.

Two passes over the edge list into a flat CSR array: no per-node Vec allocations, no reallocation churn (~1.5M heap operations on a 742k-edge graph, down from ~750k edge pushes into growing per-node vectors plus map-insert adjacency growth).

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.

Mirrors Python _prepare_graph’s iterative dead-end pruning: pruning a node may drop another node’s live degree below 2, so peeling continues to a fixpoint. Nodes on cycles always retain degree ≥ 2, so the surviving subgraph (the 2-core) is identical regardless of peel order.

Complexity: O(V + E) — a degree-array work queue visits each edge a constant number of times, then one ordered CSR rebuild pass (preserving edge insertion order, so DFS enumeration order is unchanged).

Panics

Panics if the number of surviving edges exceeds u32::MAX (architectural bound of the CSR offset 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.

Trait Implementations

impl Clone for PathGraph

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.