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