ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 02 Aug 2017 04:50:28 +0200Paths beginning with a certain vertexhttps://ask.sagemath.org/question/38452/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?
Tue, 01 Aug 2017 00:09:40 +0200https://ask.sagemath.org/question/38452/paths-beginning-with-a-certain-vertex/Answer by vukov for <p>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$. </p>
<p>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?</p>
https://ask.sagemath.org/question/38452/paths-beginning-with-a-certain-vertex/?answer=38453#post-id-38453I'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)]
Tue, 01 Aug 2017 04:42:07 +0200https://ask.sagemath.org/question/38452/paths-beginning-with-a-certain-vertex/?answer=38453#post-id-38453Answer by dan_fulea for <p>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$. </p>
<p>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?</p>
https://ask.sagemath.org/question/38452/paths-beginning-with-a-certain-vertex/?answer=38460#post-id-38460Let 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.)
Wed, 02 Aug 2017 04:50:28 +0200https://ask.sagemath.org/question/38452/paths-beginning-with-a-certain-vertex/?answer=38460#post-id-38460