1 use std::marker::PhantomData;
2 
3 use petgraph::data::Build;
4 use petgraph::prelude::*;
5 use petgraph::visit::NodeIndexable;
6 
7 use petgraph::EdgeType;
8 
9 /// Petersen A and B are isomorphic
10 ///
11 /// http://www.dharwadker.org/tevet/isomorphism/
12 const PETERSEN_A: &str = "
13  0 1 0 0 1 0 1 0 0 0
14  1 0 1 0 0 0 0 1 0 0
15  0 1 0 1 0 0 0 0 1 0
16  0 0 1 0 1 0 0 0 0 1
17  1 0 0 1 0 1 0 0 0 0
18  0 0 0 0 1 0 0 1 1 0
19  1 0 0 0 0 0 0 0 1 1
20  0 1 0 0 0 1 0 0 0 1
21  0 0 1 0 0 1 1 0 0 0
22  0 0 0 1 0 0 1 1 0 0
23 ";
24 
25 const PETERSEN_B: &str = "
26  0 0 0 1 0 1 0 0 0 1
27  0 0 0 1 1 0 1 0 0 0
28  0 0 0 0 0 0 1 1 0 1
29  1 1 0 0 0 0 0 1 0 0
30  0 1 0 0 0 0 0 0 1 1
31  1 0 0 0 0 0 1 0 1 0
32  0 1 1 0 0 1 0 0 0 0
33  0 0 1 1 0 0 0 0 1 0
34  0 0 0 0 1 1 0 1 0 0
35  1 0 1 0 1 0 0 0 0 0
36 ";
37 
38 /// An almost full set, isomorphic
39 const FULL_A: &str = "
40  1 1 1 1 1 1 1 1 1 1
41  1 1 1 1 1 1 1 1 1 1
42  1 1 1 1 1 1 1 1 1 1
43  1 1 1 1 1 1 1 1 1 1
44  1 1 1 1 1 1 1 1 1 1
45  1 1 1 1 1 1 1 1 1 1
46  1 1 1 1 1 1 1 1 1 1
47  1 1 1 1 1 1 1 1 1 1
48  1 1 1 1 0 1 1 1 0 1
49  1 1 1 1 1 1 1 1 1 1
50 ";
51 
52 const FULL_B: &str = "
53  1 1 1 1 1 1 1 1 1 1
54  1 1 1 1 1 1 1 1 1 1
55  1 1 0 1 1 1 0 1 1 1
56  1 1 1 1 1 1 1 1 1 1
57  1 1 1 1 1 1 1 1 1 1
58  1 1 1 1 1 1 1 1 1 1
59  1 1 1 1 1 1 1 1 1 1
60  1 1 1 1 1 1 1 1 1 1
61  1 1 1 1 1 1 1 1 1 1
62  1 1 1 1 1 1 1 1 1 1
63 ";
64 
65 /// Praust A and B are not isomorphic
66 const PRAUST_A: &str = "
67  0 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
68  1 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0
69  1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0
70  1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0
71  1 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0
72  0 1 0 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0
73  0 0 1 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0
74  0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0
75  1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0
76  0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0
77  0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0
78  0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1
79  0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0
80  0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 1 0 0 0
81  0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1
82  0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0
83  0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1
84  0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 1
85  0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1
86  0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0
87 ";
88 
89 const PRAUST_B: &str = "
90  0 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
91  1 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0
92  1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0
93  1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0
94  1 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0
95  0 1 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1
96  0 0 1 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0
97  0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0
98  1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0
99  0 1 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0
100  0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0
101  0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0
102  0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1
103  0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 1 0
104  0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 1 0 1
105  0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0 1 0
106  0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 1 1 0
107  0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 1
108  0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0 0 1
109  0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 1 1 0
110 ";
111 
112 const BIGGER: &str = "
113  0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
114  0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0
115  0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0
116  0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
117  0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
118  0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
119  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
120  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
121  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
122  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
123  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
124  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
125  0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0
126  0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 1 0 0 0
127  0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1
128  0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0
129  0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1
130  0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0 1 1 1 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 1
131  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1
132  0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0
133  0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
134  1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 1 0 1 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0
135  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
136  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
137  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
138  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
139  0 0 1 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0
140  0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0
141  1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0
142  0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0
143  0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0
144  0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1
145  0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0
146  0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 1 0 0 0
147  0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1
148  0 1 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0
149  0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1
150  0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 1
151  0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1
152  0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0
153 ";
154 
155 /// A random bipartite graph.
156 const BIPARTITE: &str = "
157  0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1
158  0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1
159  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0
160  0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0
161  0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 0
162  0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0
163  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0
164  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0
165  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1
166  0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 1
167  1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
168  0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
169  0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
170  0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
171  0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
172  0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0
173  0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0
174  0 0 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0
175  0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
176  1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0
177 ";
178 
179 /// Parse a text adjacency matrix format into a directed graph
parse_graph<Ty, G>(s: &str) -> G where Ty: EdgeType, G: Default + Build<NodeWeight = (), EdgeWeight = ()> + NodeIndexable,180 fn parse_graph<Ty, G>(s: &str) -> G
181 where
182     Ty: EdgeType,
183     G: Default + Build<NodeWeight = (), EdgeWeight = ()> + NodeIndexable,
184 {
185     let mut g: G = Default::default();
186     let s = s.trim();
187     let lines = s.lines().filter(|l| !l.is_empty());
188     for (row, line) in lines.enumerate() {
189         for (col, word) in line.split(' ').filter(|s| !s.is_empty()).enumerate() {
190             let has_edge = word.parse::<i32>().unwrap();
191             assert!(has_edge == 0 || has_edge == 1);
192             if has_edge == 0 {
193                 continue;
194             }
195             while col >= g.node_count() || row >= g.node_count() {
196                 g.add_node(());
197             }
198             let a = g.from_index(row);
199             let b = g.from_index(col);
200             g.update_edge(a, b, ());
201         }
202     }
203     g
204 }
205 
206 pub struct GraphFactory<Ty, G = Graph<(), (), Ty>> {
207     ty: PhantomData<Ty>,
208     g: PhantomData<G>,
209 }
210 
211 impl<Ty, G> GraphFactory<Ty, G>
212 where
213     Ty: EdgeType,
214     G: Default + Build<NodeWeight = (), EdgeWeight = ()> + NodeIndexable,
215 {
new() -> Self216     fn new() -> Self {
217         GraphFactory {
218             ty: PhantomData,
219             g: PhantomData,
220         }
221     }
222 
petersen_a(self) -> G223     pub fn petersen_a(self) -> G {
224         parse_graph::<Ty, _>(PETERSEN_A)
225     }
226 
petersen_b(self) -> G227     pub fn petersen_b(self) -> G {
228         parse_graph::<Ty, _>(PETERSEN_B)
229     }
230 
full_a(self) -> G231     pub fn full_a(self) -> G {
232         parse_graph::<Ty, _>(FULL_A)
233     }
234 
full_b(self) -> G235     pub fn full_b(self) -> G {
236         parse_graph::<Ty, _>(FULL_B)
237     }
238 
praust_a(self) -> G239     pub fn praust_a(self) -> G {
240         parse_graph::<Ty, _>(PRAUST_A)
241     }
242 
praust_b(self) -> G243     pub fn praust_b(self) -> G {
244         parse_graph::<Ty, _>(PRAUST_B)
245     }
246 
bigger(self) -> G247     pub fn bigger(self) -> G {
248         parse_graph::<Ty, _>(BIGGER)
249     }
250 
bipartite(self) -> G251     pub fn bipartite(self) -> G {
252         parse_graph::<Ty, _>(BIPARTITE)
253     }
254 }
255 
graph<Ty: EdgeType>() -> GraphFactory<Ty, Graph<(), (), Ty>>256 pub fn graph<Ty: EdgeType>() -> GraphFactory<Ty, Graph<(), (), Ty>> {
257     GraphFactory::new()
258 }
259 
ungraph() -> GraphFactory<Undirected, Graph<(), (), Undirected>>260 pub fn ungraph() -> GraphFactory<Undirected, Graph<(), (), Undirected>> {
261     graph()
262 }
263 
digraph() -> GraphFactory<Directed, Graph<(), (), Directed>>264 pub fn digraph() -> GraphFactory<Directed, Graph<(), (), Directed>> {
265     graph()
266 }
267 
stable_graph<Ty: EdgeType>() -> GraphFactory<Ty, StableGraph<(), (), Ty>>268 pub fn stable_graph<Ty: EdgeType>() -> GraphFactory<Ty, StableGraph<(), (), Ty>> {
269     GraphFactory::new()
270 }
271 
stable_ungraph() -> GraphFactory<Undirected, StableGraph<(), (), Undirected>>272 pub fn stable_ungraph() -> GraphFactory<Undirected, StableGraph<(), (), Undirected>> {
273     stable_graph()
274 }
275 
stable_digraph() -> GraphFactory<Directed, StableGraph<(), (), Directed>>276 pub fn stable_digraph() -> GraphFactory<Directed, StableGraph<(), (), Directed>> {
277     stable_graph()
278 }
279 
tournament(node_count: usize) -> DiGraph<(), ()>280 pub fn tournament(node_count: usize) -> DiGraph<(), ()> {
281     let mut edge_forward = true;
282     let mut g = DiGraph::new();
283 
284     for _ in 0..node_count {
285         g.add_node(());
286     }
287 
288     for i in g.node_indices() {
289         for j in g.node_indices() {
290             if i >= j {
291                 continue;
292             }
293             let (source, target) = if edge_forward { (i, j) } else { (j, i) };
294             g.add_edge(source, target, ());
295             edge_forward = !edge_forward;
296         }
297     }
298 
299     g
300 }
301 
302 /// An F_(1,n) graph (where **|E| == 2(|N|) - 1**) with pseudo-random edge directions.
directed_fan(n: usize) -> DiGraph<(), ()>303 pub fn directed_fan(n: usize) -> DiGraph<(), ()> {
304     let mut g = DiGraph::new();
305 
306     for _ in 0..(n + 1) {
307         g.add_node(());
308     }
309 
310     let mut indices = g.node_indices();
311     let ix_0 = indices.next().unwrap();
312     let mut edge_forward = true;
313     let mut prev_ix = None;
314 
315     for ix in indices {
316         let (source, target) = if edge_forward { (ix_0, ix) } else { (ix, ix_0) };
317 
318         g.add_edge(source, target, ());
319 
320         if let Some(prev_ix) = prev_ix {
321             let (source, target) = if edge_forward {
322                 (prev_ix, ix)
323             } else {
324                 (ix, prev_ix)
325             };
326             g.add_edge(source, target, ());
327         }
328 
329         edge_forward = !edge_forward;
330         prev_ix = Some(ix);
331     }
332 
333     g
334 }
335