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