Struct SeqGraph

pub struct SeqGraph<NodeId: U16orU32 = u16> {
    pub nodes: Nodes<NodeId>,
    pub edges: HashMap<(NodeId, NodeId), BitVec>,
}

Fields

nodes: Nodes<NodeId>

edges: HashMap<(NodeId, NodeId), BitVec>

Implementations

impl<NodeId: U16orU32> SeqGraph<NodeId>

pub fn builder(nodes_len: usize) -> SeqGraphBuilder<NodeId>

Create a new SeqGraphBuilder with the given number of nodes.

Default NodeId is u16, which can hold up to 65536 nodes. If you need more nodes, you can specify u32 as the NodeId type, like SeqGraph::<u32>::builder(100_000)

pub fn into_builder(self) -> SeqGraphBuilder<NodeId>

Converts this graph into a builder.

This is useful if you want to update the graph, like resizing nodes or adding/removing edges.

Then you can build the graph again.

pub fn neighbor_to(&self, curr: NodeId, dest: NodeId) -> Option<NodeId>

Given a current node and a destination node, return the first neighboring node that is the shortest path to the destination node.

This operation is very fast as all paths for all nodes are precomputed.

None is returned when:

• curr and dest are the same node
• curr has no path to dest

Note: In case there are multiple neighboring nodes that lead to the destination node, the first one found will be returned. The same node will be returned for the same input. However, the order of the nodes is not guaranteed.

You can use neighbor_to_with to filter matching neighbors, or neighbors_to to get all neighboring nodes.

pub fn neighbor_to_with( &self, curr: NodeId, dest: NodeId, f: impl Fn(NodeId) -> bool, ) -> Option<NodeId>

Given a current node and a destination node, and a filter function, return the neighboring node that is the shortest path to the destination node.

Same as self.neighbors_to(curr, dest).find(f)

This may be useful if you want some custom behavior when choosing the next node.

Ex) In a game, you might want to randomize which path to take when there are multiple shortest paths.

None is returned when:

• curr and dest are the same node
• curr has no path to dest
• The filter function returns false for all neighboring nodes

pub fn neighbors_to( &self, curr: NodeId, dest: NodeId, ) -> NeighborsToIter<'_, NodeId>

Given a current node and a destination node, return all neighboring nodes that are shortest paths to the destination node.

The nodes will be returned in the same order for the same inputs. However, the ordering of the nodes is not guaranteed.

pub fn path_to(&self, curr: NodeId, dest: NodeId) -> PathIter<'_, NodeId>

Given a current node and a destination node, return a path from the current node to the destination node.

The path is a list of node IDs, starting with current node and ending at the destination node.

This is same as calling .neighbor_to repeatedly until the destination node is reached.

If there is no path, the list will be empty.

pub fn path_exists(&self, curr: NodeId, dest: NodeId) -> bool

Check if there is a path from the current node to the destination node.

pub fn neighbors(&self, node: NodeId) -> &[NodeId]

Return a list of all neighboring nodes of the given node.

pub fn nodes_len(&self) -> usize

Return the number of nodes in this graph.

pub fn edges_len(&self) -> usize

Return the number of edges in this graph.

Trait Implementations

impl<NodeId: Clone + U16orU32> Clone for SeqGraph<NodeId>

fn clone(&self) -> SeqGraph<NodeId>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<NodeId: Debug + U16orU32> Debug for SeqGraph<NodeId>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.