Merge pull request #237 from manuelmauro/master
Implement an edges_connecting(a, b) iterator for Graph
diff --git a/.travis.yml b/.travis.yml
index 720573c..f32ebc8 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -2,7 +2,7 @@
sudo: false
matrix:
include:
- - rust: 1.25.0
+ - rust: 1.37.0
env:
- ALL=' '
- rust: stable
diff --git a/Cargo.toml b/Cargo.toml
index ca207ec..df77606 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -10,11 +10,13 @@
description = "Graph data structure library. Provides graph types and graph algorithms."
documentation = "https://docs.rs/petgraph/"
-repository = "https://github.com/bluss/petgraph"
+repository = "https://github.com/petgraph/petgraph"
keywords = ["data-structure", "graph", "unionfind", "graph-algorithms"]
categories = ["data-structures"]
+edition = "2018"
+
[lib]
name = "petgraph"
@@ -26,8 +28,8 @@
debug = true
[dependencies]
-fixedbitset = { version = "0.1.4" }
-quickcheck = { optional = true, version = "0.7.1", default-features = false }
+fixedbitset = { version = "0.2.0", default-features = false }
+quickcheck = { optional = true, version = "0.8", default-features = false }
indexmap = { version = "1.0.2", optional = true }
serde = { version = "1.0", optional = true }
serde_derive = { version = "1.0", optional = true }
@@ -39,17 +41,18 @@
itertools = { version = "0.8", default-features = false }
[features]
-default = ["graphmap", "stable_graph"]
+default = ["graphmap", "stable_graph", "matrix_graph"]
graphmap = ["indexmap"]
serde-1 = ["serde", "serde_derive"]
stable_graph = []
+matrix_graph = []
# For unstable features
generate = []
unstable = ["generate"]
# feature flags for testing use only
-all = ["unstable", "quickcheck", "stable_graph", "graphmap"]
+all = ["unstable", "quickcheck", "matrix_graph", "stable_graph", "graphmap"]
[workspace]
members = ["serialization-tests"]
diff --git a/README.rst b/README.rst
index 0243d46..dff5633 100644
--- a/README.rst
+++ b/README.rst
@@ -2,7 +2,7 @@
petgraph
========
-Graph data structure library. Requires Rust 1.25 or later.
+Graph data structure library. Known to support Rust 1.37 and later.
Please read the `API documentation here`__
@@ -10,8 +10,8 @@
|build_status|_ |crates|_
-.. |build_status| image:: https://travis-ci.org/bluss/petgraph.svg?branch=master
-.. _build_status: https://travis-ci.org/bluss/petgraph
+.. |build_status| image:: https://travis-ci.org/petgraph/petgraph.svg?branch=master
+.. _build_status: https://travis-ci.org/petgraph/petgraph
.. |crates| image:: http://meritbadge.herokuapp.com/petgraph
.. _crates: https://crates.io/crates/petgraph
@@ -20,6 +20,7 @@
- ``graphmap`` (default) enable ``GraphMap``.
- ``stable_graph`` (default) enable ``StableGraph``.
+- ``matrix_graph`` (default) enable ``MatrixGraph``.
- ``serde-1`` (optional) enable serialization for ``Graph, StableGraph`` using
serde 1.0. Requires Rust version as required by serde.
diff --git a/benches/common/factories.rs b/benches/common/factories.rs
new file mode 100644
index 0000000..f0017b7
--- /dev/null
+++ b/benches/common/factories.rs
@@ -0,0 +1,251 @@
+use std::marker::PhantomData;
+
+use petgraph::prelude::*;
+use petgraph::visit::NodeIndexable;
+use petgraph::data::Build;
+
+use petgraph::EdgeType;
+
+/// Petersen A and B are isomorphic
+///
+/// http://www.dharwadker.org/tevet/isomorphism/
+const PETERSEN_A: &'static str = "
+ 0 1 0 0 1 0 1 0 0 0
+ 1 0 1 0 0 0 0 1 0 0
+ 0 1 0 1 0 0 0 0 1 0
+ 0 0 1 0 1 0 0 0 0 1
+ 1 0 0 1 0 1 0 0 0 0
+ 0 0 0 0 1 0 0 1 1 0
+ 1 0 0 0 0 0 0 0 1 1
+ 0 1 0 0 0 1 0 0 0 1
+ 0 0 1 0 0 1 1 0 0 0
+ 0 0 0 1 0 0 1 1 0 0
+";
+
+const PETERSEN_B: &'static str = "
+ 0 0 0 1 0 1 0 0 0 1
+ 0 0 0 1 1 0 1 0 0 0
+ 0 0 0 0 0 0 1 1 0 1
+ 1 1 0 0 0 0 0 1 0 0
+ 0 1 0 0 0 0 0 0 1 1
+ 1 0 0 0 0 0 1 0 1 0
+ 0 1 1 0 0 1 0 0 0 0
+ 0 0 1 1 0 0 0 0 1 0
+ 0 0 0 0 1 1 0 1 0 0
+ 1 0 1 0 1 0 0 0 0 0
+";
+
+/// An almost full set, isomorphic
+const FULL_A: &'static str = "
+ 1 1 1 1 1 1 1 1 1 1
+ 1 1 1 1 1 1 1 1 1 1
+ 1 1 1 1 1 1 1 1 1 1
+ 1 1 1 1 1 1 1 1 1 1
+ 1 1 1 1 1 1 1 1 1 1
+ 1 1 1 1 1 1 1 1 1 1
+ 1 1 1 1 1 1 1 1 1 1
+ 1 1 1 1 1 1 1 1 1 1
+ 1 1 1 1 0 1 1 1 0 1
+ 1 1 1 1 1 1 1 1 1 1
+";
+
+const FULL_B: &'static str = "
+ 1 1 1 1 1 1 1 1 1 1
+ 1 1 1 1 1 1 1 1 1 1
+ 1 1 0 1 1 1 0 1 1 1
+ 1 1 1 1 1 1 1 1 1 1
+ 1 1 1 1 1 1 1 1 1 1
+ 1 1 1 1 1 1 1 1 1 1
+ 1 1 1 1 1 1 1 1 1 1
+ 1 1 1 1 1 1 1 1 1 1
+ 1 1 1 1 1 1 1 1 1 1
+ 1 1 1 1 1 1 1 1 1 1
+";
+
+/// Praust A and B are not isomorphic
+const PRAUST_A: &'static str = "
+ 0 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
+ 1 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0
+ 1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0
+ 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0
+ 1 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0
+ 0 1 0 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0
+ 0 0 1 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0
+ 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0
+ 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0
+ 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0
+ 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0
+ 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1
+ 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0
+ 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 1 0 0 0
+ 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1
+ 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0
+ 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1
+ 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 1
+ 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1
+ 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0
+";
+
+const PRAUST_B: &'static str = "
+ 0 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
+ 1 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0
+ 1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0
+ 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0
+ 1 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0
+ 0 1 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1
+ 0 0 1 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0
+ 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0
+ 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0
+ 0 1 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0
+ 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0
+ 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0
+ 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1
+ 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 1 0
+ 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 1 0 1
+ 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0 1 0
+ 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 1 1 0
+ 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 1
+ 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0 0 1
+ 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 1 1 0
+";
+
+const BIGGER: &'static str = "
+ 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
+ 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0
+ 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0
+ 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
+ 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
+ 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
+ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
+ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
+ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
+ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
+ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
+ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
+ 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0
+ 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 1 0 0 0
+ 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1
+ 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0
+ 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1
+ 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0 1 1 1 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 1
+ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1
+ 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0
+ 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
+ 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 1 0 1 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0
+ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
+ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
+ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
+ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
+ 0 0 1 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0
+ 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0
+ 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0
+ 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0
+ 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0
+ 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1
+ 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0
+ 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 1 0 0 0
+ 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1
+ 0 1 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0
+ 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1
+ 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 1
+ 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1
+ 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0
+";
+
+/// Parse a text adjacency matrix format into a directed graph
+fn parse_graph<Ty, G>(s: &str) -> G
+ where Ty: EdgeType,
+ G: Default + Build<NodeWeight=(), EdgeWeight=()> + NodeIndexable,
+{
+ let mut g: G = Default::default();
+ let s = s.trim();
+ let lines = s.lines().filter(|l| !l.is_empty());
+ for (row, line) in lines.enumerate() {
+ for (col, word) in line.split(' ')
+ .filter(|s| s.len() > 0)
+ .enumerate()
+ {
+ let has_edge = word.parse::<i32>().unwrap();
+ assert!(has_edge == 0 || has_edge == 1);
+ if has_edge == 0 {
+ continue;
+ }
+ while col >= g.node_count() || row >= g.node_count() {
+ g.add_node(());
+ }
+ let a = g.from_index(row);
+ let b = g.from_index(col);
+ g.update_edge(a, b, ());
+ }
+ }
+ g
+}
+
+pub struct GraphFactory<Ty, G = Graph<(), (), Ty>> {
+ ty: PhantomData<Ty>,
+ g: PhantomData<G>,
+}
+
+impl<Ty, G> GraphFactory<Ty, G>
+ where Ty: EdgeType,
+ G: Default + Build<NodeWeight=(), EdgeWeight=()> + NodeIndexable,
+{
+ fn new() -> Self {
+ GraphFactory {
+ ty: PhantomData,
+ g: PhantomData,
+ }
+ }
+
+ pub fn petersen_a(self) -> G {
+ parse_graph::<Ty, _>(PETERSEN_A)
+ }
+
+ pub fn petersen_b(self) -> G {
+ parse_graph::<Ty, _>(PETERSEN_B)
+ }
+
+ pub fn full_a(self) -> G {
+ parse_graph::<Ty, _>(FULL_A)
+ }
+
+ pub fn full_b(self) -> G {
+ parse_graph::<Ty, _>(FULL_B)
+ }
+
+ pub fn praust_a(self) -> G {
+ parse_graph::<Ty, _>(PRAUST_A)
+ }
+
+ pub fn praust_b(self) -> G {
+ parse_graph::<Ty, _>(PRAUST_B)
+ }
+
+ pub fn bigger(self) -> G {
+ parse_graph::<Ty, _>(BIGGER)
+ }
+}
+
+pub fn graph<Ty: EdgeType>() -> GraphFactory<Ty, Graph<(), (), Ty>> {
+ GraphFactory::new()
+}
+
+pub fn ungraph() -> GraphFactory<Undirected, Graph<(), (), Undirected>> {
+ graph()
+}
+
+pub fn digraph() -> GraphFactory<Directed, Graph<(), (), Directed>> {
+ graph()
+}
+
+pub fn stable_graph<Ty: EdgeType>() -> GraphFactory<Ty, StableGraph<(), (), Ty>> {
+ GraphFactory::new()
+}
+
+pub fn stable_ungraph() -> GraphFactory<Undirected, StableGraph<(), (), Undirected>> {
+ stable_graph()
+}
+
+pub fn stable_digraph() -> GraphFactory<Directed, StableGraph<(), (), Directed>> {
+ stable_graph()
+}
diff --git a/benches/common/mod.rs b/benches/common/mod.rs
new file mode 100644
index 0000000..739c041
--- /dev/null
+++ b/benches/common/mod.rs
@@ -0,0 +1,2 @@
+mod factories;
+pub use factories::*;
diff --git a/benches/iso.rs b/benches/iso.rs
index a142b9e..008de39 100644
--- a/benches/iso.rs
+++ b/benches/iso.rs
@@ -3,222 +3,50 @@
extern crate test;
extern crate petgraph;
-use petgraph::prelude::*;
-use petgraph::{
- EdgeType,
-};
-use petgraph::graph::{
- node_index,
-};
+use test::Bencher;
-/// Petersen A and B are isomorphic
-///
-/// http://www.dharwadker.org/tevet/isomorphism/
-const PETERSEN_A: &'static str = "
- 0 1 0 0 1 0 1 0 0 0
- 1 0 1 0 0 0 0 1 0 0
- 0 1 0 1 0 0 0 0 1 0
- 0 0 1 0 1 0 0 0 0 1
- 1 0 0 1 0 1 0 0 0 0
- 0 0 0 0 1 0 0 1 1 0
- 1 0 0 0 0 0 0 0 1 1
- 0 1 0 0 0 1 0 0 0 1
- 0 0 1 0 0 1 1 0 0 0
- 0 0 0 1 0 0 1 1 0 0
-";
+#[allow(dead_code)]
+mod common;
+use common::*;
-const PETERSEN_B: &'static str = "
- 0 0 0 1 0 1 0 0 0 1
- 0 0 0 1 1 0 1 0 0 0
- 0 0 0 0 0 0 1 1 0 1
- 1 1 0 0 0 0 0 1 0 0
- 0 1 0 0 0 0 0 0 1 1
- 1 0 0 0 0 0 1 0 1 0
- 0 1 1 0 0 1 0 0 0 0
- 0 0 1 1 0 0 0 0 1 0
- 0 0 0 0 1 1 0 1 0 0
- 1 0 1 0 1 0 0 0 0 0
-";
-
-/// An almost full set, isomorphic
-const FULL_A: &'static str = "
- 1 1 1 1 1 1 1 1 1 1
- 1 1 1 1 1 1 1 1 1 1
- 1 1 1 1 1 1 1 1 1 1
- 1 1 1 1 1 1 1 1 1 1
- 1 1 1 1 1 1 1 1 1 1
- 1 1 1 1 1 1 1 1 1 1
- 1 1 1 1 1 1 1 1 1 1
- 1 1 1 1 1 1 1 1 1 1
- 1 1 1 1 0 1 1 1 0 1
- 1 1 1 1 1 1 1 1 1 1
-";
-
-const FULL_B: &'static str = "
- 1 1 1 1 1 1 1 1 1 1
- 1 1 1 1 1 1 1 1 1 1
- 1 1 0 1 1 1 0 1 1 1
- 1 1 1 1 1 1 1 1 1 1
- 1 1 1 1 1 1 1 1 1 1
- 1 1 1 1 1 1 1 1 1 1
- 1 1 1 1 1 1 1 1 1 1
- 1 1 1 1 1 1 1 1 1 1
- 1 1 1 1 1 1 1 1 1 1
- 1 1 1 1 1 1 1 1 1 1
-";
-
-/// Praust A and B are not isomorphic
-const PRAUST_A: &'static str = "
- 0 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
- 1 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0
- 1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0
- 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0
- 1 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0
- 0 1 0 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0
- 0 0 1 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0
- 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0
- 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0
- 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0
- 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0
- 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1
- 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0
- 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 1 0 0 0
- 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1
- 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0
- 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1
- 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 1
- 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1
- 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0
-";
-
-const PRAUST_B: &'static str = "
- 0 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
- 1 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0
- 1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0
- 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0
- 1 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0
- 0 1 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1
- 0 0 1 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0
- 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0
- 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0
- 0 1 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0
- 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0
- 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0
- 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1
- 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 1 0
- 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 1 0 1
- 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0 1 0
- 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 1 1 0
- 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 1
- 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0 0 1
- 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 1 1 0
-";
-
-/// Parse a text adjacency matrix format into a directed graph
-fn parse_graph<Ty: EdgeType>(s: &str) -> Graph<(), (), Ty>
-{
- let mut gr = Graph::with_capacity(0, 0);
- let s = s.trim();
- let lines = s.lines().filter(|l| !l.is_empty());
- for (row, line) in lines.enumerate() {
- for (col, word) in line.split(' ')
- .filter(|s| s.len() > 0)
- .enumerate()
- {
- let has_edge = word.parse::<i32>().unwrap();
- assert!(has_edge == 0 || has_edge == 1);
- if has_edge == 0 {
- continue;
- }
- while col >= gr.node_count() || row >= gr.node_count() {
- gr.add_node(());
- }
- gr.update_edge(node_index(row), node_index(col), ());
- }
- }
- gr
-}
-
-fn str_to_graph(s: &str) -> Graph<(), (), Undirected> {
- parse_graph(s)
-}
-
-fn str_to_digraph(s: &str) -> Graph<(), (), Directed> {
- parse_graph(s)
-}
-
-/*
-fn graph_to_ad_matrix<N, E, Ty: EdgeType>(g: &Graph<N,E,Ty>)
-{
- let n = g.node_count();
- for i in (0..n) {
- for j in (0..n) {
- let ix = NodeIndex::new(i);
- let jx = NodeIndex::new(j);
- let out = match g.find_edge(ix, jx) {
- None => "0",
- Some(_) => "1",
- };
- print!("{} ", out);
- }
- println!("");
- }
-}
-*/
+use petgraph::algo::is_isomorphic;
#[bench]
-fn petersen_iso_bench(bench: &mut test::Bencher)
-{
- let a = str_to_digraph(PETERSEN_A);
- let b = str_to_digraph(PETERSEN_B);
+fn petersen_iso_bench(bench: &mut Bencher) {
+ let a = digraph().petersen_a();
+ let b = digraph().petersen_b();
- bench.iter(|| petgraph::algo::is_isomorphic(&a, &b));
+ bench.iter(|| is_isomorphic(&a, &b));
}
#[bench]
-fn petersen_undir_iso_bench(bench: &mut test::Bencher)
-{
- let a = str_to_graph(PETERSEN_A);
- let b = str_to_graph(PETERSEN_B);
+fn petersen_undir_iso_bench(bench: &mut Bencher) {
+ let a = ungraph().petersen_a();
+ let b = ungraph().petersen_b();
- bench.iter(|| petgraph::algo::is_isomorphic(&a, &b));
+ bench.iter(|| is_isomorphic(&a, &b));
}
#[bench]
-fn full_iso_bench(bench: &mut test::Bencher)
-{
- let a = str_to_graph(FULL_A);
- let b = str_to_graph(FULL_B);
+fn full_iso_bench(bench: &mut Bencher) {
+ let a = ungraph().full_a();
+ let b = ungraph().full_b();
- bench.iter(|| petgraph::algo::is_isomorphic(&a, &b));
+ bench.iter(|| is_isomorphic(&a, &b));
}
#[bench]
-fn praust_dir_no_iso_bench(bench: &mut test::Bencher)
-{
- let a = str_to_digraph(PRAUST_A);
- let b = str_to_digraph(PRAUST_B);
+fn praust_dir_no_iso_bench(bench: &mut Bencher) {
+ let a = digraph().praust_a();
+ let b = digraph().praust_b();
- bench.iter(|| petgraph::algo::is_isomorphic(&a, &b));
+ bench.iter(|| is_isomorphic(&a, &b));
}
#[bench]
-fn praust_undir_no_iso_bench(bench: &mut test::Bencher)
-{
- let a = str_to_graph(PRAUST_A);
- let b = str_to_graph(PRAUST_B);
+fn praust_undir_no_iso_bench(bench: &mut Bencher) {
+ let a = ungraph().praust_a();
+ let b = ungraph().praust_b();
- bench.iter(|| petgraph::algo::is_isomorphic(&a, &b));
-}
-
-#[bench]
-fn bench_praust_mst(bb: &mut test::Bencher)
-{
- let a = str_to_digraph(PRAUST_A);
- let b = str_to_digraph(PRAUST_B);
-
- bb.iter(|| {
- (petgraph::algo::min_spanning_tree(&a),
- petgraph::algo::min_spanning_tree(&b))
- });
+ bench.iter(|| is_isomorphic(&a, &b));
}
diff --git a/benches/matrix_graph.rs b/benches/matrix_graph.rs
new file mode 100644
index 0000000..ef81733
--- /dev/null
+++ b/benches/matrix_graph.rs
@@ -0,0 +1,237 @@
+#![feature(test)]
+
+extern crate petgraph;
+extern crate test;
+
+use test::Bencher;
+
+use petgraph::{EdgeType, Directed, Outgoing, Incoming};
+use petgraph::algo;
+use petgraph::matrix_graph::{MatrixGraph, node_index};
+
+#[bench]
+fn add_100_nodes(b: &mut test::Bencher) {
+ b.iter(|| {
+ let mut g = MatrixGraph::<(), ()>::with_capacity(100);
+
+ for _ in 0..100 {
+ let _ = g.add_node(());
+ }
+ });
+}
+
+#[bench]
+fn add_100_edges_to_self(b: &mut test::Bencher) {
+ let mut g = MatrixGraph::<(), ()>::with_capacity(100);
+ let nodes: Vec<_> = (0..100).map(|_| g.add_node(())).collect();
+ let g = g;
+
+ b.iter(|| {
+ let mut g = g.clone();
+
+ for &node in nodes.iter() {
+ let _ = g.add_edge(node, node, ());
+ }
+ });
+}
+
+#[bench]
+fn add_5_edges_for_each_of_100_nodes(b: &mut test::Bencher) {
+ let mut g = MatrixGraph::<(), ()>::with_capacity(100);
+ let nodes: Vec<_> = (0..100).map(|_| g.add_node(())).collect();
+ let g = g;
+
+ let edges_to_add: Vec<_> = nodes.iter()
+ .enumerate()
+ .map(|(i, &node)| {
+ let edges: Vec<_> = (0..5)
+ .map(|j| (i + j + 1) % nodes.len())
+ .map(|j| (node, nodes[j]))
+ .collect();
+
+ edges
+ })
+ .flat_map(|e| e)
+ .collect();
+
+ b.iter(|| {
+ let mut g = g.clone();
+
+ for &(source, target) in edges_to_add.iter() {
+ let _ = g.add_edge(source, target, ());
+ }
+ });
+}
+
+#[bench]
+fn add_edges_from_root(bench: &mut test::Bencher) {
+ bench.iter(|| {
+ let mut gr = MatrixGraph::new();
+ let a = gr.add_node(());
+
+ for _ in 0..100 {
+ let b = gr.add_node(());
+ gr.add_edge(a, b, ());
+ }
+ });
+}
+
+#[bench]
+fn add_adjacent_edges(bench: &mut test::Bencher) {
+ bench.iter(|| {
+ let mut gr = MatrixGraph::new();
+ let mut prev = None;
+ for _ in 0..100 {
+ let b = gr.add_node(());
+
+ if let Some(a) = prev {
+ gr.add_edge(a, b, ());
+ }
+
+ prev = Some(b);
+ }
+ });
+}
+
+/// An almost full set
+const FULL: &'static str = "
+ 1 1 1 1 1 1 1 1 1 1
+ 1 1 1 1 1 1 1 1 1 1
+ 1 1 1 1 1 1 1 1 1 1
+ 1 1 1 1 1 1 1 1 1 1
+ 1 1 1 1 1 1 1 1 1 1
+ 1 1 1 1 1 1 1 1 1 1
+ 1 1 1 1 1 1 1 1 1 1
+ 1 1 1 1 1 1 1 1 1 1
+ 1 1 1 1 0 1 1 1 0 1
+ 1 1 1 1 1 1 1 1 1 1
+";
+
+const BIGGER: &'static str = "
+ 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
+ 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0
+ 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0
+ 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
+ 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
+ 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
+ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
+ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
+ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
+ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
+ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
+ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
+ 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0
+ 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 1 0 0 0
+ 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1
+ 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0
+ 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1
+ 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0 1 1 1 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 1
+ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1
+ 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0
+ 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
+ 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 1 0 1 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0
+ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
+ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
+ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
+ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
+ 0 0 1 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0
+ 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0
+ 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0
+ 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0
+ 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0
+ 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1
+ 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0
+ 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 1 0 0 0
+ 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1
+ 0 1 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0
+ 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1
+ 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 1
+ 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1
+ 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0
+";
+
+/// Parse a text adjacency matrix format into a directed graph
+fn parse_matrix<Ty: EdgeType>(s: &str) -> MatrixGraph<(), (), Ty> {
+ let mut gr = MatrixGraph::default();
+ let s = s.trim();
+ let lines = s.lines().filter(|l| !l.is_empty());
+ for (row, line) in lines.enumerate() {
+ for (col, word) in line.split(' ')
+ .filter(|s| s.len() > 0)
+ .enumerate()
+ {
+ let has_edge = word.parse::<i32>().unwrap();
+ assert!(has_edge == 0 || has_edge == 1);
+ if has_edge == 0 {
+ continue;
+ }
+ while col >= gr.node_count() || row >= gr.node_count() {
+ gr.add_node(());
+ }
+ gr.add_edge(node_index(row), node_index(col), ());
+ }
+ }
+ gr
+}
+
+#[bench]
+fn full_edges_out(bench: &mut Bencher) {
+ let a = parse_matrix::<Directed>(FULL);
+ bench.iter(|| a.edges_directed(node_index(1), Outgoing).count())
+}
+
+#[bench]
+fn full_edges_in(bench: &mut Bencher) {
+ let a = parse_matrix::<Directed>(FULL);
+ bench.iter(|| a.edges_directed(node_index(1), Incoming).count())
+}
+
+#[bench]
+fn full_neighbors_out(bench: &mut Bencher) {
+ let a = parse_matrix::<Directed>(FULL);
+ bench.iter(|| a.neighbors_directed(node_index(1), Outgoing).count())
+}
+
+#[bench]
+fn full_neighbors_in(bench: &mut Bencher) {
+ let a = parse_matrix::<Directed>(FULL);
+
+ bench.iter(|| a.neighbors_directed(node_index(1), Incoming).count())
+}
+
+#[bench]
+fn full_sccs(bench: &mut Bencher) {
+ let a = parse_matrix::<Directed>(FULL);
+ bench.iter(|| algo::kosaraju_scc(&a));
+}
+
+#[bench]
+fn bigger_edges_out(bench: &mut Bencher) {
+ let a = parse_matrix::<Directed>(BIGGER);
+ bench.iter(|| a.edges_directed(node_index(1), Outgoing).count())
+}
+
+#[bench]
+fn bigger_edges_in(bench: &mut Bencher) {
+ let a = parse_matrix::<Directed>(BIGGER);
+ bench.iter(|| a.edges_directed(node_index(1), Incoming).count())
+}
+
+#[bench]
+fn bigger_neighbors_out(bench: &mut Bencher) {
+ let a = parse_matrix::<Directed>(BIGGER);
+ bench.iter(|| a.neighbors_directed(node_index(1), Outgoing).count())
+}
+
+#[bench]
+fn bigger_neighbors_in(bench: &mut Bencher) {
+ let a = parse_matrix::<Directed>(BIGGER);
+
+ bench.iter(|| a.neighbors_directed(node_index(1), Incoming).count())
+}
+
+#[bench]
+fn bigger_sccs(bench: &mut Bencher) {
+ let a = parse_matrix::<Directed>(BIGGER);
+ bench.iter(|| algo::kosaraju_scc(&a));
+}
diff --git a/benches/stable_graph.rs b/benches/stable_graph.rs
index 9bbda8f..ca4aed8 100644
--- a/benches/stable_graph.rs
+++ b/benches/stable_graph.rs
@@ -6,201 +6,80 @@
use test::Bencher;
use petgraph::prelude::*;
-use petgraph::{EdgeType};
-use petgraph::stable_graph::{
- node_index,
-};
+#[allow(dead_code)]
+mod common;
+use common::*;
-/// An almost full set
-const FULL_A: &'static str = "
- 1 1 1 1 1 1 1 1 1 1
- 1 1 1 1 1 1 1 1 1 1
- 1 1 1 1 1 1 1 1 1 1
- 1 1 1 1 1 1 1 1 1 1
- 1 1 1 1 1 1 1 1 1 1
- 1 1 1 1 1 1 1 1 1 1
- 1 1 1 1 1 1 1 1 1 1
- 1 1 1 1 1 1 1 1 1 1
- 1 1 1 1 0 1 1 1 0 1
- 1 1 1 1 1 1 1 1 1 1
-";
-
-const BIGGER: &'static str = "
- 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
- 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0
- 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0
- 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
- 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
- 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
- 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
- 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
- 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
- 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
- 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
- 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
- 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0
- 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 1 0 0 0
- 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1
- 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0
- 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1
- 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0 1 1 1 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 1
- 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1
- 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0
- 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
- 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 1 0 1 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0
- 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
- 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
- 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
- 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
- 0 0 1 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0
- 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0
- 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0
- 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0
- 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0
- 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1
- 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0
- 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 1 0 0 0
- 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1
- 0 1 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0
- 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1
- 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 1
- 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1
- 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0
-";
+use petgraph::stable_graph::node_index;
#[bench]
-fn full_edges_default(bench: &mut Bencher)
-{
- let a = parse_stable_graph::<Directed>(FULL_A);
-
+fn full_edges_default(bench: &mut Bencher) {
+ let a = stable_digraph().full_a();
bench.iter(|| a.edges(node_index(1)).count())
}
#[bench]
-fn full_edges_out(bench: &mut Bencher)
-{
- let a = parse_stable_graph::<Directed>(FULL_A);
+fn full_edges_out(bench: &mut Bencher) {
+ let a = stable_digraph().full_a();
bench.iter(|| a.edges_directed(node_index(1), Outgoing).count())
}
-#[bench]
-fn full_edges_in(bench: &mut Bencher)
-{
- let a = parse_stable_graph::<Directed>(FULL_A);
+#[bench]
+fn full_edges_in(bench: &mut Bencher) {
+ let a = stable_digraph().full_a();
bench.iter(|| a.edges_directed(node_index(1), Incoming).count())
}
#[bench]
-fn neighbors_default(bench: &mut Bencher)
-{
- let a = parse_stable_graph::<Directed>(FULL_A);
-
+fn neighbors_default(bench: &mut Bencher) {
+ let a = stable_digraph().full_a();
bench.iter(|| a.neighbors(node_index(1)).count())
}
#[bench]
-fn neighbors_out(bench: &mut Bencher)
-{
- let a = parse_stable_graph::<Directed>(FULL_A);
+fn neighbors_out(bench: &mut Bencher) {
+ let a = stable_digraph().full_a();
bench.iter(|| a.neighbors_directed(node_index(1), Outgoing).count())
}
-#[bench]
-fn neighbors_in(bench: &mut Bencher)
-{
- let a = parse_stable_graph::<Directed>(FULL_A);
+#[bench]
+fn neighbors_in(bench: &mut Bencher) {
+ let a = stable_digraph().full_a();
bench.iter(|| a.neighbors_directed(node_index(1), Incoming).count())
}
#[bench]
-fn sccs_stable_graph(bench: &mut Bencher)
-{
- let a = parse_stable_graph::<Directed>(BIGGER);
+fn sccs_stable_graph(bench: &mut Bencher) {
+ let a = stable_digraph().bigger();
bench.iter(|| petgraph::algo::kosaraju_scc(&a));
}
#[bench]
-fn sccs_graph(bench: &mut Bencher)
-{
- let a = parse_graph::<Directed>(BIGGER);
+fn sccs_graph(bench: &mut Bencher) {
+ let a = digraph().bigger();
bench.iter(|| petgraph::algo::kosaraju_scc(&a));
}
-/// Parse a text adjacency matrix format into a directed graph
-fn parse_stable_graph<Ty: EdgeType>(s: &str) -> StableGraph<(), (), Ty>
-{
- let mut gr = StableGraph::default();
- let s = s.trim();
- let lines = s.lines().filter(|l| !l.is_empty());
- for (row, line) in lines.enumerate() {
- for (col, word) in line.split(' ')
- .filter(|s| s.len() > 0)
- .enumerate()
- {
- let has_edge = word.parse::<i32>().unwrap();
- assert!(has_edge == 0 || has_edge == 1);
- if has_edge == 0 {
- continue;
- }
- while col >= gr.node_count() || row >= gr.node_count() {
- gr.add_node(());
- }
- gr.update_edge(node_index(row), node_index(col), ());
- }
- }
- gr
-}
-
-/// Parse a text adjacency matrix format into a directed graph
-fn parse_graph<Ty: EdgeType>(s: &str) -> Graph<(), (), Ty>
-{
- let mut gr = Graph::with_capacity(0, 0);
- let s = s.trim();
- let lines = s.lines().filter(|l| !l.is_empty());
- for (row, line) in lines.enumerate() {
- for (col, word) in line.split(' ')
- .filter(|s| s.len() > 0)
- .enumerate()
- {
- let has_edge = word.parse::<i32>().unwrap();
- assert!(has_edge == 0 || has_edge == 1);
- if has_edge == 0 {
- continue;
- }
- while col >= gr.node_count() || row >= gr.node_count() {
- gr.add_node(());
- }
- gr.update_edge(node_index(row), node_index(col), ());
- }
- }
- gr
-}
-
-
#[bench]
-fn stable_graph_map(bench: &mut Bencher)
-{
- let a = parse_stable_graph::<Directed>(BIGGER);
+fn stable_graph_map(bench: &mut Bencher) {
+ let a = stable_digraph().bigger();
bench.iter(|| a.map(|i, _| i, |i, _| i));
}
#[bench]
-fn graph_map(bench: &mut Bencher)
-{
- let a = parse_graph::<Directed>(BIGGER);
+fn graph_map(bench: &mut Bencher) {
+ let a = digraph().bigger();
bench.iter(|| a.map(|i, _| i, |i, _| i));
}
#[bench]
-fn stable_graph_retain_nodes(bench: &mut Bencher)
-{
- let mut a = parse_stable_graph::<Directed>(BIGGER);
- bench.iter(|| a.retain_nodes(|gr, i| (i.index() + 1) % 3700 != 0));
+fn stable_graph_retain_nodes(bench: &mut Bencher) {
+ let mut a = stable_digraph().bigger();
+ bench.iter(|| a.retain_nodes(|_gr, i| (i.index() + 1) % 3700 != 0));
}
#[bench]
-fn stable_graph_retain_edges(bench: &mut Bencher)
-{
- let mut a = parse_stable_graph::<Directed>(BIGGER);
- bench.iter(|| a.retain_edges(|gr, i| (i.index() + 1) % 3700 != 0));
+fn stable_graph_retain_edges(bench: &mut Bencher) {
+ let mut a = stable_digraph().bigger();
+ bench.iter(|| a.retain_edges(|_gr, i| (i.index() + 1) % 3700 != 0));
}
diff --git a/benches/unionfind.rs b/benches/unionfind.rs
new file mode 100644
index 0000000..cf7066e
--- /dev/null
+++ b/benches/unionfind.rs
@@ -0,0 +1,192 @@
+#![feature(test)]
+
+extern crate test;
+extern crate petgraph;
+
+use test::Bencher;
+
+#[allow(dead_code)]
+mod common;
+use common::*;
+
+use petgraph::algo::{connected_components, is_cyclic_undirected, min_spanning_tree};
+
+#[bench]
+fn connected_components_praust_undir_bench(bench: &mut Bencher) {
+ let a = ungraph().praust_a();
+ let b = ungraph().praust_b();
+
+ bench.iter(|| {
+ (connected_components(&a), connected_components(&b))
+ });
+}
+
+#[bench]
+fn connected_components_praust_dir_bench(bench: &mut Bencher) {
+ let a = digraph().praust_a();
+ let b = digraph().praust_b();
+
+ bench.iter(|| {
+ (connected_components(&a), connected_components(&b))
+ });
+}
+
+#[bench]
+fn connected_components_full_undir_bench(bench: &mut Bencher) {
+ let a = ungraph().full_a();
+ let b = ungraph().full_b();
+
+ bench.iter(|| {
+ (connected_components(&a), connected_components(&b))
+ });
+}
+
+#[bench]
+fn connected_components_full_dir_bench(bench: &mut Bencher) {
+ let a = digraph().full_a();
+ let b = digraph().full_b();
+
+ bench.iter(|| {
+ (connected_components(&a), connected_components(&b))
+ });
+}
+
+#[bench]
+fn connected_components_petersen_undir_bench(bench: &mut Bencher) {
+ let a = ungraph().petersen_a();
+ let b = ungraph().petersen_b();
+
+ bench.iter(|| {
+ (connected_components(&a), connected_components(&b))
+ });
+}
+
+#[bench]
+fn connected_components_petersen_dir_bench(bench: &mut Bencher) {
+ let a = digraph().petersen_a();
+ let b = digraph().petersen_b();
+
+ bench.iter(|| {
+ (connected_components(&a), connected_components(&b))
+ });
+}
+
+#[bench]
+fn is_cyclic_undirected_praust_undir_bench(bench: &mut Bencher) {
+ let a = ungraph().praust_a();
+ let b = ungraph().praust_b();
+
+ bench.iter(|| {
+ (is_cyclic_undirected(&a), is_cyclic_undirected(&b))
+ });
+}
+
+#[bench]
+fn is_cyclic_undirected_praust_dir_bench(bench: &mut Bencher) {
+ let a = digraph().praust_a();
+ let b = digraph().praust_b();
+
+ bench.iter(|| {
+ (is_cyclic_undirected(&a), is_cyclic_undirected(&b))
+ });
+}
+
+#[bench]
+fn is_cyclic_undirected_full_undir_bench(bench: &mut Bencher) {
+ let a = ungraph().full_a();
+ let b = ungraph().full_b();
+
+ bench.iter(|| {
+ (is_cyclic_undirected(&a), is_cyclic_undirected(&b))
+ });
+}
+
+#[bench]
+fn is_cyclic_undirected_full_dir_bench(bench: &mut Bencher) {
+ let a = digraph().full_a();
+ let b = digraph().full_b();
+
+ bench.iter(|| {
+ (is_cyclic_undirected(&a), is_cyclic_undirected(&b))
+ });
+}
+
+#[bench]
+fn is_cyclic_undirected_petersen_undir_bench(bench: &mut Bencher) {
+ let a = ungraph().petersen_a();
+ let b = ungraph().petersen_b();
+
+ bench.iter(|| {
+ (is_cyclic_undirected(&a), is_cyclic_undirected(&b))
+ });
+}
+
+#[bench]
+fn is_cyclic_undirected_petersen_dir_bench(bench: &mut Bencher) {
+ let a = digraph().petersen_a();
+ let b = digraph().petersen_b();
+
+ bench.iter(|| {
+ (is_cyclic_undirected(&a), is_cyclic_undirected(&b))
+ });
+}
+
+#[bench]
+fn min_spanning_tree_praust_undir_bench(bench: &mut Bencher) {
+ let a = ungraph().praust_a();
+ let b = ungraph().praust_b();
+
+ bench.iter(|| {
+ (min_spanning_tree(&a), min_spanning_tree(&b))
+ });
+}
+
+#[bench]
+fn min_spanning_tree_praust_dir_bench(bench: &mut Bencher) {
+ let a = digraph().praust_a();
+ let b = digraph().praust_b();
+
+ bench.iter(|| {
+ (min_spanning_tree(&a), min_spanning_tree(&b))
+ });
+}
+
+#[bench]
+fn min_spanning_tree_full_undir_bench(bench: &mut Bencher) {
+ let a = ungraph().full_a();
+ let b = ungraph().full_b();
+
+ bench.iter(|| {
+ (min_spanning_tree(&a), min_spanning_tree(&b))
+ });
+}
+
+#[bench]
+fn min_spanning_tree_full_dir_bench(bench: &mut Bencher) {
+ let a = digraph().full_a();
+ let b = digraph().full_b();
+
+ bench.iter(|| {
+ (min_spanning_tree(&a), min_spanning_tree(&b))
+ });
+}
+
+#[bench]
+fn min_spanning_tree_petersen_undir_bench(bench: &mut Bencher) {
+ let a = ungraph().petersen_a();
+ let b = ungraph().petersen_b();
+
+ bench.iter(|| {
+ (min_spanning_tree(&a), min_spanning_tree(&b))
+ });
+}
+
+#[bench]
+fn min_spanning_tree_petersen_dir_bench(bench: &mut Bencher) {
+ let a = digraph().petersen_a();
+ let b = digraph().petersen_b();
+
+ bench.iter(|| {
+ (min_spanning_tree(&a), min_spanning_tree(&b))
+ });
+}
diff --git a/serialization-tests/Cargo.toml b/serialization-tests/Cargo.toml
index 063fd44..6ac6e58 100644
--- a/serialization-tests/Cargo.toml
+++ b/serialization-tests/Cargo.toml
@@ -19,6 +19,6 @@
[dev-dependencies]
serde_json = "1.0"
-quickcheck = { version = "0.7.1", default-features = false }
+quickcheck = { version = "0.8", default-features = false }
bincode = "1.0.1"
defmac = "0.1"
diff --git a/src/algo/dominators.rs b/src/algo/dominators.rs
index 0b215e4..5cbf281 100644
--- a/src/algo/dominators.rs
+++ b/src/algo/dominators.rs
@@ -15,7 +15,7 @@
use std::collections::{HashMap, HashSet};
use std::hash::Hash;
-use visit::{DfsPostOrder, GraphBase, IntoNeighbors, Visitable, Walker};
+use crate::visit::{DfsPostOrder, GraphBase, IntoNeighbors, Visitable, Walker};
/// The dominance relation for some graph and root.
#[derive(Debug, Clone)]
diff --git a/src/algo/mod.rs b/src/algo/mod.rs
index b64f536..2d3087f 100644
--- a/src/algo/mod.rs
+++ b/src/algo/mod.rs
@@ -9,12 +9,12 @@
use std::collections::BinaryHeap;
use std::cmp::min;
-use prelude::*;
+use crate::prelude::*;
use super::{
EdgeType,
};
-use scored::MinScored;
+use crate::scored::MinScored;
use super::visit::{
GraphRef,
GraphBase,
@@ -34,9 +34,9 @@
use super::graph::{
IndexType,
};
-use visit::{Data, NodeRef, IntoNodeReferences};
-use visit::Walker;
-use data::{
+use crate::visit::{Data, NodeRef, IntoNodeReferences};
+use crate::visit::Walker;
+use crate::data::{
Element,
};
@@ -47,7 +47,7 @@
pub use super::dijkstra::dijkstra;
pub use super::astar::astar;
-/// [Generic] Return the number of connected components of the graph.
+/// \[Generic\] Return the number of connected components of the graph.
///
/// For a directed graph, this is the *weakly* connected components.
/// # Example
@@ -102,7 +102,7 @@
}
-/// [Generic] Return `true` if the input graph contains a cycle.
+/// \[Generic\] Return `true` if the input graph contains a cycle.
///
/// Always treats the input graph as if undirected.
pub fn is_cyclic_undirected<G>(g: G) -> bool
@@ -122,7 +122,7 @@
}
-/// [Generic] Perform a topological sort of a directed graph.
+/// \[Generic\] Perform a topological sort of a directed graph.
///
/// If the graph was acyclic, return a vector of nodes in topological order:
/// each node is ordered before its successors.
@@ -187,14 +187,14 @@
})
}
-/// [Generic] Return `true` if the input directed graph contains a cycle.
+/// \[Generic\] Return `true` if the input directed graph contains a cycle.
///
/// This implementation is recursive; use `toposort` if an alternative is
/// needed.
pub fn is_cyclic_directed<G>(g: G) -> bool
where G: IntoNodeIdentifiers + IntoNeighbors + Visitable,
{
- use visit::{depth_first_search, DfsEvent};
+ use crate::visit::{depth_first_search, DfsEvent};
depth_first_search(g, g.node_identifiers(), |event| {
match event {
@@ -251,7 +251,7 @@
f(dfs)
}
-/// [Generic] Check if there exists a path starting at `from` and reaching `to`.
+/// \[Generic\] Check if there exists a path starting at `from` and reaching `to`.
///
/// If `from` and `to` are equal, this function returns true.
///
@@ -277,7 +277,7 @@
kosaraju_scc(g)
}
-/// [Generic] Compute the *strongly connected components* using [Kosaraju's algorithm][1].
+/// \[Generic\] Compute the *strongly connected components* using [Kosaraju's algorithm][1].
///
/// [1]: https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm
///
@@ -328,7 +328,7 @@
sccs
}
-/// [Generic] Compute the *strongly connected components* using [Tarjan's algorithm][1].
+/// \[Generic\] Compute the *strongly connected components* using [Tarjan's algorithm][1].
///
/// [1]: https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
///
@@ -544,7 +544,7 @@
condensed
}
-/// [Generic] Compute a *minimum spanning tree* of a graph.
+/// \[Generic\] Compute a *minimum spanning tree* of a graph.
///
/// The input graph is treated as if undirected.
///
@@ -647,7 +647,7 @@
#[derive(Clone, Debug, PartialEq)]
pub struct NegativeCycle(());
-/// [Generic] Compute shortest paths from node `source` to all other.
+/// \[Generic\] Compute shortest paths from node `source` to all other.
///
/// Using the [Bellman–Ford algorithm][bf]; negative edge costs are
/// permitted, but the graph must not have a cycle of negative weights
diff --git a/src/astar.rs b/src/astar.rs
index 0ebd4fe..b9435f5 100644
--- a/src/astar.rs
+++ b/src/astar.rs
@@ -9,7 +9,7 @@
use std::hash::Hash;
-use scored::MinScored;
+use crate::scored::MinScored;
use super::visit::{
EdgeRef,
GraphBase,
@@ -18,9 +18,9 @@
Visitable,
};
-use algo::Measure;
+use crate::algo::Measure;
-/// [Generic] A* shortest path algorithm.
+/// \[Generic\] A* shortest path algorithm.
///
/// Computes the shortest path from `start` to `finish`, including the total path cost.
///
diff --git a/src/csr.rs b/src/csr.rs
index 1ce87cc..7c603f5 100644
--- a/src/csr.rs
+++ b/src/csr.rs
@@ -6,16 +6,16 @@
use std::iter::{Enumerate, Zip};
use std::slice::Windows;
-use visit::{EdgeRef, GraphBase, IntoNeighbors, NodeIndexable, IntoEdges};
-use visit::{NodeCompactIndexable, IntoNodeIdentifiers, Visitable};
-use visit::{Data, IntoEdgeReferences, NodeCount, GraphProp};
+use crate::visit::{EdgeRef, GraphBase, IntoNeighbors, NodeIndexable, IntoEdges};
+use crate::visit::{NodeCompactIndexable, IntoNodeIdentifiers, Visitable};
+use crate::visit::{Data, IntoEdgeReferences, NodeCount, GraphProp};
-use util::zip;
+use crate::util::zip;
#[doc(no_inline)]
-pub use graph::{IndexType, DefaultIx};
+pub use crate::graph::{IndexType, DefaultIx};
-use {
+use crate::{
EdgeType,
Directed,
IntoWeightedEdge,
@@ -43,6 +43,7 @@
/// Self loops are allowed, no parallel edges.
///
/// Fast iteration of the outgoing edges of a vertex.
+///
/// [`CSR`]: https://en.wikipedia.org/wiki/Sparse_matrix#Compressed_sparse_row_(CSR,_CRS_or_Yale_format)
#[derive(Debug)]
pub struct Csr<N = (), E = (), Ty = Directed, Ix = DefaultIx> {
@@ -269,7 +270,7 @@
/// Adds a new node with the given weight, returning the corresponding node index.
pub fn add_node(&mut self, weight: N) -> NodeIndex<Ix> {
let i = self.row.len() - 1;
- self.row.insert(i, 0);
+ self.row.insert(i, self.column.len());
self.node_weights.insert(i, weight);
Ix::new(i)
}
@@ -701,11 +702,11 @@
#[cfg(test)]
mod tests {
use super::Csr;
- use Undirected;
- use visit::Dfs;
- use visit::VisitMap;
- use algo::tarjan_scc;
- use algo::bellman_ford;
+ use crate::Undirected;
+ use crate::visit::Dfs;
+ use crate::visit::VisitMap;
+ use crate::algo::tarjan_scc;
+ use crate::algo::bellman_ford;
#[test]
fn csr1() {
@@ -889,8 +890,8 @@
#[test]
fn test_edge_references() {
- use visit::EdgeRef;
- use visit::IntoEdgeReferences;
+ use crate::visit::EdgeRef;
+ use crate::visit::IntoEdgeReferences;
let m: Csr<(), _> = Csr::from_sorted_edges(&[
(0, 1, 0.5),
(0, 2, 2.),
@@ -937,4 +938,25 @@
assert_eq!(g.edge_count(), 3);
}
+
+ #[test]
+ fn test_add_node_with_existing_edges() {
+ let mut g: Csr = Csr::new();
+ let a = g.add_node(());
+ let b = g.add_node(());
+
+ assert!(g.add_edge(a, b, ()));
+
+ let c = g.add_node(());
+
+ println!("{:?}", g);
+
+ assert_eq!(g.node_count(), 3);
+
+ assert_eq!(g.neighbors_slice(a), &[b]);
+ assert_eq!(g.neighbors_slice(b), &[]);
+ assert_eq!(g.neighbors_slice(c), &[]);
+
+ assert_eq!(g.edge_count(), 1);
+ }
}
diff --git a/src/data.rs b/src/data.rs
index 1509461..03f1b31 100644
--- a/src/data.rs
+++ b/src/data.rs
@@ -1,16 +1,16 @@
//! Graph traits for associated data and graph construction.
-use Graph;
+use crate::Graph;
#[cfg(feature = "stable_graph")]
-use stable_graph::StableGraph;
-use ::{
+use crate::stable_graph::StableGraph;
+use crate::{
EdgeType,
};
-use graph::IndexType;
+use crate::graph::IndexType;
#[cfg(feature = "graphmap")]
-use graphmap::{GraphMap, NodeTrait};
-use visit::{
+use crate::graphmap::{GraphMap, NodeTrait};
+use crate::visit::{
Data,
NodeCount,
NodeIndexable,
diff --git a/src/dijkstra.rs b/src/dijkstra.rs
index e7b6feb..b856e60 100644
--- a/src/dijkstra.rs
+++ b/src/dijkstra.rs
@@ -9,16 +9,16 @@
use std::hash::Hash;
-use scored::MinScored;
+use crate::scored::MinScored;
use super::visit::{
Visitable,
VisitMap,
IntoEdges,
EdgeRef,
};
-use algo::Measure;
+use crate::algo::Measure;
-/// [Generic] Dijkstra's shortest path algorithm.
+/// \[Generic\] Dijkstra's shortest path algorithm.
///
/// Compute the length of the shortest path from `start` to every reachable
/// node.
diff --git a/src/dot.rs b/src/dot.rs
index 09bf26b..7defdee 100644
--- a/src/dot.rs
+++ b/src/dot.rs
@@ -2,7 +2,7 @@
use std::fmt::{self, Display, Write};
-use visit::{GraphRef};
+use crate::visit::{GraphRef};
/// `Dot` implements output to graphviz .dot format for a graph.
///
@@ -80,12 +80,14 @@
EdgeIndexLabel,
/// Use no edge labels.
EdgeNoLabel,
+ /// Do not print the graph/digraph string.
+ GraphContentOnly,
#[doc(hidden)]
_Incomplete(()),
}
-use visit::{ IntoNodeReferences, NodeIndexable, IntoEdgeReferences, EdgeRef};
-use visit::{ Data, NodeRef, GraphProp, };
+use crate::visit::{ IntoNodeReferences, NodeIndexable, IntoEdgeReferences, EdgeRef};
+use crate::visit::{ Data, NodeRef, GraphProp, };
impl<'a, G> Dot<'a, G>
{
@@ -94,42 +96,46 @@
where G: NodeIndexable + IntoNodeReferences + IntoEdgeReferences,
G: GraphProp,
G: Data<NodeWeight=NW, EdgeWeight=EW>,
- NF: FnMut(&NW, &mut FnMut(&Display) -> fmt::Result) -> fmt::Result,
- EF: FnMut(&EW, &mut FnMut(&Display) -> fmt::Result) -> fmt::Result,
+ NF: FnMut(&NW, &mut dyn FnMut(&dyn Display) -> fmt::Result) -> fmt::Result,
+ EF: FnMut(&EW, &mut dyn FnMut(&dyn Display) -> fmt::Result) -> fmt::Result,
{
- try!(writeln!(f, "{} {{", TYPE[g.is_directed() as usize]));
+ if !self.config.contains(&Config::GraphContentOnly) {
+ writeln!(f, "{} {{", TYPE[g.is_directed() as usize])?;
+ }
// output all labels
for node in g.node_references() {
- try!(write!(f, "{}{}", INDENT, g.to_index(node.id())));
+ write!(f, "{}{}", INDENT, g.to_index(node.id()))?;
if self.config.contains(&Config::NodeIndexLabel) {
- try!(writeln!(f, ""));
+ writeln!(f)?;
} else {
- try!(write!(f, " [label=\""));
- try!(node_fmt(node.weight(), &mut |d| Escaped(d).fmt(f)));
- try!(writeln!(f, "\"]"));
+ write!(f, " [label=\"")?;
+ node_fmt(node.weight(), &mut |d| Escaped(d).fmt(f))?;
+ writeln!(f, "\"]")?;
}
}
// output all edges
for (i, edge) in g.edge_references().enumerate() {
- try!(write!(f, "{}{} {} {}",
+ write!(f, "{}{} {} {}",
INDENT,
g.to_index(edge.source()),
EDGE[g.is_directed() as usize],
- g.to_index(edge.target())));
+ g.to_index(edge.target()))?;
if self.config.contains(&Config::EdgeNoLabel) {
- try!(writeln!(f, ""));
+ writeln!(f)?;
} else if self.config.contains(&Config::EdgeIndexLabel) {
- try!(writeln!(f, " [label=\"{}\"]", i));
+ writeln!(f, " [label=\"{}\"]", i)?;
} else {
- try!(write!(f, " [label=\""));
- try!(edge_fmt(edge.weight(), &mut |d| Escaped(d).fmt(f)));
- try!(writeln!(f, "\"]"));
+ write!(f, " [label=\"")?;
+ edge_fmt(edge.weight(), &mut |d| Escaped(d).fmt(f))?;
+ writeln!(f, "\"]")?;
}
}
- try!(writeln!(f, "}}"));
+ if !self.config.contains(&Config::GraphContentOnly) {
+ writeln!(f, "}}")?;
+ }
Ok(())
}
}
@@ -164,14 +170,14 @@
{
fn write_str(&mut self, s: &str) -> fmt::Result {
for c in s.chars() {
- try!(self.write_char(c));
+ self.write_char(c)?;
}
Ok(())
}
fn write_char(&mut self, c: char) -> fmt::Result {
match c {
- '"' | '\\' => try!(self.0.write_char('\\')),
+ '"' | '\\' => self.0.write_char('\\')?,
// \l is for left justified linebreak
'\n' => return self.0.write_str("\\l"),
_ => {}
@@ -188,7 +194,7 @@
{
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
if f.alternate() {
- write!(&mut Escaper(f), "{:#}\n", &self.0)
+ writeln!(&mut Escaper(f), "{:#}", &self.0)
} else {
write!(&mut Escaper(f), "{}", &self.0)
}
diff --git a/src/generate.rs b/src/generate.rs
index 91ea64a..e717239 100644
--- a/src/generate.rs
+++ b/src/generate.rs
@@ -3,8 +3,8 @@
//! ***Unstable: API may change at any time.*** Depends on `feature = "generate"`.
//!
-use {Graph, Directed, EdgeType};
-use graph::NodeIndex;
+use crate::{Graph, Directed, EdgeType};
+use crate::graph::NodeIndex;
// A DAG has the property that the adjacency matrix is lower triangular,
// diagonal zero.
diff --git a/src/graph_impl/frozen.rs b/src/graph_impl/frozen.rs
index 488cc55..bb96618 100644
--- a/src/graph_impl/frozen.rs
+++ b/src/graph_impl/frozen.rs
@@ -1,17 +1,17 @@
use std::ops::{Deref, Index, IndexMut};
-use graph::Graph;
+use crate::graph::Graph;
use super::Frozen;
-use graph::{IndexType, GraphIndex};
-use {
+use crate::graph::{IndexType, GraphIndex};
+use crate::{
Direction,
EdgeType,
};
-use visit::{Data, IntoNodeIdentifiers, GraphProp, NodeIndexable, IntoNeighborsDirected};
-use visit::{IntoNeighbors, IntoNodeReferences, IntoEdgeReferences, Visitable};
-use visit::{NodeCompactIndexable, GetAdjacencyMatrix, NodeCount, IntoEdges, IntoEdgesDirected};
-use data::{DataMap, DataMapMut};
+use crate::visit::{Data, IntoNodeIdentifiers, GraphProp, NodeIndexable, IntoNeighborsDirected};
+use crate::visit::{IntoNeighbors, IntoNodeReferences, IntoEdgeReferences, Visitable};
+use crate::visit::{NodeCompactIndexable, GetAdjacencyMatrix, NodeCount, IntoEdges, IntoEdgesDirected};
+use crate::data::{DataMap, DataMapMut};
impl<'a, G> Frozen<'a, G> {
diff --git a/src/graph_impl/mod.rs b/src/graph_impl/mod.rs
index c439633..1e8d1d6 100644
--- a/src/graph_impl/mod.rs
+++ b/src/graph_impl/mod.rs
@@ -7,7 +7,7 @@
use std::ops::{Index, IndexMut, Range};
use std::slice;
-use {
+use crate::{
Direction, Outgoing, Incoming,
Undirected,
Directed,
@@ -15,15 +15,15 @@
IntoWeightedEdge,
};
-use iter_format::{
+use crate::iter_format::{
IterFormatExt,
NoPretty,
DebugMap,
};
-use visit::EdgeRef;
-use visit::{IntoNodeReferences, IntoEdges, IntoEdgesDirected};
-use util::enumerate;
+use crate::visit::EdgeRef;
+use crate::visit::{IntoNodeReferences, IntoEdges, IntoEdgesDirected};
+use crate::util::enumerate;
#[cfg(feature = "serde-1")]
mod serialization;
@@ -262,6 +262,9 @@
/// - Edge type `Ty` that determines whether the graph edges are directed or undirected.
/// - Index type `Ix`, which determines the maximum size of the graph.
///
+/// The `Graph` is a regular Rust collection and is `Send` and `Sync` (as long
+/// as associated data `N` and `E` are).
+///
/// The graph uses **O(|V| + |E|)** space, and allows fast node and edge insert,
/// efficient graph search and graph algorithms.
/// It implements **O(e')** edge lookup and edge and node removals, where **e'**
@@ -296,17 +299,16 @@
/// example for *n* nodes indices are 0 to *n* - 1 inclusive.
///
/// `NodeIndex` and `EdgeIndex` are types that act as references to nodes and edges,
-/// but these are only stable across certain operations.
-/// **Adding nodes or edges keeps indices stable.
-/// Removing nodes or edges may shift other indices.**
-/// Removing a node will force the last node to shift its index to
-/// take its place. Similarly, removing an edge shifts the index of the last edge.
+/// but these are only stable across certain operations:
+///
+/// * **Removing nodes or edges may shift other indices.** Removing a node will
+/// force the last node to shift its index to take its place. Similarly,
+/// removing an edge shifts the index of the last edge.
+/// * Adding nodes or edges keeps indices stable.
///
/// The `Ix` parameter is `u32` by default. The goal is that you can ignore this parameter
/// completely unless you need a very big graph -- then you can use `usize`.
///
-/// ### Pros and Cons of Indices
-///
/// * The fact that the node and edge indices in the graph each are numbered in compact
/// intervals (from 0 to *n* - 1 for *n* nodes) simplifies some graph algorithms.
///
@@ -319,12 +321,7 @@
/// * You can create several graphs using the equal node indices but with
/// differing weights or differing edges.
///
-/// * The `Graph` is a regular rust collection and is `Send` and `Sync` (as long
-/// as associated data `N` and `E` are).
-///
-/// * Some indices shift during node or edge removal, so that is a drawback
-/// of removing elements. Indices don't allow as much compile time checking as
-/// references.
+/// * Indices don't allow as much compile time checking as references.
///
pub struct Graph<N, E, Ty = Directed, Ix = DefaultIx> {
nodes: Vec<Node<N, Ix>>,
@@ -953,7 +950,18 @@
Externals{iter: self.nodes.iter().enumerate(), dir: dir, ty: PhantomData}
}
- /// Return an iterator over the node indices of the graph
+ /// Return an iterator over the node indices of the graph.
+ ///
+ /// For example, in a rare case where a graph algorithm were not applicable,
+ /// the following code will iterate through all nodes to find a
+ /// specific index:
+ ///
+ /// ```
+ /// # use petgraph::Graph;
+ /// # let mut g = Graph::<&str, i32>::new();
+ /// # g.add_node("book");
+ /// let index = g.node_indices().find(|i| g[*i] == "book").unwrap();
+ /// ```
pub fn node_indices(&self) -> NodeIndices<Ix> {
NodeIndices { r: 0..self.node_count(), ty: PhantomData }
}
@@ -1550,7 +1558,7 @@
edges: &'a [Edge<E, Ix>],
/// Next edge to visit.
- /// If we are only following one direction, we only use next[0] regardless.
+ /// If we are only following one direction, we only use `next[0]` regardless.
next: [EdgeIndex<Ix>; 2],
/// Which direction to follow
diff --git a/src/graph_impl/serialization.rs b/src/graph_impl/serialization.rs
index c400693..8c93c2e 100644
--- a/src/graph_impl/serialization.rs
+++ b/src/graph_impl/serialization.rs
@@ -3,14 +3,14 @@
use std::marker::PhantomData;
-use prelude::*;
+use crate::prelude::*;
-use EdgeType;
-use graph::Node;
-use graph::{IndexType, Edge};
-use serde_utils::MappedSequenceVisitor;
-use serde_utils::CollectSeqWithLength;
-use serde_utils::{IntoSerializable, FromDeserialized};
+use crate::EdgeType;
+use crate::graph::Node;
+use crate::graph::{IndexType, Edge};
+use crate::serde_utils::MappedSequenceVisitor;
+use crate::serde_utils::CollectSeqWithLength;
+use crate::serde_utils::{IntoSerializable, FromDeserialized};
use super::{NodeIndex, EdgeIndex};
use serde::{Serialize, Serializer, Deserialize, Deserializer};
diff --git a/src/graph_impl/stable_graph/mod.rs b/src/graph_impl/stable_graph/mod.rs
index 293efaa..c730336 100644
--- a/src/graph_impl/stable_graph/mod.rs
+++ b/src/graph_impl/stable_graph/mod.rs
@@ -12,7 +12,7 @@
use std::ops::{Index, IndexMut};
use std::slice;
-use {
+use crate::{
Graph,
EdgeType,
Directed,
@@ -22,12 +22,12 @@
Outgoing,
};
-use iter_format::{
+use crate::iter_format::{
IterFormatExt,
NoPretty,
DebugMap,
};
-use iter_utils::IterUtilsExt;
+use crate::iter_utils::IterUtilsExt;
use super::{
Edge,
@@ -37,8 +37,8 @@
Pair,
Frozen,
};
-use IntoWeightedEdge;
-use visit::{
+use crate::IntoWeightedEdge;
+use crate::visit::{
EdgeRef,
IntoNodeReferences,
IntoEdges,
@@ -49,7 +49,7 @@
// reexport those things that are shared with Graph
#[doc(no_inline)]
-pub use graph::{
+pub use crate::graph::{
NodeIndex,
EdgeIndex,
GraphIndex,
@@ -59,7 +59,7 @@
edge_index,
};
-use util::enumerate;
+use crate::util::enumerate;
#[cfg(feature = "serde-1")]
mod serialization;
@@ -1291,7 +1291,7 @@
edges: &'a [Edge<Option<E>, Ix>],
/// Next edge to visit.
- /// If we are only following one direction, we only use next[0] regardless.
+ /// If we are only following one direction, we only use `next[0]` regardless.
next: [EdgeIndex<Ix>; 2],
/// Which direction to follow
@@ -1682,7 +1682,7 @@
#[test]
fn dfs() {
- use visit::Dfs;
+ use crate::visit::Dfs;
let mut gr = StableGraph::<_, _>::with_capacity(0, 0);
let a = gr.add_node("a");
diff --git a/src/graph_impl/stable_graph/serialization.rs b/src/graph_impl/stable_graph/serialization.rs
index bc26c57..da031c6 100644
--- a/src/graph_impl/stable_graph/serialization.rs
+++ b/src/graph_impl/stable_graph/serialization.rs
@@ -5,17 +5,17 @@
use std::marker::PhantomData;
-use prelude::*;
+use crate::prelude::*;
-use EdgeType;
-use graph::Node;
-use graph::{IndexType, Edge};
-use stable_graph::StableGraph;
-use util::rev;
-use serde_utils::MappedSequenceVisitor;
-use serde_utils::CollectSeqWithLength;
-use serde_utils::{IntoSerializable, FromDeserialized};
-use visit::NodeIndexable;
+use crate::EdgeType;
+use crate::graph::Node;
+use crate::graph::{IndexType, Edge};
+use crate::stable_graph::StableGraph;
+use crate::util::rev;
+use crate::serde_utils::MappedSequenceVisitor;
+use crate::serde_utils::CollectSeqWithLength;
+use crate::serde_utils::{IntoSerializable, FromDeserialized};
+use crate::visit::NodeIndexable;
use super::super::serialization::{EdgeProperty, invalid_length_err, invalid_node_err};
@@ -231,8 +231,8 @@
#[test]
fn test_from_deserialized_with_holes() {
- use graph::node_index;
- use stable_graph::StableUnGraph;
+ use crate::graph::node_index;
+ use crate::stable_graph::StableUnGraph;
use serde::de::value::Error as SerdeError;
use itertools::assert_equal;
diff --git a/src/graphmap.rs b/src/graphmap.rs
index 5adac89..8a4d97c 100644
--- a/src/graphmap.rs
+++ b/src/graphmap.rs
@@ -20,7 +20,7 @@
};
use indexmap::map::Keys;
-use {
+use crate::{
EdgeType,
Directed,
Undirected,
@@ -29,11 +29,11 @@
Outgoing,
};
-use IntoWeightedEdge;
-use visit::{IntoNodeIdentifiers, NodeCount, IntoNodeReferences, NodeIndexable};
-use visit::{NodeCompactIndexable, IntoEdgeReferences, IntoEdges};
-use graph::Graph;
-use graph::node_index;
+use crate::IntoWeightedEdge;
+use crate::visit::{IntoNodeIdentifiers, NodeCount, IntoNodeReferences, NodeIndexable};
+use crate::visit::{NodeCompactIndexable, IntoEdgeReferences, IntoEdges};
+use crate::graph::Graph;
+use crate::graph::node_index;
/// A `GraphMap` with undirected edges.
///
@@ -414,7 +414,7 @@
/// **Panics** if the number of nodes or edges does not fit with
/// the resulting graph's index type.
pub fn into_graph<Ix>(self) -> Graph<N, E, Ty, Ix>
- where Ix: ::graph::IndexType,
+ where Ix: crate::graph::IndexType,
{
// assuming two successive iterations of the same hashmap produce the same order
let mut gr = Graph::with_capacity(self.node_count(), self.edge_count());
diff --git a/src/isomorphism.rs b/src/isomorphism.rs
index 8632dde..1554b37 100644
--- a/src/isomorphism.rs
+++ b/src/isomorphism.rs
@@ -201,7 +201,7 @@
trait SemanticMatcher<T> {
fn enabled() -> bool;
- fn eq(&mut self, &T, &T) -> bool;
+ fn eq(&mut self, _: &T, _: &T) -> bool;
}
struct NoSemanticMatch;
diff --git a/src/iter_format.rs b/src/iter_format.rs
index 3f1c9cf..de03a2a 100644
--- a/src/iter_format.rs
+++ b/src/iter_format.rs
@@ -70,12 +70,12 @@
};
if let Some(fst) = iter.next() {
- try!(cb(&fst, f));
+ cb(&fst, f)?;
for elt in iter {
if !self.sep.is_empty() {
- try!(f.write_str(self.sep));
+ f.write_str(self.sep)?;
}
- try!(cb(&elt, f));
+ cb(&elt, f)?;
}
}
Ok(())
diff --git a/src/lib.rs b/src/lib.rs
index 7c6f82a..4a76111 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -10,6 +10,9 @@
//! - [`GraphMap`](./graphmap/struct.GraphMap.html) is an adjacency list graph
//! which is backed by a hash table and the node identifiers are the keys
//! into the table.
+//!
+//! - [`MatrixGraph`](./matrix_graph/struct.MatrixGraph.html) is an adjacency matrix graph.
+//!
//! - [`CSR`](./csr/struct.Csr.html) is a sparse adjacency matrix graph with
//! arbitrary associated data.
//!
@@ -31,9 +34,9 @@
extern crate itertools;
#[doc(no_inline)]
-pub use graph::Graph;
+pub use crate::graph::Graph;
-pub use Direction::{Outgoing, Incoming};
+pub use crate::Direction::{Outgoing, Incoming};
#[macro_use]
mod macros;
@@ -50,6 +53,8 @@
pub mod generate;
#[cfg(feature = "graphmap")]
pub mod graphmap;
+#[cfg(feature = "matrix_graph")]
+pub mod matrix_graph;
mod graph_impl;
pub mod dot;
pub mod unionfind;
@@ -70,7 +75,7 @@
/// `Graph<N, E, Ty, Ix>` is a graph datastructure using an adjacency list representation.
pub mod graph {
- pub use graph_impl::{
+ pub use crate::graph_impl::{
Edge,
EdgeIndex,
EdgeIndices,
@@ -99,7 +104,7 @@
}
#[cfg(feature = "stable_graph")]
-pub use graph_impl::stable_graph;
+pub use crate::graph_impl::stable_graph;
macro_rules! copyclone {
($name:ident) => {
@@ -141,7 +146,7 @@
}
#[doc(hidden)]
-pub use Direction as EdgeDirection;
+pub use crate::Direction as EdgeDirection;
/// Marker type for a directed graph.
#[derive(Copy, Debug)]
diff --git a/src/matrix_graph.rs b/src/matrix_graph.rs
new file mode 100644
index 0000000..3d2bd8a
--- /dev/null
+++ b/src/matrix_graph.rs
@@ -0,0 +1,1565 @@
+//! `MatrixGraph<N, E, Ty, NullN, NullE, Ix>` is a graph datastructure backed by an adjacency matrix.
+
+use std::marker::PhantomData;
+use std::ops::{Index, IndexMut};
+
+use std::cmp;
+use std::mem;
+
+use indexmap::IndexSet;
+
+use fixedbitset::FixedBitSet;
+
+use crate::{
+ Directed,
+ EdgeType,
+ Outgoing,
+ Undirected,
+ Direction,
+ IntoWeightedEdge,
+};
+
+use crate::graph::NodeIndex as GraphNodeIndex;
+
+use crate::visit::{
+ Data,
+ GetAdjacencyMatrix,
+ GraphBase,
+ GraphProp,
+ IntoEdgeReferences,
+ IntoEdges,
+ IntoNeighbors,
+ IntoNeighborsDirected,
+ IntoNodeIdentifiers,
+ IntoNodeReferences,
+ NodeCount,
+ NodeIndexable,
+ NodeCompactIndexable,
+ Visitable,
+};
+
+use crate::data::Build;
+
+pub use crate::graph::IndexType;
+
+// The following types are used to control the max size of the adjacency matrix. Since the maximum
+// size of the matrix vector's is the square of the maximum number of nodes, the number of nodes
+// should be reasonably picked.
+type DefaultIx = u16;
+
+/// Node identifier.
+pub type NodeIndex<Ix=DefaultIx> = GraphNodeIndex<Ix>;
+
+mod private {
+ pub trait Sealed {}
+
+ impl<T> Sealed for super::NotZero<T> {}
+ impl<T> Sealed for Option<T> {}
+}
+
+/// Wrapper trait for an `Option`, allowing user-defined structs to be input as containers when
+/// defining a null element.
+///
+/// Note: this trait is currently *sealed* and cannot be implemented for types outside this crate.
+pub trait Nullable: Default + Into<Option<<Self as Nullable>::Wrapped>> + private::Sealed {
+ #[doc(hidden)]
+ type Wrapped;
+
+ #[doc(hidden)]
+ fn new(value: Self::Wrapped) -> Self;
+
+ #[doc(hidden)]
+ fn as_ref(&self) -> Option<&Self::Wrapped>;
+
+ #[doc(hidden)]
+ fn as_mut(&mut self) -> Option<&mut Self::Wrapped>;
+
+ #[doc(hidden)]
+ fn is_null(&self) -> bool {
+ self.as_ref().is_none()
+ }
+}
+
+impl<T> Nullable for Option<T> {
+ type Wrapped = T;
+
+ fn new(value: T) -> Self {
+ Some(value)
+ }
+
+ fn as_ref(&self) -> Option<&Self::Wrapped> {
+ self.as_ref()
+ }
+
+ fn as_mut(&mut self) -> Option<&mut Self::Wrapped> {
+ self.as_mut()
+ }
+}
+
+/// `NotZero` is used to optimize the memory usage of edge weights `E` in a
+/// [`MatrixGraph`](struct.MatrixGraph.html), replacing the default `Option<E>` sentinel.
+///
+/// Pre-requisite: edge weight should implement [`Zero`](trait.Zero.html).
+///
+/// Note that if you're already using the standard non-zero types (such as `NonZeroU32`), you don't
+/// have to use this wrapper and can leave the default `Null` type argument.
+pub struct NotZero<T>(T);
+
+impl<T: Zero> Default for NotZero<T> {
+ fn default() -> Self {
+ NotZero(T::zero())
+ }
+}
+
+impl<T: Zero> Nullable for NotZero<T> {
+ type Wrapped = T;
+
+ fn new(value: T) -> Self {
+ assert!(!value.is_zero());
+ NotZero(value)
+ }
+
+ // implemented here for optimization purposes
+ fn is_null(&self) -> bool {
+ self.0.is_zero()
+ }
+
+ fn as_ref(&self) -> Option<&Self::Wrapped> {
+ if !self.is_null() { Some(&self.0) }
+ else { None }
+ }
+
+ fn as_mut(&mut self) -> Option<&mut Self::Wrapped> {
+ if !self.is_null() { Some(&mut self.0) }
+ else { None }
+ }
+}
+
+impl<T: Zero> Into<Option<T>> for NotZero<T> {
+ fn into(self) -> Option<T> {
+ if !self.is_null() { Some(self.0) }
+ else { None }
+ }
+}
+
+/// Base trait for types that can be wrapped in a [`NotZero`](struct.NotZero.html).
+///
+/// Implementors must provide a singleton object that will be used to mark empty edges in a
+/// [`MatrixGraph`](struct.MatrixGraph.html).
+///
+/// Note that this trait is already implemented for the base numeric types.
+pub trait Zero {
+ /// Return the singleton object which can be used as a sentinel value.
+ fn zero() -> Self;
+
+ /// Return true if `self` is equal to the sentinel value.
+ fn is_zero(&self) -> bool;
+}
+
+macro_rules! not_zero_impl {
+ ($t:ty,$z:expr) => {
+ impl Zero for $t {
+ fn zero() -> Self {
+ $z as $t
+ }
+
+ fn is_zero(&self) -> bool {
+ self == &Self::zero()
+ }
+ }
+ }
+}
+
+macro_rules! not_zero_impls {
+ ($($t:ty),*) => {
+ $(
+ not_zero_impl!($t, 0);
+ )*
+ }
+}
+
+not_zero_impls!(u8, u16, u32, u64, usize);
+not_zero_impls!(i8, i16, i32, i64, isize);
+not_zero_impls!(f32, f64);
+
+/// Short version of `NodeIndex::new` (with Ix = `DefaultIx`)
+#[inline]
+pub fn node_index(ax: usize) -> NodeIndex {
+ NodeIndex::new(ax)
+}
+
+/// `MatrixGraph<N, E, Ty, Null>` is a graph datastructure using an adjacency matrix
+/// representation.
+///
+/// `MatrixGraph` is parameterized over:
+///
+/// - Associated data `N` for nodes and `E` for edges, called *weights*.
+/// The associated data can be of arbitrary type.
+/// - Edge type `Ty` that determines whether the graph edges are directed or undirected.
+/// - Nullable type `Null`, which denotes the edges' presence (defaults to `Option<E>`). You may
+/// specify [`NotZero<E>`](struct.NotZero.html) if you want to use a sentinel value (such as 0)
+/// to mark the absence of an edge.
+/// - Index type `Ix` that sets the maximum size for the graph (defaults to `DefaultIx`).
+///
+/// The graph uses **O(|V^2|)** space, with fast edge insertion & amortized node insertion, as well
+/// as efficient graph search and graph algorithms on dense graphs.
+///
+/// This graph is backed by a flattened 2D array. For undirected graphs, only the lower triangular
+/// matrix is stored. Since the backing array stores edge weights, it is recommended to box large
+/// edge weights.
+#[derive(Clone)]
+pub struct MatrixGraph<N, E, Ty = Directed, Null: Nullable<Wrapped=E> = Option<E>, Ix = DefaultIx> {
+ node_adjacencies: Vec<Null>,
+ node_capacity: usize,
+ nodes: IdStorage<N>,
+ nb_edges: usize,
+ ty: PhantomData<Ty>,
+ ix: PhantomData<Ix>,
+}
+
+/// A `MatrixGraph` with directed edges.
+pub type DiMatrix<N, E, Null = Option<E>, Ix = DefaultIx> = MatrixGraph<N, E, Directed, Null, Ix>;
+
+/// A `MatrixGraph` with undirected edges.
+pub type UnMatrix<N, E, Null = Option<E>, Ix = DefaultIx> = MatrixGraph<N, E, Undirected, Null, Ix>;
+
+impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> MatrixGraph<N, E, Ty, Null, Ix> {
+ /// Create a new `MatrixGraph` with estimated capacity for nodes.
+ pub fn with_capacity(node_capacity: usize) -> Self {
+ let mut m = Self {
+ node_adjacencies: vec![],
+ node_capacity: 0,
+ nodes: IdStorage::with_capacity(node_capacity),
+ nb_edges: 0,
+ ty: PhantomData,
+ ix: PhantomData,
+ };
+
+ debug_assert!(node_capacity <= <Ix as IndexType>::max().index());
+ m.extend_capacity_for_node(NodeIndex::new(node_capacity));
+
+ m
+ }
+
+ #[inline]
+ fn to_edge_position(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> usize {
+ to_linearized_matrix_position::<Ty>(a.index(), b.index(), self.node_capacity)
+ }
+
+ /// Remove all nodes and edges.
+ pub fn clear(&mut self) {
+ for edge in self.node_adjacencies.iter_mut() {
+ *edge = Default::default();
+ }
+ self.nodes.clear();
+ self.nb_edges = 0;
+ }
+
+ /// Return the number of nodes (vertices) in the graph.
+ ///
+ /// Computes in **O(1)** time.
+ #[inline]
+ pub fn node_count(&self) -> usize {
+ self.nodes.len()
+ }
+
+ /// Return the number of edges in the graph.
+ ///
+ /// Computes in **O(1)** time.
+ #[inline]
+ pub fn edge_count(&self) -> usize {
+ self.nb_edges
+ }
+
+ /// Return whether the graph has directed edges or not.
+ #[inline]
+ pub fn is_directed(&self) -> bool {
+ Ty::is_directed()
+ }
+
+ /// Add a node (also called vertex) with associated data `weight` to the graph.
+ ///
+ /// Computes in **O(1)** time.
+ ///
+ /// Return the index of the new node.
+ ///
+ /// **Panics** if the MatrixGraph is at the maximum number of nodes for its index type.
+ pub fn add_node(&mut self, weight: N) -> NodeIndex<Ix> {
+ NodeIndex::new(self.nodes.add(weight))
+ }
+
+ /// Remove `a` from the graph.
+ ///
+ /// Computes in **O(V)** time, due to the removal of edges with other nodes.
+ ///
+ /// **Panics** if the node `a` does not exist.
+ pub fn remove_node(&mut self, a: NodeIndex<Ix>) -> N {
+ for id in self.nodes.iter_ids() {
+ let position = self.to_edge_position(a, NodeIndex::new(id));
+ self.node_adjacencies[position] = Default::default();
+
+ if Ty::is_directed() {
+ let position = self.to_edge_position(NodeIndex::new(id), a);
+ self.node_adjacencies[position] = Default::default();
+ }
+ }
+
+ self.nodes.remove(a.index())
+ }
+
+ #[inline]
+ fn extend_capacity_for_node(&mut self, min_node: NodeIndex<Ix>) {
+ self.node_capacity = extend_linearized_matrix::<Ty, _>(&mut self.node_adjacencies, self.node_capacity, min_node.index());
+ }
+
+ #[inline]
+ fn extend_capacity_for_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) {
+ let min_node = cmp::max(a, b);
+ if min_node.index() >= self.node_capacity {
+ self.extend_capacity_for_node(min_node);
+ }
+ }
+
+ /// Update the edge from `a` to `b` to the graph, with its associated data `weight`.
+ ///
+ /// Return the previous data, if any.
+ ///
+ /// Computes in **O(1)** time, best case.
+ /// Computes in **O(|V|^2)** time, worst case (matrix needs to be re-allocated).
+ ///
+ /// **Panics** if any of the nodes don't exist.
+ pub fn update_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E) -> Option<E> {
+ self.extend_capacity_for_edge(a, b);
+
+ let p = self.to_edge_position(a, b);
+ let old_weight = mem::replace(&mut self.node_adjacencies[p], Null::new(weight));
+ if old_weight.is_null() {
+ self.nb_edges += 1;
+ }
+ old_weight.into()
+ }
+
+ /// Add an edge from `a` to `b` to the graph, with its associated
+ /// data `weight`.
+ ///
+ /// Return the index of the new edge.
+ ///
+ /// Computes in **O(1)** time, best case.
+ /// Computes in **O(|V|^2)** time, worst case (matrix needs to be re-allocated).
+ ///
+ /// **Panics** if any of the nodes don't exist.
+ /// **Panics** if an edge already exists from `a` to `b`.
+ ///
+ /// **Note:** `MatrixGraph` does not allow adding parallel (“duplicate”) edges. If you want to avoid
+ /// this, use [`.update_edge(a, b, weight)`](#method.update_edge) instead.
+ pub fn add_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E) {
+ let old_edge_id = self.update_edge(a, b, weight);
+ assert!(old_edge_id.is_none());
+ }
+
+ /// Remove the edge from `a` to `b` to the graph.
+ ///
+ /// **Panics** if any of the nodes don't exist.
+ /// **Panics** if no edge exists between `a` and `b`.
+ pub fn remove_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> E {
+ let p = self.to_edge_position(a, b);
+ let old_weight = mem::replace(&mut self.node_adjacencies[p], Default::default()).into().unwrap();
+ let old_weight: Option<_> = old_weight.into();
+ self.nb_edges -= 1;
+ old_weight.unwrap()
+ }
+
+ /// Return true if there is an edge between `a` and `b`.
+ ///
+ /// **Panics** if any of the nodes don't exist.
+ pub fn has_edge(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool {
+ let p = self.to_edge_position(a, b);
+ !self.node_adjacencies[p].is_null()
+ }
+
+ /// Access the weight for node `a`.
+ ///
+ /// Also available with indexing syntax: `&graph[a]`.
+ ///
+ /// **Panics** if the node doesn't exist.
+ pub fn node_weight(&self, a: NodeIndex<Ix>) -> &N {
+ &self.nodes[a.index()]
+ }
+
+ /// Access the weight for node `a`, mutably.
+ ///
+ /// Also available with indexing syntax: `&mut graph[a]`.
+ ///
+ /// **Panics** if the node doesn't exist.
+ pub fn node_weight_mut(&mut self, a: NodeIndex<Ix>) -> &mut N {
+ &mut self.nodes[a.index()]
+ }
+
+ /// Access the weight for edge `e`.
+ ///
+ /// Also available with indexing syntax: `&graph[e]`.
+ ///
+ /// **Panics** if no edge exists between `a` and `b`.
+ pub fn edge_weight(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> &E {
+ let p = self.to_edge_position(a, b);
+ self.node_adjacencies[p].as_ref().unwrap()
+ }
+
+ /// Access the weight for edge `e`, mutably.
+ ///
+ /// Also available with indexing syntax: `&mut graph[e]`.
+ ///
+ /// **Panics** if no edge exists between `a` and `b`.
+ pub fn edge_weight_mut(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> &mut E {
+ let p = self.to_edge_position(a, b);
+ self.node_adjacencies[p].as_mut().unwrap()
+ }
+
+ /// Return an iterator of all nodes with an edge starting from `a`.
+ ///
+ /// - `Directed`: Outgoing edges from `a`.
+ /// - `Undirected`: All edges from or to `a`.
+ ///
+ /// Produces an empty iterator if the node doesn't exist.<br>
+ /// Iterator element type is [`NodeIndex<Ix>`](../graph/struct.NodeIndex.html).
+ pub fn neighbors(&self, a: NodeIndex<Ix>) -> Neighbors<Ty, Null, Ix> {
+ Neighbors(Edges::on_columns(a.index(), &self.node_adjacencies, self.node_capacity))
+ }
+
+ /// Return an iterator of all edges of `a`.
+ ///
+ /// - `Directed`: Outgoing edges from `a`.
+ /// - `Undirected`: All edges connected to `a`.
+ ///
+ /// Produces an empty iterator if the node doesn't exist.<br>
+ /// Iterator element type is [`Edges<E, Ix>`](../graph/struct.Edges.html).
+ pub fn edges(&self, a: NodeIndex<Ix>) -> Edges<Ty, Null, Ix> {
+ Edges::on_columns(a.index(), &self.node_adjacencies, self.node_capacity)
+ }
+
+ /// Create a new `MatrixGraph` from an iterable of edges.
+ ///
+ /// Node weights `N` are set to default values.
+ /// Edge weights `E` may either be specified in the list,
+ /// or they are filled with default values.
+ ///
+ /// Nodes are inserted automatically to match the edges.
+ ///
+ /// ```
+ /// use petgraph::matrix_graph::MatrixGraph;
+ ///
+ /// let gr = MatrixGraph::<(), i32>::from_edges(&[
+ /// (0, 1), (0, 2), (0, 3),
+ /// (1, 2), (1, 3),
+ /// (2, 3),
+ /// ]);
+ /// ```
+ pub fn from_edges<I>(iterable: I) -> Self
+ where I: IntoIterator,
+ I::Item: IntoWeightedEdge<E>,
+ <I::Item as IntoWeightedEdge<E>>::NodeId: Into<NodeIndex<Ix>>,
+ N: Default,
+ {
+ let mut g = Self::default();
+ g.extend_with_edges(iterable);
+ g
+ }
+
+ /// Extend the graph from an iterable of edges.
+ ///
+ /// Node weights `N` are set to default values.
+ /// Edge weights `E` may either be specified in the list,
+ /// or they are filled with default values.
+ ///
+ /// Nodes are inserted automatically to match the edges.
+ pub fn extend_with_edges<I>(&mut self, iterable: I)
+ where I: IntoIterator,
+ I::Item: IntoWeightedEdge<E>,
+ <I::Item as IntoWeightedEdge<E>>::NodeId: Into<NodeIndex<Ix>>,
+ N: Default,
+ {
+ for elt in iterable {
+ let (source, target, weight) = elt.into_weighted_edge();
+ let (source, target) = (source.into(), target.into());
+ let nx = cmp::max(source, target);
+ while nx.index() >= self.node_count() {
+ self.add_node(N::default());
+ }
+ self.add_edge(source, target, weight);
+ }
+ }
+}
+
+impl<N, E, Null: Nullable<Wrapped=E>, Ix: IndexType> MatrixGraph<N, E, Directed, Null, Ix> {
+ /// Return an iterator of all neighbors that have an edge between them and
+ /// `a`, in the specified direction.
+ /// If the graph's edges are undirected, this is equivalent to *.neighbors(a)*.
+ ///
+ /// - `Directed`, `Outgoing`: All edges from `a`.
+ /// - `Directed`, `Incoming`: All edges to `a`.
+ /// - `Undirected`: All edges from or to `a`.
+ ///
+ /// Produces an empty iterator if the node doesn't exist.<br>
+ /// Iterator element type is [`NodeIndex<Ix>`](../graph/struct.NodeIndex.html).
+ pub fn neighbors_directed(&self, a: NodeIndex<Ix>, d: Direction) -> Neighbors<Directed, Null, Ix> {
+ if d == Outgoing {
+ self.neighbors(a)
+ } else {
+ Neighbors(Edges::on_rows(a.index(), &self.node_adjacencies, self.node_capacity))
+ }
+ }
+
+ /// Return an iterator of all edges of `a`, in the specified direction.
+ ///
+ /// - `Directed`, `Outgoing`: All edges from `a`.
+ /// - `Directed`, `Incoming`: All edges to `a`.
+ /// - `Undirected`: All edges connected to `a`.
+ ///
+ /// Produces an empty iterator if the node `a` doesn't exist.<br>
+ /// Iterator element type is [`EdgeReference<E, Ix>`](../graph/struct.EdgeReference.html).
+ pub fn edges_directed(&self, a: NodeIndex<Ix>, d: Direction) -> Edges<Directed, Null, Ix> {
+ if d == Outgoing {
+ self.edges(a)
+ } else {
+ Edges::on_rows(a.index(), &self.node_adjacencies, self.node_capacity)
+ }
+ }
+}
+
+/// Iterator over the node identifiers of a graph.
+///
+/// Created from a call to [`.node_identifiers()`][1] on a [`MatrixGraph`][2].
+///
+/// [1]: ../visit/trait.IntoNodeIdentifiers.html#tymethod.node_identifiers
+/// [2]: struct.MatrixGraph.html
+pub struct NodeIdentifiers<'a, Ix> {
+ iter: IdIterator<'a>,
+ ix: PhantomData<Ix>,
+}
+
+impl<'a, Ix: IndexType> NodeIdentifiers<'a, Ix> {
+ fn new(iter: IdIterator<'a>) -> Self {
+ Self { iter, ix: PhantomData }
+ }
+}
+
+impl<'a, Ix: IndexType> Iterator for NodeIdentifiers<'a, Ix> {
+ type Item = NodeIndex<Ix>;
+
+ fn next(&mut self) -> Option<Self::Item> {
+ self.iter.next().map(NodeIndex::new)
+ }
+}
+
+/// Iterator over all nodes of a graph.
+///
+/// Created from a call to [`.node_references()`][1] on a [`MatrixGraph`][2].
+///
+/// [1]: ../visit/trait.IntoNodeReferences.html#tymethod.node_references
+/// [2]: struct.MatrixGraph.html
+pub struct NodeReferences<'a, N: 'a, Ix> {
+ nodes: &'a IdStorage<N>,
+ iter: IdIterator<'a>,
+ ix: PhantomData<Ix>,
+}
+
+impl<'a, N: 'a, Ix> NodeReferences<'a, N, Ix> {
+ fn new(nodes: &'a IdStorage<N>) -> Self {
+ NodeReferences {
+ nodes: nodes,
+ iter: nodes.iter_ids(),
+ ix: PhantomData,
+ }
+ }
+}
+
+impl<'a, N: 'a, Ix: IndexType> Iterator for NodeReferences<'a, N, Ix> {
+ type Item = (NodeIndex<Ix>, &'a N);
+
+ fn next(&mut self) -> Option<Self::Item> {
+ self.iter.next().map(|i| (NodeIndex::new(i), &self.nodes[i]))
+ }
+}
+
+/// Iterator over all edges of a graph.
+///
+/// Created from a call to [`.edge_references()`][1] on a [`MatrixGraph`][2].
+///
+/// [1]: ../visit/trait.IntoEdgeReferences.html#tymethod.edge_references
+/// [2]: struct.MatrixGraph.html
+pub struct EdgeReferences<'a, Ty: EdgeType, Null: 'a + Nullable, Ix> {
+ row: usize,
+ column: usize,
+ node_adjacencies: &'a [Null],
+ node_capacity: usize,
+ ty: PhantomData<Ty>,
+ ix: PhantomData<Ix>,
+}
+
+impl<'a, Ty: EdgeType, Null: 'a + Nullable, Ix> EdgeReferences<'a, Ty, Null, Ix> {
+ fn new(node_adjacencies: &'a [Null], node_capacity: usize) -> Self {
+ EdgeReferences {
+ row: 0, column: 0,
+ node_adjacencies: node_adjacencies,
+ node_capacity: node_capacity,
+ ty: PhantomData,
+ ix: PhantomData,
+ }
+ }
+}
+
+impl<'a, Ty: EdgeType, Null: Nullable, Ix: IndexType> Iterator for EdgeReferences<'a, Ty, Null, Ix> {
+ type Item = (NodeIndex<Ix>, NodeIndex<Ix>, &'a Null::Wrapped);
+
+ fn next(&mut self) -> Option<Self::Item> {
+ loop {
+ let (row, column) = (self.row, self.column);
+ if row >= self.node_capacity {
+ return None;
+ }
+
+ // By default, advance the column. Reset and advance the row if the column overflows.
+ //
+ // Note that for undirected graphs, we don't want to yield the same edge twice,
+ // therefore the maximum column length should be the index new after the row index.
+ self.column += 1;
+ let max_column_len = if !Ty::is_directed() { row + 1 } else { self.node_capacity };
+ if self.column >= max_column_len {
+ self.column = 0;
+ self.row += 1;
+ }
+
+ let p = to_linearized_matrix_position::<Ty>(row, column, self.node_capacity);
+ if let Some(e) = self.node_adjacencies[p].as_ref() {
+ return Some((NodeIndex::new(row), NodeIndex::new(column), e));
+ }
+ }
+ }
+}
+
+/// Iterator over the neighbors of a node.
+///
+/// Iterator element type is `NodeIndex<Ix>`.
+///
+/// Created with [`.neighbors()`][1], [`.neighbors_directed()`][2].
+///
+/// [1]: struct.MatrixGraph.html#method.neighbors
+/// [2]: struct.MatrixGraph.html#method.neighbors_directed
+pub struct Neighbors<'a, Ty: EdgeType, Null: 'a + Nullable, Ix>(Edges<'a, Ty, Null, Ix>);
+
+impl<'a, Ty: EdgeType, Null: Nullable, Ix: IndexType> Iterator for Neighbors<'a, Ty, Null, Ix> {
+ type Item = NodeIndex<Ix>;
+
+ fn next(&mut self) -> Option<Self::Item> {
+ self.0.next().map(|(_, b, _)| b)
+ }
+}
+
+enum NeighborIterDirection {
+ Rows,
+ Columns,
+}
+
+/// Iterator over the edges of from or to a node
+///
+/// Created with [`.edges()`][1], [`.edges_directed()`][2].
+///
+/// [1]: struct.MatrixGraph.html#method.edges
+/// [2]: struct.MatrixGraph.html#method.edges_directed
+pub struct Edges<'a, Ty: EdgeType, Null: 'a + Nullable, Ix> {
+ iter_direction: NeighborIterDirection,
+ node_adjacencies: &'a [Null],
+ node_capacity: usize,
+ row: usize,
+ column: usize,
+ ty: PhantomData<Ty>,
+ ix: PhantomData<Ix>,
+}
+
+impl<'a, Ty: EdgeType, Null: 'a + Nullable, Ix> Edges<'a, Ty, Null, Ix> {
+ fn on_columns(row: usize, node_adjacencies: &'a [Null], node_capacity: usize) -> Self {
+ Edges {
+ iter_direction: NeighborIterDirection::Columns,
+ node_adjacencies: node_adjacencies,
+ node_capacity: node_capacity,
+ row: row,
+ column: 0,
+ ty: PhantomData,
+ ix: PhantomData,
+ }
+ }
+
+ fn on_rows(column: usize, node_adjacencies: &'a [Null], node_capacity: usize) -> Self {
+ Edges {
+ iter_direction: NeighborIterDirection::Rows,
+ node_adjacencies: node_adjacencies,
+ node_capacity: node_capacity,
+ row: 0,
+ column: column,
+ ty: PhantomData,
+ ix: PhantomData,
+ }
+ }
+}
+
+impl<'a, Ty: EdgeType, Null: Nullable, Ix: IndexType> Iterator for Edges<'a, Ty, Null, Ix> {
+ type Item = (NodeIndex<Ix>, NodeIndex<Ix>, &'a Null::Wrapped);
+
+ fn next(&mut self) -> Option<Self::Item> {
+ use self::NeighborIterDirection::*;
+
+ loop {
+ let (row, column) = (self.row, self.column);
+ if row >= self.node_capacity || column >= self.node_capacity {
+ return None;
+ }
+
+ match self.iter_direction {
+ Rows => self.row += 1,
+ Columns => self.column += 1,
+ }
+
+ let p = to_linearized_matrix_position::<Ty>(row, column, self.node_capacity);
+ if let Some(e) = self.node_adjacencies[p].as_ref() {
+ let (a, b) = match self.iter_direction {
+ Rows => (column, row),
+ Columns => (row, column),
+ };
+
+ return Some((NodeIndex::new(a), NodeIndex::new(b), e));
+ }
+ }
+ }
+}
+
+#[inline]
+fn to_linearized_matrix_position<Ty: EdgeType>(row: usize, column: usize, width: usize) -> usize {
+ if Ty::is_directed() {
+ to_flat_square_matrix_position(row, column, width)
+ } else {
+ to_lower_triangular_matrix_position(row, column)
+ }
+}
+
+#[inline]
+fn extend_linearized_matrix<Ty: EdgeType, T: Default>(node_adjacencies: &mut Vec<T>, old_node_capacity: usize, min_node_capacity: usize) -> usize {
+ if Ty::is_directed() {
+ extend_flat_square_matrix(node_adjacencies, old_node_capacity, min_node_capacity)
+ } else {
+ extend_lower_triangular_matrix(node_adjacencies, min_node_capacity)
+ }
+}
+
+#[inline]
+fn to_flat_square_matrix_position(row: usize, column: usize, width: usize) -> usize {
+ row * width + column
+}
+
+#[inline]
+fn extend_flat_square_matrix<T: Default>(node_adjacencies: &mut Vec<T>, old_node_capacity: usize, min_node_capacity: usize) -> usize {
+ let min_node_capacity = (min_node_capacity + 1).next_power_of_two();
+
+ // Optimization: when resizing the matrix this way we skip the first few grows to make
+ // small matrices a bit faster to work with.
+ const MIN_CAPACITY: usize = 4;
+ let new_node_capacity = cmp::max(min_node_capacity, MIN_CAPACITY);
+
+ let mut new_node_adjacencies = vec![];
+ ensure_len(&mut new_node_adjacencies, new_node_capacity.pow(2));
+
+ for c in 0..old_node_capacity {
+ let pos = c * old_node_capacity;
+ let new_pos = c * new_node_capacity;
+
+ let mut old = &mut node_adjacencies[pos..pos + old_node_capacity];
+ let mut new = &mut new_node_adjacencies[new_pos..new_pos + old_node_capacity];
+
+ mem::swap(&mut old, &mut new);
+ }
+
+ mem::swap(node_adjacencies, &mut new_node_adjacencies);
+
+ new_node_capacity
+}
+
+#[inline]
+fn to_lower_triangular_matrix_position(row: usize, column: usize) -> usize {
+ let (row, column) = if row > column { (row, column) } else { (column, row) };
+ (row * (row + 1)) / 2 + column
+}
+
+#[inline]
+fn extend_lower_triangular_matrix<T: Default>(node_adjacencies: &mut Vec<T>, new_node_capacity: usize) -> usize {
+ let max_pos = to_lower_triangular_matrix_position(new_node_capacity, new_node_capacity);
+ ensure_len(node_adjacencies, max_pos + 1);
+ new_node_capacity + 1
+}
+
+/// Grow a Vec by appending the type's default value the `size` is reached.
+fn ensure_len<T: Default>(v: &mut Vec<T>, size: usize) {
+ if let Some(n) = size.checked_sub(v.len()) {
+ v.reserve(n);
+ for _ in 0..n {
+ v.push(T::default());
+ }
+ }
+}
+
+#[derive(Clone)]
+struct IdStorage<T> {
+ elements: Vec<Option<T>>,
+ upper_bound: usize,
+ removed_ids: IndexSet<usize>,
+}
+
+impl<T> IdStorage<T> {
+ fn with_capacity(capacity: usize) -> Self {
+ IdStorage {
+ elements: Vec::with_capacity(capacity),
+ upper_bound: 0,
+ removed_ids: IndexSet::new(),
+ }
+ }
+
+ fn add(&mut self, element: T) -> usize {
+ let id = if let Some(id) = self.removed_ids.pop() {
+ id
+ } else {
+ let id = self.upper_bound;
+ self.upper_bound += 1;
+
+ ensure_len(&mut self.elements, id + 1);
+
+ id
+ };
+
+ self.elements[id] = Some(element);
+
+ id
+ }
+
+ fn remove(&mut self, id: usize) -> T {
+ let data = self.elements[id].take().unwrap();
+ if self.upper_bound - id == 1 {
+ self.upper_bound -= 1;
+ } else {
+ self.removed_ids.insert(id);
+ }
+ data
+ }
+
+ fn clear(&mut self) {
+ self.upper_bound = 0;
+ self.elements.clear();
+ self.removed_ids.clear();
+ }
+
+ #[inline]
+ fn len(&self) -> usize {
+ self.upper_bound - self.removed_ids.len()
+ }
+
+ fn iter_ids(&self) -> IdIterator {
+ IdIterator {
+ upper_bound: self.upper_bound,
+ removed_ids: &self.removed_ids,
+ current: None,
+ }
+ }
+}
+
+impl<T> Index<usize> for IdStorage<T> {
+ type Output = T;
+ fn index(&self, index: usize) -> &T {
+ self.elements[index].as_ref().unwrap()
+ }
+}
+
+impl<T> IndexMut<usize> for IdStorage<T> {
+ fn index_mut(&mut self, index: usize) -> &mut T {
+ self.elements[index].as_mut().unwrap()
+ }
+}
+
+struct IdIterator<'a> {
+ upper_bound: usize,
+ removed_ids: &'a IndexSet<usize>,
+ current: Option<usize>,
+}
+
+impl<'a> Iterator for IdIterator<'a> {
+ type Item = usize;
+
+ fn next(&mut self) -> Option<Self::Item> {
+ // initialize / advance
+ let current = {
+ if self.current.is_none() {
+ self.current = Some(0);
+ self.current.as_mut().unwrap()
+ } else {
+ let current = self.current.as_mut().unwrap();
+ *current += 1;
+ current
+ }
+ };
+
+ // skip removed ids
+ while self.removed_ids.contains(current) && *current < self.upper_bound {
+ *current += 1;
+ }
+
+ if *current < self.upper_bound {
+ Some(*current)
+ } else {
+ None
+ }
+ }
+}
+
+/// Create a new empty `MatrixGraph`.
+impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> Default for MatrixGraph<N, E, Ty, Null, Ix> {
+ fn default() -> Self {
+ Self::with_capacity(0)
+ }
+}
+
+impl<N, E> MatrixGraph<N, E, Directed> {
+ /// Create a new `MatrixGraph` with directed edges.
+ ///
+ /// This is a convenience method. Use `MatrixGraph::with_capacity` or `MatrixGraph::default` for
+ /// a constructor that is generic in all the type parameters of `MatrixGraph`.
+ pub fn new() -> Self {
+ MatrixGraph::default()
+ }
+}
+
+impl<N, E> MatrixGraph<N, E, Undirected> {
+ /// Create a new `MatrixGraph` with undirected edges.
+ ///
+ /// This is a convenience method. Use `MatrixGraph::with_capacity` or `MatrixGraph::default` for
+ /// a constructor that is generic in all the type parameters of `MatrixGraph`.
+ pub fn new_undirected() -> Self {
+ MatrixGraph::default()
+ }
+}
+
+/// Index the `MatrixGraph` by `NodeIndex` to access node weights.
+///
+/// **Panics** if the node doesn't exist.
+impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> Index<NodeIndex<Ix>> for MatrixGraph<N, E, Ty, Null, Ix> {
+ type Output = N;
+
+ fn index(&self, ax: NodeIndex<Ix>) -> &N {
+ self.node_weight(ax)
+ }
+}
+
+/// Index the `MatrixGraph` by `NodeIndex` to access node weights.
+///
+/// **Panics** if the node doesn't exist.
+impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> IndexMut<NodeIndex<Ix>> for MatrixGraph<N, E, Ty, Null, Ix> {
+ fn index_mut(&mut self, ax: NodeIndex<Ix>) -> &mut N {
+ self.node_weight_mut(ax)
+ }
+}
+
+impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> NodeCount for MatrixGraph<N, E, Ty, Null, Ix> {
+ fn node_count(&self) -> usize {
+ MatrixGraph::node_count(self)
+ }
+}
+
+/// Index the `MatrixGraph` by `NodeIndex` pair to access edge weights.
+///
+/// Also available with indexing syntax: `&graph[e]`.
+///
+/// **Panics** if no edge exists between `a` and `b`.
+impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> Index<(NodeIndex<Ix>, NodeIndex<Ix>)> for MatrixGraph<N, E, Ty, Null, Ix> {
+ type Output = E;
+
+ fn index(&self, (ax, bx): (NodeIndex<Ix>, NodeIndex<Ix>)) -> &E {
+ self.edge_weight(ax, bx)
+ }
+}
+
+/// Index the `MatrixGraph` by `NodeIndex` pair to access edge weights.
+///
+/// Also available with indexing syntax: `&mut graph[e]`.
+///
+/// **Panics** if no edge exists between `a` and `b`.
+impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> IndexMut<(NodeIndex<Ix>, NodeIndex<Ix>)> for MatrixGraph<N, E, Ty, Null, Ix> {
+ fn index_mut(&mut self, (ax, bx): (NodeIndex<Ix>, NodeIndex<Ix>)) -> &mut E {
+ self.edge_weight_mut(ax, bx)
+ }
+}
+
+impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> GetAdjacencyMatrix for MatrixGraph<N, E, Ty, Null, Ix> {
+ type AdjMatrix = ();
+
+ fn adjacency_matrix(&self) -> Self::AdjMatrix {
+ }
+
+ fn is_adjacent(&self, _: &Self::AdjMatrix, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool {
+ MatrixGraph::has_edge(self, a, b)
+ }
+}
+
+impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> Visitable for MatrixGraph<N, E, Ty, Null, Ix> {
+ type Map = FixedBitSet;
+
+ fn visit_map(&self) -> FixedBitSet {
+ FixedBitSet::with_capacity(self.node_count())
+ }
+
+ fn reset_map(&self, map: &mut Self::Map) {
+ map.clear();
+ map.grow(self.node_count());
+ }
+}
+
+impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> GraphBase for MatrixGraph<N, E, Ty, Null, Ix> {
+ type NodeId = NodeIndex<Ix>;
+ type EdgeId = (NodeIndex<Ix>, NodeIndex<Ix>);
+}
+
+impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> GraphProp for MatrixGraph<N, E, Ty, Null, Ix> {
+ type EdgeType = Ty;
+}
+
+impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> Data for MatrixGraph<N, E, Ty, Null, Ix> {
+ type NodeWeight = N;
+ type EdgeWeight = E;
+}
+
+impl<'a, N, E: 'a, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> IntoNodeIdentifiers for &'a MatrixGraph<N, E, Ty, Null, Ix> {
+ type NodeIdentifiers = NodeIdentifiers<'a, Ix>;
+
+ fn node_identifiers(self) -> Self::NodeIdentifiers {
+ NodeIdentifiers::new(self.nodes.iter_ids())
+ }
+}
+
+impl<'a, N, E: 'a, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> IntoNeighbors for &'a MatrixGraph<N, E, Ty, Null, Ix> {
+ type Neighbors = Neighbors<'a, Ty, Null, Ix>;
+
+ fn neighbors(self, a: NodeIndex<Ix>) -> Self::Neighbors {
+ MatrixGraph::neighbors(self, a)
+ }
+}
+
+impl<'a, N, E: 'a, Null: Nullable<Wrapped=E>, Ix: IndexType> IntoNeighborsDirected for &'a MatrixGraph<N, E, Directed, Null, Ix> {
+ type NeighborsDirected = Neighbors<'a, Directed, Null, Ix>;
+
+ fn neighbors_directed(self, a: NodeIndex<Ix>, d: Direction) -> Self::NeighborsDirected {
+ MatrixGraph::neighbors_directed(self, a, d)
+ }
+}
+
+impl<'a, N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> IntoNodeReferences for &'a MatrixGraph<N, E, Ty, Null, Ix> {
+ type NodeRef = (NodeIndex<Ix>, &'a N);
+ type NodeReferences = NodeReferences<'a, N, Ix>;
+ fn node_references(self) -> Self::NodeReferences {
+ NodeReferences::new(&self.nodes)
+ }
+}
+
+impl<'a, N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> IntoEdgeReferences for &'a MatrixGraph<N, E, Ty, Null, Ix> {
+ type EdgeRef = (NodeIndex<Ix>, NodeIndex<Ix>, &'a E);
+ type EdgeReferences = EdgeReferences<'a, Ty, Null, Ix>;
+ fn edge_references(self) -> Self::EdgeReferences {
+ EdgeReferences::new(&self.node_adjacencies, self.node_capacity)
+ }
+}
+
+impl<'a, N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> IntoEdges for &'a MatrixGraph<N, E, Ty, Null, Ix> {
+ type Edges = Edges<'a, Ty, Null, Ix>;
+ fn edges(self, a: Self::NodeId) -> Self::Edges {
+ MatrixGraph::edges(self, a)
+ }
+}
+
+impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> NodeIndexable for MatrixGraph<N, E, Ty, Null, Ix> {
+ fn node_bound(&self) -> usize {
+ self.node_count()
+ }
+
+ fn to_index(&self, ix: NodeIndex<Ix>) -> usize {
+ ix.index()
+ }
+
+ fn from_index(&self, ix: usize) -> Self::NodeId {
+ NodeIndex::new(ix)
+ }
+}
+
+impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> NodeCompactIndexable for MatrixGraph<N, E, Ty, Null, Ix> {
+}
+
+impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped=E>, Ix: IndexType> Build for MatrixGraph<N, E, Ty, Null, Ix> {
+ fn add_node(&mut self, weight: Self::NodeWeight) -> Self::NodeId {
+ self.add_node(weight)
+ }
+
+ fn add_edge(&mut self, a: Self::NodeId, b: Self::NodeId, weight: Self::EdgeWeight) -> Option<Self::EdgeId> {
+ if !self.has_edge(a, b) {
+ MatrixGraph::update_edge(self, a, b, weight);
+ Some((a, b))
+ } else {
+ None
+ }
+ }
+
+ fn update_edge(&mut self, a: Self::NodeId, b: Self::NodeId, weight: Self::EdgeWeight) -> Self::EdgeId {
+ MatrixGraph::update_edge(self, a, b, weight);
+ (a, b)
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use super::*;
+ use crate::{Outgoing, Incoming};
+
+ #[test]
+ fn test_new() {
+ let g = MatrixGraph::<i32, i32>::new();
+ assert_eq!(g.node_count(), 0);
+ assert_eq!(g.edge_count(), 0);
+ }
+
+ #[test]
+ fn test_default() {
+ let g = MatrixGraph::<i32, i32>::default();
+ assert_eq!(g.node_count(), 0);
+ assert_eq!(g.edge_count(), 0);
+ }
+
+ #[test]
+ fn test_with_capacity() {
+ let g = MatrixGraph::<i32, i32>::with_capacity(10);
+ assert_eq!(g.node_count(), 0);
+ assert_eq!(g.edge_count(), 0);
+ }
+
+ #[test]
+ fn test_node_indexing() {
+ let mut g: MatrixGraph<char, ()> = MatrixGraph::new();
+ let a = g.add_node('a');
+ let b = g.add_node('b');
+ assert_eq!(g.node_count(), 2);
+ assert_eq!(g.edge_count(), 0);
+ assert_eq!(g[a], 'a');
+ assert_eq!(g[b], 'b');
+ }
+
+ #[test]
+ fn test_remove_node() {
+ let mut g: MatrixGraph<char, ()> = MatrixGraph::new();
+ let a = g.add_node('a');
+
+ g.remove_node(a);
+
+ assert_eq!(g.node_count(), 0);
+ assert_eq!(g.edge_count(), 0);
+ }
+
+ #[test]
+ fn test_add_edge() {
+ let mut g = MatrixGraph::new();
+ let a = g.add_node('a');
+ let b = g.add_node('b');
+ let c = g.add_node('c');
+ g.add_edge(a, b, ());
+ g.add_edge(b, c, ());
+ assert_eq!(g.node_count(), 3);
+ assert_eq!(g.edge_count(), 2);
+ }
+
+ #[test]
+ fn test_add_edge_with_weights() {
+ let mut g = MatrixGraph::new();
+ let a = g.add_node('a');
+ let b = g.add_node('b');
+ let c = g.add_node('c');
+ g.add_edge(a, b, true);
+ g.add_edge(b, c, false);
+ assert_eq!(*g.edge_weight(a, b), true);
+ assert_eq!(*g.edge_weight(b, c), false);
+ }
+
+ #[test]
+ fn test_add_edge_with_weights_undirected() {
+ let mut g = MatrixGraph::new_undirected();
+ let a = g.add_node('a');
+ let b = g.add_node('b');
+ let c = g.add_node('c');
+ let d = g.add_node('d');
+ g.add_edge(a, b, "ab");
+ g.add_edge(a, a, "aa");
+ g.add_edge(b, c, "bc");
+ g.add_edge(d, d, "dd");
+ assert_eq!(*g.edge_weight(a, b), "ab");
+ assert_eq!(*g.edge_weight(b, c), "bc");
+ }
+
+ /// Shorthand for `.collect::<Vec<_>>()`
+ trait IntoVec<T> {
+ fn into_vec(self) -> Vec<T>;
+ }
+
+ impl<It, T> IntoVec<T> for It
+ where It: Iterator<Item=T>,
+ {
+ fn into_vec(self) -> Vec<T> {
+ self.collect()
+ }
+ }
+
+ #[test]
+ fn test_clear() {
+ let mut g = MatrixGraph::new();
+ let a = g.add_node('a');
+ let b = g.add_node('b');
+ let c = g.add_node('c');
+ assert_eq!(g.node_count(), 3);
+
+ g.add_edge(a, b, ());
+ g.add_edge(b, c, ());
+ g.add_edge(c, a, ());
+ assert_eq!(g.edge_count(), 3);
+
+ g.clear();
+
+ assert_eq!(g.node_count(), 0);
+ assert_eq!(g.edge_count(), 0);
+
+ let a = g.add_node('a');
+ let b = g.add_node('b');
+ let c = g.add_node('c');
+ assert_eq!(g.node_count(), 3);
+ assert_eq!(g.edge_count(), 0);
+
+ assert_eq!(g.neighbors_directed(a, Incoming).into_vec(), vec![]);
+ assert_eq!(g.neighbors_directed(b, Incoming).into_vec(), vec![]);
+ assert_eq!(g.neighbors_directed(c, Incoming).into_vec(), vec![]);
+
+ assert_eq!(g.neighbors_directed(a, Outgoing).into_vec(), vec![]);
+ assert_eq!(g.neighbors_directed(b, Outgoing).into_vec(), vec![]);
+ assert_eq!(g.neighbors_directed(c, Outgoing).into_vec(), vec![]);
+ }
+
+ #[test]
+ fn test_clear_undirected() {
+ let mut g = MatrixGraph::new_undirected();
+ let a = g.add_node('a');
+ let b = g.add_node('b');
+ let c = g.add_node('c');
+ assert_eq!(g.node_count(), 3);
+
+ g.add_edge(a, b, ());
+ g.add_edge(b, c, ());
+ g.add_edge(c, a, ());
+ assert_eq!(g.edge_count(), 3);
+
+ g.clear();
+
+ assert_eq!(g.node_count(), 0);
+ assert_eq!(g.edge_count(), 0);
+
+ let a = g.add_node('a');
+ let b = g.add_node('b');
+ let c = g.add_node('c');
+ assert_eq!(g.node_count(), 3);
+ assert_eq!(g.edge_count(), 0);
+
+ assert_eq!(g.neighbors(a).into_vec(), vec![]);
+ assert_eq!(g.neighbors(b).into_vec(), vec![]);
+ assert_eq!(g.neighbors(c).into_vec(), vec![]);
+ }
+
+ /// Helper trait for always sorting before testing.
+ trait IntoSortedVec<T> {
+ fn into_sorted_vec(self) -> Vec<T>;
+ }
+
+ impl<It, T> IntoSortedVec<T> for It
+ where It: Iterator<Item=T>,
+ T: Ord,
+ {
+ fn into_sorted_vec(self) -> Vec<T> {
+ let mut v: Vec<T> = self.collect();
+ v.sort();
+ v
+ }
+ }
+
+ /// Helper macro for always sorting before testing.
+ macro_rules! sorted_vec {
+ ($($x:expr),*) => {
+ {
+ let mut v = vec![$($x,)*];
+ v.sort();
+ v
+ }
+ }
+ }
+
+ #[test]
+ fn test_neighbors() {
+ let mut g = MatrixGraph::new();
+ let a = g.add_node('a');
+ let b = g.add_node('b');
+ let c = g.add_node('c');
+ g.add_edge(a, b, ());
+ g.add_edge(a, c, ());
+
+ let a_neighbors = g.neighbors(a).into_sorted_vec();
+ assert_eq!(a_neighbors, sorted_vec![b, c]);
+
+ let b_neighbors = g.neighbors(b).into_sorted_vec();
+ assert_eq!(b_neighbors, vec![]);
+
+ let c_neighbors = g.neighbors(c).into_sorted_vec();
+ assert_eq!(c_neighbors, vec![]);
+ }
+
+ #[test]
+ fn test_neighbors_undirected() {
+ let mut g = MatrixGraph::new_undirected();
+ let a = g.add_node('a');
+ let b = g.add_node('b');
+ let c = g.add_node('c');
+ g.add_edge(a, b, ());
+ g.add_edge(a, c, ());
+
+ let a_neighbors = g.neighbors(a).into_sorted_vec();
+ assert_eq!(a_neighbors, sorted_vec![b, c]);
+
+ let b_neighbors = g.neighbors(b).into_sorted_vec();
+ assert_eq!(b_neighbors, sorted_vec![a]);
+
+ let c_neighbors = g.neighbors(c).into_sorted_vec();
+ assert_eq!(c_neighbors, sorted_vec![a]);
+ }
+
+ #[test]
+ fn test_remove_node_and_edges() {
+ let mut g = MatrixGraph::new();
+ let a = g.add_node('a');
+ let b = g.add_node('b');
+ let c = g.add_node('c');
+ g.add_edge(a, b, ());
+ g.add_edge(b, c, ());
+ g.add_edge(c, a, ());
+
+ // removing b should break the `a -> b` and `b -> c` edges
+ g.remove_node(b);
+
+ assert_eq!(g.node_count(), 2);
+
+ let a_neighbors = g.neighbors(a).into_sorted_vec();
+ assert_eq!(a_neighbors, vec![]);
+
+ let c_neighbors = g.neighbors(c).into_sorted_vec();
+ assert_eq!(c_neighbors, vec![a]);
+ }
+
+ #[test]
+ fn test_remove_node_and_edges_undirected() {
+ let mut g = UnMatrix::new_undirected();
+ let a = g.add_node('a');
+ let b = g.add_node('b');
+ let c = g.add_node('c');
+ g.add_edge(a, b, ());
+ g.add_edge(b, c, ());
+ g.add_edge(c, a, ());
+
+ // removing a should break the `a - b` and `a - c` edges
+ g.remove_node(a);
+
+ assert_eq!(g.node_count(), 2);
+
+ let b_neighbors = g.neighbors(b).into_sorted_vec();
+ assert_eq!(b_neighbors, vec![c]);
+
+ let c_neighbors = g.neighbors(c).into_sorted_vec();
+ assert_eq!(c_neighbors, vec![b]);
+ }
+
+ #[test]
+ fn test_node_identifiers() {
+ let mut g = MatrixGraph::new();
+ let a = g.add_node('a');
+ let b = g.add_node('b');
+ let c = g.add_node('c');
+ let d = g.add_node('c');
+ g.add_edge(a, b, ());
+ g.add_edge(a, c, ());
+
+ let node_ids = g.node_identifiers().into_sorted_vec();
+ assert_eq!(node_ids, sorted_vec![a, b, c, d]);
+ }
+
+ #[test]
+ fn test_edges_directed() {
+ let g: MatrixGraph<char, bool> = MatrixGraph::from_edges(&[
+ (0, 5), (0, 2), (0, 3), (0, 1),
+ (1, 3),
+ (2, 3), (2, 4),
+ (4, 0),
+ (6, 6),
+ ]);
+
+ assert_eq!(g.edges_directed(node_index(0), Outgoing).count(), 4);
+ assert_eq!(g.edges_directed(node_index(1), Outgoing).count(), 1);
+ assert_eq!(g.edges_directed(node_index(2), Outgoing).count(), 2);
+ assert_eq!(g.edges_directed(node_index(3), Outgoing).count(), 0);
+ assert_eq!(g.edges_directed(node_index(4), Outgoing).count(), 1);
+ assert_eq!(g.edges_directed(node_index(5), Outgoing).count(), 0);
+ assert_eq!(g.edges_directed(node_index(6), Outgoing).count(), 1);
+
+ assert_eq!(g.edges_directed(node_index(0), Incoming).count(), 1);
+ assert_eq!(g.edges_directed(node_index(1), Incoming).count(), 1);
+ assert_eq!(g.edges_directed(node_index(2), Incoming).count(), 1);
+ assert_eq!(g.edges_directed(node_index(3), Incoming).count(), 3);
+ assert_eq!(g.edges_directed(node_index(4), Incoming).count(), 1);
+ assert_eq!(g.edges_directed(node_index(5), Incoming).count(), 1);
+ assert_eq!(g.edges_directed(node_index(6), Incoming).count(), 1);
+ }
+
+ #[test]
+ fn test_edges_undirected() {
+ let g: UnMatrix<char, bool> = UnMatrix::from_edges(&[
+ (0, 5), (0, 2), (0, 3), (0, 1),
+ (1, 3),
+ (2, 3), (2, 4),
+ (4, 0),
+ (6, 6),
+ ]);
+
+ assert_eq!(g.edges(node_index(0)).count(), 5);
+ assert_eq!(g.edges(node_index(1)).count(), 2);
+ assert_eq!(g.edges(node_index(2)).count(), 3);
+ assert_eq!(g.edges(node_index(3)).count(), 3);
+ assert_eq!(g.edges(node_index(4)).count(), 2);
+ assert_eq!(g.edges(node_index(5)).count(), 1);
+ assert_eq!(g.edges(node_index(6)).count(), 1);
+ }
+
+ #[test]
+ fn test_edges_of_absent_node_is_empty_iterator() {
+ let g: MatrixGraph<char, bool> = MatrixGraph::new();
+ assert_eq!(g.edges(node_index(0)).count(), 0);
+ }
+
+ #[test]
+ fn test_neighbors_of_absent_node_is_empty_iterator() {
+ let g: MatrixGraph<char, bool> = MatrixGraph::new();
+ assert_eq!(g.neighbors(node_index(0)).count(), 0);
+ }
+
+ #[test]
+ fn test_edge_references() {
+ let g: MatrixGraph<char, bool> = MatrixGraph::from_edges(&[
+ (0, 5), (0, 2), (0, 3), (0, 1),
+ (1, 3),
+ (2, 3), (2, 4),
+ (4, 0),
+ (6, 6),
+ ]);
+
+ assert_eq!(g.edge_references().count(), 9);
+ }
+
+ #[test]
+ fn test_edge_references_undirected() {
+ let g: UnMatrix<char, bool> = UnMatrix::from_edges(&[
+ (0, 5), (0, 2), (0, 3), (0, 1),
+ (1, 3),
+ (2, 3), (2, 4),
+ (4, 0),
+ (6, 6),
+ ]);
+
+ assert_eq!(g.edge_references().count(), 9);
+ }
+
+ #[test]
+ fn test_id_storage() {
+ use super::IdStorage;
+
+ let mut storage: IdStorage<char> = IdStorage::with_capacity(0);
+ let a = storage.add('a');
+ let b = storage.add('b');
+ let c = storage.add('c');
+
+ assert!(a < b && b < c);
+
+ // list IDs
+ assert_eq!(storage.iter_ids().into_vec(), vec![a, b, c]);
+
+ storage.remove(b);
+
+ // re-use of IDs
+ let bb = storage.add('B');
+ assert_eq!(b, bb);
+
+ // list IDs
+ assert_eq!(storage.iter_ids().into_vec(), vec![a, b, c]);
+ }
+
+ #[test]
+ fn test_not_zero() {
+ let mut g: MatrixGraph<(), i32, Directed, NotZero<i32>> = MatrixGraph::default();
+
+ let a = g.add_node(());
+ let b = g.add_node(());
+
+ assert!(!g.has_edge(a, b));
+ assert_eq!(g.edge_count(), 0);
+
+ g.add_edge(a, b, 12);
+
+ assert!(g.has_edge(a, b));
+ assert_eq!(g.edge_count(), 1);
+ assert_eq!(g.edge_weight(a, b), &12);
+
+ g.remove_edge(a, b);
+
+ assert!(!g.has_edge(a, b));
+ assert_eq!(g.edge_count(), 0);
+ }
+
+ #[test]
+ #[should_panic]
+ fn test_not_zero_asserted() {
+ let mut g: MatrixGraph<(), i32, Directed, NotZero<i32>> = MatrixGraph::default();
+
+ let a = g.add_node(());
+ let b = g.add_node(());
+
+ g.add_edge(a, b, 0); // this should trigger an assertion
+ }
+
+ #[test]
+ fn test_not_zero_float() {
+ let mut g: MatrixGraph<(), f32, Directed, NotZero<f32>> = MatrixGraph::default();
+
+ let a = g.add_node(());
+ let b = g.add_node(());
+
+ assert!(!g.has_edge(a, b));
+ assert_eq!(g.edge_count(), 0);
+
+ g.add_edge(a, b, 12.);
+
+ assert!(g.has_edge(a, b));
+ assert_eq!(g.edge_count(), 1);
+ assert_eq!(g.edge_weight(a, b), &12.);
+
+ g.remove_edge(a, b);
+
+ assert!(!g.has_edge(a, b));
+ assert_eq!(g.edge_count(), 0);
+ }
+}
diff --git a/src/prelude.rs b/src/prelude.rs
index 51602c9..d35161e 100644
--- a/src/prelude.rs
+++ b/src/prelude.rs
@@ -6,7 +6,7 @@
//! ```
#[doc(no_inline)]
-pub use graph::{
+pub use crate::graph::{
Graph,
NodeIndex,
EdgeIndex,
@@ -15,26 +15,26 @@
};
#[cfg(feature = "graphmap")]
#[doc(no_inline)]
-pub use graphmap::{
+pub use crate::graphmap::{
GraphMap,
DiGraphMap,
UnGraphMap,
};
#[doc(no_inline)]
#[cfg(feature = "stable_graph")]
-pub use stable_graph::{
+pub use crate::stable_graph::{
StableGraph,
StableDiGraph,
StableUnGraph,
};
#[doc(no_inline)]
-pub use visit::{
+pub use crate::visit::{
Bfs,
Dfs,
DfsPostOrder,
};
#[doc(no_inline)]
-pub use ::{
+pub use crate::{
Direction,
Incoming,
Outgoing,
@@ -43,6 +43,6 @@
};
#[doc(no_inline)]
-pub use visit::{
+pub use crate::visit::{
EdgeRef,
};
diff --git a/src/quickcheck.rs b/src/quickcheck.rs
index bda1594..7ce6cad 100644
--- a/src/quickcheck.rs
+++ b/src/quickcheck.rs
@@ -1,23 +1,23 @@
extern crate quickcheck;
use self::quickcheck::{Gen, Arbitrary};
-use {
+use crate::{
Graph,
EdgeType,
};
-use graph::{
+use crate::graph::{
IndexType,
node_index,
};
#[cfg(feature = "stable_graph")]
-use stable_graph::StableGraph;
+use crate::stable_graph::StableGraph;
#[cfg(feature = "graphmap")]
-use graphmap::{
+use crate::graphmap::{
GraphMap,
NodeTrait,
};
-use visit::NodeIndexable;
+use crate::visit::NodeIndexable;
/// Return a random float in the range [0, 1.)
fn random_01<G: Gen>(g: &mut G) -> f64 {
@@ -71,7 +71,7 @@
// shrink the graph by splitting it in two by a very
// simple algorithm, just even and odd node indices
- fn shrink(&self) -> Box<Iterator<Item=Self>> {
+ fn shrink(&self) -> Box<dyn Iterator<Item=Self>> {
let self_ = self.clone();
Box::new((0..2).filter_map(move |x| {
let gr = self_.filter_map(|i, w| {
@@ -149,7 +149,7 @@
// shrink the graph by splitting it in two by a very
// simple algorithm, just even and odd node indices
- fn shrink(&self) -> Box<Iterator<Item=Self>> {
+ fn shrink(&self) -> Box<dyn Iterator<Item=Self>> {
let self_ = self.clone();
Box::new((0..2).filter_map(move |x| {
let gr = self_.filter_map(|i, w| {
diff --git a/src/traits_graph.rs b/src/traits_graph.rs
index 90e5fba..1eef177 100644
--- a/src/traits_graph.rs
+++ b/src/traits_graph.rs
@@ -11,10 +11,10 @@
NodeIndex,
};
#[cfg(feature = "stable_graph")]
-use stable_graph::StableGraph;
+use crate::stable_graph::StableGraph;
#[cfg(feature = "stable_graph")]
-use visit::{NodeIndexable, IntoEdgeReferences};
-use visit::EdgeRef;
+use crate::visit::{NodeIndexable, IntoEdgeReferences};
+use crate::visit::EdgeRef;
use super::visit::GetAdjacencyMatrix;
diff --git a/src/unionfind.rs b/src/unionfind.rs
index 6521468..986d60d 100644
--- a/src/unionfind.rs
+++ b/src/unionfind.rs
@@ -33,6 +33,13 @@
xs.get_unchecked(index)
}
+#[inline]
+unsafe fn get_unchecked_mut<K>(xs: &mut [K], index: usize) -> &mut K
+{
+ debug_assert!(index < xs.len());
+ xs.get_unchecked_mut(index)
+}
+
impl<K> UnionFind<K>
where K: IndexType
{
@@ -79,17 +86,22 @@
}
}
- unsafe fn find_mut_recursive(&mut self, x: K) -> K
+ unsafe fn find_mut_recursive(&mut self, mut x: K) -> K
{
- let xparent = *get_unchecked(&self.parent, x.index());
- if xparent != x {
- let xrep = self.find_mut_recursive(xparent);
- let xparent = self.parent.get_unchecked_mut(x.index());
- *xparent = xrep;
- *xparent
- } else {
- xparent
+ let mut parent = *get_unchecked(&self.parent, x.index());
+ while parent != x {
+ let grandparent = *get_unchecked(&self.parent, parent.index());
+ *get_unchecked_mut(&mut self.parent, x.index()) = grandparent;
+ x = parent;
+ parent = grandparent;
}
+ x
+ }
+
+ /// Returns `true` if the given elements belong to the same set, and returns
+ /// `false` otherwise.
+ pub fn equiv(&self, x: K, y: K) -> bool {
+ self.find(x) == self.find(y)
}
diff --git a/src/visit/dfsvisit.rs b/src/visit/dfsvisit.rs
index 79df937..5ac93c7 100644
--- a/src/visit/dfsvisit.rs
+++ b/src/visit/dfsvisit.rs
@@ -1,7 +1,7 @@
-use visit::IntoNeighbors;
-use visit::{VisitMap, Visitable};
+use crate::visit::IntoNeighbors;
+use crate::visit::{VisitMap, Visitable};
/// Strictly monotonically increasing event time for a depth first search.
#[derive(Copy, Clone, Debug, PartialEq, PartialOrd, Eq, Ord, Default, Hash)]
@@ -32,7 +32,7 @@
x => if x.should_break() {
return x;
} else if x.should_prune() {
- $p;
+ $p
}
}
}
diff --git a/src/visit/filter.rs b/src/visit/filter.rs
index cb64c79..7f7c568 100644
--- a/src/visit/filter.rs
+++ b/src/visit/filter.rs
@@ -1,11 +1,11 @@
-use prelude::*;
+use crate::prelude::*;
use fixedbitset::FixedBitSet;
use std::collections::HashSet;
use std::marker::PhantomData;
-use visit::{
+use crate::visit::{
GraphBase,
GraphProp,
IntoEdgeReferences,
@@ -20,8 +20,8 @@
VisitMap,
Visitable,
};
-use visit::{Data, NodeCompactIndexable, NodeCount};
-use data::{DataMap};
+use crate::visit::{Data, NodeCompactIndexable, NodeCount};
+use crate::data::{DataMap};
/// A graph filter for nodes.
pub trait FilterNode<N>
diff --git a/src/visit/mod.rs b/src/visit/mod.rs
index 7383497..d9351f9 100644
--- a/src/visit/mod.rs
+++ b/src/visit/mod.rs
@@ -55,26 +55,26 @@
};
use std::hash::{Hash, BuildHasher};
-use prelude::{Graph, Direction};
+use crate::prelude::{Graph, Direction};
#[cfg(feature = "graphmap")]
-use prelude::GraphMap;
+use crate::prelude::GraphMap;
#[cfg(feature = "stable_graph")]
-use prelude::StableGraph;
-use graph::{NodeIndex};
+use crate::prelude::StableGraph;
+use crate::graph::{NodeIndex};
use super::{
graph,
EdgeType,
};
-use graph::{
+use crate::graph::{
IndexType,
};
#[cfg(feature = "stable_graph")]
-use stable_graph;
-use graph::Frozen;
+use crate::stable_graph;
+use crate::graph::Frozen;
#[cfg(feature = "graphmap")]
-use graphmap::{
+use crate::graphmap::{
self,
NodeTrait,
};
diff --git a/src/visit/reversed.rs b/src/visit/reversed.rs
index 9380aa3..29c6d48 100644
--- a/src/visit/reversed.rs
+++ b/src/visit/reversed.rs
@@ -1,10 +1,10 @@
-use ::{
+use crate::{
Direction,
Incoming,
};
-use visit::{
+use crate::visit::{
GraphBase,
GraphRef,
IntoNodeIdentifiers,
diff --git a/src/visit/traversal.rs b/src/visit/traversal.rs
index d48d083..3a40e7c 100644
--- a/src/visit/traversal.rs
+++ b/src/visit/traversal.rs
@@ -1,5 +1,5 @@
-use {Incoming};
+use crate::{Incoming};
use super::{IntoNeighbors, IntoNeighborsDirected, Visitable, VisitMap};
use super::{GraphRef, Reversed, IntoNodeIdentifiers};
use std::collections::VecDeque;
diff --git a/tests/quickcheck.rs b/tests/quickcheck.rs
index c000c3c..2831a2d 100644
--- a/tests/quickcheck.rs
+++ b/tests/quickcheck.rs
@@ -565,7 +565,7 @@
// shrink the graph by splitting it in two by a very
// simple algorithm, just even and odd node indices
- fn shrink(&self) -> Box<Iterator<Item=Self>> {
+ fn shrink(&self) -> Box<dyn Iterator<Item=Self>> {
let self_ = self.clone();
Box::new((0..2).filter_map(move |x| {
let gr = self_.0.filter_map(|i, w| {
diff --git a/tests/unionfind.rs b/tests/unionfind.rs
index ba3bdc5..ff8a51f 100644
--- a/tests/unionfind.rs
+++ b/tests/unionfind.rs
@@ -34,6 +34,34 @@
}
#[test]
+fn uf_test_with_equiv() {
+ let n = 8;
+ let mut u = UnionFind::new(n);
+ for i in 0..n {
+ assert_eq!(u.find(i), i);
+ assert_eq!(u.find_mut(i), i);
+ assert!(u.equiv(i, i));
+ }
+
+ u.union(0, 1);
+ assert!(u.equiv(0, 1));
+ u.union(1, 3);
+ u.union(1, 4);
+ u.union(4, 7);
+ assert!(u.equiv(0, 7));
+ assert!(u.equiv(1, 3));
+ assert!(!u.equiv(0, 2));
+ assert!(u.equiv(7, 0));
+ u.union(5, 6);
+ assert!(u.equiv(6, 5));
+ assert!(!u.equiv(6, 7));
+
+ // check that there are now 3 disjoint sets
+ let set = (0..n).map(|i| u.find(i)).collect::<HashSet<_>>();
+ assert_eq!(set.len(), 3);
+}
+
+#[test]
fn uf_rand() {
let n = 1 << 14;
let mut rng = ChaChaRng::from_rng(thread_rng()).unwrap();
diff --git a/tests/utils/qc.rs b/tests/utils/qc.rs
index a03568e..2715ab1 100644
--- a/tests/utils/qc.rs
+++ b/tests/utils/qc.rs
@@ -19,7 +19,7 @@
Small(T::arbitrary(&mut StdGen::new(g, sz)))
}
- fn shrink(&self) -> Box<Iterator<Item=Self>> {
+ fn shrink(&self) -> Box<dyn Iterator<Item=Self>> {
Box::new((**self).shrink().map(Small))
}
}
