1 files changed, 133 insertions, 0 deletions
diff --git a/vendor/petgraph/src/generate.rs b/vendor/petgraph/src/generate.rs
new file mode 100644
index 000000000..9dc7dbf4d
--- /dev/null
+++ b/vendor/petgraph/src/generate.rs
@@ -0,0 +1,133 @@
+//! ***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()
+    }
+}