v.net.steiner fails on a network with large number of intersections

[cmbarton]

v.net.steiner is broken.

I created a network in the nc_08 demo data set from streets_wake and highschools extracted from schools_wake. When I ran v.net.steiner, I got the following error:

(Sat Oct  6 23:39:56 2012)                                                      
v.net.steiner input=hs_net_g6@spatialtech2012 output=hs_steiner_g6 tcats=4-164  
Number of terminals: 21
Number of Steiner points set to 19
v.net.steiner(65199) malloc: *** mmap(size=233472) failed
(error code=12)
*** error: can't allocate region
*** set a breakpoint in malloc_error_break to debug
Current region rows: 1350, cols: 1500
ERROR: G_malloc: unable to allocate 233168 bytes of memory at main.c:475

It is broken in trunk (GRASS 7) too, but there is no error in GRASS 7. It just silently fails. v.net.spanning tree seems to be working incorrectly too. It largely reproduces the original network rather than finding a minimum set of connections between nodes.

Michael

[mmetz]

The Steiner tree problem [0] is NP-hard and a heuristic algorithm is used in this module so the result may be suboptimal. The implemented algorithm needs quite a lot of memory in order to determine a good (not necessarily optimal) solution. This is not a bug but inherent to the algorithm used by the module. There may be less memory-intensive solutions. Changing type to enhancement.

[0] ​http://en.wikipedia.org/wiki/Steiner_tree_problem

[cmbarton]

Replying to mmetz:

The Steiner tree problem [0] is NP-hard and a heuristic algorithm is used in this module so the result may be suboptimal. The implemented algorithm needs quite a lot of memory in order to determine a good (not necessarily optimal) solution. This is not a bug but inherent to the algorithm used by the module. There may be less memory-intensive solutions. Changing type to enhancement.

[0] ​http://en.wikipedia.org/wiki/Steiner_tree_problem

In GRASS 7, it simply doesn't do anything. No message. Nothing. It finishes with no output. That is a problem. In GRASS 6.4.3 it generates a memory error. These are clearly errors. If there is not enough memory, then it should simply give that as a message, not generate error messages or fail silently. So at least this needs to be fixed. I'm leaving this at minor, even though it will probably fail for many uses and users won't know why. But I'm changing this back to a defect because it needs to fail in a more graceful and informative manner at a minimum.

I have 8GB RAM and sufficient disk space, and this fails on the streets_wake map with 3 nodes. it seems like a serious problem if it cannot handle this limited real-world network with the resources I have. Some suggestion in the docs to a realistic limit in the size of the network this can handle would be helpful until the algorithm can be better optimized.

[marisn]

Michael, I made some fixes to v.net.steiner and now it produces correct output on small networks in 7.1 (r68000 and r68001).

As for OOM condition - it is triggered by number of intersections in the network not number of terminals as the module is trying to allocate memory for a 2D array holding length (cost) of the trip between all intersections! I added a warning to documentation (r68003) but a better algorithm is required.

Here is an example for testing with NC (be ware - it triggers instant OOM!):

v.net input=streets_wake@PERMANENT points=schools_wake@PERMANENT output=mynet operation=connect threshold=500
v.net.steiner input=mynet@user1 output=mysteiner terminal_cats=1-10

[neteler]

Milestone renamed

[mlennert]

Michael,

Do Maris' changes fix your issue ?

[mlennert]

ping

[cmbarton]

Have not had a chance to test. Traveling and in conferences. Will try to do so when I get back. But it will be several weeks. Sorry

[neteler]

Ticket retargeted after milestone closed

[neteler]

Ticket retargeted after milestone closed

[martinl]

Ticket retargeted after milestone closed

[martinl]

No activity.