[Lemon-user] TSP on incomplete path and different start / end -point

[Kovács Péter]

Hi Thomas,

Your copy method could be simplified: the intermediate storage 
vector<vector<int> > can be skipped.

For each edge of the ListGraph, once you have the corresponding node IDs 
i and j, you can directly set the length to the edge map of the 
FullGraph. Using operator() of FullGraph, you can get the i-th and j-th 
nodes, and using the edge() method, you can get the edge between them.
E.g. length[fullGraph.edge(fullGraph(i), fullGraph(j))] = ...

For more information, see the API of FullGraph:
http://lemon.cs.elte.hu/pub/doc/1.3.1/a00177.html

Regards,
Péter


> Hi Peter,
>
> thanks. This is exactly what I want to do. Works like a charm.
> The issue with wrong pathlength was caused by copying the the ListGraph
> to the FullGraph iterating over the lists.
> I forgot that the iterator visits the nodes and edges differently for
> each graph.
>
> 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.
>
> Quite tedious but anyways the code does what it should. And so much
> easier to understand than boost::Graph :-)
>
> Cheers,
>
> Thomas
>
>
> *Gesendet:* Mittwoch, 08. Februar 2017 um 16:50 Uhr
> *Von:* "Kovács Péter" <kpeter at inf.elte.hu>
> *An:* "Lion Bull" <lion.bull at gmx.de>, lemon-user at lemon.cs.elte.hu
> *Betreff:* Re: [Lemon-user] TSP on incomplete path and different start /
> end -point
> Hi Thomas,
>
> If you extend the graph this way with edges corresponding to shortest
> paths, then note that the found TSP tours may visit nodes more than once
> in terms of the original graph. If it is not a problem, then you can
> apply this approach.
>
> As far as I understand, you are actually looking for a Hamiltonian path
> from a start node to an end node instead of a tour (Hamiltonian cycle).
> Your approach seems to be practical, but may need some extra work.
>
> Note that you can manually convert any tour to a path. Let s and e
> denote that start and end node, and let sp, sn, ep, en denote the
> previous and next node of s and e according to the tour. You can
> (i) remove edges s-sp and e-ep, and add the edge sp-ep instead OR
> (ii) remove edges s-sn and e-en, and add the edge sn-en instead.
> Both way you get a path between s and e. Choose the one with the smaller
> total length. (E.g. in case of (i), the path is: <s..ep part of the
> tour>, ep-sp edge, <sp..t part of the tour in reverse order>.)
>
> Furthermore, you can try other TSP solvers, not only ChristofidesTsp.
> You can check the available algorithms here:
> http://lemon.cs.elte.hu/pub/doc/1.3.1/a00618.html
>
> I suggest to give a try to Opt2Tsp. It can be started with a tour
> computed with other algorithm, e.g. with ChristofidesTsp. (Actually,
> Opt2Tsp applies transformations similar to the one described above.)
>
> I hope this helps.
>
> Anyway, it is really strange what you wrote about negative costs. The
> total cost of a tour is computed by simply summing the costs of the
> edges in the tour.
>
> Regards,
> Péter
>
>
>
>> Hi all,
>>
>> maybe someone of you can point me in the right direction.
>>
>> I have an incomplete Graph for which I want a TSP solution.
>> What I did so far:
>> 1. Convert the graph to be complete
>> For this I calculate the distance between nodes not having an edge
>> jet, using dijkstra.
>> Than I add a new edge with this length.
>> 2. Set the distance between start end end node to be zero
>> 3. Run the TSP algorithm
>>
>> Issue: The TSP is solved but start and end point are never visited one
>> directly after another.
>>
>> Is this possible at all? I even tried to add a negative distance to the
>> edge between start and end point.
>> Interestingly here I get a negative length of the route even this edge
>> is not used.
>>
>> Regards,
>>
>> Thomas
>>
>>
>>
>> _______________________________________________
>> Lemon-user mailing list
>> Lemon-user at lemon.cs.elte.hu
>> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
>>
>