Changeset 930:e89f3bd26fd4 in lemon0.x for src
 Timestamp:
 09/30/04 19:30:20 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1252
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/lemon/graph_wrapper.h
r923 r930 328 328 329 329 330 / //A graph wrapper for hiding nodes and edges from a graph.330 /*! \brief A graph wrapper for hiding nodes and edges from a graph. 331 331 332 ///\warning Graph wrappers are in even more experimental state than the other 333 ///parts of the lib. Use them at you own risk. 334 /// 335 /// This wrapper shows a graph with filtered nodeset and 336 /// edgeset. 337 /// Given a boolvalued map on the nodeset and one on 338 /// the edgeset of the graph, the iterators show only the objects 339 /// having true value. We have to note that this does not mean that an 340 /// induced subgraph is obtained, the nodeiterator cares only the filter 341 /// on the nodeset, and the edgeiterators care only the filter on the 342 /// edgeset. 343 /// \code 344 /// typedef SmartGraph Graph; 345 /// Graph g; 346 /// typedef Graph::Node Node; 347 /// typedef Graph::Edge Edge; 348 /// Node u=g.addNode(); //node of id 0 349 /// Node v=g.addNode(); //node of id 1 350 /// Node e=g.addEdge(u, v); //edge of id 0 351 /// Node f=g.addEdge(v, u); //edge of id 1 352 /// Graph::NodeMap<bool> nm(g, true); 353 /// nm.set(u, false); 354 /// Graph::EdgeMap<bool> em(g, true); 355 /// em.set(e, false); 356 /// typedef SubGraphWrapper<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW; 357 /// SubGW gw(g, nm, em); 358 /// for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl; 359 /// std::cout << ":)" << std::endl; 360 /// for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl; 361 /// \endcode 362 /// The output of the above code is the following. 363 /// \code 364 /// 1 365 /// :) 366 /// 1 367 /// \endcode 368 /// Note that \c n is of type \c SubGW::NodeIt, but it can be converted to 369 /// \c Graph::Node that is why \c g.id(n) can be applied. 370 /// 371 ///\author Marton Makai 332 \warning Graph wrappers are in even more experimental state than the other 333 parts of the lib. Use them at you own risk. 334 335 This wrapper shows a graph with filtered nodeset and 336 edgeset. 337 Given a boolvalued map on the nodeset and one on 338 the edgeset of the graph, the iterators show only the objects 339 having true value. We have to note that this does not mean that an 340 induced subgraph is obtained, the nodeiterator cares only the filter 341 on the nodeset, and the edgeiterators care only the filter on the 342 edgeset. 343 \code 344 typedef SmartGraph Graph; 345 Graph g; 346 typedef Graph::Node Node; 347 typedef Graph::Edge Edge; 348 Node u=g.addNode(); //node of id 0 349 Node v=g.addNode(); //node of id 1 350 Node e=g.addEdge(u, v); //edge of id 0 351 Node f=g.addEdge(v, u); //edge of id 1 352 Graph::NodeMap<bool> nm(g, true); 353 nm.set(u, false); 354 Graph::EdgeMap<bool> em(g, true); 355 em.set(e, false); 356 typedef SubGraphWrapper<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW; 357 SubGW gw(g, nm, em); 358 for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl; 359 std::cout << ":)" << std::endl; 360 for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl; 361 \endcode 362 The output of the above code is the following. 363 \code 364 1 365 :) 366 1 367 \endcode 368 Note that \c n is of type \c SubGW::NodeIt, but it can be converted to 369 \c Graph::Node that is why \c g.id(n) can be applied. 370 371 Consider now a mathematically more invloved problem, where the application 372 of SubGraphWrapper is reasonable sure enough. If a shortest path is to be 373 searched between two nodes \c s and \c t, then this can be done easily by 374 applying the Dijkstra algorithm class. What happens, if a maximum number of 375 edgedisjoint shortest paths is to be computed. It can be proved that an 376 edge can be in a shortest path if and only if it is tight with respect to 377 the potential function computed by Dijkstra. Moreover, any path containing 378 only such edges is a shortest one. Thus we have to compute a maximum number 379 of edgedisjoint path between \c s and \c t in the graph which has edgeset 380 all the tight edges. The computation will be demonstrated on the following 381 graph, which is read from a dimacs file. 382 383 \dot 384 digraph lemon_dot_example { 385 node [ shape=ellipse, fontname=Helvetica, fontsize=10 ]; 386 n0 [ label="0 (s)" ]; 387 n1 [ label="1" ]; 388 n2 [ label="2" ]; 389 n3 [ label="3" ]; 390 n4 [ label="4" ]; 391 n5 [ label="5" ]; 392 n6 [ label="6 (t)" ]; 393 edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ]; 394 n5 > n6 [ label="9, length:4" ]; 395 n4 > n6 [ label="8, length:2" ]; 396 n3 > n5 [ label="7, length:1" ]; 397 n2 > n5 [ label="6, length:3" ]; 398 n2 > n6 [ label="5, length:5" ]; 399 n2 > n4 [ label="4, length:2" ]; 400 n1 > n4 [ label="3, length:3" ]; 401 n0 > n3 [ label="2, length:1" ]; 402 n0 > n2 [ label="1, length:2" ]; 403 n0 > n1 [ label="0, length:3" ]; 404 } 405 \enddot 406 407 \code 408 Graph g; 409 Node s, t; 410 LengthMap length(g); 411 412 readDimacs(std::cin, g, length, s, t); 413 414 cout << "edges with lengths (of form id, taillength>head): " << endl; 415 for(EdgeIt e(g); e!=INVALID; ++e) 416 cout << g.id(e) << ", " << g.id(g.tail(e)) << "" 417 << length[e] << ">" << g.id(g.head(e)) << endl; 418 419 cout << "s: " << g.id(s) << " t: " << g.id(t) << endl; 420 \endcode 421 Next, the potential function is computed with Dijkstra. 422 \code 423 typedef Dijkstra<Graph, LengthMap> Dijkstra; 424 Dijkstra dijkstra(g, length); 425 dijkstra.run(s); 426 \endcode 427 Next, we consrtruct a map which filters the edgeset to the tight edges. 428 \code 429 typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap> 430 TightEdgeFilter; 431 TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length); 432 433 ConstMap<Node, bool> const_true_map(true); 434 typedef SubGraphWrapper<Graph, ConstMap<Node, bool>, TightEdgeFilter> SubGW; 435 SubGW gw(g, const_true_map, tight_edge_filter); 436 \endcode 437 Then, the maximum nimber of edgedisjoint \c s\c t paths are computed 438 with a max flow algorithm Preflow. 439 \code 440 ConstMap<Edge, int> const_1_map(1); 441 Graph::EdgeMap<int> flow(g, 0); 442 443 Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> > 444 preflow(gw, s, t, const_1_map, flow); 445 preflow.run(); 446 \endcode 447 Last, the output is: 448 \code 449 cout << "maximum number of edgedisjoint shortest path: " 450 << preflow.flowValue() << endl; 451 cout << "edges of the maximum number of edgedisjoint shortest st paths: " 452 << endl; 453 for(EdgeIt e(g); e!=INVALID; ++e) 454 if (flow[e]) 455 cout << " " << g.id(g.tail(e)) << "" 456 << length[e] << ">" << g.id(g.head(e)) << endl; 457 \endcode 458 The program has the following (expected :)) output: 459 \code 460 edges with lengths (of form id, taillength>head): 461 9, 54>6 462 8, 42>6 463 7, 31>5 464 6, 23>5 465 5, 25>6 466 4, 22>4 467 3, 13>4 468 2, 01>3 469 1, 02>2 470 0, 03>1 471 s: 0 t: 6 472 maximum number of edgedisjoint shortest path: 2 473 edges of the maximum number of edgedisjoint shortest st paths: 474 9, 54>6 475 8, 42>6 476 7, 31>5 477 4, 22>4 478 2, 01>3 479 1, 02>2 480 \endcode 481 \author Marton Makai 482 */ 372 483 template<typename Graph, typename NodeFilterMap, 373 484 typename EdgeFilterMap>
Note: See TracChangeset
for help on using the changeset viewer.