Re: [graph-tool] dfs/bfs seem to have overhead depending on total graph size

Am 26.02.21 um 12:08 schrieb My-Tien Nguyen:

I noticed that when I call e.g. dfs_iterator or dfs_search on a source vertex, it takes around 1 – 2 seconds to return. The upper bound is depending on the component’s size, but the lower bound seems to be the same for all components.

DFS creates and initializes a property map keeping track of the vertices that have been visited, which is an O(N) operation. It's possible to change the code such that the property map can be passed to the algorithm, and then shared between multiple calls, removing this overhead. Please open an issue in the website, and I'll add this for the next release. Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>