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.
#1761: v.net.steiner broken
---------------------------+------------------------------------------------
Reporter: cmbarton | Owner: grass-dev@…
Type: enhancement | Status: new
Priority: minor | Milestone: 7.0.0
Component: Vector | Version: svn-trunk
Keywords: v.net.steiner | Platform: All
Cpu: All |
---------------------------+------------------------------------------------
Changes (by mmetz):
* priority: critical => minor
* platform: Unspecified => All
* version: unspecified => svn-trunk
* milestone: 6.4.3 => 7.0.0
* type: defect => enhancement
* cpu: Unspecified => All
Comment:
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.
#1761: v.net.steiner broken
---------------------------+------------------------------------------------
Reporter: cmbarton | Owner: grass-dev@…
Type: defect | Status: new
Priority: minor | Milestone: 7.0.0
Component: Vector | Version: svn-trunk
Keywords: v.net.steiner | Platform: All
Cpu: All |
---------------------------+------------------------------------------------
Changes (by cmbarton):
* type: enhancement => defect
Comment:
Replying to [comment:2 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.