Opened 9 years ago

Closed 2 years ago

#1761 closed defect (wontfix)

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

Reported by: cmbarton Owned by: grass-dev@…
Priority: normal Milestone: 7.2.4
Component: Vector Version: svn-trunk
Keywords: v.net.steiner Cc:
CPU: All Platform: All

Description

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

Change History (14)

comment:1 Changed 9 years ago by martinl

Keywords: v.net.steiner added

comment:2 Changed 9 years ago by mmetz

CPU: UnspecifiedAll
Milestone: 6.4.37.0.0
Platform: UnspecifiedAll
Priority: criticalminor
Type: defectenhancement
Version: unspecifiedsvn-trunk

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

comment:3 in reply to:  2 Changed 9 years ago by cmbarton

Type: enhancementdefect

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.

comment:4 Changed 5 years ago by marisn

Milestone: 7.0.07.1.0
Priority: minornormal
Summary: v.net.steiner brokenv.net.steiner fails on a network with large number of intersections

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

comment:5 Changed 5 years ago by neteler

Milestone: 7.1.07.2.0

Milestone renamed

comment:6 Changed 5 years ago by mlennert

Michael,

Do Maris' changes fix your issue ?

comment:7 Changed 5 years ago by mlennert

ping

comment:8 Changed 5 years ago by 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

comment:9 Changed 5 years ago by neteler

Milestone: 7.2.07.2.1

Ticket retargeted after milestone closed

comment:10 Changed 4 years ago by martinl

Milestone: 7.2.17.2.2

comment:11 Changed 4 years ago by neteler

Milestone: 7.2.27.2.3

Ticket retargeted after milestone closed

comment:12 Changed 3 years ago by martinl

Milestone: 7.2.3

Ticket retargeted after milestone closed

comment:13 Changed 3 years ago by martinl

Milestone: 7.2.4

comment:14 Changed 2 years ago by martinl

Resolution: wontfix
Status: newclosed

No activity.

Note: See TracTickets for help on using tickets.