1use crate::builder::{Buildable, Builder};
20use crate::num::traits::FromPrimitive;
21use crate::traits::Graph;
22
23pub fn path<G>(m: usize) -> G
27where
28 G: Graph + Buildable,
29{
30 let mut b = G::Builder::with_capacities(m + 1, m);
31 let nodes: Vec<_> = (0..=m).map(|_| b.add_node()).collect();
32 for (u, v) in nodes.iter().zip(nodes.iter().skip(1)) {
33 b.add_edge(*u, *v);
34 }
35 b.into_graph()
36}
37
38pub fn cycle<G>(n: usize) -> G
42where
43 G: Graph + Buildable,
44{
45 let mut b = G::Builder::with_capacities(n, n);
46 let nodes: Vec<_> = (0..n).map(|_| b.add_node()).collect();
47 for (u, v) in nodes.iter().zip(nodes.iter().cycle().skip(1)) {
48 b.add_edge(*u, *v);
49 }
50 b.into_graph()
51}
52
53pub fn complete_graph<G>(n: usize) -> G
55where
56 G: Graph + Buildable,
57{
58 let mut b = G::Builder::with_capacities(n, n * (n - 1) / 2);
59 let nodes: Vec<_> = (0..n).map(|_| b.add_node()).collect();
60 for (i, &u) in nodes.iter().enumerate() {
61 for &v in &nodes[i + 1..] {
62 b.add_edge(u, v);
63 }
64 }
65 b.into_graph()
66}
67
68pub fn complete_bipartite<G>(n: usize, m: usize) -> G
73where
74 G: Graph + Buildable,
75{
76 let mut b = G::Builder::with_capacities(n + m, n * m);
77 let nodes: Vec<_> = (0..n + m).map(|_| b.add_node()).collect();
78 for &u in &nodes[..n] {
79 for &v in &nodes[n..] {
80 b.add_edge(u, v);
81 }
82 }
83 b.into_graph()
84}
85
86pub fn star<G>(n: usize) -> G
94where
95 G: Graph + Buildable,
96{
97 complete_bipartite::<G>(1, n)
98}
99
100pub fn hypercube<G>(d: u32) -> G
102where
103 G: Graph + Buildable,
104{
105 let n = 2usize.pow(d);
106 let mut b = G::Builder::with_capacities(n, n * usize::from_u32(d).unwrap());
107 let nodes: Vec<_> = (0..n).map(|_| b.add_node()).collect();
108 for i in 0..n {
109 for bit in 0..d {
110 if i & (1 << bit) == 0 {
111 b.add_edge(nodes[i], nodes[i | (1 << bit)]);
112 }
113 }
114 }
115 b.into_graph()
116}
117
118pub fn grid<G>(n: usize, m: usize) -> G
145where
146 G: Graph + Buildable,
147{
148 let mut b = G::Builder::with_capacities(n * m, (n - 1) * m + n * (m - 1));
149 let nodes: Vec<_> = (0..n * m).map(|_| b.add_node()).collect();
150 for x in 0..n - 1 {
151 for y in 0..m {
152 b.add_edge(nodes[y * n + x], nodes[y * n + x + 1]);
153 }
154 }
155 for x in 0..n {
156 for y in 0..m - 1 {
157 b.add_edge(nodes[y * n + x], nodes[y * n + x + n]);
158 }
159 }
160 b.into_graph()
161}
162
163pub fn peterson<G>() -> G
165where
166 G: Graph + Buildable,
167{
168 let mut b = G::Builder::with_capacities(10, 15);
169 let nodes: Vec<_> = (0..10).map(|_| b.add_node()).collect();
170 for i in 0..5 {
171 b.add_edge(nodes[i], nodes[(i + 1) % 5]);
172 b.add_edge(nodes[i + 5], nodes[(i + 2) % 5 + 5]);
173 b.add_edge(nodes[i], nodes[i + 5]);
174 }
175 b.into_graph()
176}
177
178#[cfg(test)]
179mod tests {
180
181 use super::{complete_bipartite, complete_graph, cycle, hypercube, path, star};
182 use crate::traits::*;
183 use crate::Net;
184 use std::cmp::{max, min};
185
186 #[test]
187 fn test_path() {
188 let g = path::<Net>(5);
189 assert_eq!(g.num_nodes(), 6);
190 assert_eq!(g.num_edges(), 5);
191 let mut degrees = vec![0; g.num_nodes()];
192 for e in g.edges() {
193 let (u, v) = g.enodes(e);
194 assert_eq!(min(u.index(), v.index()) + 1, max(u.index(), v.index()));
195 degrees[u.index()] += 1;
196 degrees[v.index()] += 1;
197 }
198 assert_eq!(degrees.iter().filter(|x| **x == 1).count(), 2);
199 assert_eq!(degrees.iter().filter(|x| **x == 2).count(), g.num_nodes() - 2);
200 }
201
202 #[test]
203 fn test_cycle() {
204 let g = cycle::<Net>(42);
205 assert_eq!(g.num_nodes(), 42);
206 assert_eq!(g.num_edges(), 42);
207 let mut degrees = vec![0; g.num_nodes()];
208 for e in g.edges() {
209 let (u, v) = g.enodes(e);
210 let (u, v) = (u.index(), v.index());
211 assert!((min(u, v) + 1 == max(u, v)) || (min(u, v) == 0 && max(u, v) == g.num_nodes() - 1));
212 degrees[u] += 1;
213 degrees[v] += 1;
214 }
215 assert!(degrees.into_iter().all(|x| x == 2));
216 }
217
218 #[test]
219 fn test_complete() {
220 let n = 12;
221 let g = complete_graph::<Net>(n);
222 assert_eq!(g.num_nodes(), n);
223 assert_eq!(g.num_edges(), n * (n - 1) / 2);
224 let mut degrees = vec![0; n];
225 for e in g.edges() {
226 let (u, v) = g.enodes(e);
227 degrees[u.index()] += 1;
228 degrees[v.index()] += 1;
229 }
230 assert!(degrees.into_iter().all(|x| x == n - 1));
231 }
232
233 #[test]
234 fn test_complete_bipartite() {
235 let n = 13;
236 let m = 7;
237 let g = complete_bipartite::<Net>(n, m);
238 assert_eq!(g.num_nodes(), n + m);
239 assert_eq!(g.num_edges(), n * m);
240 let mut degrees = vec![0; n + m];
241 for e in g.edges() {
242 let (u, v) = g.enodes(e);
243 let (u, v) = (u.index(), v.index());
244 assert!(min(u, v) < n);
245 assert!(max(u, v) >= m);
246 degrees[u] += 1;
247 degrees[v] += 1;
248 }
249 assert!(degrees[..n].iter().all(|x| *x == m));
250 assert!(degrees[n..].iter().all(|x| *x == n));
251 }
252
253 #[test]
254 fn test_star() {
255 let n = 17;
256 let g: Net = star(n);
257 assert_eq!(g.num_nodes(), n + 1);
258 assert_eq!(g.num_edges(), n);
259 let mut degrees = vec![0; n + 1];
260 for e in g.edges() {
261 let (u, v) = g.enodes(e);
262 let (u, v) = (u.index(), v.index());
263 assert_eq!(min(u, v), 0);
264 degrees[u] += 1;
265 degrees[v] += 1;
266 }
267 assert_eq!(degrees[0], n);
268 assert!(degrees[1..].iter().all(|x| *x == 1));
269 }
270
271 #[test]
272 fn test_hypercube() {
273 let g: Net = hypercube(3);
274 assert_eq!(g.num_nodes(), 8);
275 assert_eq!(g.num_edges(), 12);
276
277 let mut edges: Vec<_> = g.edges().map(|e| (g.src(e).index(), g.snk(e).index())).collect();
278 edges.sort();
279
280 assert_eq!(
281 edges,
282 vec![
283 (0, 1),
284 (0, 2),
285 (0, 4),
286 (1, 3),
287 (1, 5),
288 (2, 3),
289 (2, 6),
290 (3, 7),
291 (4, 5),
292 (4, 6),
293 (5, 7),
294 (6, 7),
295 ]
296 );
297 }
298}