1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
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()
}
}
|
