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