# Paths beginning with a certain vertex

So I have a graph $G$ and a distinguished vertex, labeled with $0$ say. I would like to create a list of all paths of length $k$ that start with $0$.

One way I see how to do this with subgraph_search is to change $0$ into a large clique (larger than the clique number of $G$) and then use subgraph_search_iterator to find all subgraphs with a large clique connected to a path of length $k-1$. However, this seems pretty inefficient. Is there a better way?

edit retag close merge delete

Sort by » oldest newest most voted

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

more

I'm not sure if this is the most efficient, but I did find a way. If you want the the path to begin with (v1, v2), then you can use:

    S = list(SubgraphSearch(G, graphs.PathGraph(n)))
S[:] = [path for path in S if (path[0] == v1 and path[1] == v2)]

more