How is all_shortest_paths defined?
Hello, I was wondering how the all_shortest_paths function was defined. I have a large network ("g"). In that network there are two nodes ("source" and "target", say) for which I am interested as to how they interconnect.
From prior research I know that there is at least one set of connections between them. I have verified that this path actually exists in the network manually as far as I can tell.
When I however run all_shortest_paths(g,source,target) this path is not part of the results set. Why is that? Does all_shortest_paths stop searching after it has found a certain number of results? If so, is it possible to change this cut-off criterion? Finally, is it possible to also obtain an edge descriptor as a result? Currently I think the documentation states that the result is an iterator over the sequence of vertices from source to target. Best wishes, Philipp
On 09.03.2016 22:17, Philipp-Maximilian Jacob wrote:
When I however run all_shortest_paths(g,source,target) this path is not part of the results set. Why is that?
The function finds all _shortest_ paths, not all paths. Are you sure the known path belong to the shortest set?
Finally, is it possible to also obtain an edge descriptor as a result? Currently I think the documentation states that the result is an iterator over the sequence of vertices from source to target.
You can get the edge between any two vertices u and v by calling the Graph.edge(u, v) function. Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
The known path is three steps long (i.e. contains four vertices) while the paths returned by all_shortest_paths are only two steps long. Is there any way of extending the cut off criterion for all_shortest_paths so that it would return the known path too? My problem with the graph.edge(u,v) function for me in this case is the fact that in many cases I have multiple edges connecting two given vertices. Each edge has a unique ID allowing me to link it back to an entry in an external database. Though it is of interest to me which vertices lie along the path when I run all_shortest_paths what I really am after are the IDs associated to the edges along the path. It seems to me as if graph.edge(u,v) only returns one edge when called. So when I have twenty edges that each link u and v I am not sure yet how I can access the other edges to obtain their IDs. I could presumably note down the edge and then delete it and then rerun graph.edge but that probably is not the most ideal way. Best, Philipp -----Original Message----- From: graph-tool [mailto:graph-tool-bounces@skewed.de] On Behalf Of Tiago de Paula Peixoto Sent: 09 March 2016 21:22 To: graph-tool@skewed.de Subject: Re: [graph-tool] How is all_shortest_paths defined? On 09.03.2016 22:17, Philipp-Maximilian Jacob wrote:
When I however run all_shortest_paths(g,source,target) this path is not part of the results set. Why is that?
The function finds all _shortest_ paths, not all paths. Are you sure the known path belong to the shortest set?
Finally, is it possible to also obtain an edge descriptor as a result? Currently I think the documentation states that the result is an iterator over the sequence of vertices from source to target.
You can get the edge between any two vertices u and v by calling the Graph.edge(u, v) function. 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 09.03.2016 22:58, Philipp-Maximilian Jacob wrote:
The known path is three steps long (i.e. contains four vertices) while the paths returned by all_shortest_paths are only two steps long. Is there any way of extending the cut off criterion for all_shortest_paths so that it would return the known path too?
So, you want a function that returns all shortest paths to return a path that is not the shortest one? There is no "cut off criterion"... The algorithm finds the shortest paths, which in this case are paths of length two.
It seems to me as if graph.edge(u,v) only returns one edge when called.
Please take a more careful look at the documentation: https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.edg... Note what it says about the "all_edges" argument: "If all_edges=True then a list is returned with all the parallel edges from s to t, otherwise only one edge is returned." Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
Yes and no. What I am really after is an algorithm that returns me all paths connecting two given nodes up to a certain path length as I want to then analyse this result set further to analyse how "efficient" a given path is. For me there is some correlation between path length and efficiency, however, the shortest path may not necessarily be the most efficient path so I need to define the result set that I feed into my analysis slightly wider than just the list of shortest paths. In this case I may be interested in e.g. all paths of length 3, 4, and 5. I realise that returning all paths connecting two nodes may lead to combinatorial explosion in some cases but is it possible to get graph-tool to return all paths up to a certain length? Thank you for pointing me towards that documentation entry - I should indeed clearly have read it more carefully. Best wishes, Philipp -----Original Message----- From: graph-tool [mailto:graph-tool-bounces@skewed.de] On Behalf Of Tiago de Paula Peixoto Sent: 09 March 2016 22:13 To: graph-tool@skewed.de Subject: Re: [graph-tool] How is all_shortest_paths defined? On 09.03.2016 22:58, Philipp-Maximilian Jacob wrote:
The known path is three steps long (i.e. contains four vertices) while the paths returned by all_shortest_paths are only two steps long. Is there any way of extending the cut off criterion for all_shortest_paths so that it would return the known path too?
So, you want a function that returns all shortest paths to return a path that is not the shortest one? There is no "cut off criterion"... The algorithm finds the shortest paths, which in this case are paths of length two.
It seems to me as if graph.edge(u,v) only returns one edge when called.
Please take a more careful look at the documentation: https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.edg... Note what it says about the "all_edges" argument: "If all_edges=True then a list is returned with all the parallel edges from s to t, otherwise only one edge is returned." Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
On 09.03.2016 23:39, Philipp-Maximilian Jacob wrote:
I realise that returning all paths connecting two nodes may lead to combinatorial explosion in some cases but is it possible to get graph-tool to return all paths up to a certain length?
A function that returns all paths is not yet implemented, but is planned. Please open a feature-request issue in the website to help speed it up. Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
Done. Thank you. Do you know how long it may take until this function appears? I have no idea how complex it is to implement or how many other projects may be pending so excuse the potentially naïve question. -----Original Message----- From: graph-tool [mailto:graph-tool-bounces@skewed.de] On Behalf Of Tiago de Paula Peixoto Sent: 09 March 2016 22:48 To: graph-tool@skewed.de Subject: Re: [graph-tool] How is all_shortest_paths defined? On 09.03.2016 23:39, Philipp-Maximilian Jacob wrote:
I realise that returning all paths connecting two nodes may lead to combinatorial explosion in some cases but is it possible to get graph-tool to return all paths up to a certain length?
A function that returns all paths is not yet implemented, but is planned. Please open a feature-request issue in the website to help speed it up. Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
On 10.03.2016 00:10, Tiago de Paula Peixoto wrote:
On 10.03.2016 00:08, Philipp-Maximilian Jacob wrote:
Do you know how long it may take until this function appears?
It is hard to say. I will do it when time permits.
Time permitted. There is now a function all_paths() in git. Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
Thanks! Is there any documentation on it? I couldn't find anything. Cheers, Philipp -- 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 14.03.2016 13:43, P-M wrote:
Thanks! Is there any documentation on it? I couldn't find anything.
https://graph-tool.skewed.de/static/doc/dev/topology.html#graph_tool.topolog... -- Tiago de Paula Peixoto <tiago@skewed.de>
I have compared the output of all_paths to that of all_shortest_paths on a network that I have which contains a reasonable number of "duplicate" edges (connecting the same two vertices but each having different edge properties). The shortest path connecting "source" and "target" comprises two edges. Running all_shortest_paths(g,source,target) returns me a list of length 201. Running all_paths(g,source,target,2) returns me a list of length 11. It seems as if all_paths has "deduplicated" most of the list, however does contain a few "duplicate" paths (if I remove all "duplicate" paths I obtain a list of size 8). Why is that? Is this linked to one of them using a depth-first search while the other uses breadth-first? Best wishes, Philipp -- 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.03.2016 13:36, P-M wrote:
I have compared the output of all_paths to that of all_shortest_paths on a network that I have which contains a reasonable number of "duplicate" edges (connecting the same two vertices but each having different edge properties). The shortest path connecting "source" and "target" comprises two edges.
Running all_shortest_paths(g,source,target) returns me a list of length 201. Running all_paths(g,source,target,2) returns me a list of length 11. It seems as if all_paths has "deduplicated" most of the list, however does contain a few "duplicate" paths (if I remove all "duplicate" paths I obtain a list of size 8). Why is that? Is this linked to one of them using a depth-first search while the other uses breadth-first?
This is a bug... I've fixed it in git. Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
Thank you! I am just recompiling it and will try it again. Out of interest, I receive a lot of warnings when running "make" along the line of "warning: typedef 'index' locally defined but not used [-Wunused-local-typedefs] typedef typename Array::index index;". Presumably these slow compilation down (?). Are they expected behaviour? If so, is there a way of suppressing them? Cheers, Philipp -- 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 16.03.2016 11:26, P-M wrote:
Out of interest, I receive a lot of warnings when running "make" along the line of "warning: typedef 'index' locally defined but not used [-Wunused-local-typedefs] typedef typename Array::index index;".
Presumably these slow compilation down (?). Are they expected behaviour? If so, is there a way of suppressing them?
They don't slow compilation down and are harmless. They come from boost, not graph-tool, in any case. You can suppress them by passing the appropriate compiler flags (in this case it would be -Wno-unused-local-typedefs). Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
participants (3)
-
P-M -
Philipp-Maximilian Jacob
-
Tiago de Paula Peixoto