Changeset 2402:da8eb8f4ea41 in lemon-0.x for tools
- Timestamp:
- 03/12/07 14:26:56 (17 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3233
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
tools/lgf-gen.cc
r2391 r2402 30 30 #include <algorithm> 31 31 #include <lemon/unionfind.h> 32 #include <lemon/time_measure.h> 32 33 33 34 using namespace lemon; … … 37 38 UGRAPH_TYPEDEFS(ListUGraph); 38 39 40 bool progress=true; 41 39 42 int N; 40 int girth;43 // int girth; 41 44 42 45 ListUGraph g; … … 235 238 236 239 void minTree() { 240 int en=0; 241 int pr=0; 237 242 std::vector<Pedge> pedges; 243 Timer T; 244 std::cout << T.realTime() << "s: Setting up the edges...\n"; 238 245 for(NodeIt n(g);n!=INVALID;++n) 239 for(NodeIt m=++(NodeIt(n));m!=INVALID;++m) 240 { 241 Pedge p; 242 p.a=n; 243 p.b=m; 244 p.len=(coords[m]-coords[n]).normSquare(); 245 pedges.push_back(p); 246 } 246 { 247 for(NodeIt m=++(NodeIt(n));m!=INVALID;++m) 248 { 249 Pedge p; 250 p.a=n; 251 p.b=m; 252 p.len=(coords[m]-coords[n]).normSquare(); 253 pedges.push_back(p); 254 } 255 en++; 256 if(progress && en>=pr*double(N)/100) 257 { 258 std::cout << pr << "% \r" << std::flush; 259 pr++; 260 } 261 } 262 std::cout << T.realTime() << "s: Sorting the edges...\n"; 247 263 std::sort(pedges.begin(),pedges.end(),pedgeLess); 264 std::cout << T.realTime() << "s: Creating the tree...\n"; 248 265 ListUGraph::NodeMap<int> comp(g); 249 266 UnionFind<ListUGraph::NodeMap<int> > uf(comp); 250 267 for (NodeIt it(g); it != INVALID; ++it) 251 uf.insert(it); 252 253 int en=0; 268 uf.insert(it); 254 269 for(std::vector<Pedge>::iterator pi=pedges.begin();pi!=pedges.end();++pi) 255 270 { 256 271 if ( uf.join(pi->a,pi->b) ) { 257 272 g.addEdge(pi->a,pi->b); 258 en++; 259 if(en>=N-1) return; 260 } 261 } 273 if(en>=N-1) 274 break; 275 } 276 } 277 std::cout << T.realTime() << "s: Done\n"; 262 278 } 263 279 … … 268 284 ArgParser ap(argc,argv); 269 285 270 bool eps;286 // bool eps; 271 287 bool disc_d, square_d, gauss_d; 272 bool tsp_a,two_a,tree_a;288 // bool tsp_a,two_a,tree_a; 273 289 int num_of_cities=1; 274 290 double area=1; 275 291 N=100; 276 girth=10;292 // girth=10; 277 293 std::string ndist("disc"); 278 ap. option("n", "Number of nodes (default is 100)", N)279 . option("g", "Girth parameter (default is 10)", girth)280 . option("cities", "Number of cities (default is 1)", num_of_cities)281 . option("area", "Full relative area of the cities (default is 1)", area)282 . option("disc", "Nodes are evenly distributed on a unit disc (default)",disc_d)294 ap.refOption("n", "Number of nodes (default is 100)", N) 295 .intOption("g", "Girth parameter (default is 10)", 10) 296 .refOption("cities", "Number of cities (default is 1)", num_of_cities) 297 .refOption("area", "Full relative area of the cities (default is 1)", area) 298 .refOption("disc", "Nodes are evenly distributed on a unit disc (default)",disc_d) 283 299 .optionGroup("dist", "disc") 284 . option("square", "Nodes are evenly distributed on a unit square", square_d)300 .refOption("square", "Nodes are evenly distributed on a unit square", square_d) 285 301 .optionGroup("dist", "square") 286 . option("gauss",302 .refOption("gauss", 287 303 "Nodes are located according to a two-dim gauss distribution", 288 304 gauss_d) … … 290 306 // .mandatoryGroup("dist") 291 307 .onlyOneGroup("dist") 292 . option("eps", "Also generate .eps output (prefix.eps)",eps)293 . option("2con", "Create a two connected planar graph",two_a)308 .boolOption("eps", "Also generate .eps output (prefix.eps)") 309 .boolOption("2con", "Create a two connected planar graph") 294 310 .optionGroup("alg","2con") 295 . option("tree", "Create a min. cost spanning tree",tree_a)311 .boolOption("tree", "Create a min. cost spanning tree") 296 312 .optionGroup("alg","tree") 297 . option("tsp", "Create a TSP tour",tsp_a)313 .boolOption("tsp", "Create a TSP tour") 298 314 .optionGroup("alg","tsp") 299 315 .onlyOneGroup("alg") … … 353 369 } 354 370 355 if( tsp_a) {371 if(ap["tsp"]) { 356 372 tsp(); 357 373 std::cout << "#2-opt improvements: " << tsp_impr_num << std::endl; 358 374 } 359 else if( two_a) {375 else if(ap["2con"]) { 360 376 std::cout << "Make triangles\n"; 361 377 // triangle(); 362 sparseTriangle( girth);378 sparseTriangle(ap["g"]); 363 379 std::cout << "Make it sparser\n"; 364 sparse2( girth);380 sparse2(ap["g"]); 365 381 } 366 else if( tree_a) {382 else if(ap["tree"]) { 367 383 minTree(); 368 384 } … … 375 391 tlen+=sqrt((coords[g.source(e)]-coords[g.target(e)]).normSquare()); 376 392 std::cout << "Total edge length : " << tlen << std::endl; 377 if( eps)393 if(ap["eps"]) 378 394 graphToEps(g,prefix+".eps"). 379 395 scale(600).nodeScale(.2).edgeWidthScale(.001).preScale(false).
Note: See TracChangeset
for help on using the changeset viewer.