Performance search vs shortest_path

graph-tool
1

First of all, thanks a lot for this amazing library.

I have a question about the performance of shortest_path vs dijkstra_search
with a custom Visitor.

I implemented a very basic example
<https://nabble.skewed.de/file/t496286/basic_example.py&gt; with a Visitor
with just the method

Using a graph of approx. 60k edges and 60k vertices, the performance of
dijkstra_search are 30 times slower than the default method shortest_path.

Is this difference normal, or I am doing some error in the code?

Thanks,

Alessandro

2

This is perfectly normal.

The function dijkstra_search() involves the Python interpreter when
invoking your visitor object, but shortest_path() is implemented purely
in C++. This is where the speed difference comes from.

dijkstra_search() is there when you want to customize somehow the search
(see also dijkstra_iterator()). But if you only want to compute shortest
paths or distances, then you should use the specialized functions.

Best,
Tiago

3

Dear Tiago,

Thanks a lot for the prompt answer.

I imagined the reason was the c++ implementation.

Unfortunately for same case I need to implement a graph with time-dependent
weights (e.g. Time Dependent Dijkstra (TDD)), therefore I have to customize
the dijkstra search.

In case I would like to write a c++ extension, which steps do you suggest me
to take?
I saw that you use dijkstra_shortest_paths_no_color_map_no_init from boost
library with the class djk_max_visitor. Do you think I can just extend the
class adding the examine_edge method?

Thanks again,

Alessandro

4

In case I would like to write a c++ extension, which steps do you suggest me
to take?

Read the documentation:

I saw that you use dijkstra_shortest_paths_no_color_map_no_init from boost
library with the class djk_max_visitor. Do you think I can just extend the
class adding the examine_edge method?

Sure, why not...

Best,
Tiago