Opened 13 years ago
Closed 13 years ago
#1650 closed enhancement (fixed)
v.net.salesman - add sequence output
| Reported by: | gfleming | Owned by: | |
|---|---|---|---|
| Priority: | normal | Milestone: | 6.4.3 |
| Component: | Default | Version: | unspecified |
| Keywords: | Cc: | ||
| CPU: | Unspecified | Platform: | Unspecified |
Description
it would be nice to have tsp sequence output available as a formal command option.
in 6.4.1 if DEBUG is set to 2 then the node sequence is output after the arc sequence in the Cycle section.
in 6.4.2 the node sequence is apparently output just by using --verbose.
I'm sure it is a common use case not only to see the route as a map but to get the node-visiting-sequence as well (which is not always clear from the map).
It is usable as is (comma delimited array), but it might also be useful to stdout or a db table. What could be most useful is another column attached to the nodes layer in the output called, say, 'sequence', containing the explicit order (1,2,3...)
Attachments (1)
Change History (11)
comment:1 by , 13 years ago
follow-up: 3 comment:2 by , 13 years ago
No idea if it is linked to your commit, but I get a segfault running the following on a fresh checkout (r51586) & compile of trunk (including a 'make distclean'):
v.net in=streets_wake points=schools_wake out=streets_with_schools operation=connect thresh=50 v.net.salesman in=streets_with_schools out=salesroute ccats=1-999
I've attached the backtrace.
If it's not linked, I can open a separate ticket.
comment:3 by , 13 years ago
Replying to mlennert:
No idea if it is linked to your commit, but I get a segfault running the following on a fresh checkout (r51586) & compile of trunk (including a 'make distclean'):
> v.net in=streets_wake points=schools_wake out=streets_with_schools operation=connect thresh=50 > v.net.salesman in=streets_with_schools out=salesroute ccats=1-999
I've attached the backtrace.
If it's not linked, I can open a separate ticket.
I can not reproduce it on Linux 64 bit, but I suspect buffer overflow in buf and buf2 according to the backtrace, see also my recently added comment in the source code [0]. I will change this verbose message to a debug message and make it print out one arc / node per line, that should avoid the buffer overflow. The graph in the example has 994 arcs, but buf can only hold a bit less than 300 arcs with 5-digit category numbers.
Markus M
[0] https://trac.osgeo.org/grass/browser/grass/trunk/vector/v.net.salesman/main.c#L459
follow-up: 5 comment:4 by , 13 years ago
Yep, multiplying buffer size by 10 gets rid of the segfault. Any reason not to simply do that ?
Moritz
comment:5 by , 13 years ago
Replying to mlennert:
Yep, multiplying buffer size by 10 gets rid of the segfault. Any reason not to simply do that ?
This is not enough for thousands of nodes as e.g. in the testdata from the TSPLIB which I am currently using. And I am not so sure how useful this information is when printed to stderr. I have removed buf and buf2 in r51587, the arc and node sequences are now printed out with DEBUG=2 one arc/node per line.
Markus M
follow-up: 7 comment:6 by , 13 years ago
Beautiful, especially the new sequence parameter !
Just one small issue: when using sequence=- the result is printed to the terminal before the build process output. This can be solved by using the quiet flag, but is there any way to do this even without that flag ? Glancing over the code, I don't see any other way than creating some temporary buffer which can then be output later, so we would be at the starting point of the problem again, except if there is a possibility to buffer to a temp file and then print out the results at the end.
Moritz
follow-up: 8 comment:7 by , 13 years ago
Replying to mlennert:
Just one small issue: when using sequence=- the result is printed to the terminal before the build process output. This can be solved by using the quiet flag, but is there any way to do this even without that flag ? Glancing over the code, I don't see any other way than creating some temporary buffer which can then be output later, so we would be at the starting point of the problem again, except if there is a possibility to buffer to a temp file and then print out the results at the end.
Done in r51602. The sequence is first written to a temp file and then at the very end written to stdout.
Markus M
follow-up: 9 comment:8 by , 13 years ago
Replying to mmetz:
Replying to mlennert:
Just one small issue: when using sequence=- the result is printed to the terminal before the build process output. This can be solved by using the quiet flag, but is there any way to do this even without that flag ? Glancing over the code, I don't see any other way than creating some temporary buffer which can then be output later, so we would be at the starting point of the problem again, except if there is a possibility to buffer to a temp file and then print out the results at the end.
Done in r51602. The sequence is first written to a temp file and then at the very end written to stdout.
Perfect, thanks a lot !
This ticket can be closed for me. I'll just leave it open for now as a possible reminder for backporting to grass6dev.
Moritz
follow-up: 10 comment:9 by , 13 years ago
comment:10 by , 13 years ago
| Resolution: | → fixed |
|---|---|
| Status: | new → closed |
There is a new option to v.net.salesman in trunk to specify an output file where the sequence is written in tabular format with two columns, sequence and category number. Adding a new column to the attribute table is difficult because 1) several nodes could have the same category value, 2) a single internal node could be visited twice if it is not a user-selected node.
The current output in verbose or debug mode in 6.x is correct only in special cases, for somewhat more complex routes, some nodes will be skipped by that output, or not all nodes will be printed.
BTW, v.net.salesman in trunk is magnitudes faster than in 6.x, particularly for many (100+) nodes, and solves symmetric and asymmetric TSPs.
Markus M