Hi, A much faster way is to use shortest_distance() to return a predecessor map: dist, pred = shortest_distance(g, source=v, pred_map=True) The "pred" map contains for each vertex reachable from v the predecessor node in the BFS (or Dijkstra if weighted) tree. Best, Tiago On 16.08.2015 16:00, Christopher Morris wrote:

Okay, I'm sorry, seems to be solved by dijkstra_search(...).

On 16.08.2015 15:56, Christopher Morris wrote:

...

Hi,

given a vertex v, I want compute all shortest paths starting at v, i.e., I want a list of edge or vertex lists, or some kind of DAG. Of course this can be easily solved by Dijkstra's Algorithm, but Graph-Tools doesn't seem to provide the right interface for this problem.

Any ideas?

Best regards, Chris _______________________________________________ graph-tool mailing list graph-tool@skewed.de http://lists.skewed.de/mailman/listinfo/graph-tool

_______________________________________________ graph-tool mailing list graph-tool@skewed.de http://lists.skewed.de/mailman/listinfo/graph-tool

-- Tiago de Paula Peixoto <tiago@skewed.de>

On 17.08.2015 10:40, Christopher Morris wrote:

Is it somehow possible to obtain a successor relation instead of a predecessor relation?

You can convert the predecessor map into a tree using predecessor_tree(), and then you can traverse it in any way you want: http://graph-tool.skewed.de/static/doc/generation.html#graph_tool.generation... Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>

On 17.08.2015 17:23, Christopher Morris wrote:

Thanks, is it also possible to obtain the leaves of the resulting tree without traversing the whole tree?

The leaves are just the nodes that are visited last by the BFS/Dijkstra, i.e. the ones that are furthest away from the source. Are you sure this is what you want? In any case, the answer is no, you have to find them in the tree. Note however that the ordering of the nodes in this tree are the same as in the original graph. So if you want to traverse the successor/predecessor of any particular node v in the original graph, you can lookup t.vertex(v) in time O(1), where t is the predecessor tree. Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>