24 #include <lemon/counter.h> |
24 #include <lemon/counter.h> |
25 #include <lemon/suurballe.h> |
25 #include <lemon/suurballe.h> |
26 #include <lemon/graph_to_eps.h> |
26 #include <lemon/graph_to_eps.h> |
27 #include <lemon/graph_writer.h> |
27 #include <lemon/graph_writer.h> |
28 #include <lemon/arg_parser.h> |
28 #include <lemon/arg_parser.h> |
|
29 #include <lemon/euler.h> |
29 #include <cmath> |
30 #include <cmath> |
30 #include <algorithm> |
31 #include <algorithm> |
31 #include <lemon/unionfind.h> |
32 #include <lemon/unionfind.h> |
32 #include <lemon/time_measure.h> |
33 #include <lemon/time_measure.h> |
33 |
34 |
268 uf.insert(it); |
276 uf.insert(it); |
269 for(std::vector<Pedge>::iterator pi=pedges.begin();pi!=pedges.end();++pi) |
277 for(std::vector<Pedge>::iterator pi=pedges.begin();pi!=pedges.end();++pi) |
270 { |
278 { |
271 if ( uf.join(pi->a,pi->b) ) { |
279 if ( uf.join(pi->a,pi->b) ) { |
272 g.addEdge(pi->a,pi->b); |
280 g.addEdge(pi->a,pi->b); |
|
281 en++; |
273 if(en>=N-1) |
282 if(en>=N-1) |
274 break; |
283 break; |
275 } |
284 } |
276 } |
285 } |
277 std::cout << T.realTime() << "s: Done\n"; |
286 std::cout << T.realTime() << "s: Done\n"; |
278 } |
287 } |
279 |
288 |
|
289 Node common(UEdge e, UEdge f) |
|
290 { |
|
291 return (g.source(e)==g.source(f)||g.source(e)==g.target(f))? |
|
292 g.source(e):g.target(e); |
|
293 } |
|
294 |
|
295 void tsp2() |
|
296 { |
|
297 std::cout << "Find a tree..." << std::endl; |
|
298 |
|
299 minTree(); |
|
300 |
|
301 std::cout << "Total edge length (tree) : " << totalLen() << std::endl; |
|
302 |
|
303 std::cout << "Make it Euler..." << std::endl; |
|
304 |
|
305 { |
|
306 std::vector<Node> leafs; |
|
307 for(NodeIt n(g);n!=INVALID;++n) |
|
308 if(countIncEdges(g,n)%2==1) leafs.push_back(n); |
|
309 for(unsigned int i=0;i<leafs.size();i+=2) |
|
310 g.addEdge(leafs[i],leafs[i+1]); |
|
311 } |
|
312 |
|
313 for(NodeIt n(g);n!=INVALID;++n) |
|
314 if(countIncEdges(g,n)%2) |
|
315 std::cout << "GEBASZ!!!" << std::endl; |
|
316 |
|
317 std::cout << "Number of edges : " << countUEdges(g) << std::endl; |
|
318 |
|
319 // for(NodeIt n(g);n!=INVALID;++n) |
|
320 // if(countIncEdges(g,n)>2) |
|
321 // std::cout << "+"; |
|
322 // std::cout << std::endl; |
|
323 |
|
324 std::cout << "Total edge length (euler) : " << totalLen() << std::endl; |
|
325 |
|
326 ListUGraph::UEdgeMap<UEdge> enext(g); |
|
327 { |
|
328 UEulerIt<ListUGraph> e(g); |
|
329 UEdge eo=e; |
|
330 UEdge ef=e; |
|
331 // std::cout << "Tour edge: " << g.id(UEdge(e)) << std::endl; |
|
332 for(++e;e!=INVALID;++e) |
|
333 { |
|
334 // std::cout << "Tour edge: " << g.id(UEdge(e)) << std::endl; |
|
335 enext[eo]=e; |
|
336 eo=e; |
|
337 } |
|
338 enext[eo]=ef; |
|
339 } |
|
340 |
|
341 std::cout << "Creating a tour from that..." << std::endl; |
|
342 |
|
343 int nnum = countNodes(g); |
|
344 int ednum = countUEdges(g); |
|
345 |
|
346 for(UEdge p=UEdgeIt(g);ednum>nnum;p=enext[p]) |
|
347 { |
|
348 // std::cout << "Checking edge " << g.id(p) << std::endl; |
|
349 UEdge e=enext[p]; |
|
350 UEdge f=enext[e]; |
|
351 Node n2=common(e,f); |
|
352 Node n1=g.oppositeNode(n2,e); |
|
353 Node n3=g.oppositeNode(n2,f); |
|
354 if(countIncEdges(g,n2)>2) |
|
355 { |
|
356 // std::cout << "Remove an Edge" << std::endl; |
|
357 UEdge ff=enext[f]; |
|
358 g.erase(e); |
|
359 g.erase(f); |
|
360 UEdge ne=g.addEdge(n1,n3); |
|
361 enext[p]=ne; |
|
362 enext[ne]=ff; |
|
363 ednum--; |
|
364 } |
|
365 } |
|
366 |
|
367 std::cout << "Total edge length (tour) : " << totalLen() << std::endl; |
|
368 |
|
369 tsp_improve(); |
|
370 |
|
371 std::cout << "Total edge length (2-opt tour) : " << totalLen() << std::endl; |
|
372 } |
280 |
373 |
281 |
374 |
282 int main(int argc,const char **argv) |
375 int main(int argc,const char **argv) |
283 { |
376 { |
284 ArgParser ap(argc,argv); |
377 ArgParser ap(argc,argv); |
304 gauss_d) |
397 gauss_d) |
305 .optionGroup("dist", "gauss") |
398 .optionGroup("dist", "gauss") |
306 // .mandatoryGroup("dist") |
399 // .mandatoryGroup("dist") |
307 .onlyOneGroup("dist") |
400 .onlyOneGroup("dist") |
308 .boolOption("eps", "Also generate .eps output (prefix.eps)") |
401 .boolOption("eps", "Also generate .eps output (prefix.eps)") |
|
402 .boolOption("dir", "Directed graph is generated (each edges are replaced by two directed ones)") |
309 .boolOption("2con", "Create a two connected planar graph") |
403 .boolOption("2con", "Create a two connected planar graph") |
310 .optionGroup("alg","2con") |
404 .optionGroup("alg","2con") |
311 .boolOption("tree", "Create a min. cost spanning tree") |
405 .boolOption("tree", "Create a min. cost spanning tree") |
312 .optionGroup("alg","tree") |
406 .optionGroup("alg","tree") |
313 .boolOption("tsp", "Create a TSP tour") |
407 .boolOption("tsp", "Create a TSP tour") |
314 .optionGroup("alg","tsp") |
408 .optionGroup("alg","tsp") |
|
409 .boolOption("tsp2", "Create a TSP tour (tree based)") |
|
410 .optionGroup("alg","tsp2") |
315 .onlyOneGroup("alg") |
411 .onlyOneGroup("alg") |
316 .other("[prefix]","Prefix of the output files. Default is 'lgf-gen-out'") |
412 .other("[prefix]","Prefix of the output files. Default is 'lgf-gen-out'") |
317 .run(); |
413 .run(); |
318 |
414 |
319 std::string prefix; |
415 std::string prefix; |
370 |
466 |
371 if(ap["tsp"]) { |
467 if(ap["tsp"]) { |
372 tsp(); |
468 tsp(); |
373 std::cout << "#2-opt improvements: " << tsp_impr_num << std::endl; |
469 std::cout << "#2-opt improvements: " << tsp_impr_num << std::endl; |
374 } |
470 } |
|
471 if(ap["tsp2"]) { |
|
472 tsp2(); |
|
473 std::cout << "#2-opt improvements: " << tsp_impr_num << std::endl; |
|
474 } |
375 else if(ap["2con"]) { |
475 else if(ap["2con"]) { |
376 std::cout << "Make triangles\n"; |
476 std::cout << "Make triangles\n"; |
377 // triangle(); |
477 // triangle(); |
378 sparseTriangle(ap["g"]); |
478 sparseTriangle(ap["g"]); |
379 std::cout << "Make it sparser\n"; |
479 std::cout << "Make it sparser\n"; |
393 if(ap["eps"]) |
493 if(ap["eps"]) |
394 graphToEps(g,prefix+".eps"). |
494 graphToEps(g,prefix+".eps"). |
395 scale(600).nodeScale(.2).edgeWidthScale(.001).preScale(false). |
495 scale(600).nodeScale(.2).edgeWidthScale(.001).preScale(false). |
396 coords(coords).run(); |
496 coords(coords).run(); |
397 |
497 |
398 UGraphWriter<ListUGraph>(prefix+".lgf",g). |
498 if(ap["dir"]) |
399 writeNodeMap("coordinates_x",scaleMap(xMap(coords),600)). |
499 GraphWriter<ListUGraph>(prefix+".lgf",g). |
400 writeNodeMap("coordinates_y",scaleMap(yMap(coords),600)). |
500 writeNodeMap("coordinates_x",scaleMap(xMap(coords),600)). |
401 run(); |
501 writeNodeMap("coordinates_y",scaleMap(yMap(coords),600)). |
402 } |
502 run(); |
403 |
503 else UGraphWriter<ListUGraph>(prefix+".lgf",g). |
|
504 writeNodeMap("coordinates_x",scaleMap(xMap(coords),600)). |
|
505 writeNodeMap("coordinates_y",scaleMap(yMap(coords),600)). |
|
506 run(); |
|
507 } |
|
508 |