<html><head></head><body><div style="font-family: Verdana;font-size: 12.0px;"><div>
<div>
<div>Hi Peter,</div>
<div> </div>
<div>thanks. This is exactly what I want to do. Works like a charm.</div>
<div>The issue with wrong pathlength was caused by copying the the ListGraph to the FullGraph iterating over the lists.</div>
<div>I forgot that the iterator visits the nodes and edges differently for each graph.</div>
<div> </div>
<div>Is there any function with which to do a simple copy of a ListGraph to a FullGraph? Or at least for the maps as the FullGraph is a static structure? At the moment I first iterate over all edges in the list graph, copy the length of the edges in a separate vector<vector<int> > array using the node ids as "coordinate" in the two dimensinal vector. Afterwards I iterate over the edges of the FullGraph and use the node ids to copy the edge length from the vector into the edgemap of the FullGraph.</div>
<div> </div>
<div>Quite tedious but anyways the code does what it should. And so much easier to understand than boost::Graph :-)</div>
<div> </div>
<div>Cheers,</div>
<div> </div>
<div>Thomas</div>
<div> </div>
<div> </div>
<div name="quote" style="margin:10px 5px 5px 10px; padding: 10px 0 10px 10px; border-left:2px solid #C3D9E5; word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;">
<div style="margin:0 0 10px 0;"><b>Gesendet:</b> Mittwoch, 08. Februar 2017 um 16:50 Uhr<br/>
<b>Von:</b> "Kovács Péter" <kpeter@inf.elte.hu><br/>
<b>An:</b> "Lion Bull" <lion.bull@gmx.de>, lemon-user@lemon.cs.elte.hu<br/>
<b>Betreff:</b> Re: [Lemon-user] TSP on incomplete path and different start / end -point</div>
<div name="quoted-content">Hi Thomas,<br/>
<br/>
If you extend the graph this way with edges corresponding to shortest<br/>
paths, then note that the found TSP tours may visit nodes more than once<br/>
in terms of the original graph. If it is not a problem, then you can<br/>
apply this approach.<br/>
<br/>
As far as I understand, you are actually looking for a Hamiltonian path<br/>
from a start node to an end node instead of a tour (Hamiltonian cycle).<br/>
Your approach seems to be practical, but may need some extra work.<br/>
<br/>
Note that you can manually convert any tour to a path. Let s and e<br/>
denote that start and end node, and let sp, sn, ep, en denote the<br/>
previous and next node of s and e according to the tour. You can<br/>
(i) remove edges s-sp and e-ep, and add the edge sp-ep instead OR<br/>
(ii) remove edges s-sn and e-en, and add the edge sn-en instead.<br/>
Both way you get a path between s and e. Choose the one with the smaller<br/>
total length. (E.g. in case of (i), the path is: <s..ep part of the<br/>
tour>, ep-sp edge, <sp..t part of the tour in reverse order>.)<br/>
<br/>
Furthermore, you can try other TSP solvers, not only ChristofidesTsp.<br/>
You can check the available algorithms here:<br/>
<a href="http://lemon.cs.elte.hu/pub/doc/1.3.1/a00618.html" target="_blank">http://lemon.cs.elte.hu/pub/doc/1.3.1/a00618.html</a><br/>
<br/>
I suggest to give a try to Opt2Tsp. It can be started with a tour<br/>
computed with other algorithm, e.g. with ChristofidesTsp. (Actually,<br/>
Opt2Tsp applies transformations similar to the one described above.)<br/>
<br/>
I hope this helps.<br/>
<br/>
Anyway, it is really strange what you wrote about negative costs. The<br/>
total cost of a tour is computed by simply summing the costs of the<br/>
edges in the tour.<br/>
<br/>
Regards,<br/>
Péter<br/>
<br/>
<br/>
<br/>
> Hi all,<br/>
><br/>
> maybe someone of you can point me in the right direction.<br/>
><br/>
> I have an incomplete Graph for which I want a TSP solution.<br/>
> What I did so far:<br/>
> 1. Convert the graph to be complete<br/>
> For this I calculate the distance between nodes not having an edge<br/>
> jet, using dijkstra.<br/>
> Than I add a new edge with this length.<br/>
> 2. Set the distance between start end end node to be zero<br/>
> 3. Run the TSP algorithm<br/>
><br/>
> Issue: The TSP is solved but start and end point are never visited one<br/>
> directly after another.<br/>
><br/>
> Is this possible at all? I even tried to add a negative distance to the<br/>
> edge between start and end point.<br/>
> Interestingly here I get a negative length of the route even this edge<br/>
> is not used.<br/>
><br/>
> Regards,<br/>
><br/>
> Thomas<br/>
><br/>
><br/>
><br/>
> _______________________________________________<br/>
> Lemon-user mailing list<br/>
> Lemon-user@lemon.cs.elte.hu<br/>
> <a href="http://lemon.cs.elte.hu/mailman/listinfo/lemon-user" target="_blank">http://lemon.cs.elte.hu/mailman/listinfo/lemon-user</a><br/>
><br/>
</div>
</div>
</div>
</div></div></body></html>