1 | initial version |

Let us start with the following code:

```
def findAllPaths( G, startVertex, length ):
vertices = G.vertices()
edges = G.edges( labels=False )
sim_edges = [ (k,j) for (j,k) in edges if j != k ]
edges += sim_edges
edges . sort()
paths = [ [ startVertex, ] ]
L = 0
while L < length:
paths = [ pat + [ vertex, ]
for pat in paths
for vertex in vertices
if ( pat[-1], vertex ) in edges ]
L += 1
return paths
G = graphs.OctahedralGraph()
pathsG7 = findAllPaths( G, 0, 7 )
for path in pathsG7:
print ''.join( [ str(v) for v in path ] )
```

(There was no check for `length in ZZ and length >=0`

with a corresponding traceback information.)
The result list ends with

```
04545420
04545421
04545424
04545425
04545430
04545431
04545434
04545435
04545451
04545452
04545453
04545454
```

One more check:

```
sage: len( pathsG7 )
16384
sage: 4^7
16384
```

The code uses a simple recursion and computes relatively quick the $4^7$ paths starting from node $0$ inside the octahedral graph. The recursion scheme is not optimal, since the `while`

block is simply structured w.r.t. the constructive path length, which covers the values $0,1,2,3,4,5,6,7$, parallel to the "split" $7 = 1+1+1+1+1+1+1 $.

A better recursion would have been to "split in two almost equal parts", writing $7=4+3$, then make dictionaries for all paths of length $4$ and $3$, with keys (starting + ending points). The while block would join them. This is going almost to the half of the length. Now write $4=2+2$ and $3=2+1$, and so on. (It is a kind of quicksort-splitting of the number.) Then further split $2=1+1$. Starting with $27$ instead of $7$ (and having a rather sparse adjacency), we would then write:

- either $27=16+8+2+1$, and each programmer would already feel happy,
- or $27=14+13$, $14=7+7$ and $13=6+7$, and $7=4+3$, $6=3+3$, and... and each programmer would hate the boss for this idea.

The coding effort can now be chosen depending on the graph and the length... I tried something like:

```
def quickFindAllPaths( G, startVertex, length ):
vertices = G.vertices()
edges = G.edges( labels=False )
sim_edges = [ (k,j) for (j,k) in edges if j != k ]
edges += sim_edges
twopowerlogs = [ k
for k in [ 0 .. ceil( log(length) / log(2) ) ]
if 2**k <= length ] # sorry, i never trust numeric approximations
dic = {} # dic of lists, k -> { v -> paths from v of length k }
dic[0] = dict( [ ( v, [ [x,w] for (x,w) in edges if v == x ] )
for v in vertices ] ) # paths of len = 2^0
for k in twopowerlogs:
if k == 0: continue
dic[k] = {}
print "k=", k
pprint.pprint( dic[k-1] )
for v in vertices:
dic[k] [ v ] = [ vw + wx[1:]
for w in vertices
for vw in dic[k-1] [ v ]
for wx in dic[k-1] [ w ]
if vw[-1] == w ] # paths of len 2^(k-1)+ 2^(k-1) = 2^k
# and finally we join...
digits = length.digits( base=2 )
relevant_k_list = [ k
for k in range( len( digits ) )
if digits[ k ] ]
relevant_k_list . reverse()
j = 0
k0 = relevant_k_list[ 0 ]
paths = dic[ k0 ] [ startVertex ]
while j < len( relevant_k_list ) - 1:
j += 1
k = relevant_k_list[ j ]
paths = [ pathtow + pathfromw[1:]
for w in vertices
for pathtow in paths
for pathfromw in dic[k] [ w ]
if pathtow[-1] == w ]
return paths
G = graphs.OctahedralGraph()
quickpathsG7 = quickFindAllPaths( G, 0, 7 )
quickpathsG7 . sort()
for path in quickpathsG7:
print ''.join( [ str(v) for v in path ] )
```

Sorry for not documenting the function properly, best, write a better version. (The list comprehensions make the computation suboptimal.)

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.