232 } |
235 } |
233 } |
236 } |
234 } |
237 } |
235 |
238 |
236 void minTree() { |
239 void minTree() { |
|
240 int en=0; |
|
241 int pr=0; |
237 std::vector<Pedge> pedges; |
242 std::vector<Pedge> pedges; |
|
243 Timer T; |
|
244 std::cout << T.realTime() << "s: Setting up the edges...\n"; |
238 for(NodeIt n(g);n!=INVALID;++n) |
245 for(NodeIt n(g);n!=INVALID;++n) |
239 for(NodeIt m=++(NodeIt(n));m!=INVALID;++m) |
246 { |
240 { |
247 for(NodeIt m=++(NodeIt(n));m!=INVALID;++m) |
241 Pedge p; |
248 { |
242 p.a=n; |
249 Pedge p; |
243 p.b=m; |
250 p.a=n; |
244 p.len=(coords[m]-coords[n]).normSquare(); |
251 p.b=m; |
245 pedges.push_back(p); |
252 p.len=(coords[m]-coords[n]).normSquare(); |
246 } |
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 std::sort(pedges.begin(),pedges.end(),pedgeLess); |
263 std::sort(pedges.begin(),pedges.end(),pedgeLess); |
|
264 std::cout << T.realTime() << "s: Creating the tree...\n"; |
248 ListUGraph::NodeMap<int> comp(g); |
265 ListUGraph::NodeMap<int> comp(g); |
249 UnionFind<ListUGraph::NodeMap<int> > uf(comp); |
266 UnionFind<ListUGraph::NodeMap<int> > uf(comp); |
250 for (NodeIt it(g); it != INVALID; ++it) |
267 for (NodeIt it(g); it != INVALID; ++it) |
251 uf.insert(it); |
268 uf.insert(it); |
252 |
|
253 int en=0; |
|
254 for(std::vector<Pedge>::iterator pi=pedges.begin();pi!=pedges.end();++pi) |
269 for(std::vector<Pedge>::iterator pi=pedges.begin();pi!=pedges.end();++pi) |
255 { |
270 { |
256 if ( uf.join(pi->a,pi->b) ) { |
271 if ( uf.join(pi->a,pi->b) ) { |
257 g.addEdge(pi->a,pi->b); |
272 g.addEdge(pi->a,pi->b); |
258 en++; |
273 if(en>=N-1) |
259 if(en>=N-1) return; |
274 break; |
260 } |
275 } |
261 } |
276 } |
|
277 std::cout << T.realTime() << "s: Done\n"; |
262 } |
278 } |
263 |
279 |
264 |
280 |
265 |
281 |
266 int main(int argc,char **argv) |
282 int main(int argc,char **argv) |
267 { |
283 { |
268 ArgParser ap(argc,argv); |
284 ArgParser ap(argc,argv); |
269 |
285 |
270 bool eps; |
286 // bool eps; |
271 bool disc_d, square_d, gauss_d; |
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 int num_of_cities=1; |
289 int num_of_cities=1; |
274 double area=1; |
290 double area=1; |
275 N=100; |
291 N=100; |
276 girth=10; |
292 // girth=10; |
277 std::string ndist("disc"); |
293 std::string ndist("disc"); |
278 ap.option("n", "Number of nodes (default is 100)", N) |
294 ap.refOption("n", "Number of nodes (default is 100)", N) |
279 .option("g", "Girth parameter (default is 10)", girth) |
295 .intOption("g", "Girth parameter (default is 10)", 10) |
280 .option("cities", "Number of cities (default is 1)", num_of_cities) |
296 .refOption("cities", "Number of cities (default is 1)", num_of_cities) |
281 .option("area", "Full relative area of the cities (default is 1)", area) |
297 .refOption("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) |
298 .refOption("disc", "Nodes are evenly distributed on a unit disc (default)",disc_d) |
283 .optionGroup("dist", "disc") |
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 .optionGroup("dist", "square") |
301 .optionGroup("dist", "square") |
286 .option("gauss", |
302 .refOption("gauss", |
287 "Nodes are located according to a two-dim gauss distribution", |
303 "Nodes are located according to a two-dim gauss distribution", |
288 gauss_d) |
304 gauss_d) |
289 .optionGroup("dist", "gauss") |
305 .optionGroup("dist", "gauss") |
290 // .mandatoryGroup("dist") |
306 // .mandatoryGroup("dist") |
291 .onlyOneGroup("dist") |
307 .onlyOneGroup("dist") |
292 .option("eps", "Also generate .eps output (prefix.eps)",eps) |
308 .boolOption("eps", "Also generate .eps output (prefix.eps)") |
293 .option("2con", "Create a two connected planar graph",two_a) |
309 .boolOption("2con", "Create a two connected planar graph") |
294 .optionGroup("alg","2con") |
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 .optionGroup("alg","tree") |
312 .optionGroup("alg","tree") |
297 .option("tsp", "Create a TSP tour",tsp_a) |
313 .boolOption("tsp", "Create a TSP tour") |
298 .optionGroup("alg","tsp") |
314 .optionGroup("alg","tsp") |
299 .onlyOneGroup("alg") |
315 .onlyOneGroup("alg") |
300 .other("[prefix]","Prefix of the output files. Default is 'lgf-gen-out'") |
316 .other("[prefix]","Prefix of the output files. Default is 'lgf-gen-out'") |
301 .run(); |
317 .run(); |
302 |
318 |
350 coords[n]=center+rnd.disc()*area* |
366 coords[n]=center+rnd.disc()*area* |
351 std::sqrt(sizes[s]/sum_sizes); |
367 std::sqrt(sizes[s]/sum_sizes); |
352 } |
368 } |
353 } |
369 } |
354 |
370 |
355 if(tsp_a) { |
371 if(ap["tsp"]) { |
356 tsp(); |
372 tsp(); |
357 std::cout << "#2-opt improvements: " << tsp_impr_num << std::endl; |
373 std::cout << "#2-opt improvements: " << tsp_impr_num << std::endl; |
358 } |
374 } |
359 else if(two_a) { |
375 else if(ap["2con"]) { |
360 std::cout << "Make triangles\n"; |
376 std::cout << "Make triangles\n"; |
361 // triangle(); |
377 // triangle(); |
362 sparseTriangle(girth); |
378 sparseTriangle(ap["g"]); |
363 std::cout << "Make it sparser\n"; |
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 minTree(); |
383 minTree(); |
368 } |
384 } |
369 |
385 |
370 |
386 |
371 std::cout << "Number of nodes : " << countNodes(g) << std::endl; |
387 std::cout << "Number of nodes : " << countNodes(g) << std::endl; |
372 std::cout << "Number of edges : " << countUEdges(g) << std::endl; |
388 std::cout << "Number of edges : " << countUEdges(g) << std::endl; |
373 double tlen=0; |
389 double tlen=0; |
374 for(UEdgeIt e(g);e!=INVALID;++e) |
390 for(UEdgeIt e(g);e!=INVALID;++e) |
375 tlen+=sqrt((coords[g.source(e)]-coords[g.target(e)]).normSquare()); |
391 tlen+=sqrt((coords[g.source(e)]-coords[g.target(e)]).normSquare()); |
376 std::cout << "Total edge length : " << tlen << std::endl; |
392 std::cout << "Total edge length : " << tlen << std::endl; |
377 if(eps) |
393 if(ap["eps"]) |
378 graphToEps(g,prefix+".eps"). |
394 graphToEps(g,prefix+".eps"). |
379 scale(600).nodeScale(.2).edgeWidthScale(.001).preScale(false). |
395 scale(600).nodeScale(.2).edgeWidthScale(.001).preScale(false). |
380 coords(coords).run(); |
396 coords(coords).run(); |
381 |
397 |
382 UGraphWriter<ListUGraph>(prefix+".lgf",g). |
398 UGraphWriter<ListUGraph>(prefix+".lgf",g). |