3 unstable releases
0.3.1 | Feb 14, 2023 |
---|---|
0.3.0 | Feb 9, 2023 |
0.2.0 | Feb 9, 2023 |
0.1.0 |
|
#344 in Data structures
120KB
2.5K
SLoC
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.
Dependencies
~265–465KB