Opened 8 years ago

Closed 8 years ago

#1650 closed enhancement (fixed)

v.net.salesman - add sequence output

Reported by: gfleming Owned by: grass-dev@…
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)

bt_salesman (17.5 KB) - added by mlennert 8 years ago.
backtrace of segfault

Download all attachments as: .zip

Change History (11)

comment:1 Changed 8 years ago by mmetz

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

Changed 8 years ago by mlennert

Attachment: bt_salesman added

backtrace of segfault

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

comment:3 in reply to:  2 Changed 8 years ago by mmetz

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

comment:4 Changed 8 years ago by mlennert

Yep, multiplying buffer size by 10 gets rid of the segfault. Any reason not to simply do that ?

Moritz

comment:5 in reply to:  4 Changed 8 years ago by mmetz

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

comment:6 Changed 8 years ago by mlennert

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

comment:7 in reply to:  6 ; Changed 8 years ago by 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.

Markus M

comment:8 in reply to:  7 ; Changed 8 years ago by mlennert

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

comment:9 in reply to:  8 ; Changed 8 years ago by mmetz

Replying to 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.

Markus M

comment:10 in reply to:  9 Changed 8 years ago by mlennert

Resolution: fixed
Status: newclosed

Replying to mmetz:

Replying to 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.

Thanks, closing ticket.

Moritz

Note: See TracTickets for help on using tickets.