Graphica is an open-source graph crate for Rust that allows for the generation, manipulation and canonization of multi-edge graphs with mixed directed and undirected edges and arbitrary node and edge data.
Graphica was open sourced by Ruijl Research and is a part of Symbolica.
Generate all unique graphs with two external edges with edge data g and with vertices with specific edge attachments:
let g = HalfEdge::undirected("g");
let q = HalfEdge::incoming("q");
let gs = Graph::<_, &str>::generate(
&[(1, g), (2, g)],
&[vec![g, g, g], vec![q.flip(), q, g], vec![g, g, g, g]],
GenerationSettings::new()
.max_loops(2)
.max_bridges(0)
.allow_self_loops(true),
)
.unwrap();
let r = gs.keys().next().unwrap().to_mermaid();
println!("{}", r);yields
graph TD;
0["0"];
1["0"];
2["0"];
3["1"];
4["2"];
0 ---|"g"| 1;
0 ---|"g"| 2;
0 ---|"g"| 3;
0 ---|"g"| 4;
1 -->|"q"| 2;
2 -->|"q"| 1;
Use a modified version of McKay's graph canonization algorithm to canonize graphs and detect isomorphisms:
let mut g = Graph::new();
let n0 = g.add_node(1);
let n1 = g.add_node(0);
let n2 = g.add_node(1);
let n3 = g.add_node(0);
let n4 = g.add_node(2);
let n5 = g.add_node(0);
let n6 = g.add_node(1);
let n7 = g.add_node(0);
let n8 = g.add_node(1);
g.add_edge(n0, n1, false, 0).unwrap();
g.add_edge(n0, n3, false, 0).unwrap();
g.add_edge(n1, n2, false, 0).unwrap();
g.add_edge(n1, n3, false, 0).unwrap();
g.add_edge(n1, n4, false, 0).unwrap();
g.add_edge(n1, n5, false, 0).unwrap();
g.add_edge(n2, n5, false, 0).unwrap();
g.add_edge(n3, n4, false, 0).unwrap();
g.add_edge(n3, n6, false, 0).unwrap();
g.add_edge(n3, n7, false, 0).unwrap();
g.add_edge(n4, n5, false, 0).unwrap();
g.add_edge(n4, n7, false, 0).unwrap();
g.add_edge(n5, n7, false, 0).unwrap();
g.add_edge(n5, n8, false, 0).unwrap();
g.add_edge(n6, n7, false, 0).unwrap();
g.add_edge(n7, n8, false, 0).unwrap();
let c = g.canonize();
assert_eq!(c.orbit_generators.len(), 2);
assert_eq!(c.automorphism_group_size, 8);
println!("{}", c.graph.to_dot());yields canonical graph
graph TD;
0["0"];
1["0"];
2["0"];
3["0"];
4["1"];
5["1"];
6["1"];
7["1"];
8["2"];
0 ---|"0"| 2;
0 ---|"0"| 3;
0 ---|"0"| 6;
0 ---|"0"| 7;
0 ---|"0"| 8;
1 ---|"0"| 2;
1 ---|"0"| 3;
1 ---|"0"| 4;
1 ---|"0"| 5;
1 ---|"0"| 8;
2 ---|"0"| 5;
2 ---|"0"| 7;
2 ---|"0"| 8;
3 ---|"0"| 4;
3 ---|"0"| 6;
3 ---|"0"| 8;
Follow the development and discussions on Zulip!