[GRASS-dev] [GRASS GIS] #2936: v.net.distance: wrong directions in one-way streets

GDAL · February 25, 2016, 3:59pm

#2936: v.net.distance: wrong directions in one-way streets
-------------------------------------------------+-------------------------
Reporter: mlennert | Owner: grass-dev@…
Type: defect | Status: new
Priority: normal | Milestone: 7.0.4
Component: Vector | Version: svn-trunk
Keywords: v.net.distance network one-way | CPU: Unspecified
direction |
Platform: Unspecified |
-------------------------------------------------+-------------------------
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.

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/2936>
GRASS GIS <https://grass.osgeo.org>

GDAL · February 25, 2016, 4:00pm

#2936: v.net.distance: wrong directions in one-way streets
-------------------------+-------------------------------------------------
  Reporter: mlennert | Owner: grass-dev@…
      Type: defect | Status: new
  Priority: normal | Milestone: 7.0.4
Component: Vector | Version: svn-trunk
Resolution: | Keywords: v.net.distance network one-way
       CPU: | direction
  Unspecified | Platform: Unspecified
-------------------------+-------------------------------------------------
Changes (by mlennert):

* Attachment "v_distance_map.png" added.

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/2936>
GRASS GIS <https://grass.osgeo.org>

GDAL · February 25, 2016, 4:00pm

#2936: v.net.distance: wrong directions in one-way streets
-------------------------+-------------------------------------------------
  Reporter: mlennert | Owner: grass-dev@…
      Type: defect | Status: new
  Priority: normal | Milestone: 7.0.4
Component: Vector | Version: svn-trunk
Resolution: | Keywords: v.net.distance network one-way
       CPU: | direction
  Unspecified | Platform: Unspecified
-------------------------+-------------------------------------------------
Changes (by mlennert):

* Attachment "v_net_path_example.png" added.

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/2936>
GRASS GIS <https://grass.osgeo.org>

GDAL · February 29, 2016, 10:42pm

#2936: v.net.distance: wrong directions in one-way streets
-------------------------+-------------------------------------------------
  Reporter: mlennert | Owner: grass-dev@…
      Type: defect | Status: new
  Priority: normal | Milestone: 7.0.4
Component: Vector | Version: svn-trunk
Resolution: | Keywords: v.net.distance network one-way
       CPU: | direction
  Unspecified | Platform: Unspecified
-------------------------+-------------------------------------------------

Comment (by 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).

--
Ticket URL: <http://trac.osgeo.org/grass/ticket/2936#comment:1>
GRASS GIS <https://grass.osgeo.org>

GDAL · March 1, 2016, 8:39am

#2936: v.net.distance: wrong directions in one-way streets
-------------------------+-------------------------------------------------
  Reporter: mlennert | Owner: grass-dev@…
      Type: defect | Status: new
  Priority: normal | Milestone: 7.0.4
Component: Vector | Version: svn-trunk
Resolution: | Keywords: v.net.distance network one-way
       CPU: | direction
  Unspecified | Platform: Unspecified
-------------------------+-------------------------------------------------

Comment (by mlennert):

Replying to [comment:1 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...

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/2936#comment:2>
GRASS GIS <https://grass.osgeo.org>

GDAL · March 1, 2016, 11:35pm

#2936: v.net.distance: wrong directions in one-way streets
-------------------------+-------------------------------------------------
  Reporter: mlennert | Owner: grass-dev@…
      Type: defect | Status: new
  Priority: normal | Milestone: 7.0.4
Component: Vector | Version: svn-trunk
Resolution: | Keywords: v.net.distance network one-way
       CPU: | direction
  Unspecified | Platform: Unspecified
-------------------------+-------------------------------------------------

Comment (by mmetz):

Replying to [comment:2 mlennert]:
> Replying to [comment:1 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.

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/2936#comment:3>
GRASS GIS <https://grass.osgeo.org>

GDAL · March 2, 2016, 2:56pm

#2936: v.net.distance: wrong directions in one-way streets
-------------------------+-------------------------------------------------
  Reporter: mlennert | Owner: grass-dev@…
      Type: defect | Status: new
  Priority: normal | Milestone: 7.0.4
Component: Vector | Version: svn-trunk
Resolution: | Keywords: v.net.distance network one-way
       CPU: | direction
  Unspecified | Platform: Unspecified
-------------------------+-------------------------------------------------

Comment (by mlennert):

Replying to [comment:3 mmetz]:
> Replying to [comment:2 mlennert]:
> > Replying to [comment:1 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
}}}

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/2936#comment:4>
GRASS GIS <https://grass.osgeo.org>

GDAL · March 3, 2016, 9:06pm

#2936: v.net.distance: wrong directions in one-way streets
-------------------------+-------------------------------------------------
  Reporter: mlennert | Owner: grass-dev@…
      Type: defect | Status: new
  Priority: normal | Milestone: 7.0.4
Component: Vector | Version: svn-trunk
Resolution: | Keywords: v.net.distance network one-way
       CPU: | direction
  Unspecified | Platform: Unspecified
-------------------------+-------------------------------------------------

Comment (by mmetz):

Replying to [comment:4 mlennert]:
> Replying to [comment:3 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?

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/2936#comment:5>
GRASS GIS <https://grass.osgeo.org>

GDAL · March 4, 2016, 1:50pm

#2936: v.net.distance: wrong directions in one-way streets
-------------------------+-------------------------------------------------
  Reporter: mlennert | Owner: grass-dev@…
      Type: defect | Status: new
  Priority: normal | Milestone: 7.0.4
Component: Vector | Version: svn-trunk
Resolution: | Keywords: v.net.distance network one-way
       CPU: | direction
  Unspecified | Platform: Unspecified
-------------------------+-------------------------------------------------

Comment (by mlennert):

Replying to [comment:5 mmetz]:
> Replying to [comment:4 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.

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/2936#comment:6>
GRASS GIS <https://grass.osgeo.org>

GDAL · March 5, 2016, 11:14pm

#2936: v.net.distance: wrong directions in one-way streets
-------------------------+-------------------------------------------------
  Reporter: mlennert | Owner: grass-dev@…
      Type: defect | Status: new
  Priority: normal | Milestone: 7.0.4
Component: Vector | Version: svn-trunk
Resolution: | Keywords: v.net.distance network one-way
       CPU: | direction
  Unspecified | Platform: Unspecified
-------------------------+-------------------------------------------------

Comment (by mmetz):

Replying to [comment:6 mlennert]:
> Replying to [comment:5 mmetz]:
> > Replying to [comment:4 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.

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/2936#comment:7>
GRASS GIS <https://grass.osgeo.org>

GDAL · March 6, 2016, 5:00pm

#2936: v.net.distance: wrong directions in one-way streets
-------------------------+-------------------------------------------------
  Reporter: mlennert | Owner: grass-dev@…
      Type: defect | Status: new
  Priority: normal | Milestone: 7.0.4
Component: Vector | Version: svn-trunk
Resolution: | Keywords: v.net.distance network one-way
       CPU: | direction
  Unspecified | Platform: Unspecified
-------------------------+-------------------------------------------------

Comment (by neteler):

Replying to [comment:7 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.

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/2936#comment:8>
GRASS GIS <https://grass.osgeo.org>

GDAL · March 8, 2016, 8:58pm

#2936: v.net.distance: wrong directions in one-way streets
-------------------------+-------------------------------------------------
  Reporter: mlennert | Owner: grass-dev@…
      Type: defect | Status: new
  Priority: normal | Milestone: 7.0.4
Component: Vector | Version: svn-trunk
Resolution: | Keywords: v.net.distance network one-way
       CPU: | direction
  Unspecified | Platform: Unspecified
-------------------------+-------------------------------------------------

Comment (by mmetz):

Replying to [comment:8 neteler]:
> Replying to [comment:7 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.

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/2936#comment:9>
GRASS GIS <https://grass.osgeo.org>

GDAL · March 17, 2016, 9:31am

#2936: v.net.distance: wrong directions in one-way streets
-------------------------+-------------------------------------------------
  Reporter: mlennert | Owner: grass-dev@…
      Type: defect | Status: closed
  Priority: normal | Milestone: 7.0.4
Component: Vector | Version: svn-trunk
Resolution: fixed | Keywords: v.net.distance network one-way
       CPU: | direction
  Unspecified | Platform: Unspecified
-------------------------+-------------------------------------------------
Changes (by mlennert):

* status: new => closed
* resolution: => fixed

Comment:

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

--
Ticket URL: <https://trac.osgeo.org/grass/ticket/2936#comment:10>
GRASS GIS <https://grass.osgeo.org>