How is all_shortest_paths defined?

graph-tool
1

It is hard to say. I will do it when time permits.

2

Time permitted. There is now a function all_paths() in git.

Best,
Tiago

3

Thanks! Is there any documentation on it? I couldn't find anything.

Cheers,

Philipp

4

https://graph-tool.skewed.de/static/doc/dev/topology.html#graph_tool.topology.all_paths

5

I have compared the output of all_paths to that of all_shortest_paths on a
network that I have which contains a reasonable number of "duplicate" edges
(connecting the same two vertices but each having different edge
properties). The shortest path connecting "source" and "target" comprises
two edges.

Running all_shortest_paths(g,source,target) returns me a list of length 201.
Running all_paths(g,source,target,2) returns me a list of length 11. It
seems as if all_paths has "deduplicated" most of the list, however does
contain a few "duplicate" paths (if I remove all "duplicate" paths I obtain
a list of size 8). Why is that? Is this linked to one of them using a
depth-first search while the other uses breadth-first?

Best wishes,

Philipp

6

This is a bug... I've fixed it in git.

Best,
Tiago

7

Thank you! I am just recompiling it and will try it again.

Out of interest, I receive a lot of warnings when running "make" along the
line of "warning: typedef 'index' locally defined but not used
[-Wunused-local-typedefs]
       typedef typename Array::index index;".

Presumably these slow compilation down (?). Are they expected behaviour? If
so, is there a way of suppressing them?

Cheers,

Philipp

8

They don't slow compilation down and are harmless. They come from boost,
not graph-tool, in any case. You can suppress them by passing the
appropriate compiler flags (in this case it would be
-Wno-unused-local-typedefs).

Best,
Tiago