Struct TopologyGraph 

pub struct TopologyGraph<D> { /* private fields */ }

A TokenGraph with a lookup from a token pair to its edge.

Derefs to the graph, so the usual petgraph reads work on it directly.

Implementations

impl<D> TopologyGraph<D>

pub fn pools_between(&self, from: NodeIndex, to: NodeIndex) -> &[EdgeData<D>]

The pools trading from for to, empty if the pair is not connected.

pub fn get_token_ix(&self, token: &Address) -> Option<NodeIndex>

The node holding token, or None if the market has no such token.

pub fn paths_between( &self, from: &Address, to: &Address, filter: &GraphQueryFilter, ) -> Result<Vec<TokenPath>, GraphError>

Every route between two tokens, as token sequences.

See TopologyGraph::paths_between_ix, which this resolves the addresses for.

Errors

GraphError::TokenNotFound naming whichever of the two the market does not hold.

pub fn paths_between_ix( &self, from: NodeIndex, to: NodeIndex, filter: &GraphQueryFilter, ) -> Vec<TokenPath>

Every token path from from to to within the filter’s hop bounds.

Empty when there is no route. Check TopologyGraph::expand_path for expanded pool paths.

Routes come back shortest first. Within a length they are in no particular order.

pub fn expand_path( &self, token_path: &[NodeIndex], max_paths: Option<usize>, ) -> Vec<Path<'_, D>>

Writes out one route per combination of pools along token_path.

A token sequence stands for as many routes as the product of the pools on each of its legs. They are enumerated by counting: the rightmost leg advances first, and carries into the leg to its left when it wraps.

That product is unbounded — four legs of twenty pools is 160,000 routes — so max_paths caps how many are written. The ones past the cap are dropped in counting order, which no ranking has seen yet, so a cap trades routes the caller might have wanted for a bound on what one sequence can allocate. None writes them all.

Methods from Deref<Target = TokenGraph<D>>

pub fn capacity(&self) -> (usize, usize)

Return the current node and edge capacity of the graph.

pub fn node_count(&self) -> usize

Return the number of nodes (vertices) in the graph.

Computes in O(1) time.

pub fn edge_count(&self) -> usize

Return the number of edges in the graph.

Computes in O(1) time.

pub fn is_directed(&self) -> bool

Whether the graph has directed edges or not.

pub fn contains_node(&self, a: NodeIndex<Ix>) -> bool

pub fn node_weight(&self, a: NodeIndex<Ix>) -> Option<&N>

Access the weight for node a.

Also available with indexing syntax: &graph[a].

pub fn node_weights(&self) -> impl Iterator<Item = &N>

Return an iterator yielding immutable access to all node weights.

The order in which weights are yielded matches the order of their node indices.

pub fn node_indices(&self) -> NodeIndices<'_, N, Ix>

Return an iterator over the node indices of the graph

pub fn edge_weight(&self, e: EdgeIndex<Ix>) -> Option<&E>

Access the weight for edge e.

Also available with indexing syntax: &graph[e].

pub fn edge_weights(&self) -> impl Iterator<Item = &E>

Return an iterator yielding immutable access to all edge weights.

The order in which weights are yielded matches the order of their edge indices.

pub fn edge_endpoints( &self, e: EdgeIndex<Ix>, ) -> Option<(NodeIndex<Ix>, NodeIndex<Ix>)>

Access the source and target nodes for e.

pub fn edge_indices(&self) -> EdgeIndices<'_, E, Ix>

Return an iterator over the edge indices of the graph

pub fn edges_connecting( &self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, ) -> EdgesConnecting<'_, E, Ty, Ix>

Return an iterator over all the edges connecting a and b.

• Directed: Outgoing edges from a.
• Undirected: All edges connected to a.

Iterator element type is EdgeReference<E, Ix>.

pub fn contains_edge(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool

Lookup if there is an edge from a to b.

Computes in O(e’) time, where e’ is the number of edges connected to a (and b, if the graph edges are undirected).

pub fn find_edge( &self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, ) -> Option<EdgeIndex<Ix>>

Lookup an edge from a to b.

Computes in O(e’) time, where e’ is the number of edges connected to a (and b, if the graph edges are undirected).

pub fn find_edge_undirected( &self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, ) -> Option<(EdgeIndex<Ix>, Direction)>

Lookup an edge between a and b, in either direction.

If the graph is undirected, then this is equivalent to .find_edge().

Return the edge index and its directionality, with Outgoing meaning from a to b and Incoming the reverse, or None if the edge does not exist.

pub fn neighbors(&self, a: NodeIndex<Ix>) -> Neighbors<'_, E, Ix>

Return an iterator of all nodes with an edge starting from a.

• Directed: Outgoing edges from a.
• Undirected: All edges connected to a.

Produces an empty iterator if the node doesn’t exist.
Iterator element type is NodeIndex<Ix>.

Use .neighbors(a).detach() to get a neighbor walker that does not borrow from the graph.

pub fn neighbors_directed( &self, a: NodeIndex<Ix>, dir: Direction, ) -> Neighbors<'_, E, Ix>

Return an iterator of all neighbors that have an edge between them and a, in the specified direction. If the graph’s edges are undirected, this is equivalent to .neighbors(a).

• Directed, Outgoing: All edges from a.
• Directed, Incoming: All edges to a.
• Undirected: All edges connected to a.

Produces an empty iterator if the node doesn’t exist.
Iterator element type is NodeIndex<Ix>.

Use .neighbors_directed(a, dir).detach() to get a neighbor walker that does not borrow from the graph.

pub fn neighbors_undirected(&self, a: NodeIndex<Ix>) -> Neighbors<'_, E, Ix>

Return an iterator of all neighbors that have an edge between them and a, in either direction. If the graph’s edges are undirected, this is equivalent to .neighbors(a).

• Directed and Undirected: All edges connected to a.

Produces an empty iterator if the node doesn’t exist.
Iterator element type is NodeIndex<Ix>.

Use .neighbors_undirected(a).detach() to get a neighbor walker that does not borrow from the graph.

pub fn edges(&self, a: NodeIndex<Ix>) -> Edges<'_, E, Ty, Ix>

Return an iterator of all edges of a.

• Directed: Outgoing edges from a.
• Undirected: All edges connected to a.

Produces an empty iterator if the node doesn’t exist.
Iterator element type is EdgeReference<E, Ix>.

pub fn edges_directed( &self, a: NodeIndex<Ix>, dir: Direction, ) -> Edges<'_, E, Ty, Ix>

Return an iterator of all edges of a, in the specified direction.

• Directed, Outgoing: All edges from a.
• Directed, Incoming: All edges to a.
• Undirected, Outgoing: All edges connected to a, with a being the source of each edge.
• Undirected, Incoming: All edges connected to a, with a being the target of each edge.

Produces an empty iterator if the node a doesn’t exist.
Iterator element type is EdgeReference<E, Ix>.

pub fn externals(&self, dir: Direction) -> Externals<'_, N, Ty, Ix>

Return an iterator over either the nodes without edges to them (Incoming) or from them (Outgoing).

An internal node has both incoming and outgoing edges. The nodes in .externals(Incoming) are the source nodes and .externals(Outgoing) are the sinks of the graph.

For a graph with undirected edges, both the sinks and the sources are just the nodes without edges.

The whole iteration computes in O(|V|) time.

pub fn map<'a, F, G, N2, E2>( &'a self, node_map: F, edge_map: G, ) -> StableGraph<N2, E2, Ty, Ix>

where F: FnMut(NodeIndex<Ix>, &'a N) -> N2, G: FnMut(EdgeIndex<Ix>, &'a E) -> E2,

Create a new StableGraph by mapping node and edge weights to new values.

The resulting graph has the same structure and the same graph indices as self.

pub fn filter_map<'a, F, G, N2, E2>( &'a self, node_map: F, edge_map: G, ) -> StableGraph<N2, E2, Ty, Ix>

where F: FnMut(NodeIndex<Ix>, &'a N) -> Option<N2>, G: FnMut(EdgeIndex<Ix>, &'a E) -> Option<E2>,

Create a new StableGraph by mapping nodes and edges. A node or edge may be mapped to None to exclude it from the resulting graph.

Nodes are mapped first with the node_map closure, then edge_map is called for the edges that have not had any endpoint removed.

The resulting graph has the structure of a subgraph of the original graph. Nodes and edges that are not removed maintain their old node or edge indices.

Trait Implementations

impl<D> Default for TopologyGraph<D>

fn default() -> Self

Returns the “default value” for a type.

impl<D> Deref for TopologyGraph<D>

type Target = StableGraph<Bytes, PairEdge<D>>

The resulting type after dereferencing.

fn deref(&self) -> &Self::Target

Dereferences the value.

impl<D: Clone + Send + Sync> GraphManager<TopologyGraph<D>> for TopologyGraphManager<D>

fn initialize_graph( &mut self, component_topology: &FxHashMap<ComponentId, Vec<Address>>, )

Initializes the graph from the market topology.

fn graph(&self) -> &TopologyGraph<D>

Returns a reference to the managed graph.