vector directed graph library BUG2

[mmetz]

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

[hamish]

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

H

[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

[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

[neteler]

Can this report be closed?

[martinl]

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