#1650: v.net.salesman - add sequence output
-------------------------+--------------------------------------------------
Reporter: gfleming | Owner: grass-dev@…
Type: enhancement | Status: new
Priority: normal | Milestone: 6.4.3
Component: Default | Version: unspecified
Keywords: | Platform: Unspecified
Cpu: Unspecified |
-------------------------+--------------------------------------------------
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...)
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.
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'):
Replying to [comment:2 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'):
> 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.
Replying to [comment:4 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.
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.
Replying to [comment:6 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.
Replying to [comment:7 mmetz]:
> Replying to [comment:6 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.
Replying to [comment:8 mlennert]:
>
> This ticket can be closed for me. I'll just leave it open for now as a
possible reminder for backporting to grass6dev.
Replying to [comment:9 mmetz]:
> Replying to [comment:8 mlennert]:
> >
> > This ticket can be closed for me. I'll just leave it open for now as a
possible reminder for backporting to grass6dev.
>
> Backported to 6.5 in r51609.