mapgraph

A powerful library for directed adjacency list graphs.

Graph is a complex data structure where relations between nodes may often be cyclic which doesn't go well with the Rust's type system. A typical approach to this is to refer to nodes and edges in a graph using node and edge indices (sometimes called IDs or keys) which are mapped to the actual nodes, edges and their weights instead of using references or pointers. Since we're mapping indices anyway why not make the maps we use generic and allow custom indices?

mapgraph provides the generic Graph type that is based on two maps: one for nodes and one for edges. By using the rich system of traits from the map submodule the Graph type may borrow some capabilities of the maps it's based on. For example, using a HashMap as a node map for a Graph makes it accept external indices for nodes, effectively making the graph an index for its own nodes.

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.