Opened 11 years ago

Closed 18 months ago

#584 closed defect (fixed)

vector directed graph library BUG2

Reported by: mmetz Owned by: grass-dev@…
Priority: normal Milestone: 7.0.7
Component: Vector Version: svn-develbranch6
Keywords: shortest path, edge costs Cc:
CPU: Unspecified Platform: Unspecified

Description

See https://trac.osgeo.org/grass/browser/grass/trunk/lib/vector/dglib/BUGS

BUG2 (24.2.2003):

If 2 nodes are connected by more arcs, SP doesn't return the shortest one but the last arc (between these two nodes) inserted to graph.

Possible solution

When building a graph and adding a new edge, check if there is already an edge connecting the two nodes. If the cost of the edge to be inserted is lower than the current cost connecting these two nodes, replace old edge, else don't add the new edge.

This could be done in https://trac.osgeo.org/grass/browser/grass/trunk/lib/vector/Vlib/net.c

Just an idea, needs testing.

Markus M

Change History (8)

comment:1 Changed 11 years ago by hamish

sounds reasonable, but it's so obvious it makes me wonder why it wasn't done the first time.

H

comment:2 in reply to:  1 Changed 11 years ago by mmetz

Replying to hamish:

sounds reasonable, but it's so obvious it makes me wonder why it wasn't done the first time.

I agree, but both the directed graph library and the Vect_net_*() functions look quite polished to me, maybe it's not that easy. Updating the database with costs could be difficult. I will not get to testing it in the next few weeks, maybe Daniel Bundala can look into it when he starts working on his GSoC project. In any case, it's a bug and should be addressed, and here in trac it is a bit more prominent than in the BUGS file hidden in lib/vector/dglib.

Markus M

comment:3 Changed 9 years ago by mmetz

I did some testing and found out that

  • I could only reproduce BUG2 with cache enabled
  • BUG2 occurred only if the path to the node closer to start was requested first
  • BUG2 occurred only if the distance or cumulative cost was requested and not the actual path

BUG2 is now fixed in trunk and devbr6, at least I can no longer reproduce it, but maybe I have overlooked some special case.

Markus M

comment:4 Changed 5 years ago by neteler

Can this report be closed?

comment:5 Changed 4 years ago by martinl

Milestone: 7.0.07.0.5

comment:6 Changed 3 years ago by neteler

Milestone: 7.0.57.0.6

comment:7 Changed 2 years ago by neteler

Milestone: 7.0.67.0.7

comment:8 Changed 18 months ago by martinl

Resolution: fixed
Status: newclosed

No activity for a long time. Closing. Feel free to reopen if needed.

Note: See TracTickets for help on using tickets.