1 //! ***Unstable.*** Graph generation. 2 //! 3 //! ***Unstable: API may change at any time.*** Depends on `feature = "generate"`. 4 //! 5 6 use crate::graph::NodeIndex; 7 use crate::{Directed, EdgeType, Graph}; 8 9 // A DAG has the property that the adjacency matrix is lower triangular, 10 // diagonal zero. 11 // 12 // This means we only allow edges i → j where i < j. 13 // 14 // The set of all DAG of a particular size is simply the power set of all 15 // possible edges. 16 // 17 // For a graph of n=3 nodes we have (n - 1) * n / 2 = 3 possible edges. 18 19 /// A graph generator of “all” graphs of a particular size. 20 /// 21 /// ***Unstable: API may change at any time.*** Depends on `feature = "generate"`. 22 pub struct Generator<Ty> { 23 acyclic: bool, 24 selfloops: bool, 25 nodes: usize, 26 /// number of possible edges 27 nedges: usize, 28 /// current edge bitmap 29 bits: u64, 30 g: Graph<(), (), Ty>, 31 } 32 33 impl Generator<Directed> { 34 /// Generate all possible Directed acyclic graphs (DAGs) of a particular number of vertices. 35 /// 36 /// These are only generated with one per isomorphism, so they use 37 /// one canonical node labeling where node *i* can only have edges to node *j* if *i < j*. 38 /// 39 /// For a graph of *k* vertices there are *e = (k - 1) k / 2* possible edges and 40 /// *2<sup>e</sup>* DAGs. 41 pub fn directed_acyclic(nodes: usize) -> Self { 42 assert!(nodes != 0); 43 let nedges = (nodes - 1) * nodes / 2; 44 assert!(nedges < 64); 45 Generator { 46 acyclic: true, 47 selfloops: false, 48 nodes: nodes, 49 nedges: nedges, 50 bits: !0, 51 g: Graph::with_capacity(nodes, nedges), 52 } 53 } 54 } 55 56 impl<Ty: EdgeType> Generator<Ty> { 57 /// Generate all possible graphs of a particular number of vertices. 58 /// 59 /// All permutations are generated, so the graphs are not unique down to isomorphism. 60 /// 61 /// For a graph of *k* vertices there are *e = k²* possible edges and 62 /// *2<sup>k<sup>2</sup></sup>* graphs. 63 pub fn all(nodes: usize, allow_selfloops: bool) -> Self { 64 let scale = if Ty::is_directed() { 1 } else { 2 }; 65 let nedges = if allow_selfloops { 66 (nodes * nodes - nodes) / scale + nodes 67 } else { 68 (nodes * nodes) / scale - nodes 69 }; 70 assert!(nedges < 64); 71 Generator { dijkstra<G, F, K>( graph: G, start: G::NodeId, goal: Option<G::NodeId>, mut edge_cost: F, ) -> HashMap<G::NodeId, K> where G: IntoEdges + Visitable, G::NodeId: Eq + Hash, F: FnMut(G::EdgeRef) -> K, K: Measure + Copy,72 acyclic: false, 73 selfloops: allow_selfloops, 74 nodes: nodes, 75 nedges: nedges, 76 bits: !0, 77 g: Graph::with_capacity(nodes, nedges), 78 } 79 } 80 81 fn state_to_graph(&mut self) -> &Graph<(), (), Ty> { 82 self.g.clear(); 83 for _ in 0..self.nodes { 84 self.g.add_node(()); 85 } 86 // For a DAG: 87 // interpret the bits in order, it's a lower triangular matrix: 88 // a b c d 89 // a x x x x 90 // b 0 x x x 91 // c 1 2 x x 92 // d 3 4 5 x 93 let mut bit = 0; 94 for i in 0..self.nodes { 95 let start = if self.acyclic || !self.g.is_directed() { 96 i 97 } else { 98 0 99 }; 100 for j in start..self.nodes { 101 if i == j && !self.selfloops { 102 continue; 103 } 104 if self.bits & (1u64 << bit) != 0 { 105 self.g.add_edge(NodeIndex::new(i), NodeIndex::new(j), ()); 106 } 107 108 bit += 1; 109 } 110 } 111 &self.g 112 } 113 114 pub fn next_ref(&mut self) -> Option<&Graph<(), (), Ty>> { 115 if self.bits == !0 { 116 self.bits = 0; 117 } else { 118 self.bits += 1; 119 if self.bits >= 1u64 << self.nedges { 120 return None; 121 } 122 } 123 Some(self.state_to_graph()) 124 } 125 } 126 127 impl<Ty: EdgeType> Iterator for Generator<Ty> { 128 type Item = Graph<(), (), Ty>; 129 130 fn next(&mut self) -> Option<Self::Item> { 131 self.next_ref().cloned() 132 } 133 } 134