[GRASS-user] v.net.salesman unreachable nodes

GRASS GRASS user
1

Hi,

I’m trying to run a travelling salesman analysis between point features on a road map, but it tells me that two nodes are unreachable from one another, which is a fatal error.

I’ve successfully done this exact analysis using ARC/View, but I’m trying to find an OSS alternative that works on Debian - and it seems GRASS is the only software currently able to do network analyses.

I patched together two ESRI shapefile datasets, following the Grass 6.0 v1.2 tutorial.
I tried linking the attributes to the original datasets and tried without linking.
I tried putting the new points on both the same layer and a new layer.
I tried running every single v.clean function on both the original and patched datasets.
I am certain that all the points are actually on the network.
I’ve searched all mailing lists, reference materials, and bugtracker, but didn’t find anything explicitly related to unreachable nodes.

Assuming the error message does mean that the map I am using has segments disconnected from the rest of the network, the questions are:

  • How do I detect them and remove them?
    The node numbers given don’t match the cat attribute, so I assumed they referred to the id attribute. The two nodes referred to by id are however connected to each other (directly) and to the main part of the network. I suspect the node numbers therefore don’t correspond to any attribute as such, but are rather internal. In that case, how do I identify the actual nodes/segments responsible?

  • Shouldn’t the algorithm be tolerant of such errors anyway?
    I checked, and none of the relevant nodes are actually within segments I can see are disconnected, so the analysis results should be the same if the algorithm ignored the error… Is this perhaps because of the heuristics used to solve this NP-hard problem? Does anyone know what ArcView does differently?

Any ideas?

Cheers,

Joseph Guillaume

2

If you bring the patched data (nodes/terminals and arcs) into v.digit, do you see dangling arcs (red) that might cause the network to be disconnected? Particularly at the patched nodes?

On 8/3/07, Joseph Guillaume <josephguillaume@gmail.com> wrote:

Hi,

I’m trying to run a travelling salesman analysis between point features on a road map, but it tells me that two nodes are unreachable from one another, which is a fatal error.

I’ve successfully done this exact analysis using ARC/View, but I’m trying to find an OSS alternative that works on Debian - and it seems GRASS is the only software currently able to do network analyses.

I patched together two ESRI shapefile datasets, following the Grass 6.0 v1.2 tutorial.
I tried linking the attributes to the original datasets and tried without linking.
I tried putting the new points on both the same layer and a new layer.
I tried running every single v.clean function on both the original and patched datasets.
I am certain that all the points are actually on the network.
I’ve searched all mailing lists, reference materials, and bugtracker, but didn’t find anything explicitly related to unreachable nodes.

Assuming the error message does mean that the map I am using has segments disconnected from the rest of the network, the questions are:

  • How do I detect them and remove them?
    The node numbers given don’t match the cat attribute, so I assumed they referred to the id attribute. The two nodes referred to by id are however connected to each other (directly) and to the main part of the network. I suspect the node numbers therefore don’t correspond to any attribute as such, but are rather internal. In that case, how do I identify the actual nodes/segments responsible?

  • Shouldn’t the algorithm be tolerant of such errors anyway?
    I checked, and none of the relevant nodes are actually within segments I can see are disconnected, so the analysis results should be the same if the algorithm ignored the error… Is this perhaps because of the heuristics used to solve this NP-hard problem? Does anyone know what ArcView does differently?

Any ideas?

Cheers,

Joseph Guillaume

grassuser mailing list
grassuser@grass.itc.it
http://grass.itc.it/mailman/listinfo/grassuser

3

Joseph,

it is most likely that your nodes aren't physically connected to the
network, or that they are connected but have no category number
or the conneting line doesn't have a category number. Myself, I wasted
much time with such problems. But this is history now :slight_smile:

Since recently, GRASS 6.3 contains an updated v.net (thanks to Martin
Landa) which makes it a snap to connect nodes to a graph ("connect" tool).

I have just added a v.net.steiner example:
http://grass.itc.it/grass63/manuals/html63_user/v.net.steiner.html

Please take a look - it's very easy now (before this update of v.net,
connecting nodes was a nightmare). v.net.salesman should work in
a similar way.

Markus

Joseph Guillaume wrote on 08/03/2007 10:37 AM:

Hi,

I'm trying to run a travelling salesman analysis between point
features on a road map, but it tells me that two nodes are unreachable
from one another, which is a fatal error.

I've successfully done this exact analysis using ARC/View, but I'm
trying to find an OSS alternative that works on Debian - and it seems
GRASS is the only software currently able to do network analyses.

I patched together two ESRI shapefile datasets, following the Grass
6.0 v1.2 tutorial.
I tried linking the attributes to the original datasets and tried
without linking.
I tried putting the new points on both the same layer and a new layer.
I tried running every single v.clean function on both the original and
patched datasets.
I am certain that all the points are actually on the network.
I've searched all mailing lists, reference materials, and bugtracker,
but didn't find anything explicitly related to unreachable nodes.

Assuming the error message does mean that the map I am using has
segments disconnected from the rest of the network, the questions are:

* How do I detect them and remove them?
The node numbers given don't match the cat attribute, so I assumed
they referred to the id attribute. The two nodes referred to by id are
however connected to each other (directly) and to the main part of the
network. I suspect the node numbers therefore don't correspond to any
attribute as such, but are rather internal. In that case, how do I
identify the actual nodes/segments responsible?

* Shouldn't the algorithm be tolerant of such errors anyway?
I checked, and none of the relevant nodes are actually within segments
I can see are disconnected, so the analysis results should be the same
if the algorithm ignored the error... Is this perhaps because of the
heuristics used to solve this NP-hard problem? Does anyone know what
ArcView does differently?

Any ideas?

Cheers,

Joseph Guillaume

------------------
ITC -> dall'1 marzo 2007 Fondazione Bruno Kessler
ITC -> since 1 March 2007 Fondazione Bruno Kessler
------------------

4

Markus Neteler wrote on 08/03/2007 02:12 PM:

I have just added a v.net.steiner example:
http://grass.itc.it/grass63/manuals/html63_user/v.net.steiner.html

Please take a look - it's very easy now (before this update of v.net,
connecting nodes was a nightmare). v.net.salesman should work in
a similar way.
  

OK, working example added:
http://grass.itc.it/grass63/manuals/html63_user/v.net.salesman.html

Markus

------------------
ITC -> dall'1 marzo 2007 Fondazione Bruno Kessler
ITC -> since 1 March 2007 Fondazione Bruno Kessler
------------------

5

The issues Markus outlined are good things to try. I had the same problems he had discussed on this thread.

Those module enhancements sounds awesome. I had some problems, which required tedious node/line snapping on my part when running some of the network modules (particularly v.net.steiner). the module performed most excellent once all the network topology was correct.

I am anxious to check out and use some of the new tools that have been developed (this connect tool, and the unsplitting of pseudo nodes between lines with common attributes). These sound like promising enhancements, especially since I may have very heavy usage of the network modules in the upcoming months/year.

Mark

On 8/3/07, Markus Neteler <neteler@itc.it> wrote:

Joseph,

it is most likely that your nodes aren’t physically connected to the
network, or that they are connected but have no category number
or the conneting line doesn’t have a category number. Myself, I wasted
much time with such problems. But this is history now :slight_smile:

Since recently, GRASS 6.3 contains an updated v.net (thanks to Martin
Landa) which makes it a snap to connect nodes to a graph (“connect” tool).

I have just added a v.net.steiner example:
http://grass.itc.it/grass63/manuals/html63_user/v.net.steiner.html

Please take a look - it’s very easy now (before this update of v.net,
connecting nodes was a nightmare). v.net.salesman should work in
a similar way.

Markus

Joseph Guillaume wrote on 08/03/2007 10:37 AM:

Hi,

I’m trying to run a travelling salesman analysis between point
features on a road map, but it tells me that two nodes are unreachable
from one another, which is a fatal error.

I’ve successfully done this exact analysis using ARC/View, but I’m
trying to find an OSS alternative that works on Debian - and it seems
GRASS is the only software currently able to do network analyses.

I patched together two ESRI shapefile datasets, following the Grass
6.0 v1.2 tutorial.
I tried linking the attributes to the original datasets and tried
without linking.
I tried putting the new points on both the same layer and a new layer.
I tried running every single v.clean function on both the original and
patched datasets.
I am certain that all the points are actually on the network.
I’ve searched all mailing lists, reference materials, and bugtracker,
but didn’t find anything explicitly related to unreachable nodes.

Assuming the error message does mean that the map I am using has
segments disconnected from the rest of the network, the questions are:

  • How do I detect them and remove them?
    The node numbers given don’t match the cat attribute, so I assumed
    they referred to the id attribute. The two nodes referred to by id are
    however connected to each other (directly) and to the main part of the
    network. I suspect the node numbers therefore don’t correspond to any
    attribute as such, but are rather internal. In that case, how do I
    identify the actual nodes/segments responsible?

  • Shouldn’t the algorithm be tolerant of such errors anyway?
    I checked, and none of the relevant nodes are actually within segments
    I can see are disconnected, so the analysis results should be the same
    if the algorithm ignored the error… Is this perhaps because of the
    heuristics used to solve this NP-hard problem? Does anyone know what
    ArcView does differently?

Any ideas?

Cheers,

Joseph Guillaume

ITC → dall’1 marzo 2007 Fondazione Bruno Kessler
ITC → since 1 March 2007 Fondazione Bruno Kessler

grassuser mailing list
grassuser@grass.itc.it
http://grass.itc.it/mailman/listinfo/grassuser

6

Fri 03 Aug 2007 10:37, Joseph Guillaume wrote:

I'm trying to run a travelling salesman analysis between point features on a
road map, but it tells me that two nodes are unreachable from one another,
which is a fatal error.

yes, i too guess vertex A is not connected with vertex B for some
reason..

..sometimes the problem is quite subtle, like not matching charsets while
importing data http://pgrouting.postlbs.org/discussion/12/27
etc..

there's some high-quality sample data available (download "Premium", free
registation required) which you could use to check if the issue is really
GRASS or your own (faulty) data ..
http://www.adci.com/samples/navteq.html

find an OSS alternative that works on Debian - and it seems GRASS is the
only software currently able to do network analyses.

NAK, have there's also http://pgrouting.postlbs.org/.

7

On Fri, Aug 03, 2007 at 05:53:17PM +0200, sebastian sauer wrote:
...

there's some high-quality sample data available (download "Premium", free
registation required) which you could use to check if the issue is really
GRASS or your own (faulty) data ..
http://www.adci.com/samples/navteq.html

If you like, take really free data instead [1]:
http://www.grassbook.org/
-> Download book datasets
   -> "OSGeo sample dataset for research, development and education"
       nc_spm_05_2007_0509.tar.gz: North Carolina (NC)
                           State Plane metric LOCATION

It contains two street networks: one is detailed, one is
less detailed. Additionally bus routes, also hospitals,
firestations, schools and further point maps, see
   -> Data set list of maps

We plan to update the data set the next week for
additional maps and a few fixes.

Cheers
Markus

[1] http://www.foss4g2007.org/presentations/view.php?abstract_id=201

8

Thanks everybody!

It turns out my road network was faulty in the first place - the point features were well placed, but the roads were interrupted by bad intersections, as shown by v.digit (which btw, seems to be using much more memory in the latest cvs snapshot than in debian unstable version 6.2 - ~700MB where previously it didn’t even have to swap)

I fixed this using v.clean’s snap on just the road network which apparently hadn’t worked previously because I’d forgotten to specify a threshold, and the default wasn’t sufficient. Snapping the lines meant that some of the previously ok features were now off the line, which is where the connect came in.

The v.net connect tool in the latest CVS snapshot worked like a charm (though the provided cvs debian package was too old - you weren’t kidding that it was a new feature :-P), and the worked example was a perfect guide too.

I then went back and tried to follow the rest of the connecting instructions in the tutorial (p89), but it didn’t quite work as well as the new tool. Looks like I started using GRASS at just the right time for my problems… I still managed to get a few shortest paths working where previously I was getting nothing - the main problem definitely was with the dataset.

Thanks for the links to other datasets. In this particular case though, I wanted to clean up the one I had, because it’s a university-provided dataset of the local region. They may come in handy later though :slight_smile:

Thanks again!

Joseph

On 8/3/07, Joseph Guillaume <josephguillaume@gmail.com > wrote:

Hi,

I’m trying to run a travelling salesman analysis between point features on a road map, but it tells me that two nodes are unreachable from one another, which is a fatal error.

I’ve successfully done this exact analysis using ARC/View, but I’m trying to find an OSS alternative that works on Debian - and it seems GRASS is the only software currently able to do network analyses.

I patched together two ESRI shapefile datasets, following the Grass 6.0 v1.2 tutorial.
I tried linking the attributes to the original datasets and tried without linking.
I tried putting the new points on both the same layer and a new layer.
I tried running every single v.clean function on both the original and patched datasets.
I am certain that all the points are actually on the network.
I’ve searched all mailing lists, reference materials, and bugtracker, but didn’t find anything explicitly related to unreachable nodes.

Assuming the error message does mean that the map I am using has segments disconnected from the rest of the network, the questions are:

  • How do I detect them and remove them?
    The node numbers given don’t match the cat attribute, so I assumed they referred to the id attribute. The two nodes referred to by id are however connected to each other (directly) and to the main part of the network. I suspect the node numbers therefore don’t correspond to any attribute as such, but are rather internal. In that case, how do I identify the actual nodes/segments responsible?

  • Shouldn’t the algorithm be tolerant of such errors anyway?
    I checked, and none of the relevant nodes are actually within segments I can see are disconnected, so the analysis results should be the same if the algorithm ignored the error… Is this perhaps because of the heuristics used to solve this NP-hard problem? Does anyone know what ArcView does differently?

Any ideas?

Cheers,

Joseph Guillaume