diff options
Diffstat (limited to 'third_party/rust/petgraph/benches')
| -rw-r--r-- | third_party/rust/petgraph/benches/common/factories.rs | 250 | ||||
| -rw-r--r-- | third_party/rust/petgraph/benches/common/mod.rs | 2 | ||||
| -rw-r--r-- | third_party/rust/petgraph/benches/dijkstra.rs | 32 | ||||
| -rw-r--r-- | third_party/rust/petgraph/benches/iso.rs | 52 | ||||
| -rw-r--r-- | third_party/rust/petgraph/benches/matrix_graph.rs | 235 | ||||
| -rw-r--r-- | third_party/rust/petgraph/benches/ograph.rs | 52 | ||||
| -rw-r--r-- | third_party/rust/petgraph/benches/stable_graph.rs | 85 | ||||
| -rw-r--r-- | third_party/rust/petgraph/benches/unionfind.rs | 156 |
8 files changed, 864 insertions, 0 deletions
diff --git a/third_party/rust/petgraph/benches/common/factories.rs b/third_party/rust/petgraph/benches/common/factories.rs new file mode 100644 index 0000000000..8ab8068629 --- /dev/null +++ b/third_party/rust/petgraph/benches/common/factories.rs @@ -0,0 +1,250 @@ +use std::marker::PhantomData; + +use petgraph::data::Build; +use petgraph::prelude::*; +use petgraph::visit::NodeIndexable; + +use petgraph::EdgeType; + +/// Petersen A and B are isomorphic +/// +/// http://www.dharwadker.org/tevet/isomorphism/ +const PETERSEN_A: &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: &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: &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: &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: &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: &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: &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.is_empty()).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/third_party/rust/petgraph/benches/common/mod.rs b/third_party/rust/petgraph/benches/common/mod.rs new file mode 100644 index 0000000000..739c04197a --- /dev/null +++ b/third_party/rust/petgraph/benches/common/mod.rs @@ -0,0 +1,2 @@ +mod factories; +pub use factories::*; diff --git a/third_party/rust/petgraph/benches/dijkstra.rs b/third_party/rust/petgraph/benches/dijkstra.rs new file mode 100644 index 0000000000..7901983ffd --- /dev/null +++ b/third_party/rust/petgraph/benches/dijkstra.rs @@ -0,0 +1,32 @@ +#![feature(test)] + +extern crate petgraph; +extern crate test; + +use petgraph::prelude::*; +use std::cmp::{max, min}; +use test::Bencher; + +use petgraph::algo::dijkstra; + +#[bench] +fn dijkstra_bench(bench: &mut Bencher) { + static NODE_COUNT: usize = 10_000; + let mut g = Graph::new_undirected(); + let nodes: Vec<NodeIndex<_>> = (0..NODE_COUNT).into_iter().map(|i| g.add_node(i)).collect(); + for i in 0..NODE_COUNT { + let n1 = nodes[i]; + let neighbour_count = i % 8 + 3; + let j_from = max(0, i as i32 - neighbour_count as i32 / 2) as usize; + let j_to = min(NODE_COUNT, j_from + neighbour_count); + for j in j_from..j_to { + let n2 = nodes[j]; + let distance = (i + 3) % 10; + g.add_edge(n1, n2, distance); + } + } + + bench.iter(|| { + let _scores = dijkstra(&g, nodes[0], None, |e| *e.weight()); + }); +} diff --git a/third_party/rust/petgraph/benches/iso.rs b/third_party/rust/petgraph/benches/iso.rs new file mode 100644 index 0000000000..f0875c1109 --- /dev/null +++ b/third_party/rust/petgraph/benches/iso.rs @@ -0,0 +1,52 @@ +#![feature(test)] + +extern crate petgraph; +extern crate test; + +use test::Bencher; + +#[allow(dead_code)] +mod common; +use common::*; + +use petgraph::algo::is_isomorphic; + +#[bench] +fn petersen_iso_bench(bench: &mut Bencher) { + let a = digraph().petersen_a(); + let b = digraph().petersen_b(); + + bench.iter(|| is_isomorphic(&a, &b)); +} + +#[bench] +fn petersen_undir_iso_bench(bench: &mut Bencher) { + let a = ungraph().petersen_a(); + let b = ungraph().petersen_b(); + + bench.iter(|| is_isomorphic(&a, &b)); +} + +#[bench] +fn full_iso_bench(bench: &mut Bencher) { + let a = ungraph().full_a(); + let b = ungraph().full_b(); + + bench.iter(|| is_isomorphic(&a, &b)); +} + +#[bench] +fn praust_dir_no_iso_bench(bench: &mut Bencher) { + let a = digraph().praust_a(); + let b = digraph().praust_b(); + + bench.iter(|| is_isomorphic(&a, &b)); +} + +#[bench] +fn praust_undir_no_iso_bench(bench: &mut Bencher) { + let a = ungraph().praust_a(); + let b = ungraph().praust_b(); + + bench.iter(|| is_isomorphic(&a, &b)); +} diff --git a/third_party/rust/petgraph/benches/matrix_graph.rs b/third_party/rust/petgraph/benches/matrix_graph.rs new file mode 100644 index 0000000000..72f5aae692 --- /dev/null +++ b/third_party/rust/petgraph/benches/matrix_graph.rs @@ -0,0 +1,235 @@ +#![feature(test)] + +extern crate petgraph; +extern crate test; + +use test::Bencher; + +use petgraph::algo; +use petgraph::matrix_graph::{node_index, MatrixGraph}; +use petgraph::{Directed, EdgeType, Incoming, Outgoing}; + +#[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() { + 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 + }) + .flatten() + .collect(); + + b.iter(|| { + let mut g = g.clone(); + + for &(source, target) in edges_to_add.iter() { + 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: &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: &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.is_empty()).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/third_party/rust/petgraph/benches/ograph.rs b/third_party/rust/petgraph/benches/ograph.rs new file mode 100644 index 0000000000..d3f29869c8 --- /dev/null +++ b/third_party/rust/petgraph/benches/ograph.rs @@ -0,0 +1,52 @@ +#![feature(test)] + +extern crate petgraph; +extern crate test; + +use petgraph::graph::Graph; + +#[bench] +fn bench_inser(b: &mut test::Bencher) { + let mut og = Graph::new(); + let fst = og.add_node(0i32); + for x in 1..125 { + let n = og.add_node(x); + og.add_edge(fst, n, ()); + } + b.iter(|| og.add_node(1)) +} + +#[bench] +fn bench_add_edge(b: &mut test::Bencher) { + let mut og = Graph::new(); + for _ in 0..100 { + og.add_node(()); + } + + b.iter(|| { + for (a, b) in og.node_indices().zip(og.node_indices().skip(1)) { + og.add_edge(a, b, ()); + } + og.clear_edges(); + }) +} + +#[bench] +fn bench_remove(b: &mut test::Bencher) { + // removal is very slow in a big graph. + // and this one doesn't even have many nodes. + let mut og = Graph::new(); + let fst = og.add_node(0i32); + let mut prev = fst; + for x in 1..1250 { + let n = og.add_node(x); + og.add_edge(prev, n, ()); + prev = n; + } + //println!("{}", og); + b.iter(|| { + for _ in 0..100 { + og.remove_node(fst); + } + }) +} diff --git a/third_party/rust/petgraph/benches/stable_graph.rs b/third_party/rust/petgraph/benches/stable_graph.rs new file mode 100644 index 0000000000..9dffd91cf4 --- /dev/null +++ b/third_party/rust/petgraph/benches/stable_graph.rs @@ -0,0 +1,85 @@ +#![feature(test)] + +extern crate petgraph; +extern crate test; + +use petgraph::prelude::*; +use test::Bencher; + +#[allow(dead_code)] +mod common; +use common::*; + +use petgraph::stable_graph::node_index; + +#[bench] +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 = stable_digraph().full_a(); + bench.iter(|| a.edges_directed(node_index(1), Outgoing).count()) +} + +#[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 = stable_digraph().full_a(); + bench.iter(|| a.neighbors(node_index(1)).count()) +} + +#[bench] +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 = stable_digraph().full_a(); + bench.iter(|| a.neighbors_directed(node_index(1), Incoming).count()) +} + +#[bench] +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 = digraph().bigger(); + bench.iter(|| petgraph::algo::kosaraju_scc(&a)); +} + +#[bench] +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 = digraph().bigger(); + bench.iter(|| a.map(|i, _| i, |i, _| i)); +} + +#[bench] +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 = stable_digraph().bigger(); + bench.iter(|| a.retain_edges(|_gr, i| (i.index() + 1) % 3700 != 0)); +} diff --git a/third_party/rust/petgraph/benches/unionfind.rs b/third_party/rust/petgraph/benches/unionfind.rs new file mode 100644 index 0000000000..dd4446a52b --- /dev/null +++ b/third_party/rust/petgraph/benches/unionfind.rs @@ -0,0 +1,156 @@ +#![feature(test)] + +extern crate petgraph; +extern crate test; + +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))); +} |