diff options
Diffstat (limited to 'vendor/petgraph/src/generate.rs')
| -rw-r--r-- | vendor/petgraph/src/generate.rs | 133 |
1 files changed, 0 insertions, 133 deletions
diff --git a/vendor/petgraph/src/generate.rs b/vendor/petgraph/src/generate.rs deleted file mode 100644 index 9dc7dbf4..00000000 --- a/vendor/petgraph/src/generate.rs +++ /dev/null @@ -1,133 +0,0 @@ -//! ***Unstable.*** Graph generation. -//! -//! ***Unstable: API may change at any time.*** Depends on `feature = "generate"`. -//! - -use crate::graph::NodeIndex; -use crate::{Directed, EdgeType, Graph}; - -// A DAG has the property that the adjacency matrix is lower triangular, -// diagonal zero. -// -// This means we only allow edges i → j where i < j. -// -// The set of all DAG of a particular size is simply the power set of all -// possible edges. -// -// For a graph of n=3 nodes we have (n - 1) * n / 2 = 3 possible edges. - -/// A graph generator of “all” graphs of a particular size. -/// -/// ***Unstable: API may change at any time.*** Depends on `feature = "generate"`. -pub struct Generator<Ty> { - acyclic: bool, - selfloops: bool, - nodes: usize, - /// number of possible edges - nedges: usize, - /// current edge bitmap - bits: u64, - g: Graph<(), (), Ty>, -} - -impl Generator<Directed> { - /// Generate all possible Directed acyclic graphs (DAGs) of a particular number of vertices. - /// - /// These are only generated with one per isomorphism, so they use - /// one canonical node labeling where node *i* can only have edges to node *j* if *i < j*. - /// - /// For a graph of *k* vertices there are *e = (k - 1) k / 2* possible edges and - /// *2<sup>e</sup>* DAGs. - pub fn directed_acyclic(nodes: usize) -> Self { - assert!(nodes != 0); - let nedges = (nodes - 1) * nodes / 2; - assert!(nedges < 64); - Generator { - acyclic: true, - selfloops: false, - nodes: nodes, - nedges: nedges, - bits: !0, - g: Graph::with_capacity(nodes, nedges), - } - } -} - -impl<Ty: EdgeType> Generator<Ty> { - /// Generate all possible graphs of a particular number of vertices. - /// - /// All permutations are generated, so the graphs are not unique down to isomorphism. - /// - /// For a graph of *k* vertices there are *e = k²* possible edges and - /// *2<sup>k<sup>2</sup></sup>* graphs. - pub fn all(nodes: usize, allow_selfloops: bool) -> Self { - let scale = if Ty::is_directed() { 1 } else { 2 }; - let nedges = if allow_selfloops { - (nodes * nodes - nodes) / scale + nodes - } else { - (nodes * nodes) / scale - nodes - }; - assert!(nedges < 64); - Generator { - acyclic: false, - selfloops: allow_selfloops, - nodes: nodes, - nedges: nedges, - bits: !0, - g: Graph::with_capacity(nodes, nedges), - } - } - - fn state_to_graph(&mut self) -> &Graph<(), (), Ty> { - self.g.clear(); - for _ in 0..self.nodes { - self.g.add_node(()); - } - // For a DAG: - // interpret the bits in order, it's a lower triangular matrix: - // a b c d - // a x x x x - // b 0 x x x - // c 1 2 x x - // d 3 4 5 x - let mut bit = 0; - for i in 0..self.nodes { - let start = if self.acyclic || !self.g.is_directed() { - i - } else { - 0 - }; - for j in start..self.nodes { - if i == j && !self.selfloops { - continue; - } - if self.bits & (1u64 << bit) != 0 { - self.g.add_edge(NodeIndex::new(i), NodeIndex::new(j), ()); - } - - bit += 1; - } - } - &self.g - } - - pub fn next_ref(&mut self) -> Option<&Graph<(), (), Ty>> { - if self.bits == !0 { - self.bits = 0; - } else { - self.bits += 1; - if self.bits >= 1u64 << self.nedges { - return None; - } - } - Some(self.state_to_graph()) - } -} - -impl<Ty: EdgeType> Iterator for Generator<Ty> { - type Item = Graph<(), (), Ty>; - - fn next(&mut self) -> Option<Self::Item> { - self.next_ref().cloned() - } -} |