1 extern crate petgraph;
2
3 use std::collections::HashSet;
4 use std::fs::File;
5 use std::io::prelude::*;
6
7 use petgraph::graph::{edge_index, node_index};
8 use petgraph::prelude::*;
9 use petgraph::EdgeType;
10
11 use petgraph::algo::{
12 is_isomorphic, is_isomorphic_matching, is_isomorphic_subgraph, subgraph_isomorphisms_iter,
13 };
14
15 /// Petersen A and B are isomorphic
16 ///
17 /// http://www.dharwadker.org/tevet/isomorphism/
18 const PETERSEN_A: &str = "
19 0 1 0 0 1 0 1 0 0 0
20 1 0 1 0 0 0 0 1 0 0
21 0 1 0 1 0 0 0 0 1 0
22 0 0 1 0 1 0 0 0 0 1
23 1 0 0 1 0 1 0 0 0 0
24 0 0 0 0 1 0 0 1 1 0
25 1 0 0 0 0 0 0 0 1 1
26 0 1 0 0 0 1 0 0 0 1
27 0 0 1 0 0 1 1 0 0 0
28 0 0 0 1 0 0 1 1 0 0
29 ";
30
31 const PETERSEN_B: &str = "
32 0 0 0 1 0 1 0 0 0 1
33 0 0 0 1 1 0 1 0 0 0
34 0 0 0 0 0 0 1 1 0 1
35 1 1 0 0 0 0 0 1 0 0
36 0 1 0 0 0 0 0 0 1 1
37 1 0 0 0 0 0 1 0 1 0
38 0 1 1 0 0 1 0 0 0 0
39 0 0 1 1 0 0 0 0 1 0
40 0 0 0 0 1 1 0 1 0 0
41 1 0 1 0 1 0 0 0 0 0
42 ";
43
44 /// An almost full set, isomorphic
45 const FULL_A: &str = "
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 1 1 1 1 1 1
49 1 1 1 1 1 1 1 1 1 1
50 1 1 1 1 1 1 1 1 1 1
51 1 1 1 1 1 1 1 1 1 1
52 1 1 1 1 1 1 1 1 1 1
53 1 1 1 1 1 1 1 1 1 1
54 1 1 1 1 0 1 1 1 0 1
55 1 1 1 1 1 1 1 1 1 1
56 ";
57
58 const FULL_B: &str = "
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 0 1 1 1 0 1 1 1
62 1 1 1 1 1 1 1 1 1 1
63 1 1 1 1 1 1 1 1 1 1
64 1 1 1 1 1 1 1 1 1 1
65 1 1 1 1 1 1 1 1 1 1
66 1 1 1 1 1 1 1 1 1 1
67 1 1 1 1 1 1 1 1 1 1
68 1 1 1 1 1 1 1 1 1 1
69 ";
70
71 /// Praust A and B are not isomorphic
72 const PRAUST_A: &str = "
73 0 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
74 1 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0
75 1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0
76 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0
77 1 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0
78 0 1 0 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0
79 0 0 1 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0
80 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0
81 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0
82 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0
83 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0
84 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1
85 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0
86 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 1 0 0 0
87 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1
88 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0
89 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1
90 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 1
91 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1
92 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0
93 ";
94
95 const PRAUST_B: &str = "
96 0 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
97 1 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0
98 1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0
99 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0
100 1 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0
101 0 1 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1
102 0 0 1 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0
103 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0
104 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0
105 0 1 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0
106 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0
107 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0
108 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1
109 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 1 0
110 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 1 0 1
111 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0 1 0
112 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 1 1 0
113 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 1
114 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0 0 1
115 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 1 1 0
116 ";
117
118 const G1U: &str = "
119 0 1 1 0 1
120 1 0 1 0 0
121 1 1 0 0 0
122 0 0 0 0 0
123 1 0 0 0 0
124 ";
125
126 const G2U: &str = "
127 0 1 0 1 0
128 1 0 0 1 1
129 0 0 0 0 0
130 1 1 0 0 0
131 0 1 0 0 0
132 ";
133
134 const G4U: &str = "
135 0 1 1 0 1
136 1 0 0 1 0
137 1 0 0 0 0
138 0 1 0 0 0
139 1 0 0 0 0
140 ";
141
142 const G1D: &str = "
143 0 1 1 0 1
144 0 0 1 0 0
145 0 0 0 0 0
146 0 0 0 0 0
147 0 0 0 0 0
148 ";
149
150 const G4D: &str = "
151 0 1 1 0 1
152 0 0 0 1 0
153 0 0 0 0 0
154 0 0 0 0 0
155 0 0 0 0 0
156 ";
157
158 // G8 1,2 are not iso
159 const G8_1: &str = "
160 0 1 1 0 0 1 1 1
161 1 0 1 0 1 0 1 1
162 1 1 0 1 0 0 1 1
163 0 0 1 0 1 1 1 1
164 0 1 0 1 0 1 1 1
165 1 0 0 1 1 0 1 1
166 1 1 1 1 1 1 0 1
167 1 1 1 1 1 1 1 0
168 ";
169
170 const G8_2: &str = "
171 0 1 0 1 0 1 1 1
172 1 0 1 0 1 0 1 1
173 0 1 0 1 0 1 1 1
174 1 0 1 0 1 0 1 1
175 0 1 0 1 0 1 1 1
176 1 0 1 0 1 0 1 1
177 1 1 1 1 1 1 0 1
178 1 1 1 1 1 1 1 0
179 ";
180
181 // G3 1,2 are not iso
182 const G3_1: &str = "
183 0 1 0
184 1 0 1
185 0 1 0
186 ";
187 const G3_2: &str = "
188 0 1 1
189 1 0 1
190 1 1 0
191 ";
192
193 // Non-isomorphic due to selfloop difference
194 const S1: &str = "
195 1 1 1
196 1 0 1
197 1 0 0
198 ";
199 const S2: &str = "
200 1 1 1
201 0 1 1
202 1 0 0
203 ";
204
205 /// Parse a text adjacency matrix format into a directed graph
parse_graph<Ty: EdgeType>(s: &str) -> Graph<(), (), Ty>206 fn parse_graph<Ty: EdgeType>(s: &str) -> Graph<(), (), Ty> {
207 let mut gr = Graph::with_capacity(0, 0);
208 let s = s.trim();
209 let lines = s.lines().filter(|l| !l.is_empty());
210 for (row, line) in lines.enumerate() {
211 for (col, word) in line.split(' ').filter(|s| !s.is_empty()).enumerate() {
212 let has_edge = word.parse::<i32>().unwrap();
213 assert!(has_edge == 0 || has_edge == 1);
214 if has_edge == 0 {
215 continue;
216 }
217 while col >= gr.node_count() || row >= gr.node_count() {
218 gr.add_node(());
219 }
220 gr.update_edge(node_index(row), node_index(col), ());
221 }
222 }
223 gr
224 }
225
str_to_graph(s: &str) -> Graph<(), (), Undirected>226 fn str_to_graph(s: &str) -> Graph<(), (), Undirected> {
227 parse_graph(s)
228 }
229
str_to_digraph(s: &str) -> Graph<(), (), Directed>230 fn str_to_digraph(s: &str) -> Graph<(), (), Directed> {
231 parse_graph(s)
232 }
233
234 /// Parse a file in adjacency matrix format into a directed graph
graph_from_file(path: &str) -> Graph<(), (), Directed>235 fn graph_from_file(path: &str) -> Graph<(), (), Directed> {
236 let mut f = File::open(path).expect("file not found");
237 let mut contents = String::new();
238 f.read_to_string(&mut contents)
239 .expect("failed to read from file");
240 parse_graph(&contents)
241 }
242
243 /*
244 fn graph_to_ad_matrix<N, E, Ty: EdgeType>(g: &Graph<N,E,Ty>)
245 {
246 let n = g.node_count();
247 for i in (0..n) {
248 for j in (0..n) {
249 let ix = NodeIndex::new(i);
250 let jx = NodeIndex::new(j);
251 let out = match g.find_edge(ix, jx) {
252 None => "0",
253 Some(_) => "1",
254 };
255 print!("{} ", out);
256 }
257 println!("");
258 }
259 }
260 */
261
262 #[test]
petersen_iso()263 fn petersen_iso() {
264 // The correct isomorphism is
265 // 0 => 0, 1 => 3, 2 => 1, 3 => 4, 5 => 2, 6 => 5, 7 => 7, 8 => 6, 9 => 8, 4 => 9
266 let peta = str_to_digraph(PETERSEN_A);
267 let petb = str_to_digraph(PETERSEN_B);
268 /*
269 println!("{:?}", peta);
270 graph_to_ad_matrix(&peta);
271 println!("");
272 graph_to_ad_matrix(&petb);
273 */
274
275 assert!(petgraph::algo::is_isomorphic(&peta, &petb));
276 }
277
278 #[test]
petersen_undir_iso()279 fn petersen_undir_iso() {
280 // The correct isomorphism is
281 // 0 => 0, 1 => 3, 2 => 1, 3 => 4, 5 => 2, 6 => 5, 7 => 7, 8 => 6, 9 => 8, 4 => 9
282 let peta = str_to_digraph(PETERSEN_A);
283 let petb = str_to_digraph(PETERSEN_B);
284
285 assert!(petgraph::algo::is_isomorphic(&peta, &petb));
286 }
287
288 #[test]
full_iso()289 fn full_iso() {
290 let a = str_to_graph(FULL_A);
291 let b = str_to_graph(FULL_B);
292
293 assert!(petgraph::algo::is_isomorphic(&a, &b));
294 }
295
296 #[test]
297 #[cfg_attr(miri, ignore = "Takes too long to run in Miri")]
praust_dir_no_iso()298 fn praust_dir_no_iso() {
299 let a = str_to_digraph(PRAUST_A);
300 let b = str_to_digraph(PRAUST_B);
301
302 assert!(!petgraph::algo::is_isomorphic(&a, &b));
303 }
304
305 #[test]
306 #[cfg_attr(miri, ignore = "Takes too long to run in Miri")]
praust_undir_no_iso()307 fn praust_undir_no_iso() {
308 let a = str_to_graph(PRAUST_A);
309 let b = str_to_graph(PRAUST_B);
310
311 assert!(!petgraph::algo::is_isomorphic(&a, &b));
312 }
313
314 #[test]
coxeter_di_iso()315 fn coxeter_di_iso() {
316 // The correct isomorphism is
317 let a = str_to_digraph(COXETER_A);
318 let b = str_to_digraph(COXETER_B);
319 assert!(petgraph::algo::is_isomorphic(&a, &b));
320 }
321
322 #[test]
coxeter_undi_iso()323 fn coxeter_undi_iso() {
324 // The correct isomorphism is
325 let a = str_to_graph(COXETER_A);
326 let b = str_to_graph(COXETER_B);
327 assert!(petgraph::algo::is_isomorphic(&a, &b));
328 }
329
330 #[test]
g14_dir_not_iso()331 fn g14_dir_not_iso() {
332 let a = str_to_digraph(G1D);
333 let b = str_to_digraph(G4D);
334 assert!(!petgraph::algo::is_isomorphic(&a, &b));
335 }
336
337 #[test]
g14_undir_not_iso()338 fn g14_undir_not_iso() {
339 let a = str_to_digraph(G1U);
340 let b = str_to_digraph(G4U);
341 assert!(!petgraph::algo::is_isomorphic(&a, &b));
342 }
343
344 #[test]
g12_undir_iso()345 fn g12_undir_iso() {
346 let a = str_to_digraph(G1U);
347 let b = str_to_digraph(G2U);
348 assert!(petgraph::algo::is_isomorphic(&a, &b));
349 }
350
351 #[test]
g3_not_iso()352 fn g3_not_iso() {
353 let a = str_to_digraph(G3_1);
354 let b = str_to_digraph(G3_2);
355 assert!(!petgraph::algo::is_isomorphic(&a, &b));
356 }
357
358 #[test]
g8_not_iso()359 fn g8_not_iso() {
360 let a = str_to_digraph(G8_1);
361 let b = str_to_digraph(G8_2);
362 assert_eq!(a.edge_count(), b.edge_count());
363 assert_eq!(a.node_count(), b.node_count());
364 assert!(!petgraph::algo::is_isomorphic(&a, &b));
365 }
366
367 #[test]
s12_not_iso()368 fn s12_not_iso() {
369 let a = str_to_digraph(S1);
370 let b = str_to_digraph(S2);
371 assert_eq!(a.edge_count(), b.edge_count());
372 assert_eq!(a.node_count(), b.node_count());
373 assert!(!petgraph::algo::is_isomorphic(&a, &b));
374 }
375
376 #[test]
iso1()377 fn iso1() {
378 let mut g0 = Graph::<_, ()>::new();
379 let mut g1 = Graph::<_, ()>::new();
380 assert!(petgraph::algo::is_isomorphic(&g0, &g1));
381
382 // very simple cases
383 let a0 = g0.add_node(0);
384 let a1 = g1.add_node(0);
385 assert!(petgraph::algo::is_isomorphic(&g0, &g1));
386 let b0 = g0.add_node(1);
387 let b1 = g1.add_node(1);
388 assert!(petgraph::algo::is_isomorphic(&g0, &g1));
389 let _ = g0.add_node(2);
390 assert!(!petgraph::algo::is_isomorphic(&g0, &g1));
391 let _ = g1.add_node(2);
392 assert!(petgraph::algo::is_isomorphic(&g0, &g1));
393 g0.add_edge(a0, b0, ());
394 assert!(!petgraph::algo::is_isomorphic(&g0, &g1));
395 g1.add_edge(a1, b1, ());
396 assert!(petgraph::algo::is_isomorphic(&g0, &g1));
397 }
398
399 #[test]
iso2()400 fn iso2() {
401 let mut g0 = Graph::<_, ()>::new();
402 let mut g1 = Graph::<_, ()>::new();
403
404 let a0 = g0.add_node(0);
405 let a1 = g1.add_node(0);
406 let b0 = g0.add_node(1);
407 let b1 = g1.add_node(1);
408 let c0 = g0.add_node(2);
409 let c1 = g1.add_node(2);
410 g0.add_edge(a0, b0, ());
411 g1.add_edge(c1, b1, ());
412 assert!(petgraph::algo::is_isomorphic(&g0, &g1));
413 // a -> b
414 // a -> c
415 // vs.
416 // c -> b
417 // c -> a
418 g0.add_edge(a0, c0, ());
419 g1.add_edge(c1, a1, ());
420 assert!(petgraph::algo::is_isomorphic(&g0, &g1));
421
422 // add
423 // b -> c
424 // vs
425 // b -> a
426
427 let _ = g0.add_edge(b0, c0, ());
428 let _ = g1.add_edge(b1, a1, ());
429 assert!(petgraph::algo::is_isomorphic(&g0, &g1));
430 let d0 = g0.add_node(3);
431 let d1 = g1.add_node(3);
432 let e0 = g0.add_node(4);
433 let e1 = g1.add_node(4);
434 assert!(petgraph::algo::is_isomorphic(&g0, &g1));
435 // add
436 // b -> e -> d
437 // vs
438 // b -> d -> e
439 g0.add_edge(b0, e0, ());
440 g0.add_edge(e0, d0, ());
441 g1.add_edge(b1, d1, ());
442 g1.add_edge(d1, e1, ());
443 assert!(petgraph::algo::is_isomorphic(&g0, &g1));
444 }
445
446 #[test]
iso_matching()447 fn iso_matching() {
448 let g0 = Graph::<(), _>::from_edges(&[(0, 0, 1), (0, 1, 2), (0, 2, 3), (1, 2, 4)]);
449
450 let mut g1 = g0.clone();
451 g1[edge_index(0)] = 0;
452 assert!(!is_isomorphic_matching(
453 &g0,
454 &g1,
455 |x, y| x == y,
456 |x, y| x == y
457 ));
458 let mut g2 = g0.clone();
459 g2[edge_index(1)] = 0;
460 assert!(!is_isomorphic_matching(
461 &g0,
462 &g2,
463 |x, y| x == y,
464 |x, y| x == y
465 ));
466 }
467
468 #[test]
iso_100n_100e()469 fn iso_100n_100e() {
470 let g0 = str_to_digraph(include_str!("res/graph_100n_100e.txt"));
471 let g1 = str_to_digraph(include_str!("res/graph_100n_100e_iso.txt"));
472 assert!(petgraph::algo::is_isomorphic(&g0, &g1));
473 }
474
475 #[test]
476 #[cfg_attr(miri, ignore = "Too large for Miri")]
iso_large()477 fn iso_large() {
478 let g0 = graph_from_file("tests/res/graph_1000n_1000e.txt");
479 let g1 = graph_from_file("tests/res/graph_1000n_1000e.txt");
480 assert!(petgraph::algo::is_isomorphic(&g0, &g1));
481 }
482
483 // isomorphism isn't correct for multigraphs.
484 // Keep this testcase to document how
485 #[should_panic]
486 #[test]
iso_multigraph_failure()487 fn iso_multigraph_failure() {
488 let g0 = Graph::<(), ()>::from_edges(&[(0, 0), (0, 0), (0, 1), (1, 1), (1, 1), (1, 0)]);
489
490 let g1 = Graph::<(), ()>::from_edges(&[(0, 0), (0, 1), (0, 1), (1, 1), (1, 0), (1, 0)]);
491 assert!(!is_isomorphic(&g0, &g1));
492 }
493
494 #[test]
495 #[cfg_attr(miri, ignore = "Takes too long to run in Miri")]
iso_subgraph()496 fn iso_subgraph() {
497 let g0 = Graph::<(), ()>::from_edges(&[(0, 1), (1, 2), (2, 0)]);
498 let g1 = Graph::<(), ()>::from_edges(&[(0, 1), (1, 2), (2, 0), (2, 3), (0, 4)]);
499 assert!(!is_isomorphic(&g0, &g1));
500 assert!(is_isomorphic_subgraph(&g0, &g1));
501 }
502
503 #[test]
504 #[cfg_attr(miri, ignore = "Takes too long to run in Miri")]
iter_subgraph()505 fn iter_subgraph() {
506 let a = Graph::<(), ()>::from_edges(&[(0, 1), (1, 2), (2, 0)]);
507 let b = Graph::<(), ()>::from_edges(&[(0, 1), (1, 2), (2, 0), (2, 3), (0, 4)]);
508 let a_ref = &a;
509 let b_ref = &b;
510 let mut node_match = { |x: &(), y: &()| x == y };
511 let mut edge_match = { |x: &(), y: &()| x == y };
512
513 let mappings =
514 subgraph_isomorphisms_iter(&a_ref, &b_ref, &mut node_match, &mut edge_match).unwrap();
515
516 // Verify the iterator returns the expected mappings
517 let expected_mappings: Vec<Vec<usize>> = vec![vec![0, 1, 2], vec![1, 2, 0], vec![2, 0, 1]];
518 for mapping in mappings {
519 assert!(expected_mappings.contains(&mapping))
520 }
521
522 // Verify all the mappings from the iterator are different
523 let a = str_to_digraph(COXETER_A);
524 let b = str_to_digraph(COXETER_B);
525 let a_ref = &a;
526 let b_ref = &b;
527
528 let mut unique = HashSet::new();
529 assert!(
530 subgraph_isomorphisms_iter(&a_ref, &b_ref, &mut node_match, &mut edge_match)
531 .unwrap()
532 .all(|x| unique.insert(x))
533 );
534
535 // The iterator should return None for graphs that are not isomorphic
536 let a = str_to_digraph(G8_1);
537 let b = str_to_digraph(G8_2);
538 let a_ref = &a;
539 let b_ref = &b;
540
541 assert!(
542 subgraph_isomorphisms_iter(&a_ref, &b_ref, &mut node_match, &mut edge_match)
543 .unwrap()
544 .next()
545 .is_none()
546 );
547
548 // https://github.com/petgraph/petgraph/issues/534
549 let mut g = Graph::<String, ()>::new();
550 let e1 = g.add_node("l1".to_string());
551 let e2 = g.add_node("l2".to_string());
552 g.add_edge(e1, e2, ());
553 let e3 = g.add_node("l3".to_string());
554 g.add_edge(e2, e3, ());
555 let e4 = g.add_node("l4".to_string());
556 g.add_edge(e3, e4, ());
557
558 let mut sub = Graph::<String, ()>::new();
559 let e3 = sub.add_node("l3".to_string());
560 let e4 = sub.add_node("l4".to_string());
561 sub.add_edge(e3, e4, ());
562
563 let mut node_match = { |x: &String, y: &String| x == y };
564 let mut edge_match = { |x: &(), y: &()| x == y };
565 assert_eq!(
566 subgraph_isomorphisms_iter(&&sub, &&g, &mut node_match, &mut edge_match)
567 .unwrap()
568 .collect::<Vec<_>>(),
569 vec![vec![2, 3]]
570 );
571 }
572
573 /// Isomorphic pair
574 const COXETER_A: &str = "
575 0 1 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 1
576 1 0 1 0 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
577 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 1 0 0 0 0
578 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
579 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
580 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
581 0 0 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 1 0 0
582 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
583 0 1 0 0 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
584 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
585 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
586 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
587 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
588 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
589 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
590 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0
591 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1
592 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0
593 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0
594 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0
595 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0
596 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0
597 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0
598 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0
599 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0
600 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0
601 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 1 0 1 0 0
602 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0
603 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1
604 1 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 0 1 0
605 ";
606
607 const COXETER_B: &str = "
608 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0
609 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0
610 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0
611 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
612 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
613 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0
614 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0
615 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0
616 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
617 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
618 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0
619 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
620 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
621 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
622 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0
623 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
624 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
625 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1
626 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
627 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1
628 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
629 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0
630 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
631 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
632 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
633 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0
634 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0
635 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
636 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1
637 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0
638 ";
639