Hi!
For the project I'm working on I need to calculate distances on a graph from a couple of vertices to all other vertices. The topology.shortest_distance can only do either from all vertices or from a single one, and to save time I'd like this to run in parallel, so I set out to implement this in C++. I took inspiration from graph-tool's implementation of shortest_distance for pair-wise distances in unweighted graphs (running BFS from all vertices in parallel), and managed to modify that to only run from some vertices. However I ran into a problem trying to do the same for weighted graphs. I think the problem I have is that when passing the vector for distances to all vertices it is supposed to be a property map and not a vector, but I cannot figure out how to get a 1d property map from a 2d property map on a C++ level, basically I pass a vector<double> property map to my function but I need to pass a simple double property map to the dijskstra function from boost. Could anyone please help me point to how would I do that? Or is my approach wrong completely? What most confuses me that the same approach works fine for breadth_first_search.
The errors I'm getting in compilation:
/usr/include/boost/graph/dijkstra_shortest_paths_no_color_map.hpp:43:63: error: no type named ‘value_type’ in ‘struct boost::property_traits<std::vector<double> >’ 43 | typedef typename property_traits<DistanceMap>::value_type Distance;
/usr/include/boost/pending/indirect_cmp.hpp:32:78: error: no type named ‘value_type’ in ‘struct boost::property_traits<std::vector<double> >’ 32 | typedef typename boost::property_traits<ReadablePropertyMap>::value_type T; | ^ /usr/include/boost/pending/indirect_cmp.hpp:33:76: error: no type named ‘key_type’ in ‘struct boost::property_traits<std::vector<double> >’ 33 | typedef typename boost::property_traits<ReadablePropertyMap>::key_type K;
Thank you,
Mikuláš
Hi Mikuláš,
Posting the compilation errors without showing the source code is not very useful...
It's possible to adapt property maps, but I think the simplest approach for you would be to use an auxiliary scalar property map, and then copy its values into the vector property map. However, I'm only speculating, since you described your task only very vaguely.
Best, Tiago
Am 08.08.19 um 10:06 schrieb Mikuláš Poul:
Hi!
For the project I'm working on I need to calculate distances on a graph from a couple of vertices to all other vertices. The topology.shortest_distance can only do either from all vertices or from a single one, and to save time I'd like this to run in parallel, so I set out to implement this in C++. I took inspiration from graph-tool's implementation of shortest_distance for pair-wise distances in unweighted graphs (running BFS from all vertices in parallel), and managed to modify that to only run from some vertices. However I ran into a problem trying to do the same for weighted graphs. I think the problem I have is that when passing the vector for distances to all vertices it is supposed to be a property map and not a vector, but I cannot figure out how to get a 1d property map from a 2d property map on a C++ level, basically I pass a vector<double> property map to my function but I need to pass a simple double property map to the dijskstra function from boost. Could anyone please help me point to how would I do that? Or is my approach wrong completely? What most confuses me that the same approach works fine for breadth_first_search.
The errors I'm getting in compilation:
/usr/include/boost/graph/dijkstra_shortest_paths_no_color_map.hpp:43:63: error: no type named ‘value_type’ in ‘struct boost::property_traits<std::vector<double> >’ 43 | typedef typename property_traits<DistanceMap>::value_type Distance;
/usr/include/boost/pending/indirect_cmp.hpp:32:78: error: no type named ‘value_type’ in ‘struct boost::property_traits<std::vector<double> >’ 32 | typedef typename boost::property_traits<ReadablePropertyMap>::value_type T; | ^ /usr/include/boost/pending/indirect_cmp.hpp:33:76: error: no type named ‘key_type’ in ‘struct boost::property_traits<std::vector<double> >’ 33 | typedef typename boost::property_traits<ReadablePropertyMap>::key_type K;
Thank you,
Mikuláš
graph-tool mailing list graph-tool@skewed.de https://lists.skewed.de/mailman/listinfo/graph-tool
Thank you for the suggestion, for some reason that did not come to mind when I was coding it, I tried it out and finally managed to get it working.
Thanks again, Mikuláš
-- Sent from: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/
Hi Tiago,
I also got a similar question, how can I get the time series 'ss' from the vertex property map?
Thanks, Yingjie
-- Sent from: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/
Am 26.08.19 um 15:17 schrieb lenarpooo:
Hi Tiago,
I also got a similar question, how can I get the time series 'ss' from the vertex property map?
In that example, ss is a list of property maps, as the code shows. Each item in the list contains a property map with the state of all nodes for one point in time. So, e.g. ss[10][v] refers to the state of node 'v' at time 10.
Best, Tiago
Thanks, but I'm still a bit confused as ss[10][v] is an array of length 10, does it mean that the whole vector represents a single state for v? And when I try to copy other time series in ss
sss=[] for i in range(200): vpp=gp.new_vp("vector<double>") for v in gp.get_vertices(): x = np.array(ts[i])[0][v] vpp[v]=np.array([x]) sss.append(vpp)
where ts[i] is each time series in numpy.array, it reports the error. http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/file/t496178/%E5%B1%8F%E5%B9%95%E5%BF%AB%E7%85%A7_2019-08-29_%E4%B8%8B%E5%8D%884.png
Many thanks,
Yingjie
-- Sent from: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/
Am 29.08.19 um 10:59 schrieb lenarpooo:
Thanks, but I'm still a bit confused as ss[10][v] is an array of length 10, does it mean that the whole vector represents a single state for v? And when I try to copy other time series in ss
sss=[] for i in range(200): vpp=gp.new_vp("vector<double>") for v in gp.get_vertices(): x = np.array(ts[i])[0][v] vpp[v]=np.array([x]) sss.append(vpp)
where ts[i] is each time series in numpy.array, it reports the error. http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/file/t496178/%E5%B1%8F%E5%B9%95%E5%BF%AB%E7%85%A7_2019-08-29_%E4%B8%8B%E5%8D%884.png
Ah, sorry it is fact transposed. In the original example, ss is a list of many time series. Each one is a vector-value property map, containing for each node its own time series.
(BTW, please don't post images of error messages which are just text. Just post the text.)
Best, Tiago
That really solves my problem!
By the way, is it possible to recover the partition using float-type time series data?
Best wishes,
Yingjie
-- Sent from: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/
-
lenarpooo -
mikicz -
Mikuláš Poul
-
Tiago de Paula Peixoto