rs_graph/
classes.rs

1// Copyright (c) 2016-2021 Frank Fischer <frank-fischer@shadow-soft.de>
2//
3// This program is free software: you can redistribute it and/or
4// modify it under the terms of the GNU General Public License as
5// published by the Free Software Foundation, either version 3 of the
6// License, or (at your option) any later version.
7//
8// This program is distributed in the hope that it will be useful, but
9// WITHOUT ANY WARRANTY; without even the implied warranty of
10// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
11// General Public License for more details.
12//
13// You should have received a copy of the GNU General Public License
14// along with this program.  If not, see  <http://www.gnu.org/licenses/>
15//
16
17//! Some common graph classes.
18
19use crate::builder::{Buildable, Builder};
20use crate::num::traits::FromPrimitive;
21use crate::traits::Graph;
22
23/// Returns a path with `m` edges.
24///
25/// The path is directed if G is a digraph.
26pub 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
38/// Returns a cycle with length `n`.
39///
40/// The cycle is directed if G is directed
41pub 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
53/// Returns the complete graph on `n` nodes.
54pub 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
68/// Returns a complete bipartite graph on `n+m` nodes.
69///
70/// The edges will run between the first n nodes and the last m nodes.
71/// If G is a digraph, the edges will run in this direction.
72pub 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
86/// Returns a star graph with `n` rays.
87///
88/// The center node will be the first node. This is equivalent to
89/// `complete_bipartite(1,n)`.
90///
91/// If G is a digraph, the source of all edges will be the center
92/// node.
93pub fn star<G>(n: usize) -> G
94where
95    G: Graph + Buildable,
96{
97    complete_bipartite::<G>(1, n)
98}
99
100/// Returns a hypercube of dimension `d`.
101pub 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
118/// Return a grid graph with `n` columns and `m` rows.
119///
120/// The nodes are created from left to right and from bottom to top. The
121/// following is a grid graph with 5 columns and 4 rows.
122///
123///   15 - 16 - 17 - 18 - 19
124///    |    |    |    |    |
125///   10 - 11 - 12 - 13 - 14
126///    |    |    |    |    |
127///    5 -- 6 -- 7 -- 8 -- 9
128///    |    |    |    |    |
129///    0 -- 1 -- 2 -- 3 -- 4
130///
131/// ```
132/// use rs_graph::LinkedListGraph;
133/// use rs_graph::traits::*;
134/// use rs_graph::classes;
135///
136/// let g: LinkedListGraph = classes::grid(5, 4);
137/// assert_eq!(g.num_nodes(), 20);
138/// assert_eq!(g.num_edges(), 5*3 + 4*4);
139///
140/// assert_eq!(g.nodes().filter(|&u| g.neighs(u).count() == 2).count(), 4);
141/// assert_eq!(g.nodes().filter(|&u| g.neighs(u).count() == 3).count(), 10);
142/// assert_eq!(g.nodes().filter(|&u| g.neighs(u).count() == 4).count(), 6);
143/// ```
144pub 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
163/// Returns a Peterson graph.
164pub 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}