[Lemon-user] Stuck with compiling TSP solver

[Kovács Péter]

Hi Thomas,

Note that the TSP solvers in LEMON take a FullGraph as argument and a 
corresponding edge map:
http://lemon.cs.elte.hu/pub/doc/1.3.1/a00077.html

In your code, you use a graph of type ListGraph. So you should construct 
a FullGraph object and a corresponding edge map based on your graph. If 
your graph is actually a full graph, then it is easy. Otherwise, you can 
add the missing edges with length that is equal to the shortest path 
distance of the two nodes. (Assuming that the graph is connected. 
Otherwise the TSP problem is infeasible, of course.)

I hope this helps.

Regards,
Péter



> Hi lemon community,
>
> I almost finished my small little programm but am stuck with the cost
> map paramter when calling the TSP solvers. Would be great if someone
> could point me in the right direction :-)
>
> Here is what I try to do
>
> //Initiate the graph from file
> ListGraph g;
> ListGraph::NodeMap<std::string> name(g);
> ListGraph::EdgeMap<int> length(g);
> ListGraph::Node src;
> std::string title;
> graphReader(g, "graph.lgf")
>   .nodeMap("title", name)
>   .edgeMap("length", length)
>   .node("source", src)
>   .attribute("caption",title)
>   .run();
>
> //Solve TSP
> typedef ChristofidesTsp<ListGraph::EdgeMap<int> > TSP;
> TSP tour(g,
> length);
> <-------- This line won't compile
> tour.run();
> std::cout << tour.tourCost() << "\n";
>
> Somewhere initiating the ChristofidesTsp fails. Looks like the cost map
> I provide is not a cost map. So what am I missing here?
>
> lemon_test.cc:116:24: error: no matching function for call to
> ‘lemon::ChristofidesTsp<lemon::GraphExtender<lemon::ListGraphBase>::EdgeMap<int>
>>::ChristofidesTsp(lemon::ListGraph&,
> lemon::GraphExtender<lemon::ListGraphBase>::EdgeMap<int>&)’
>      TSP tour(g, length);
>                         ^
> Thanks for your help,
>
> Thomas
>
>
> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
>