# User:Salpynx/n-Genus Graph Embedding

This is a experimental investigation of a proposed category of Category:Program forms for demonstrating embedded graph structures in a language's control flow.

Source code in a language can be thought of as representing control flow as a directed graph (see Wire-crossing problem).

Nodes in the graph are Control Flow statements.

Edges in the graph are pieces of code separated by Control Flow statements.

Edges are to be uniquely labelled to confirm they are visited during program execution. Hardcoded output is the simplest way to do this, but other forms of debugging break statements may be used.

## Specific embeddings to demonstrate genus

wikipedia:Generalized Petersen graphs can be used to confirm how / whether a language can embed a genus 1 or genus 2 graph. These graphs are cubic graphs, which means every node has degree 3, which translates to a control flow structure of one incoming edge, and two possible outgoing edges. `if .. then .. else ..`.

For a genus 1 structure, use the wikipedia:Petersen graph, G(5, 2), which can be minimally embedded on a torus.

For a genus 2 structure, use the wikipedia:Desargues graph G(10, 3), which can be minimally embedded on a 2-torus.

Generalised Petersen graphs can be formed by linking a n-polygon to an n-star polygon via n spokes.

This gives 3 classes of edges, so we need to have 3 x n regions of uniquely labelled code:

• Outer `{O1 .. On}`
• Spoke `{S1 .. Sn}`
• Inner `{I1 .. In}`

The spoke return path does not need to be labelled. It is effectively adding another directed edge along the same path to get back to the outer loop the code is meant to be directed in this formulation (code is normally directed) -- hopefully these extra edges don't break the topology too much and still prove the basic structure while making the traversal neater to follow.

It is important that this label output is not constructed programatically. The labels are supposed to represent points in the literal source code. The source code is the structure of interest which is being traversed by the program's instruction pointer, and we wish to trace the pointer's path through the graph.

## Target traversal algorithm

This is not aiming to be an minimal path, but needs to demonstrate the control flow does represent a genus n embedding.

1. Once round the outer loop,
2. Take spoke i,
3. Once round the inner loop
4. If i == n (n parameter of the generalised Petersen G(n, k) notation) HALT.
5. Otherwise, back through the (unlabelled) return path of spoke i.
6. Move to next outer edge i+1 and increment i
7. Goto. 2

## Target Output

For ease of verification it makes sense to surround spoke output with newlines.

### Petersen graph

```O1 O2 O3 O4 O5 O1
S1
I1 I3 I5 I2 I4 I1 O2
S2
I2 I4 I1 I3 I5 I2 O3
S3
I3 I5 I2 I4 I1 I3 O4
S4
I4 I1 I3 I5 I2 I4 O5
S5
I5 I2 I4 I1 I3 I5
```

### Desargues graph

```O1 O2 O3 O4 O5 O6 O7 O8 O9 OA O1
S1
I1 I4 I7 IA I3 I6 I9 I2 I5 I8 I1 O2
S2
I2 I5 I8 I1 I4 I7 IA I3 I6 I9 I2 O3
S3
I3 I6 I9 I2 I5 I8 I1 I4 I7 IA I3 O4
S4
I4 I7 IA I3 I6 I9 I2 I5 I8 I1 I4 O5
S5
I5 I8 I1 I4 I7 IA I3 I6 I9 I2 I5 O6
S6
I6 I9 I2 I5 I8 I1 I4 I7 IA I3 I6 O7
S7
I7 IA I3 I6 I9 I2 I5 I8 I1 I4 I7 O8
S8
I8 I1 I4 I7 IA I3 I6 I9 I2 I5 I8 O9
S9
I9 I2 I5 I8 I1 I4 I7 IA I3 I6 I9 OA
SA
IA I3 I6 I9 I2 I5 I8 I1 I4 I7 IA
```

## Examples

### Python, Petersen graph embedding

(First attempt at this form to see what it might look like in any language. May be flawed!)

```def p(s):
"""Output wrapper."""
if s[0] == 'S':  # Add newlines to spoke edges
print('\n' + s)
else:
print(s, end=' ')

def inner(n):
"""Inner loop, 5-star polygon."""
for i in range(6):
if n == 1:
p('I1')
n = 3
elif n == 3:
p('I3')
n = 5
elif n == 5:
p('I5')
n = 2
elif n == 2:
p('I2')
n = 4
elif n == 4:
p('I4')
n = 1

if __name__ == '__main__':
i = 0
while i < 2: # Outer loop, 5-poly
p('O1')
if i == 1:
p('S1')
inner(1)
p('O2')
if i == 1:
p('S2')
inner(2)
p('O3')
if i == 1:
p('S3')
inner(3)
p('O4')
if i == 1:
p('S4')A more c
inner(4)
p('O5')
if i == 1:
p('S5')
inner(5)
i += 1
```

#### Compact Python Petersen Graph

Presumably covers the same topology with storage access (see Wire-crossing_problem#Languages_as_graphs):

```O = ['O1', 'O2', 'O3', 'O4', 'O5']
S = ['S1', 'S2', 'S3', 'S4', 'S5']
I = ['I1', 'I3', 'I5', 'I2', 'I4']

print(' '.join(O + [f'{O[i]}\n{S[i]}\n' + ' '.join(I[3 * i % 5:] + I[:1 + 3 * i % 5]) for i in range(5)]))
```

#### Compact Python Desargues Graph

```O = ['O1', 'O2', 'O3', 'O4', 'O5', 'O6', 'O7', 'O8', 'O9', 'OA']
S = ['S1', 'S2', 'S3', 'S4', 'S5', 'S6', 'S7', 'S8', 'S9', 'SA']
I = ['I1', 'I4', 'I7', 'IA', 'I3', 'I6', 'I9', 'I2', 'I5', 'I8']

print(' '.join(O + [f'{O[i]}\n{S[i]}\n' + ' '.join(I[7 * i % 10:] + I[:1 + 7 * i % 10]) for i in range(10)]))
```

### Funge-98 Petersen Graph

```rj2\$@j<            vj:,,,"O5 "<            vj:,,,"O4 "<            vj:,,,"O3 "<            vj:,,,"O2 "<            vj:,,,"O1 "1
a                       a                       a                       a                       a
:                       :                       :                       :                       :
,                       ,                       ,                       ,                       ,
"                       "                       "                       "                       "
5                       4                       3                       2                       1
S                       S                       S                       S                       S
"                       "                       "                       "                       "
,                       ,                       ,                       ,                       ,
,                       ,                       ,                       ,                       ,
,                       ,                       ,                       ,                       ,
6                       6                       6                       6                       6
_^#:-1,,,"I5 "<                                 _^#:-1,,,"I3 "<                                 _^#:-1,,,"I1 "<v
^ <
_^#:-1,,,"I4 "<                                 _^#:-1,,,"I2 "<                        <^
```