1 use std::collections::HashSet;
2 use std::hash::Hash;
3
4 use petgraph::algo::{greedy_matching, maximum_matching};
5 use petgraph::prelude::*;
6
7 macro_rules! assert_one_of {
8 ($actual:expr, [$($expected:expr),+]) => {
9 let expected = &[$($expected),+];
10 if !expected.iter().any(|expected| expected == &$actual) {
11 let expected = expected.iter().map(|e| format!("\n{:?}", e)).collect::<Vec<_>>();
12 let comma_separated = expected.join(", ");
13 panic!("assertion failed: `actual does not equal to any of expected`\nactual:\n{:?}\nexpected:{}", $actual, comma_separated);
14 }
15 };
16 }
17
18 macro_rules! set {
19 () => {
20 HashSet::new()
21 };
22 ($(($source:expr, $target:expr)),+) => {
23 {
24 let mut set = HashSet::new();
25 $(
26 set.insert(($source.into(), $target.into()));
27 )*
28 set
29 }
30 };
31 ($($elem:expr),+) => {
32 {
33 let mut set = HashSet::new();
34 $(
35 set.insert($elem.into());
36 )*
37 set
38 }
39 };
40 }
41
42 // So we don't have to type `.collect::<HashSet<_>>`.
collect<'a, T: Copy + Eq + Hash + 'a>(iter: impl Iterator<Item = T>) -> HashSet<T>43 fn collect<'a, T: Copy + Eq + Hash + 'a>(iter: impl Iterator<Item = T>) -> HashSet<T> {
44 iter.collect()
45 }
46
47 #[test]
greedy_empty()48 fn greedy_empty() {
49 let g: UnGraph<(), ()> = UnGraph::default();
50 let m = greedy_matching(&g);
51 assert_eq!(collect(m.edges()), set![]);
52 assert_eq!(collect(m.nodes()), set![]);
53 }
54
55 #[test]
greedy_disjoint()56 fn greedy_disjoint() {
57 let g: UnGraph<(), ()> = UnGraph::from_edges(&[(0, 1), (2, 3)]);
58 let m = greedy_matching(&g);
59 assert_eq!(collect(m.edges()), set![(0, 1), (2, 3)]);
60 assert_eq!(collect(m.nodes()), set![0, 1, 2, 3]);
61 }
62
63 #[test]
greedy_odd_path()64 fn greedy_odd_path() {
65 let g: UnGraph<(), ()> = UnGraph::from_edges(&[(0, 1), (1, 2), (2, 3)]);
66 let m = greedy_matching(&g);
67 assert_one_of!(collect(m.edges()), [set![(0, 1), (2, 3)], set![(1, 2)]]);
68 assert_one_of!(collect(m.nodes()), [set![0, 1, 2, 3], set![1, 2]]);
69 }
70
71 #[test]
greedy_star()72 fn greedy_star() {
73 let g: UnGraph<(), ()> = UnGraph::from_edges(&[(0, 1), (0, 2), (0, 3)]);
74 let m = greedy_matching(&g);
75 assert_one_of!(
76 collect(m.edges()),
77 [set![(0, 1)], set![(0, 2)], set![(0, 3)]]
78 );
79 assert_one_of!(collect(m.nodes()), [set![0, 1], set![0, 2], set![0, 3]]);
80 }
81
82 #[test]
maximum_empty()83 fn maximum_empty() {
84 let g: UnGraph<(), ()> = UnGraph::default();
85 let m = maximum_matching(&g);
86 assert_eq!(collect(m.edges()), set![]);
87 assert_eq!(collect(m.nodes()), set![]);
88 }
89
90 #[test]
maximum_disjoint()91 fn maximum_disjoint() {
92 let g: UnGraph<(), ()> = UnGraph::from_edges(&[(0, 1), (2, 3)]);
93 let m = maximum_matching(&g);
94 assert_eq!(collect(m.edges()), set![(0, 1), (2, 3)]);
95 assert_eq!(collect(m.nodes()), set![0, 1, 2, 3]);
96 }
97
98 #[test]
maximum_odd_path()99 fn maximum_odd_path() {
100 let g: UnGraph<(), ()> = UnGraph::from_edges(&[(0, 1), (1, 2), (2, 3)]);
101 let m = maximum_matching(&g);
102 assert_eq!(collect(m.edges()), set![(0, 1), (2, 3)]);
103 assert_eq!(collect(m.nodes()), set![0, 1, 2, 3]);
104 }
105
106 #[cfg(feature = "stable_graph")]
107 #[test]
maximum_in_stable_graph()108 fn maximum_in_stable_graph() {
109 let mut g: StableUnGraph<(), ()> =
110 StableUnGraph::from_edges(&[(0, 1), (0, 2), (1, 2), (1, 3), (2, 4), (3, 4), (3, 5)]);
111
112 // Create a hole by removing node that would otherwise belong to the maximum
113 // matching.
114 g.remove_node(NodeIndex::new(4));
115
116 let m = maximum_matching(&g);
117 assert_one_of!(
118 collect(m.edges()),
119 [
120 set![(0, 1), (3, 5)],
121 set![(0, 2), (1, 3)],
122 set![(0, 2), (3, 5)]
123 ]
124 );
125 assert_one_of!(
126 collect(m.nodes()),
127 [set![0, 1, 3, 5], set![0, 2, 1, 3], set![0, 2, 3, 5]]
128 );
129 }
130
131 #[cfg(feature = "stable_graph")]
132 #[test]
is_perfect_in_stable_graph()133 fn is_perfect_in_stable_graph() {
134 let mut g: StableUnGraph<(), ()> = StableUnGraph::from_edges(&[(0, 1), (1, 2), (2, 3)]);
135 g.remove_node(NodeIndex::new(0));
136 g.remove_node(NodeIndex::new(1));
137
138 let m = maximum_matching(&g);
139 assert_eq!(m.len(), 1);
140 assert!(m.is_perfect());
141 }
142