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