graphica 1.0.1

Open-source multi-edge and mixed directional graph generation and canonization library
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

# Graphica

<p align="center">
<a href="https://symbolica.io"><img alt="Symbolica website" src="https://img.shields.io/static/v1?label=symbolica&message=website&color=orange&style=flat-square"></a>
  <a href="https://zulip.symbolica.io"><img alt="Zulip Chat" src="https://img.shields.io/static/v1?label=zulip&message=discussions&color=blue&style=flat-square"></a>
    <a href="https://github.com/symbolica-dev/graphica"><img alt="Graphica repository" src="https://img.shields.io/static/v1?label=github&message=development&color=green&style=flat-square&logo=github"></a>
    <a href="https://app.codecov.io/gh/symbolica-dev/graphica"><img alt="Codecov" src="https://img.shields.io/codecov/c/github/symbolica-dev/graphica?token=21E993U9SQ&style=flat-square"></a>
</p>

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](https://symbolica.io).

# Examples

### Graph generation

Generate all unique graphs with two external edges with edge data `g` and with vertices with specific edge attachments:

```rust
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

```mermaid
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;
```

### Graph canonization

Use a modified version of McKay's graph canonization algorithm to canonize graphs and detect isomorphisms:

```rust
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
```mermaid
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;
```

## Development

Follow the development and discussions on [Zulip](https://reform.zulipchat.com)!