Ask Your Question
0

Paths beginning with a certain vertex

asked 2017-08-01 00:09:40 +0100

vukov gravatar image

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 flag offensive close merge delete

2 Answers

Sort by ยป oldest newest most voted
2

answered 2017-08-02 04:50:28 +0100

dan_fulea gravatar image

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

edit flag offensive delete link more
1

answered 2017-08-01 04:42:07 +0100

vukov gravatar image

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)]
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2017-08-01 00:09:40 +0100

Seen: 763 times

Last updated: Aug 02 '17