blob: 65b1c652ee8da1056fcd11e8522ba401282ea8bf [file] [log] [blame]
 //! ***Unstable.*** Graph generation. //! //! ***Unstable: API may change at any time.*** Depends on `feature = "generate"`. //! use {Graph, Directed, EdgeType}; use graph::NodeIndex; // 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 { acyclic: bool, selfloops: bool, nodes: usize, /// number of possible edges nedges: usize, /// current edge bitmap bits: u64, g: Graph<(), (), Ty>, } impl Generator { /// 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 /// *2e* 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 Generator { /// Generate all possible graphs of a particular number of vertices. /// /// All permutations are generated, so the graphs are not unique down to isomorphim. /// /// For a graph of *k* vertices there are *e = k²* possible edges and /// *2k2* 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 Iterator for Generator { type Item = Graph<(), (), Ty>; fn next(&mut self) -> Option { self.next_ref().cloned() } }