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