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 "< <^