Merge pull request #280 from jmcomets/bench-factories
Use factories to run benches on sample graphs
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/stable_graph.rs b/benches/stable_graph.rs
index d5a1e18..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);
+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);
+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
index fe288e5..cf7066e 100644
--- a/benches/unionfind.rs
+++ b/benches/unionfind.rs
@@ -3,157 +3,18 @@
extern crate test;
extern crate petgraph;
-use petgraph::prelude::*;
-use petgraph::{
- EdgeType,
-};
-use petgraph::graph::{
- node_index,
-};
+use test::Bencher;
+
+#[allow(dead_code)]
+mod common;
+use common::*;
use petgraph::algo::{connected_components, is_cyclic_undirected, min_spanning_tree};
-/// 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
-";
-
-/// Parse a text adjacency matrix format into a 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
-}
-
-/// Parse a text adjacency matrix format into a *undirected* graph
-fn str_to_ungraph(s: &str) -> Graph<(), (), Undirected> {
- parse_graph(s)
-}
-
-/// Parse a text adjacency matrix format into a *directed* graph
-fn str_to_digraph(s: &str) -> Graph<(), (), Directed> {
- parse_graph(s)
-}
-
#[bench]
-fn connected_components_praust_undir_bench(bench: &mut test::Bencher) {
- let a = str_to_ungraph(PRAUST_A);
- let b = str_to_ungraph(PRAUST_B);
+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))
@@ -161,9 +22,9 @@
}
#[bench]
-fn connected_components_praust_dir_bench(bench: &mut test::Bencher) {
- let a = str_to_digraph(PRAUST_A);
- let b = str_to_digraph(PRAUST_B);
+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))
@@ -171,9 +32,9 @@
}
#[bench]
-fn connected_components_full_undir_bench(bench: &mut test::Bencher) {
- let a = str_to_ungraph(FULL_A);
- let b = str_to_ungraph(FULL_B);
+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))
@@ -181,9 +42,9 @@
}
#[bench]
-fn connected_components_full_dir_bench(bench: &mut test::Bencher) {
- let a = str_to_digraph(FULL_A);
- let b = str_to_digraph(FULL_B);
+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))
@@ -191,9 +52,9 @@
}
#[bench]
-fn connected_components_petersen_undir_bench(bench: &mut test::Bencher) {
- let a = str_to_ungraph(PETERSEN_A);
- let b = str_to_ungraph(PETERSEN_B);
+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))
@@ -201,9 +62,9 @@
}
#[bench]
-fn connected_components_petersen_dir_bench(bench: &mut test::Bencher) {
- let a = str_to_digraph(PETERSEN_A);
- let b = str_to_digraph(PETERSEN_B);
+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))
@@ -211,9 +72,9 @@
}
#[bench]
-fn is_cyclic_undirected_praust_undir_bench(bench: &mut test::Bencher) {
- let a = str_to_ungraph(PRAUST_A);
- let b = str_to_ungraph(PRAUST_B);
+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))
@@ -221,9 +82,9 @@
}
#[bench]
-fn is_cyclic_undirected_praust_dir_bench(bench: &mut test::Bencher) {
- let a = str_to_digraph(PRAUST_A);
- let b = str_to_digraph(PRAUST_B);
+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))
@@ -231,9 +92,9 @@
}
#[bench]
-fn is_cyclic_undirected_full_undir_bench(bench: &mut test::Bencher) {
- let a = str_to_ungraph(FULL_A);
- let b = str_to_ungraph(FULL_B);
+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))
@@ -241,9 +102,9 @@
}
#[bench]
-fn is_cyclic_undirected_full_dir_bench(bench: &mut test::Bencher) {
- let a = str_to_digraph(FULL_A);
- let b = str_to_digraph(FULL_B);
+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))
@@ -251,9 +112,9 @@
}
#[bench]
-fn is_cyclic_undirected_petersen_undir_bench(bench: &mut test::Bencher) {
- let a = str_to_ungraph(PETERSEN_A);
- let b = str_to_ungraph(PETERSEN_B);
+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))
@@ -261,9 +122,9 @@
}
#[bench]
-fn is_cyclic_undirected_petersen_dir_bench(bench: &mut test::Bencher) {
- let a = str_to_digraph(PETERSEN_A);
- let b = str_to_digraph(PETERSEN_B);
+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))
@@ -271,9 +132,9 @@
}
#[bench]
-fn min_spanning_tree_praust_undir_bench(bench: &mut test::Bencher) {
- let a = str_to_ungraph(PRAUST_A);
- let b = str_to_ungraph(PRAUST_B);
+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))
@@ -281,9 +142,9 @@
}
#[bench]
-fn min_spanning_tree_praust_dir_bench(bench: &mut test::Bencher) {
- let a = str_to_digraph(PRAUST_A);
- let b = str_to_digraph(PRAUST_B);
+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))
@@ -291,9 +152,9 @@
}
#[bench]
-fn min_spanning_tree_full_undir_bench(bench: &mut test::Bencher) {
- let a = str_to_ungraph(FULL_A);
- let b = str_to_ungraph(FULL_B);
+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))
@@ -301,9 +162,9 @@
}
#[bench]
-fn min_spanning_tree_full_dir_bench(bench: &mut test::Bencher) {
- let a = str_to_digraph(FULL_A);
- let b = str_to_digraph(FULL_B);
+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))
@@ -311,9 +172,9 @@
}
#[bench]
-fn min_spanning_tree_petersen_undir_bench(bench: &mut test::Bencher) {
- let a = str_to_ungraph(PETERSEN_A);
- let b = str_to_ungraph(PETERSEN_B);
+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))
@@ -321,9 +182,9 @@
}
#[bench]
-fn min_spanning_tree_petersen_dir_bench(bench: &mut test::Bencher) {
- let a = str_to_digraph(PETERSEN_A);
- let b = str_to_digraph(PETERSEN_B);
+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))
