Struct SimpleGraph 

pub struct SimpleGraph<W> { /* private fields */ }

A simple and undirected graph.

A simple graph assumes that the node indexing starts from 0 and is not equipped with a hash map for a mapping from external complex objects to internal graph indices. As a result, SimpleGraph doesn’t have no runtime overhead for such object storage and mapping.

Examples

The following example shows how to construct a graph and find the shortest path between node 1 and 5. The data is taken from the illustration in Wikipedia’s page for Dijkstra’s algorithm.

Here, the numbering is adjusted so that the node indexing starts from 0.

use pheap::graph::SimpleGraph;

let mut g = SimpleGraph::<u32>::with_capacity(6);

g.add_weighted_edges(0, 1, 7);
g.add_weighted_edges(0, 2, 9);
g.add_weighted_edges(0, 5, 14);
g.add_weighted_edges(1, 2, 10);
g.add_weighted_edges(1, 3, 15);
g.add_weighted_edges(2, 5, 2);
g.add_weighted_edges(2, 3, 11);
g.add_weighted_edges(3, 4, 6);
g.add_weighted_edges(4, 5, 9);

// Finds an SSSP from 0 to 4.
let mut sp = g.sssp_dijkstra(0, &[4]);
assert_eq!(1, sp.len());

let sp = sp.pop().unwrap();
assert_eq!(20, sp.dist());
assert_eq!(&[0, 2, 5, 4], sp.path().as_slice());

// Adds a disconnected component to the graph.
g.add_weighted_edges(6, 7, 2);
g.add_weighted_edges(6, 8, 3);

// Finds an SSSP starting from 0. The result can be used for later query.
let lsp = g.sssp_dijkstra_lazy(0);
let lsp = g.sssp_dijkstra_lazy(0);
let sp = lsp.get(7);
assert_eq!(false, sp.is_feasible());

let sp = lsp.get(4);
assert_eq!(true, sp.is_feasible());
assert_eq!(20, sp.dist());
assert_eq!(&[0, 2, 5, 4], sp.path().as_slice());

Implementations

impl<W> SimpleGraph<W>

pub fn new() -> Self

Creates an empty graph.

pub fn with_capacity(n_nodes: usize) -> Self

Creates an empty graph with the given capacitiy of nodes.

pub fn n_nodes(&self) -> usize

Returns the number of nodes in the graph.

pub fn n_edges(&self) -> usize

Returns the number of edges in the graph.

pub fn add_weighted_edges(&mut self, node1: usize, node2: usize, weight: W)

where W: Clone + Copy,

Adds a weighted edge to the graph.

If the edge already exists in the graph, the weight will be updated.

pub fn sssp_dijkstra(&self, src: usize, dest: &[usize]) -> Vec<ShortestPath<W>>

where W: Bounded + Num + Zero + PartialOrd + Copy,

Finds the shortest paths from a source node to destination nodes.

If you want to keep the result for later usage and/or want to save memory, consider using the lazy version SimpleGraph::sssp_dijkstra_lazy, which returns the intermediate result from Dijkstra’s algorithm.

pub fn sssp_dijkstra_lazy(&self, src: usize) -> LazyShortestPaths<W>

where W: Bounded + Num + Zero + PartialOrd + Copy,

Finds the shortest paths from a source node to all nodes and returns the intermediate result for later usage.

pub fn write_edgelist<P>(&self, filepath: P) -> Result<()>

where P: AsRef<Path>, W: Display,

Write graph as a list of edges.

Each line contains one edge, following networkx’s format: index 1 index 2 {'weight': {}}.

Trait Implementations

impl<W: Debug> Debug for SimpleGraph<W>

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

Formats the value using the given formatter.

impl<W: Default> Default for SimpleGraph<W>

fn default() -> SimpleGraph<W>

Returns the “default value” for a type.