v.net.distance: wrong directions in one-way streets

[mlennert]

In the NC demo dataset:

v.net -c streets_wake op=nodes out=mynet
v.db.update map=mynet@user1 column=TF_COST value=-1 where=ONE_WAY='FT'
v.db.update map=mynet@user1 column=FT_COST value=-1 where=ONE_WAY='TF'
v.net.distance --overwrite input=mynet output=distance_7779_7780 from_layer=2 from_cats=7779 to_layer=2 to_cats=7780 arc_column=FT_COST arc_backward_column=TF_COST
v.net.distance --overwrite input=mynet output=distance_7780_7779 from_layer=2 from_cats=7780 to_layer=2 to_cats=7779 arc_column=FT_COST arc_backward_column=TF_COST
d.vect map=mynet
d.vect map=mynet display=shape,dir where="ONE_WAY='FT' OR ONE_WAY='TF'" color=red attribute_column=ONE_WAY yref=top
d.vect map=mynet layer=2 display=shape,cat cats=7779-7780 fill_color=255:165:0 icon=basic/circle label_layer=2
d.vect map=distance_7779_7780 display=shape,dir type=point,line,boundary,area,face color=blue width=3 attribute_column=cat label_color=blue
d.vect map=distance_7780_7779 display=shape,dir type=point,line,boundary,area,face color=83:201:10 width=3 attribute_column=cat label_color=83:201:10

gives the attached map v_distance_map.png. One can see there that the segment connection 7779 and 7780 directly has a line direction from 7779 to 7780, but it is defined as ONE_WAY='TF', meaning that vehicles can only go from 7780 to 7779. However, when looking at the paths identified by v.net.distance, the path coming from 7779 and going to 7780 (blue, identified in the map as 7779) goes in the opposite direction through the one-way street and that the other path takes the long route.

As a comparison, v.net.path gives correct results:

echo "1 7779 7780
2 7780 7779" | v.net.path mynet out=paths arc_column=FT_COST 
arc_backward_column=TF_COST
d.vect map=paths display=shape,cat cats=1 color=0:128:0 width=2 
label_color=0:128:0
d.vect map=paths display=shape,cat cats=2 color=128:0:128 width=2 
label_color=128:0:128

See the second attached map v_net_path_example.png which shows that path number 2 (purple), that goes from 7780 to 7779 takes the short route, while path 1 (green) takes the long route.

[mmetz]

Manual:

"Each path consist of several lines. If a line is on the shortest path from a point then the category of this point is assigned to the line. Note that every line may contain more than one category value since a single line may be on the shortest path for more than one from feature."

That means lines are copied directly from input to output, line directions are not adjusted and lines are not merged to unique paths for each from category.

Unfortunately, the paths as reported by v.net.distance (irrespective of the direction) are wrong: the shortest path from 7779 to 7780 should take the long route, and the shortest path from 7780 to 7779 should take the short route. Fixing this bug would require a new function in lib/vector/neta. Hopefully the dglib interface allows for an easy solution to provide an inverse to lib/vector/neta/path.c:NetA_distance_from_points().

This ticket should be closed and a new ticket should be opened that v.net.distance calculates paths in reverse (from to to from instead of from from to to).

[mlennert]

Replying to mmetz:

Manual:

"Each path consist of several lines. If a line is on the shortest path from a point then the category of this point is assigned to the line. Note that every line may contain more than one category value since a single line may be on the shortest path for more than one from feature."

That means lines are copied directly from input to output, line directions are not adjusted and lines are not merged to unique paths for each from category.

Unfortunately, the paths as reported by v.net.distance (irrespective of the direction) are wrong: the shortest path from 7779 to 7780 should take the long route, and the shortest path from 7780 to 7779 should take the short route. Fixing this bug would require a new function in lib/vector/neta. Hopefully the dglib interface allows for an easy solution to provide an inverse to lib/vector/neta/path.c:NetA_distance_from_points().

This ticket should be closed and a new ticket should be opened that v.net.distance calculates paths in reverse (from to to from instead of from from to to).

I don't understand why we need a new ticket. Maybe my formulation was a bit awkward, but the problem reported in the ticket is exactly that v.net.distance calculates paths in reverse...

[mmetz]

Replying to mlennert:

Replying to mmetz:

Manual:

"Each path consist of several lines. If a line is on the shortest path from a point then the category of this point is assigned to the line. Note that every line may contain more than one category value since a single line may be on the shortest path for more than one from feature."

That means lines are copied directly from input to output, line directions are not adjusted and lines are not merged to unique paths for each from category.

Unfortunately, the paths as reported by v.net.distance (irrespective of the direction) are wrong: the shortest path from 7779 to 7780 should take the long route, and the shortest path from 7780 to 7779 should take the short route. Fixing this bug would require a new function in lib/vector/neta. Hopefully the dglib interface allows for an easy solution to provide an inverse to lib/vector/neta/path.c:NetA_distance_from_points().

This ticket should be closed and a new ticket should be opened that v.net.distance calculates paths in reverse (from to to from instead of from from to to).

I don't understand why we need a new ticket. Maybe my formulation was a bit awkward, but the problem reported in the ticket is exactly that v.net.distance calculates paths in reverse...

I understand. Just for emphasis, the output line directions are not wrong because they are not meant to be in accordance with the path directions. The paths themselves were wrong in case of one-way streets. Correct paths are created with trunk r67984,5. There is also a new -l flag that produces a single line for each path with appropriate line direction. The vector libs needed some modification in order to fix v.net.distance.

[mlennert]

Replying to mmetz:

Replying to mlennert:

Replying to mmetz:

Manual:

"Each path consist of several lines. If a line is on the shortest path from a point then the category of this point is assigned to the line. Note that every line may contain more than one category value since a single line may be on the shortest path for more than one from feature."

That means lines are copied directly from input to output, line directions are not adjusted and lines are not merged to unique paths for each from category.

Unfortunately, the paths as reported by v.net.distance (irrespective of the direction) are wrong: the shortest path from 7779 to 7780 should take the long route, and the shortest path from 7780 to 7779 should take the short route. Fixing this bug would require a new function in lib/vector/neta. Hopefully the dglib interface allows for an easy solution to provide an inverse to lib/vector/neta/path.c:NetA_distance_from_points().

This ticket should be closed and a new ticket should be opened that v.net.distance calculates paths in reverse (from to to from instead of from from to to).

I don't understand why we need a new ticket. Maybe my formulation was a bit awkward, but the problem reported in the ticket is exactly that v.net.distance calculates paths in reverse...

I understand. Just for emphasis, the output line directions are not wrong because they are not meant to be in accordance with the path directions. The paths themselves were wrong in case of one-way streets.

That's exactly what I meant by wrong directions: path directions, not line directions :-). I don't have a problem with line directions remaining as in the original

Correct paths are created with trunk r67984,5.

Thanks, works great now !

There is also a new -l flag that produces a single line for each path with appropriate line direction.

Nice. Just one remark: the line seems to only have a category value in layer 2, not in layer 1. Is that intended ? It's a bit counter-intuitive, especially since default display in the GUI is of layer 1 and so you don't see anything until you specify layer 2 in the select tab...

The command line used (follow-up of the above example code):

v.net.distance -l --overwrite input=mynet output=distance_7779_7780 from_layer=2 from_cats=7779 to_layer=2 to_cats=7780 arc_column=FT_COST arc_backward_column=TF_COST --o
v.category input=distance_7779_7780@user1 option=report
Layer: 2
type       count        min        max
point          1       7779       7779
line           1       7779       7779
boundary       0          0          0
centroid       0          0          0
area           0          0          0
face           0          0          0
kernel         0          0          0
all            2       7779       7779

[mmetz]

Replying to mlennert:

Replying to mmetz:

I don't have a problem with line directions remaining as in the original.

I have, so I adjusted line directions to match path directions in r67990. v.net.path also adjusts line directions to match path directions.

Correct paths are created with trunk r67984,5.

Thanks, works great now !

There is also a new -l flag that produces a single line for each path with appropriate line direction.

Nice. Just one remark: the line seems to only have a category value in layer 2, not in layer 1. Is that intended ?

Not really intended, paths got all categories of their from feature. Changed in r67990 to match the default output of paths consisting of different lines. I got distracted by the directed graph library which is only slightly less difficult to read than the wxpython GUI code base.

AFAICT, v.net.distance is now the only module using version 2 directed graphs. All other v.net.* modules use version 1 directed graphs. The directed graph library offers to create graphs (networks) of version 1, 2, and 3. Only version 1 graphs have been used and tested since 2003 within GRASS GIS.

I have introduced this bug indirectly myself by adding options to define different forward and backward costs to lines, without updating the underlying code base (GSoC project 2009 by Daniel Bundala, impressive code quality and thorough understanding of network analysis).

It is not clear to me why v.net.distance copies 'from' features to the output but not 'to' features. Any opinion?

[mlennert]

Replying to mmetz:

Replying to mlennert:

Nice. Just one remark: the line seems to only have a category value in layer 2, not in layer 1. Is that intended ?

Not really intended, paths got all categories of their from feature. Changed in r67990 to match the default output of paths consisting of different lines.

Works great now, thanks !

As this is a bug, I believe that r67984, r67985 and r67990 are backporting candidates for grass70. At the same time they also introduce new functionality (line = path direction). What do you think ?

I got distracted by the directed graph library which is only slightly less difficult to read than the wxpython GUI code base.

That makes me feel better about not having understood very much when I tried to find the solution myself. Thanks ! ;-)

AFAICT, v.net.distance is now the only module using version 2 directed graphs. All other v.net.* modules use version 1 directed graphs. The directed graph library offers to create graphs (networks) of version 1, 2, and 3. Only version 1 graphs have been used and tested since 2003 within GRASS GIS.

Sorry for my ignorance, but what are version 2 and 3 ?

It is not clear to me why v.net.distance copies 'from' features to the output but not 'to' features. Any opinion?

I have to admit that I had never noticed that it did this... For this is not necessary. I would rather see v.net.distance offer the possibility to just output the fcat,tcat,distance values to stdout or to file, without creating the path vector map (which should be optional). That way it would even more be a network equivalent of v.distance.

But that's for a different ticket.

[mmetz]

Replying to mlennert:

Replying to mmetz:

Replying to mlennert:

Nice. Just one remark: the line seems to only have a category value in layer 2, not in layer 1. Is that intended ?

Not really intended, paths got all categories of their from feature. Changed in r67990 to match the default output of paths consisting of different lines.

Works great now, thanks !

As this is a bug, I believe that r67984, r67985 and r67990 are backporting candidates for grass70. At the same time they also introduce new functionality (line = path direction). What do you think ?

Since this is a bugfix, and the new feature makes the output more similar to v.net.path (I regard it as the reference module), I agree that the changes should be backported.

I have introduced another new feature: node costs are now considered, and closed nodes are not traversed. This new feature requires IMHO a bit more testing.

5 years ago, I have added options to define arc forward and backward costs as well as node costs to all v.net.* modules added by the GSoC 2009 project. Unfortunately, I did not update the underlying algorithms which sometimes assumed undirected graphs (e.g. v.net.distance). I am doing this now (sorry for being so late), which will require further testing. Quite interesting could be a working v.net.components module (trunk r68006) which now also requires directed graphs version 2 (see below). The output of v.net.components has been wrong ever since it has been added to GRASS.

AFAICT, v.net.distance is now the only module using version 2 directed graphs. All other v.net.* modules use version 1 directed graphs. The directed graph library offers to create graphs (networks) of version 1, 2, and 3. Only version 1 graphs have been used and tested since 2003 within GRASS GIS.

Sorry for my ignorance, but what are version 2 and 3 ?

https://grass.osgeo.org/programming7/dglib.html

"DGLib defines three different graph versions, version 1 supports directed graph with a weak concept of the edge, it can support many applications where one doesn't need to know about the input edges of a node (in-degree) and where there is no requirement to directly retrieve edges by their identifier but only by head/tail combinations. Version 2 adds in-degree support and a true edge addressing, yet supporting directed graph. Version 3 uses the same internal representation of version 2 but activates code branches to support undirected graphs."

v.net.distance needs to process input (incoming) edges for each node, not output (outgoing) edges. Therefore directed graphs version 2 are required. v.net.components processes both outgoing and incoming edges, therefore it also requires graphs version 2. Technically, weakly connected components could be determined using only GRASS vector topology (equivalent to an undirected graph), but then nodes could not be closed by setting nodes' costs to -1.

It is not clear to me why v.net.distance copies 'from' features to the output but not 'to' features. Any opinion?

I have to admit that I had never noticed that it did this... For this is not necessary.

OK.

I would rather see v.net.distance offer the possibility to just output the fcat,tcat,distance values to stdout or to file, without creating the path vector map (which should be optional). That way it would even more be a network equivalent of v.distance.

But that's for a different ticket.

OK.

[neteler]

Replying to mmetz:

As this is a bug, I believe that r67984, r67985 and r67990 are backporting candidates for grass70. At the same time they also introduce new functionality (line = path direction). What do you think ?

Since this is a bugfix, and the new feature makes the output more similar to v.net.path (I regard it as the reference module), I agree that the changes should be backported.

Please do that yourself since you are the author.

[mmetz]

Replying to neteler:

Replying to mmetz:

As this is a bug, I believe that r67984, r67985 and r67990 are backporting candidates for grass70. At the same time they also introduce new functionality (line = path direction). What do you think ?

Since this is a bugfix, and the new feature makes the output more similar to v.net.path (I regard it as the reference module), I agree that the changes should be backported.

Please do that yourself since you are the author.

Backported to relbr70 in r68023-25.

[mlennert]

Closing as the bug has been fixed in trunk and release70.