COIN-OR::LEMON - Graph Library

Changeset 930:e89f3bd26fd4 in lemon-0.x


Ignore:
Timestamp:
09/30/04 19:30:20 (19 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1252
Message:

documentation os SubGraphWrapper? with code example.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/graph_wrapper.h

    r923 r930  
    328328
    329329
    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.
    331331 
    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 node-set and
    336   /// edge-set.
    337   /// Given a bool-valued map on the node-set and one on
    338   /// the edge-set 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 node-iterator cares only the filter
    341   /// on the node-set, and the edge-iterators care only the filter on the
    342   /// edge-set.
    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 node-set and
     336  edge-set.
     337  Given a bool-valued map on the node-set and one on
     338  the edge-set 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 node-iterator cares only the filter
     341  on the node-set, and the edge-iterators care only the filter on the
     342  edge-set.
     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  edge-disjoint 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 edge-disjoint path between \c s and \c t in the graph which has edge-set
     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, tail--length->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 edge-set 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 edge-disjoint \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 edge-disjoint shortest path: "
     450       << preflow.flowValue() << endl;
     451  cout << "edges of the maximum number of edge-disjoint shortest s-t 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, tail--length->head):
     461   9, 5--4->6
     462   8, 4--2->6
     463   7, 3--1->5
     464   6, 2--3->5
     465   5, 2--5->6
     466   4, 2--2->4
     467   3, 1--3->4
     468   2, 0--1->3
     469   1, 0--2->2
     470   0, 0--3->1
     471  s: 0 t: 6
     472  maximum number of edge-disjoint shortest path: 2
     473  edges of the maximum number of edge-disjoint shortest s-t paths:
     474   9, 5--4->6
     475   8, 4--2->6
     476   7, 3--1->5
     477   4, 2--2->4
     478   2, 0--1->3
     479   1, 0--2->2
     480  \endcode
     481  \author Marton Makai
     482  */
    372483  template<typename Graph, typename NodeFilterMap,
    373484           typename EdgeFilterMap>
Note: See TracChangeset for help on using the changeset viewer.