Mutliple destination Shortest Path Dijkstra

Francois · April 12, 2015, 4:17pm

Hello,

I would like to implement a Mutliple destination Shortest Path Dijkstra, as
in pgrouting <http://docs.pgrouting.org/dev/src/kdijkstra/doc/index.html>
(see also this oldish networkx ticket
<https://networkx.lanl.gov/trac/changeset/c1dbf20b5cbf2d15e1c08846b736572c328db971/networkx>
).

As I need it to be fast, I plan to do it in the CPP side of graph-tool.
However, my CPP skills are quite limited. Would you have some references to
guide me in the right direction ?

Best,
François

Francois · April 12, 2015, 5:18pm

My first guess is to "generalize" the djk_max_visitor
<https://git.skewed.de/count0/graph-tool/blob/master/src/graph/topology/graph_distance.cc#L78>
as
described in this [gist
<https://gist.github.com/Fkawala/6c0a40320d5036e6324e>\], does it sound a
good starting point ?

F.

2015-04-12 18:17 GMT+02:00 François <francois.kawala(a)gmail.com>:

attachment.html (2.75 KB)

Francois · April 12, 2015, 5:23pm

Wrong gist link, sorry, the good one is :
https://gist.github.com/Fkawala/6c0a40320d5036e6324e

2015-04-12 19:18 GMT+02:00 François Kawala <francois.kawala(a)gmail.com>:

attachment.html (3.55 KB)

tiago · April 13, 2015, 3:25pm

Yes, I think this is pretty much it.

Best,
Tiago

Francois · April 13, 2015, 5:23pm

I guess that I should update accordingly the *get_dists *function.

Should I submit a pull request once that done ?

Best,
F.

attachment.html (1.26 KB)

tiago · April 13, 2015, 6:31pm

Sure, but be careful not to compromise the performance in the case where
there is only a single target.

Best,
Tiago

Francois · April 13, 2015, 8:06pm

What would you recommend ?

I would implement a new class called djk_max_multiple_targets_visitor that
would be used in get_dists only when there are more than one target. Does
it sounds good?

F

2015-04-13 20:32 GMT+02:00 Tiago Peixoto [via Main discussion list for the
graph-tool project] <ml-node+s982480n4026068h65(a)n3.nabble.com>:

attachment.html (4.74 KB)

tiago · April 13, 2015, 8:10pm

That sounds like the right approach.

Best,
Tiago

Francois · April 14, 2015, 9:27pm

I forked the grap_tool github repo, and tried to update the
grpah_distance.cc.

The result is visible there
<https://github.com/Fkawala/graph-tool/blob/master/src/graph/topology/graph_distance.cc>\.
However, I'm not familiar with CPP, thus the result might be disappointing.

Would it worth it that I try to go further on this ?

Best,
*—François.*

2015-04-13 22:12 GMT+02:00 Tiago Peixoto [via Main discussion list for the
graph-tool project] <ml-node+s982480n4026070h27(a)n3.nabble.com>:

attachment.html (5.21 KB)

tiago · April 14, 2015, 10:00pm

Your idea is correct, but a couple of things look strange. E.g. in line 111

std::size_t search = _target.find(v);

I'm pretty sure the iterator type of unordered_set<> is not an
integer. Also, in the function definition in line 196 you use
"std::unordered_set tgt", but you cannot receive this type of object
from Python, since it has not yet been exposed.

Did you even try to compile and use it?

(If you want, you can just wait a bit for me to implement this myself in
the next couple of days, since it is not very difficult.)

Best,
Tiago

Francois · April 14, 2015, 10:14pm

I didn't had the chance yet to compile/test it (not sufficient hardware at
this time), I was more asking for the kind a review you gave before to try
to compile/test it.

About your comment on line 196 (which probably also applies to lines 238
and 274), what is proper way to receive a set from python ?

Best,
François

2015-04-15 0:00 GMT+02:00 Tiago de Paula Peixoto <tiago(a)skewed.de>:

attachment.html (2.5 KB)

tiago · April 15, 2015, 7:01am

You have to expose the class to Python using boost::python:

http://www.boost.org/doc/libs/1_57_0/libs/python/doc/tutorial/doc/html/python/exposing.html

However, in this case a much more straightforward approach is to receive
any python iterable (a generic boost::python::object in C++), and
convert it to an unordered_set<> in C++, before the algorithm is run.

Best,
Tiago

Francois · April 17, 2015, 10:02pm

Should this convertion work ?

std::unordered_set<std::size_t> tgt = unordered_set
(std::initializer_list<size_t>
boost::python::stl_input_iterator<size_t>(target_list))

If so, is that efficient ?

Best,
F.

2015-04-15 9:03 GMT+02:00 Tiago Peixoto [via Main discussion list for the
graph-tool project] <ml-node+s982480n4026074h51(a)n3.nabble.com>:

attachment.html (5.09 KB)

Francois · April 17, 2015, 10:04pm

where target_list has type: boost::python::list
f

2015-04-18 0:02 GMT+02:00 François Kawala <francois.kawala(a)gmail.com>:

attachment.html (5.84 KB)

Francois · April 19, 2015, 5:40pm

Hello,

I did try to compile my fork, however it fails in a file that I didn't
modified: graph_blockmodel_covariates.

The error I get is below.

graph_blockmodel_covariates.cc:695:16: error: 'dense_hash_map' was not
declared in this scope
typedef vector<dense_hash_map<size_t, size_t, std::hash<size_t>>> bmap_t;
                ^
graph_blockmodel_covariates.cc:695:63: error: wrong number of template
arguments (3, should be 2)
typedef vector<dense_hash_map<size_t, size_t, std::hash<size_t>>> bmap_t;
                                                               ^
In file included from /usr/include/c++/4.8/vector:64:0,
                 from /usr/include/c++/4.8/bits/random.h:34,
                 from /usr/include/c++/4.8/random:50,
                 from /usr/include/c++/4.8/bits/stl_algo.h:65,
                 from /usr/include/c++/4.8/algorithm:62,
                 from /usr/include/boost/function/detail/prologue.hpp:13,
                 from /usr/include/boost/function/function_template.hpp:13,
                 from
/usr/include/boost/function/detail/maybe_include.hpp:13,
                 from /usr/include/boost/function/function0.hpp:11,
                 from /usr/include/boost/python/errors.hpp:13,
                 from /usr/include/boost/python/handle.hpp:11,
                 from /usr/include/boost/python/args_fwd.hpp:10,
                 from /usr/include/boost/python/args.hpp:10,
                 from /usr/include/boost/python.hpp:11,
                 from graph_blockmodel_covariates.cc:19:
/usr/include/c++/4.8/bits/stl_vector.h:210:11: error: provided for
'template<class _Tp, class _Alloc> class std::vector'
     class vector : protected _Vector_base<_Tp, _Alloc>
           ^
graph_blockmodel_covariates.cc:695:65: error: expected unqualified-id
before '>' token
typedef vector<dense_hash_map<size_t, size_t, std::hash<size_t>>> bmap_t;

Any clues ?

Best,
f

2015-04-18 0:04 GMT+02:00 François <francois.kawala(a)gmail.com>:

attachment.html (10.6 KB)

tiago · April 19, 2015, 5:53pm

This is a bug when sparse_hash is not enabled. I have fixed it now in
git.

Best,
Tiago

Francois · April 22, 2015, 7:54am

Hello,

I realize that my C++ skill aren't sufficient to produce quality /
maintainable / efficient code for this feature. Would you take care of this
?

I've update my github repo <https://github.com/Fkawala/gcloud-python>,
it compiles but does not work.

The current error stack is:

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/usr/lib/python2.7/dist-packages/graph_tool/topology/__init__.py",
line 1337, in shortest_path
    pred_map=True)[1]
  File "/usr/lib/python2.7/dist-packages/graph_tool/topology/__init__.py",
line 1263, in shortest_distance
    dist_map = dist_map[target]
  File "/usr/lib/python2.7/dist-packages/graph_tool/__init__.py", line 438,
in __getitem__
    return self.__map[self.__key_trans(k)]
Boost.Python.ArgumentError: Python argument types in
    VertexPropertyMap<int32_t>.__getitem__(VertexPropertyMap<int32_t>,
tuple)
did not match C++ signature:

__getitem__(graph_tool::PythonPropertyMap<boost::checked_vector_property_map<int,
boost::typed_identity_property_map<unsigned long> > > {lvalue},
graph_tool::PythonVertex)

best,
f

2015-04-19 19:54 GMT+02:00 Tiago Peixoto [via Main discussion list for the
graph-tool project] <ml-node+s982480n4026087h54(a)n3.nabble.com>:

attachment.html (6.42 KB)

tiago · April 22, 2015, 8:35am

This is not really a C++ thing, you are trying to access a vertex
property map with a tuple, instead of a vertex object. This tuple is
probably your list of targets. You need only to update line 1259 in
topology/__init__.py and exclude the case when 'target' is an
iterable. For instance:

    if source is not None and target != -1:
        try:
            dist_map = [dist_map[t] for t in target]
        except TypeError:
            dist_map = dist_map[target]

It seems you are almost there!

Best,
Tiago

Francois · May 3, 2015, 11:18am

Hello,

The shortest_path and shortest_distance functions are fixed to be able to
handle more than one target. In order to be be more explicit, I propose for
those two functions to return a dictionary when there is more than one
target. This dictionary would be keyed by target vertex. What do you think
about that ? This behavior is implemented in
https://github.com/Fkawala/graph-tool.

I did a minimal working example which is there:
https://gist.github.com/Fkawala/afd0a666619c1d2716a5

I guess that next steps are (1) code review, and (2) performance and/or
unit tests? Is that correct ?

Best,
François.

2015-04-22 10:37 GMT+02:00 Tiago Peixoto [via Main discussion list for the
graph-tool project] <ml-node+s982480n4026100h57(a)n3.nabble.com>:

attachment.html (7.09 KB)

tiago · May 4, 2015, 10:36am

Hello,

The shortest_path and shortest_distance functions are fixed to be able
to handle more than one target. In order to be be more explicit, I
propose for those two functions to return a dictionary when there is
more than one target. This dictionary would be keyed by target
vertex. What do you think about that ?

I would actually prefer this to be a numpy array, with the same ordering
as the list of targets... It seems more coherent with the input, and the
dict seems wasteful.

I did a minimal working example which is there: MWE graph_tool shortest path / distance with multiple targets · GitHub

I guess that next steps are (1) code review, and (2) performance and/or unit tests? Is that correct ?

Yes. For unit tests is suffices if you add an example with multiple
targets in the docstring (which will be run via sphinx).

Just some quick comments (not a full review):

     1. You changed the name of the parameter from "target" to
        "targets". Since this breaks backwards compatibility with a very
        commonly used function, that is overwhelmingly called with only
        one target, I think it makes more sense to keep the parameter as
        "target", and mention in the docstring that it accepts *both* a
        singe vertex as well as an iterable.

     2. In the code comments you write the case with one target as being
        "backwards compatibility". As per the comment above, it should
        be considered as a standard behavior, not just backwards
        compatibility.

     3. You use targets= as a default parameter. It is dangerous to
        use an empty list as default parameter, since it is mutable, and
        hence can change in the course of the program! You should
        replace this with "target = None".

     4. The indentation in C++ is not coherent with the rest of the
        program (e.g. line 114 in graph_distance.cc). You should use
        four spaces at each indentation level. The placement of braces
        is also sometimes wrong (e.g. line 219).

Also, before submitting a merge request, please merge all "bugfix" and
such trivial commits into self-contained commits with a clear
descriptions.

Best,
Tiago