diff options
Diffstat (limited to 'third_party/rust/petgraph/benches/common/factories.rs')
| -rw-r--r-- | third_party/rust/petgraph/benches/common/factories.rs | 250 |
1 files changed, 250 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() +} |