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, 10000 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 [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/sage-support/d0df352f-a07b-c854-ea78-0234b2006ae9%40uca.fr.
