Struct graph::Graph

pub struct Graph<I, N, E, Ty, Ix = DefaultIx> {
    pub inner: PGraph<N, E, Ty, Ix>,
    pub repr: PGraph<Node, (), Ty, Ix>,
    pub nodes: HashMap<Ascii<I>, NodeIndex<Ix>>,
    pub repr_nodes: HashMap<Ascii<I>, NodeIndex<Ix>>,
}

The library’s principal Graph structure.

The struct is an abstract layer built on top of the petgraph::Graph<N, E, Ty, Ix> implementation to support named nodes using I identifiers

• I is the type used for identifying the nodes, because of its purpose only values that implement Copy are allowed like &'static str or {u8, i8, …}. If the identifier is a number it is better to just use petgraph::Graph since its default behaviour is to work identifying nodes with numbers, these numbers are named indexes and don’t add any overhead like this more high-level API which uses a HashMap.
• N is the type used to store values within the graph’s nodes
• E is the type used to store values within the graph’s edges
• Ty is the Graph connection type. petgraph::Directed by default
• Ix is the number type value used as indexer for Edges and Nodes.

Fields

inner: PGraph<N, E, Ty, Ix>

The inner petgraph::Graph<N, E, Ty, Ix>

repr: PGraph<Node, (), Ty, Ix>

nodes: HashMap<Ascii<I>, NodeIndex<Ix>>

The map of the I node-name to the NodeIndex<Ix>

repr_nodes: HashMap<Ascii<I>, NodeIndex<Ix>>

Implementations

impl<I, N, E, Ty, Ix> Graph<I, N, E, Ty, Ix>where N: Coords, Ty: EdgeType, Ix: IndexType,

Implementation block for distance methods for Graphs where its type N has the Coords trait. The trait Coords is necessary to extract the node coordinates from any given generic N type.

pub fn get_haversine_table_6371( &self, to: NodeIndex<Ix> ) -> HashMap<NodeIndex<Ix>, f32>

Get the distance to all nodes from a given node idx with the Haversine formula using the Earth radius as 6371 km

pub fn get_haversine_6371(&self, from: NodeIndex<Ix>, to: NodeIndex<Ix>) -> f32

Get the distance between two nodes with the Haversine formula using the Earth radius as 6371 km

pub fn get_haversine( &self, from: NodeIndex<Ix>, to: NodeIndex<Ix>, r: f32 ) -> f32

Haversine distance between two nodes using a given radius r as the Earth radius

Formula from https://en.wikipedia.org/wiki/Haversine_formula#Formulation

pub fn get_haversine_table( &self, to: NodeIndex<Ix>, r: f32 ) -> HashMap<NodeIndex<Ix>, f32>

Get the distance to all nodes in the graph using the Haversine formula.

The returned HashMap has the node index as key and the distance as value.

impl<I, N, E, Ty, Ix> Graph<I, N, E, Ty, Ix>where Ty: EdgeType, Ix: IndexType,

pub fn new() -> Self

Create a new empty instance of graph::Graph

pub fn with_capacity(nodes: usize, edges: usize) -> Self

Create a new graph::Graph with a fixed initial size. Since we use the macro graph::count to construct the graph we do call this constructor to save a couple calls to the allocator

pub fn edge_between_unchecked( &self, source: NodeIndex<Ix>, target: NodeIndex<Ix> ) -> EdgeIndex<Ix>

Get the EdgeIndex<Ix> of the edge between two nodes in any direction.

Panics if there is no edge between the nodes.

pub fn edge_between( &self, source: NodeIndex<Ix>, target: NodeIndex<Ix> ) -> Option<EdgeIndex<Ix>>

Gets the edge between two nodes in any direction.

If there is more than one edge only the first one is taken. Return None if there is no edge connecting two nodes.

pub fn node_count(&self) -> usize

Returns the number of nodes in the graph.

pub fn edge_count(&self) -> usize

Returns the number of edges in the graph.

pub fn visit_map(&self) -> FixedBitSet

Create a bit set for registering which nodes have been visited.

impl<I, N, E, Ty, Ix> Graph<I, N, E, Ty, Ix>where I: Copy + Hash + Eq + Debug + Display, Ty: EdgeType, Ix: IndexType, Ascii<I>: Copy + Hash + Eq, NodeIndex: From<NodeIndex<Ix>>, EdgeIndex: From<EdgeIndex<Ix>>,

pub fn index_name(&self, value: NodeIndex<Ix>) -> Option<I>

Get the high-level node name from the low-level node index. E.g. NodeIndex(0) -> “Arad”

pub fn name_index(&self, ident: I) -> Option<NodeIndex<Ix>>

Get the low-level node index from the high-level node name. E.g. “Arad” -> NodeIndex(0)

pub fn next(&mut self, from: I, to: I, edge: E) -> Result<(), String>where I: Debug,

Connect two nodes by their high-level names. E.g. “Arad” -> “Neamt”

The method calls the necessary low-level methods to connect both node indexes within the inner graph.

Adds values to the inner graph’s Vec<Edge<E, Ix>> to represent neighbors between nodes and the bound E value.

pub fn unchecked_next(&mut self, from: I, to: I, edge: E)where I: Debug,

Connect two nodes by their high-level names. E.g. “Arad” -> “Neamt”

Panics if any of the nodes doesn’t exist

pub fn register(&mut self, ident: I, node: N) -> Result<(), String>where I: Debug,

Register a node with a given name and stored N value

The method calls the necessary low-level methods to connect both node indexes within the inner graph.

Adds values to the inner graph’s Vec<Node<N, Ix>> to represent neighbors between nodes and the bound N value

pub fn unchecked_register(&mut self, ident: I, node: N)where I: Debug,

Register a node with a given name and stored N value

Panics if the node already exists

pub fn done_register(&mut self)where N: Coords,

Normalize coordinates of the repr graph so that they are centered

pub fn journey( &self, start: I, goal: Option<I> ) -> Result<(NodeIndex<Ix>, Option<NodeIndex<Ix>>)>

Translates start and end node names to node indexes.

Returns an error if any of the two node identifiers is missing in the graph. (does not exist)

pub fn perform_search( &self, machine: impl Walker<Ix> ) -> Result<Step<f32, Ix>, WalkerState<Ix>>

Pergorm any shearch stratey easily

This is just a loop wrapped on any search strategy, that is any type that implements the Walker<T> trait.

The loop breaks either when a solution is found or when there are no more edges to explore.

Trait Implementations

impl<I, N, E, Ty, Ix> Default for Graph<I, N, E, Ty, Ix>where Ix: IndexType, Ty: EdgeType,

fn default() -> Self

Returns the “default value” for a type.