Paths beginning with a certain vertex

savecancel

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