Crate graphalgs

graphalgs is a graph algorithms library based on the Rust petgraph crate.

Examples

use graphalgs::shortest_path::floyd_warshall;
use graphalgs::metrics::{ weighted_radius, weighted_diameter };
use petgraph::Graph;

let inf = f32::INFINITY;

// Create a graph with `f32` edge weights.
let graph = Graph::<(), f32>::from_edges(&[
    (0, 1, 2.0), (1, 2, 10.0), (1, 3, -5.0),
    (3, 2, 2.0), (2, 3, 20.0),
]);

// Calculate the distance matrix using the Floyd-Warshall algorithm.
assert_eq!(
    floyd_warshall(&graph, |edge| *edge.weight()),
    Ok(vec![vec![0.0, 2.0, -1.0, -3.0],
            vec![inf, 0.0, -3.0, -5.0],
            vec![inf, inf,  0.0, 20.0],
            vec![inf, inf,  2.0,  0.0]])
);

// Calculate the radius and diameter of this graph,
// taking into account the weights of the edges.
assert_eq!(weighted_radius(&graph, |edge| *edge.weight()), Some(2.0));
assert_eq!(weighted_diameter(&graph, |edge| *edge.weight()), Some(inf));

Re-exports

• pub extern crate nalgebra;
• pub extern crate petgraph;

Modules

• adj_matrix
  Graph adjacency matrices based on the nalgebra crate.
• connect
  Algorithms related to graph connectivity.
• elementary_circuits
  Algorithms for finding elementary circuits.
• generate
  Graph generators.
• metrics
  Basic graph characteristics based on the concept of distance between vertices.
• mst
  Minimum spanning tree (MST) algorithms.
• shortest_path
  Shortest path algorithms.
• spec
  Special algorithms that are difficult to categorize.
• tournament
  Algorithms that simplify work with such type of graphs as a tournament.
• traits
  Some useful traits missing in petgraph.