# 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.

- Once round the outer loop,
- Take spoke
*i*, - Once round the inner loop
- If
*i*==*n*(*n*parameter of the generalised Petersen G(n, k) notation)**HALT**. - Otherwise, back through the (unlabelled) return path of spoke
*i*. - Move to next outer edge
*i+1*and increment*i* - 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 "< <^