Hello -- I am getting an unexpected shortest path (with weighted costs) result. I have isolated it to a simple script to illustrate; the files are at http://www.sfcta.org/downloads/lmz/ Files: - graph: graph_after_1iter_157_277.xml.gz - python script to illustrate my issue: path_debug.py - log file output of python script: path_debug.log The workbook, path_debug.xls, is just an excel version of path_debug.log with a calculated column (in orange) inserted to show what I expect to be the shortest distance to the given vertex. The script path_debug.py: 1) finds the shortest path from a source to a target and prints the details 2) prints the details of what I expect to be the shortest path I cannot figure out why the second path has the cost that it's printing... Mostly it's as expected, but the yellow highlighted cells are what baffles me. The graph is a pseudo-dual network so it's a bit confusing; the vertices symbolize links in a street network and the edges symbolize a turn from the incoming link to the outgoing link. Any help would be greatly appreciated! -Lisa -- 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.10.2014 04:25, lmz wrote:
Hello -- I am getting an unexpected shortest path (with weighted costs) result. I have isolated it to a simple script to illustrate; the files are at http://www.sfcta.org/downloads/lmz/
Files: - graph: graph_after_1iter_157_277.xml.gz - python script to illustrate my issue: path_debug.py - log file output of python script: path_debug.log The workbook, path_debug.xls, is just an excel version of path_debug.log with a calculated column (in orange) inserted to show what I expect to be the shortest distance to the given vertex.
The script path_debug.py: 1) finds the shortest path from a source to a target and prints the details 2) prints the details of what I expect to be the shortest path
I cannot figure out why the second path has the cost that it's printing... Mostly it's as expected, but the yellow highlighted cells are what baffles me.
You might be hitting the following bug which was fixed a while ago: https://git.skewed.de/count0/graph-tool/issues/188 This fix has not yet made into a release, so you should try the git version. Alternatively, you may get the distances from the shortest_distance function without the 'target' option, and compare. Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
Hi Lisa, I recently posted Issue #188: https://git.skewed.de/count0/graph-tool/issues/188 which Tiago resolved in the current master branch. Can you run the simple example I posted? I see in your path_debug.py that you use shortest_distance with a specified target which in version 2.2.35 stops the search as soon as the target node is discovered during Dijkstra's algorithm. If this is the problem then you either need to compile the current (git) version of graph-tool or to wait for the next pre-compiled packages. Hope that helps, Paul -- 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.
Aha that does sound promising! I'll try pulling the current git version and see if it fixes it. Thank you both! -Lisa On Fri, Oct 3, 2014 at 1:21 AM, paob [via Main discussion list for the graph-tool project] <ml-node+s982480n4025768h37@n3.nabble.com> wrote:
Hi Lisa,
I recently posted Issue #188: https://git.skewed.de/count0/graph-tool/issues/188 which Tiago resolved in the current master branch.
Can you run the simple example I posted? I see in your path_debug.py that you use shortest_distance with a specified target which in version 2.2.35 stops the search as soon as the target node is discovered during Dijkstra's algorithm.
If this is the problem then you either need to compile the current (git) version of graph-tool or to wait for the next pre-compiled packages.
Hope that helps, Paul
------------------------------ 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 unsubscribe from unexpected shortest_path result, click here <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/template/NamlServlet.jtp?macro=unsubscribe_by_code&node=4025765&code=bGlzYS56b3JuQHNmY3RhLm9yZ3w0MDI1NzY1fC0xODE1NDQ4NjE5> . 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>
-- 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.
The current git version of the code fixed my problem. Thank you! -Lisa On Fri, Oct 3, 2014 at 10:37 AM, lmz <lisa.zorn@sfcta.org> wrote:
Aha that does sound promising! I'll try pulling the current git version and see if it fixes it. Thank you both! -Lisa
On Fri, Oct 3, 2014 at 1:21 AM, paob [via Main discussion list for the graph-tool project] <[hidden email] <http://user/SendEmail.jtp?type=node&node=4025771&i=0>> wrote:
Hi Lisa,
I recently posted Issue #188: https://git.skewed.de/count0/graph-tool/issues/188 which Tiago resolved in the current master branch.
Can you run the simple example I posted? I see in your path_debug.py that you use shortest_distance with a specified target which in version 2.2.35 stops the search as soon as the target node is discovered during Dijkstra's algorithm.
If this is the problem then you either need to compile the current (git) version of graph-tool or to wait for the next pre-compiled packages.
Hope that helps, Paul
------------------------------ 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 unsubscribe from unexpected shortest_path result, 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>
------------------------------ View this message in context: Re: unexpected shortest_path result <http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/unexpected-shortest-path-result-tp4025765p4025771.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
One more question -- Do you know when you'll be releasing a version with this fix? I'm wondering if I should build an amazon image with the current code or if I should wait, so a time estimate would be useful. Thank you! -Lisa
On 20.10.2014 19:45, Lisa Zorn wrote:
One more question --
Do you know when you'll be releasing a version with this fix? I'm wondering if I should build an amazon image with the current code or if I should wait, so a time estimate would be useful.
I can't give you an expectation date. This will be done as time permits. It will happen hopefully during the next week or two. Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
participants (4)
-
Lisa Zorn -
lmz
-
paob -
Tiago de Paula Peixoto