Mutliple destination Shortest Path Dijkstra
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 -- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.
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@gmail.com>:
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/c1dbf20b5cbf2d15e1c08846b736572c328...
).
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
-- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com. _______________________________________________ graph-tool mailing list graph-tool@skewed.de http://lists.skewed.de/mailman/listinfo/graph-tool
-- François Kawala
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@gmail.com>:
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@gmail.com>:
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/c1dbf20b5cbf2d15e1c08846b736572c328...
).
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
-- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com. _______________________________________________ graph-tool mailing list graph-tool@skewed.de http://lists.skewed.de/mailman/listinfo/graph-tool
-- François Kawala
-- François Kawala
On 12.04.2015 20:23, François Kawala wrote:
Wrong gist link, sorry, the good one is : https://gist.github.com/Fkawala/6c0a40320d5036e6324e
Yes, I think this is pretty much it. Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
I guess that I should update accordingly the *get_dists *function. Should I submit a pull request once that done ? Best, F. Le lun. 13 avr. 2015 à 17:27, Tiago de Paula Peixoto <tiago@skewed.de> a écrit :
On 12.04.2015 20:23, François Kawala wrote:
Wrong gist link, sorry, the good one is : https://gist.github.com/Fkawala/6c0a40320d5036e6324e
Yes, I think this is pretty much it.
Best, Tiago
-- Tiago de Paula Peixoto <tiago@skewed.de>
_______________________________________________ graph-tool mailing list graph-tool@skewed.de http://lists.skewed.de/mailman/listinfo/graph-tool
On 13.04.2015 20:23, François Kawala wrote:
I guess that I should update accordingly the *get_dists *function.
Should I submit a pull request once that done ?
Sure, but be careful not to compromise the performance in the case where there is only a single target. Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
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@n3.nabble.com>:
On 13.04.2015 20:23, François Kawala wrote:
I guess that I should update accordingly the *get_dists *function.
Should I submit a pull request once that done ?
Sure, but be careful not to compromise the performance in the case where there is only a single target.
Best, Tiago
-- Tiago de Paula Peixoto <[hidden email] <http:///user/SendEmail.jtp?type=node&node=4026068&i=0>>
_______________________________________________ graph-tool mailing list [hidden email] <http:///user/SendEmail.jtp?type=node&node=4026068&i=1> http://lists.skewed.de/mailman/listinfo/graph-tool
*signature.asc* (836 bytes) Download Attachment <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/attachment/4026068/0/signature.asc> -- Tiago de Paula Peixoto <tiago@skewed.de>
------------------------------ If you reply to this email, your message will be added to the discussion below:
http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... To start a new topic under Main discussion list for the graph-tool project, email ml-node+s982480n2141189h16@n3.nabble.com To unsubscribe from Main discussion list for the graph-tool project, click here <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/template/NamlServlet.jtp?macro=unsubscribe_by_code&node=2141189&code=ZnJhbmNvaXMua2F3YWxhQGdtYWlsLmNvbXwyMTQxMTg5fDIxMTQ0MDk4Nzk=> . NAML <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/template/NamlServlet.jtp?macro=macro_viewer&id=instant_html%21nabble%3Aemail.naml&base=nabble.naml.namespaces.BasicNamespace-nabble.view.web.template.NabbleNamespace-nabble.view.web.template.NodeNamespace&breadcrumbs=notify_subscribers%21nabble%3Aemail.naml-instant_emails%21nabble%3Aemail.naml-send_instant_email%21nabble%3Aemail.naml>
-- François Kawala -- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.
On 13.04.2015 23:06, François wrote:
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?
That sounds like the right approach. Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
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@n3.nabble.com>:
On 13.04.2015 23:06, François wrote:
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?
That sounds like the right approach.
Best, Tiago
-- Tiago de Paula Peixoto <[hidden email] <http:///user/SendEmail.jtp?type=node&node=4026070&i=0>>
_______________________________________________ graph-tool mailing list [hidden email] <http:///user/SendEmail.jtp?type=node&node=4026070&i=1> http://lists.skewed.de/mailman/listinfo/graph-tool
*signature.asc* (836 bytes) Download Attachment <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/attachment/4026070/0/signature.asc> -- Tiago de Paula Peixoto <tiago@skewed.de>
------------------------------ If you reply to this email, your message will be added to the discussion below:
http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... To start a new topic under Main discussion list for the graph-tool project, email ml-node+s982480n2141189h16@n3.nabble.com To unsubscribe from Main discussion list for the graph-tool project, click here <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/template/NamlServlet.jtp?macro=unsubscribe_by_code&node=2141189&code=ZnJhbmNvaXMua2F3YWxhQGdtYWlsLmNvbXwyMTQxMTg5fDIxMTQ0MDk4Nzk=> . NAML <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/template/NamlServlet.jtp?macro=macro_viewer&id=instant_html%21nabble%3Aemail.naml&base=nabble.naml.namespaces.BasicNamespace-nabble.view.web.template.NabbleNamespace-nabble.view.web.template.NodeNamespace&breadcrumbs=notify_subscribers%21nabble%3Aemail.naml-instant_emails%21nabble%3Aemail.naml-send_instant_email%21nabble%3Aemail.naml>
-- François Kawala -- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.
On 15.04.2015 00:27, François wrote:
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 ?
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 -- Tiago de Paula Peixoto <tiago@skewed.de>
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@skewed.de>:
On 15.04.2015 00:27, François wrote:
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 ?
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
-- Tiago de Paula Peixoto <tiago@skewed.de>
_______________________________________________ graph-tool mailing list graph-tool@skewed.de http://lists.skewed.de/mailman/listinfo/graph-tool
-- François Kawala
On 15.04.2015 01:14, François Kawala wrote:
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 ?
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/pytho... 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 -- Tiago de Paula Peixoto <tiago@skewed.de>
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@n3.nabble.com>:
On 15.04.2015 01:14, François Kawala wrote:
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 ?
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/pytho...
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
-- Tiago de Paula Peixoto <[hidden email] <http:///user/SendEmail.jtp?type=node&node=4026074&i=0>>
_______________________________________________ graph-tool mailing list [hidden email] <http:///user/SendEmail.jtp?type=node&node=4026074&i=1> http://lists.skewed.de/mailman/listinfo/graph-tool
*signature.asc* (836 bytes) Download Attachment <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/attachment/4026074/0/signature.asc> -- Tiago de Paula Peixoto <tiago@skewed.de>
------------------------------ If you reply to this email, your message will be added to the discussion below:
http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... To start a new topic under Main discussion list for the graph-tool project, email ml-node+s982480n2141189h16@n3.nabble.com To unsubscribe from Main discussion list for the graph-tool project, click here <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/template/NamlServlet.jtp?macro=unsubscribe_by_code&node=2141189&code=ZnJhbmNvaXMua2F3YWxhQGdtYWlsLmNvbXwyMTQxMTg5fDIxMTQ0MDk4Nzk=> . NAML <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/template/NamlServlet.jtp?macro=macro_viewer&id=instant_html%21nabble%3Aemail.naml&base=nabble.naml.namespaces.BasicNamespace-nabble.view.web.template.NabbleNamespace-nabble.view.web.template.NodeNamespace&breadcrumbs=notify_subscribers%21nabble%3Aemail.naml-instant_emails%21nabble%3Aemail.naml-send_instant_email%21nabble%3Aemail.naml>
-- François Kawala -- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.
where target_list has type: boost::python::list f 2015-04-18 0:02 GMT+02:00 François Kawala <francois.kawala@gmail.com>:
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@n3.nabble.com>:
On 15.04.2015 01:14, François Kawala wrote:
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 ?
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/pytho...
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
-- Tiago de Paula Peixoto <[hidden email] <http:///user/SendEmail.jtp?type=node&node=4026074&i=0>>
_______________________________________________ graph-tool mailing list [hidden email] <http:///user/SendEmail.jtp?type=node&node=4026074&i=1> http://lists.skewed.de/mailman/listinfo/graph-tool
*signature.asc* (836 bytes) Download Attachment <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/attachment/4026074/0/signature.asc> -- Tiago de Paula Peixoto <tiago@skewed.de>
------------------------------ If you reply to this email, your message will be added to the discussion below:
http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... To start a new topic under Main discussion list for the graph-tool project, email ml-node+s982480n2141189h16@n3.nabble.com To unsubscribe from Main discussion list for the graph-tool project, click here <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/template/NamlServlet.jtp?macro=unsubscribe_by_code&node=2141189&code=ZnJhbmNvaXMua2F3YWxhQGdtYWlsLmNvbXwyMTQxMTg5fDIxMTQ0MDk4Nzk=> . NAML <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/template/NamlServlet.jtp?macro=macro_viewer&id=instant_html%21nabble%3Aemail.naml&base=nabble.naml.namespaces.BasicNamespace-nabble.view.web.template.NabbleNamespace-nabble.view.web.template.NodeNamespace&breadcrumbs=notify_subscribers%21nabble%3Aemail.naml-instant_emails%21nabble%3Aemail.naml-send_instant_email%21nabble%3Aemail.naml>
-- François Kawala
-- François Kawala -- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.
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@gmail.com>:
where target_list has type: boost::python::list f
2015-04-18 0:02 GMT+02:00 François Kawala <[hidden email] <http:///user/SendEmail.jtp?type=node&node=4026083&i=0>>:
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] <[hidden email] <http:///user/SendEmail.jtp?type=node&node=4026083&i=1>>:
On 15.04.2015 01:14, François Kawala wrote:
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 ?
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/pytho...
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
-- Tiago de Paula Peixoto <[hidden email] <http:///user/SendEmail.jtp?type=node&node=4026074&i=0>>
_______________________________________________ graph-tool mailing list [hidden email] <http:///user/SendEmail.jtp?type=node&node=4026074&i=1> http://lists.skewed.de/mailman/listinfo/graph-tool
*signature.asc* (836 bytes) Download Attachment <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/attachment/4026074/0/signature.asc> -- Tiago de Paula Peixoto <[hidden email] <http:///user/SendEmail.jtp?type=node&node=4026083&i=2>>
------------------------------ If you reply to this email, your message will be added to the discussion below:
http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... To start a new topic under Main discussion list for the graph-tool project, email [hidden email] <http:///user/SendEmail.jtp?type=node&node=4026083&i=3> To unsubscribe from Main discussion list for the graph-tool project, click here. NAML <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/template/NamlServlet.jtp?macro=macro_viewer&id=instant_html%21nabble%3Aemail.naml&base=nabble.naml.namespaces.BasicNamespace-nabble.view.web.template.NabbleNamespace-nabble.view.web.template.NodeNamespace&breadcrumbs=notify_subscribers%21nabble%3Aemail.naml-instant_emails%21nabble%3Aemail.naml-send_instant_email%21nabble%3Aemail.naml>
-- François Kawala
-- François Kawala
------------------------------ View this message in context: Re: Mutliple destination Shortest Path Dijkstra <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/Mutliple-destination-Shortest-Path-Dijkstra-tp4026059p4026083.html> Sent from the Main discussion list for the graph-tool project mailing list archive <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/> at Nabble.com.
_______________________________________________ graph-tool mailing list graph-tool@skewed.de http://lists.skewed.de/mailman/listinfo/graph-tool
-- François Kawala
On 19.04.2015 20:40, François Kawala wrote:
I did try to compile my fork, however it fails in a file that I didn't modified: graph_blockmodel_covariates.
This is a bug when sparse_hash is not enabled. I have fixed it now in git. Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
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@n3.nabble.com>:
On 19.04.2015 20:40, François Kawala wrote:
I did try to compile my fork, however it fails in a file that I didn't modified: graph_blockmodel_covariates.
This is a bug when sparse_hash is not enabled. I have fixed it now in git.
Best, Tiago
-- Tiago de Paula Peixoto <[hidden email] <http:///user/SendEmail.jtp?type=node&node=4026087&i=0>>
_______________________________________________ graph-tool mailing list [hidden email] <http:///user/SendEmail.jtp?type=node&node=4026087&i=1> http://lists.skewed.de/mailman/listinfo/graph-tool
*signature.asc* (836 bytes) Download Attachment <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/attachment/4026087/0/signature.asc> -- Tiago de Paula Peixoto <tiago@skewed.de>
------------------------------ If you reply to this email, your message will be added to the discussion below:
http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... To start a new topic under Main discussion list for the graph-tool project, email ml-node+s982480n2141189h16@n3.nabble.com To unsubscribe from Main discussion list for the graph-tool project, click here <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/template/NamlServlet.jtp?macro=unsubscribe_by_code&node=2141189&code=ZnJhbmNvaXMua2F3YWxhQGdtYWlsLmNvbXwyMTQxMTg5fDIxMTQ0MDk4Nzk=> . NAML <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/template/NamlServlet.jtp?macro=macro_viewer&id=instant_html%21nabble%3Aemail.naml&base=nabble.naml.namespaces.BasicNamespace-nabble.view.web.template.NabbleNamespace-nabble.view.web.template.NodeNamespace&breadcrumbs=notify_subscribers%21nabble%3Aemail.naml-instant_emails%21nabble%3Aemail.naml-send_instant_email%21nabble%3Aemail.naml>
-- François Kawala -- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.
On 22.04.2015 10:54, François wrote:
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)
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 -- Tiago de Paula Peixoto <tiago@skewed.de>
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@n3.nabble.com>:
On 22.04.2015 10:54, François wrote:
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) 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
-- Tiago de Paula Peixoto <[hidden email] <http:///user/SendEmail.jtp?type=node&node=4026100&i=0>>
_______________________________________________ graph-tool mailing list [hidden email] <http:///user/SendEmail.jtp?type=node&node=4026100&i=1> http://lists.skewed.de/mailman/listinfo/graph-tool
*signature.asc* (836 bytes) Download Attachment <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/attachment/4026100/0/signature.asc> -- Tiago de Paula Peixoto <tiago@skewed.de>
------------------------------ If you reply to this email, your message will be added to the discussion below:
http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... To start a new topic under Main discussion list for the graph-tool project, email ml-node+s982480n2141189h16@n3.nabble.com To unsubscribe from Main discussion list for the graph-tool project, click here <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/template/NamlServlet.jtp?macro=unsubscribe_by_code&node=2141189&code=ZnJhbmNvaXMua2F3YWxhQGdtYWlsLmNvbXwyMTQxMTg5fDIxMTQ0MDk4Nzk=> . NAML <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/template/NamlServlet.jtp?macro=macro_viewer&id=instant_html%21nabble%3Aemail.naml&base=nabble.naml.namespaces.BasicNamespace-nabble.view.web.template.NabbleNamespace-nabble.view.web.template.NodeNamespace&breadcrumbs=notify_subscribers%21nabble%3Aemail.naml-instant_emails%21nabble%3Aemail.naml-send_instant_email%21nabble%3Aemail.naml>
-- François Kawala -- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.
On 03.05.2015 13:18, François wrote:
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: 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 ?
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 -- Tiago de Paula Peixoto <tiago@skewed.de>
I'll do these modifications and submit a PR. Best, François. 2015-05-04 12:36 GMT+02:00 Tiago de Paula Peixoto <tiago@skewed.de>:
On 03.05.2015 13:18, François wrote:
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: 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 ?
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
-- Tiago de Paula Peixoto <tiago@skewed.de>
_______________________________________________ graph-tool mailing list graph-tool@skewed.de http://lists.skewed.de/mailman/listinfo/graph-tool
-- François Kawala
participants (3)
-
François -
François Kawala
-
Tiago de Paula Peixoto