mapgraph

A generic implementation of a directed graph using an adjacency list representation that can also be used as an arbitrary map.

Typically, graphs aren't used as maps which makes fast map data structures that produce their keys internally a good fit. That is how the Graph type from the petgraph crate works: it uses vectors to store nodes and edges and indices in these vectors to refer to them. This approach is really efficient since vector accesses are really fast, but I've found it is sometimes not flexible enough.

mapgraph extends this approach and replaces the vectors with arbitrary maps. By choosing maps you can customize some aspects of how exactly the Graph type behaves. For example, using a SlotMap as either a node or an edge map gives you stable versioned keys produced by the Graph internally. Using a HashMap, on the other hand, gives you arbitrary hashable keys you provide yourself.

use mapgraph::aliases::{SlotMapGraph, HashSlotMapGraph};

// Using a graph with a SlotMap backing its nodes. The node's index is produced internally.
let mut first_graph = SlotMapGraph::<String, ()>::default();
let node_index = first_graph.add_node("foo".to_string());
assert_eq!(first_graph.node_weight(node_index).unwrap(), "foo");

// Using a graph with a HashMap backing its nodes. The node's index is supplied externally.
let mut second_graph = HashSlotMapGraph::<&str, (), &str>::default();
second_graph.try_add_node_at_index("foo", "bar")?;
assert_eq!(second_graph.node_weight("foo").unwrap(), &"bar");

See the crate's documentation for more info.

License

Licensed under either of

• Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

Contribution

Contributions are welcome and should be submitted as merge requests to this repository.

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.