15 releases (9 breaking)
0.12.0 | Oct 1, 2024 |
---|---|
0.10.1 | Mar 26, 2024 |
0.6.1 | Dec 29, 2023 |
0.4.1 | Sep 4, 2023 |
0.3.1 | Feb 14, 2023 |
#336 in Data structures
190KB
3.5K
SLoC
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.
Dependencies
~0.3–0.9MB
~16K SLoC