Re: [sage-support] List all shortest paths between two vertices in a graph

[Beth Claire]

Thanks, that does exactly what I needed!  It is significantly faster and 
uses significantly less memory.
--Beth

On Wednesday, August 25, 2021 at 6:33:36 AM UTC-5 Jean-Florent Raymond 
wrote:

> Hello,
>
> The function shortest_simple_paths returns an iterator with paths sorted
> by increasing length. Therefore if you only want paths of minimum
> length, you can iterate over the result of shortest_simple_paths and
> stop as soon as you encounter a longer path. That way you do not iterate
> over all the (possibly many) irrelevant longer paths and, depending on
> how shortest_simple_paths is implemented, you might even avoid to
> compute them.
>
> Something like that:
>
> def shortest_paths_really(G, u, v):
> """Return all the shortest simple paths between u and v"""
>
> uv_paths = G.shortest_simple_paths(u, v)
> first_path = next(uv_paths) # a shortest path
> dist = len(first_path)
> yield first_path
> for path in uv_paths:
> if len(path) > dist:
> # no need to go further: paths are too long for now on
> return
> yield path
>
> It is not obvious that doing so is much faster than your solution: it
> depends on the implementation of shortest_simple_paths, which I did not
> look.
> You can convince yourself that it saves some time at least by looking at
> a graph where two vertices have few shortest paths and many longer paths
> connecting them. For instance in graphs.CircularLadderGraph(n) there are
> only two shortest paths connecting vertices 1 and n but exponentially
> many of longer length.
>
> sage: n = 10
> sage: G = graphs.CircularLadderGraph(n)
> sage: u, v = 1, n
> sage: %timeit list(shortest_paths_really(G, u, v))
> 35.9 µs ± 159 ns per loop (mean ± std. dev. of 7 runs, 1 loops each)
> sage: %timeit list(filter(lambda x: len(x) == 1+G.distance(u, v),
> G.shortest_simple_paths(u, v)))
> 66.6 ms ± 180 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
>
>
> Jean-Florent.
>
> Le 24/08/2021 à 01:39, Beth Claire a écrit :
> > Hi,
> > Given an undirected graph G, and two vertices u and v of G, I want to 
> list 
> > all paths from u to v with a length of d_G(u,v). The built-in function 
> > shortest_simple_paths 
> > <
> https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.shortest_simple_paths>,
>  
>
> > despite its name, seems to list *all* simple paths from u to v. One 
> option 
> > is to filter the output of shortest_simple_paths by length, e.g.
> > list(filter(lambda x: len(x)== 
> > 1+G.distance(u,v)),G.shortest_simple_paths(u,v)))
> > 
> > However, this is extremely inefficient, since it tells sage to generate 
> all 
> > simple paths and then discards most of them. Is there a better way to 
> get 
> > this information?
> > 
> > Thanks,
> > Beth
> > 
>

-- 
You received this message because you are subscribed to the Google Groups 
"sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-support+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-support/7f9051af-9100-496d-937a-100e3ddf3c19n%40googlegroups.com.

Re: [sage-support] List all shortest paths between two vertices in a graph

[Jean-Florent Raymond]

Hello,

The function shortest_simple_paths returns an iterator with paths sorted
by increasing length. Therefore if you only want paths of minimum
length, you can iterate over the result of shortest_simple_paths and
stop as soon as you encounter a longer path. That way you do not iterate
over all the (possibly many) irrelevant longer paths and, depending on
how shortest_simple_paths is implemented, you might even avoid to
compute them.

Something like that:

def shortest_paths_really(G, u, v):
"""Return all the shortest simple paths between u and v"""

uv_paths = G.shortest_simple_paths(u, v)
first_path = next(uv_paths) # a shortest path
dist = len(first_path)
yield first_path
for path in uv_paths:
if len(path) > dist:
# no need to go further: paths are too long for now on
return
yield path

It is not obvious that doing so is much faster than your solution: it
depends on the implementation of shortest_simple_paths, which I did not
look.
You can convince yourself that it saves some time at least by looking at
a graph where two vertices have few shortest paths and many longer paths
connecting them. For instance in graphs.CircularLadderGraph(n) there are
only two shortest paths connecting vertices 1 and n but exponentially
many of longer length.

sage: n = 10
sage: G = graphs.CircularLadderGraph(n)
sage: u, v = 1, n
sage: %timeit list(shortest_paths_really(G, u, v))
35.9 µs ± 159 ns per loop (mean ± std. dev. of 7 runs, 1 loops each)
sage: %timeit list(filter(lambda x: len(x) ==  1+G.distance(u, v),
G.shortest_simple_paths(u, v)))
66.6 ms ± 180 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)


Jean-Florent.

Le 24/08/2021 à 01:39, Beth Claire a écrit :
> Hi,
> Given an undirected graph G, and two vertices u and v of G, I want to list 
> all paths from u to v with a length of d_G(u,v).  The built-in function 
> shortest_simple_paths 
> ,
>  
> despite its name, seems to list *all* simple paths from u to v.  One option 
> is to filter the output of shortest_simple_paths by length, e.g.
> list(filter(lambda x: len(x)== 
> 1+G.distance(u,v)),G.shortest_simple_paths(u,v)))
> 
> However, this is extremely inefficient, since it tells sage to generate all 
> simple paths and then discards most of them.  Is there a better way to get 
> this information?
> 
> Thanks,
> Beth
> 

-- 
You received this message because you are subscribed to the Google Groups 
"sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-support+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-support/d0df352f-a07b-c854-ea78-0234b2006ae9%40uca.fr.

[sage-support] List all shortest paths between two vertices in a graph

[Beth Claire]

Hi,
Given an undirected graph G, and two vertices u and v of G, I want to list 
all paths from u to v with a length of d_G(u,v).  The built-in function 
shortest_simple_paths 
,
 
despite its name, seems to list *all* simple paths from u to v.  One option 
is to filter the output of shortest_simple_paths by length, e.g.
list(filter(lambda x: len(x)== 
1+G.distance(u,v)),G.shortest_simple_paths(u,v)))

However, this is extremely inefficient, since it tells sage to generate all 
simple paths and then discards most of them.  Is there a better way to get 
this information?

Thanks,
Beth

-- 
You received this message because you are subscribed to the Google Groups 
"sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-support+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-support/868b9dc9-7484-4c2f-83c1-de9d2b77bb62n%40googlegroups.com.