COIN-OR::LEMON - Graph Library

Changeset 1949:5db4ff8d69de in lemon-0.x for lemon


Ignore:
Timestamp:
02/03/06 10:18:17 (14 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2524
Message:

Fight with Doxygen.
Victory hasn't been reached yet, but it's on the horizon.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/graph_adaptor.h

    r1946 r1949  
    3939namespace lemon {
    4040
    41   // Graph adaptors
    42 
    43   /*!
    44     \addtogroup graph_adaptors
    45     @{
    46    */
    47 
    48   /*!
    49     Base type for the Graph Adaptors
    50    
    51     \warning Graph adaptors are in even more experimental state than the other
    52     parts of the lib. Use them at you own risk.
    53    
    54     This is the base type for most of LEMON graph adaptors.
    55     This class implements a trivial graph adaptor i.e. it only wraps the
    56     functions and types of the graph. The purpose of this class is to
    57     make easier implementing graph adaptors. E.g. if an adaptor is
    58     considered which differs from the wrapped graph only in some of its
    59     functions or types, then it can be derived from GraphAdaptor, and only the
    60     differences should be implemented.
    61  
    62     \author Marton Makai
    63   */
     41  //x\brief Base type for the Graph Adaptors
     42  //x\ingroup graph_adaptors
     43  //x   
     44  //xBase type for the Graph Adaptors
     45  //x   
     46  //x\warning Graph adaptors are in even
     47  //xmore experimental state than the other
     48  //xparts of the lib. Use them at you own risk.
     49  //x
     50  //xThis is the base type for most of LEMON graph adaptors.
     51  //xThis class implements a trivial graph adaptor i.e. it only wraps the
     52  //xfunctions and types of the graph. The purpose of this class is to
     53  //xmake easier implementing graph adaptors. E.g. if an adaptor is
     54  //xconsidered which differs from the wrapped graph only in some of its
     55  //xfunctions or types, then it can be derived from GraphAdaptor,
     56  //xand only the
     57  //xdifferences should be implemented.
     58  //x
     59  //xauthor Marton Makai
    6460  template<typename _Graph>
    6561  class GraphAdaptorBase {
     
    181177   
    182178
    183   /// A graph adaptor which reverses the orientation of the edges.
    184 
    185   ///\warning Graph adaptors are in even more experimental state than the other
     179  ///\brief A graph adaptor which reverses the orientation of the edges.
     180  ///\ingroup graph_adaptors
     181  ///
     182  ///\warning Graph adaptors are in even more experimental
     183  ///state than the other
    186184  ///parts of the lib. Use them at you own risk.
    187185  ///
    188   /// Let \f$G=(V, A)\f$ be a directed graph and
    189   /// suppose that a graph instange \c g of type
    190   /// \c ListGraph implements \f$G\f$.
     186  /// If \c g is defined as
    191187  ///\code
    192188  /// ListGraph g;
    193189  ///\endcode
    194   /// For each directed edge
    195   /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
    196   /// reversing its orientation.
    197   /// Then RevGraphAdaptor implements the graph structure with node-set
    198   /// \f$V\f$ and edge-set
    199   /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be
    200   /// reversing the orientation of its edges. The following code shows how
    201   /// such an instance can be constructed.
     190  /// then
    202191  ///\code
    203192  /// RevGraphAdaptor<ListGraph> gw(g);
    204193  ///\endcode
    205   ///\author Marton Makai
     194  ///implements the graph obtained from \c g by
     195  /// reversing the orientation of its edges.
    206196
    207197  template<typename _Graph>
     
    291281    }
    292282
    293     /// This function hides \c n in the graph, i.e. the iteration
    294     /// jumps over it. This is done by simply setting the value of \c n 
    295     /// to be false in the corresponding node-map.
     283    //x\e
     284
     285    //x This function hides \c n in the graph, i.e. the iteration
     286    //x jumps over it. This is done by simply setting the value of \c n 
     287    //x to be false in the corresponding node-map.
    296288    void hide(const Node& n) const { node_filter_map->set(n, false); }
    297289
    298     /// This function hides \c e in the graph, i.e. the iteration
    299     /// jumps over it. This is done by simply setting the value of \c e 
    300     /// to be false in the corresponding edge-map.
     290    //x\e
     291
     292    //x This function hides \c e in the graph, i.e. the iteration
     293    //x jumps over it. This is done by simply setting the value of \c e 
     294    //x to be false in the corresponding edge-map.
    301295    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
    302296
    303     /// The value of \c n is set to be true in the node-map which stores
    304     /// hide information. If \c n was hidden previuosly, then it is shown
    305     /// again
     297    //x\e
     298
     299    //x The value of \c n is set to be true in the node-map which stores
     300    //x hide information. If \c n was hidden previuosly, then it is shown
     301    //x again
    306302     void unHide(const Node& n) const { node_filter_map->set(n, true); }
    307303
    308     /// The value of \c e is set to be true in the edge-map which stores
    309     /// hide information. If \c e was hidden previuosly, then it is shown
    310     /// again
     304    //x\e
     305
     306    //x The value of \c e is set to be true in the edge-map which stores
     307    //x hide information. If \c e was hidden previuosly, then it is shown
     308    //x again
    311309    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
    312310
    313     /// Returns true if \c n is hidden.
     311    //x Returns true if \c n is hidden.
     312   
     313    //x\e
     314    //x
    314315    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
    315316
    316     /// Returns true if \c n is hidden.
     317    //x Returns true if \c n is hidden.
     318   
     319    //x\e
     320    //x
    317321    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
    318322
     
    383387    }
    384388
    385     /// This function hides \c n in the graph, i.e. the iteration
    386     /// jumps over it. This is done by simply setting the value of \c n 
    387     /// to be false in the corresponding node-map.
     389    //x\e
     390
     391    //x This function hides \c n in the graph, i.e. the iteration
     392    //x jumps over it. This is done by simply setting the value of \c n 
     393    //x to be false in the corresponding node-map.
    388394    void hide(const Node& n) const { node_filter_map->set(n, false); }
    389395
    390     /// This function hides \c e in the graph, i.e. the iteration
    391     /// jumps over it. This is done by simply setting the value of \c e 
    392     /// to be false in the corresponding edge-map.
     396    //x\e
     397
     398    //x This function hides \c e in the graph, i.e. the iteration
     399    //x jumps over it. This is done by simply setting the value of \c e 
     400    //x to be false in the corresponding edge-map.
    393401    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
    394402
    395     /// The value of \c n is set to be true in the node-map which stores
    396     /// hide information. If \c n was hidden previuosly, then it is shown
    397     /// again
     403    //x\e
     404
     405    //x The value of \c n is set to be true in the node-map which stores
     406    //x hide information. If \c n was hidden previuosly, then it is shown
     407    //x again
    398408     void unHide(const Node& n) const { node_filter_map->set(n, true); }
    399409
    400     /// The value of \c e is set to be true in the edge-map which stores
    401     /// hide information. If \c e was hidden previuosly, then it is shown
    402     /// again
     410    //x\e
     411
     412    //x The value of \c e is set to be true in the edge-map which stores
     413    //x hide information. If \c e was hidden previuosly, then it is shown
     414    //x again
    403415    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
    404416
    405     /// Returns true if \c n is hidden.
     417    //x Returns true if \c n is hidden.
     418   
     419    //x\e
     420    //x
    406421    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
    407422
    408     /// Returns true if \c n is hidden.
     423    //x Returns true if \c n is hidden.
     424   
     425    //x\e
     426    //x
    409427    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
    410428
     
    413431  };
    414432
    415   /*! \brief A graph adaptor for hiding nodes and edges from a graph.
    416    
    417   \warning Graph adaptors are in even more experimental state than the other
    418   parts of the lib. Use them at you own risk.
    419  
    420   SubGraphAdaptor shows the graph with filtered node-set and
    421   edge-set. If the \c checked parameter is true then it filters the edgeset
    422   to do not get invalid edges without source or target.
    423   Let \f$G=(V, A)\f$ be a directed graph
    424   and suppose that the graph instance \c g of type ListGraph implements
    425   \f$G\f$.
    426   Let moreover \f$b_V\f$ and
    427   \f$b_A\f$ be bool-valued functions resp. on the node-set and edge-set.
    428   SubGraphAdaptor<...>::NodeIt iterates
    429   on the node-set \f$\{v\in V : b_V(v)=true\}\f$ and
    430   SubGraphAdaptor<...>::EdgeIt iterates
    431   on the edge-set \f$\{e\in A : b_A(e)=true\}\f$. Similarly,
    432   SubGraphAdaptor<...>::OutEdgeIt and SubGraphAdaptor<...>::InEdgeIt iterates
    433   only on edges leaving and entering a specific node which have true value.
    434 
    435   If the \c checked template parameter is false then we have to note that
    436   the node-iterator cares only the filter on the node-set, and the
    437   edge-iterator cares only the filter on the edge-set. This way the edge-map
    438   should filter all edges which's source or target is filtered by the
    439   node-filter.
    440   \code
    441   typedef ListGraph Graph;
    442   Graph g;
    443   typedef Graph::Node Node;
    444   typedef Graph::Edge Edge;
    445   Node u=g.addNode(); //node of id 0
    446   Node v=g.addNode(); //node of id 1
    447   Node e=g.addEdge(u, v); //edge of id 0
    448   Node f=g.addEdge(v, u); //edge of id 1
    449   Graph::NodeMap<bool> nm(g, true);
    450   nm.set(u, false);
    451   Graph::EdgeMap<bool> em(g, true);
    452   em.set(e, false);
    453   typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
    454   SubGW gw(g, nm, em);
    455   for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
    456   std::cout << ":-)" << std::endl;
    457   for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
    458   \endcode
    459   The output of the above code is the following.
    460   \code
    461   1
    462   :-)
    463   1
    464   \endcode
    465   Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
    466   \c Graph::Node that is why \c g.id(n) can be applied.
    467 
    468   For other examples see also the documentation of NodeSubGraphAdaptor and
    469   EdgeSubGraphAdaptor.
    470 
    471   \author Marton Makai
    472   */
     433  //x\brief A graph adaptor for hiding nodes and edges from a graph.
     434  //x\ingroup graph_adaptors
     435  //x
     436  //x\warning Graph adaptors are in even more experimental
     437  //xstate than the other
     438  //xparts of the lib. Use them at you own risk.
     439  //x
     440  //xSubGraphAdaptor shows the graph with filtered node-set and
     441  //xedge-set. If the \c checked parameter is true then it filters the edgeset
     442  //xto do not get invalid edges without source or target.
     443  //xLet \f$G=(V, A)\f$ be a directed graph
     444  //xand suppose that the graph instance \c g of type ListGraph implements
     445  //x\f$G\f$.
     446  //x/Let moreover \f$b_V\f$ and
     447  //x\f$b_A\f$ be bool-valued functions resp. on the node-set and edge-set.
     448  //xSubGraphAdaptor<...>::NodeIt iterates
     449  //xon the node-set \f$\{v\in V : b_V(v)=true\}\f$ and
     450  //xSubGraphAdaptor<...>::EdgeIt iterates
     451  //xon the edge-set \f$\{e\in A : b_A(e)=true\}\f$. Similarly,
     452  //xSubGraphAdaptor<...>::OutEdgeIt and
     453  //xSubGraphAdaptor<...>::InEdgeIt iterates
     454  //xonly on edges leaving and entering a specific node which have true value.
     455  //x
     456  //xIf the \c checked template parameter is false then we have to note that
     457  //xthe node-iterator cares only the filter on the node-set, and the
     458  //xedge-iterator cares only the filter on the edge-set.
     459  //xThis way the edge-map
     460  //xshould filter all edges which's source or target is filtered by the
     461  //xnode-filter.
     462  //x\code
     463  //xtypedef ListGraph Graph;
     464  //xGraph g;
     465  //xtypedef Graph::Node Node;
     466  //xtypedef Graph::Edge Edge;
     467  //xNode u=g.addNode(); //node of id 0
     468  //xNode v=g.addNode(); //node of id 1
     469  //xNode e=g.addEdge(u, v); //edge of id 0
     470  //xNode f=g.addEdge(v, u); //edge of id 1
     471  //xGraph::NodeMap<bool> nm(g, true);
     472  //xnm.set(u, false);
     473  //xGraph::EdgeMap<bool> em(g, true);
     474  //xem.set(e, false);
     475  //xtypedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
     476  //xSubGW gw(g, nm, em);
     477  //xfor (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
     478  //xstd::cout << ":-)" << std::endl;
     479  //xfor (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
     480  //x\endcode
     481  //xThe output of the above code is the following.
     482  //x\code
     483  //x1
     484  //x:-)
     485  //x1
     486  //x\endcode
     487  //xNote that \c n is of type \c SubGW::NodeIt, but it can be converted to
     488  //x\c Graph::Node that is why \c g.id(n) can be applied.
     489  //x
     490  //xFor other examples see also the documentation of NodeSubGraphAdaptor and
     491  //xEdgeSubGraphAdaptor.
     492  //x
     493  //x\author Marton Makai
     494
    473495  template<typename _Graph, typename NodeFilterMap,
    474496           typename EdgeFilterMap, bool checked = true>
     
    493515
    494516
    495   /*! \brief An adaptor for hiding nodes from a graph.
    496 
    497   \warning Graph adaptors are in even more experimental state than the other
    498   parts of the lib. Use them at you own risk.
    499  
    500   An adaptor for hiding nodes from a graph.
    501   This adaptor specializes SubGraphAdaptor in the way that only the node-set
    502   can be filtered. In usual case the checked parameter is true, we get the
    503   induced subgraph. But if the checked parameter is false then we can only
    504   filter only isolated nodes.
    505   \author Marton Makai
    506   */
     517  //x\brief An adaptor for hiding nodes from a graph.
     518  //x\ingroup graph_adaptors
     519  //x
     520  //x\warning Graph adaptors are in even more experimental state
     521  //xthan the other
     522  //xparts of the lib. Use them at you own risk.
     523  //x
     524  //xAn adaptor for hiding nodes from a graph.
     525  //xThis adaptor specializes SubGraphAdaptor in the way that only
     526  //xthe node-set
     527  //xcan be filtered. In usual case the checked parameter is true, we get the
     528  //xinduced subgraph. But if the checked parameter is false then we can only
     529  //xfilter only isolated nodes.
     530  //x\author Marton Makai
    507531  template<typename Graph, typename NodeFilterMap, bool checked = true>
    508532  class NodeSubGraphAdaptor :
     
    524548
    525549
    526   /*! \brief An adaptor for hiding edges from a graph.
    527 
    528   \warning Graph adaptors are in even more experimental state than the other
    529   parts of the lib. Use them at you own risk.
    530  
    531   An adaptor for hiding edges from a graph.
    532   This adaptor specializes SubGraphAdaptor in the way that only the edge-set
    533   can be filtered. The usefulness of this adaptor is demonstrated in the
    534   problem of searching a maximum number of edge-disjoint shortest paths
    535   between
    536   two nodes \c s and \c t. Shortest here means being shortest w.r.t.
    537   non-negative edge-lengths. Note that
    538   the comprehension of the presented solution
    539   need's some elementary knowledge from combinatorial optimization.
    540 
    541   If a single shortest path is to be
    542   searched between \c s and \c t, then this can be done easily by
    543   applying the Dijkstra algorithm. What happens, if a maximum number of
    544   edge-disjoint shortest paths is to be computed. It can be proved that an
    545   edge can be in a shortest path if and only if it is tight with respect to
    546   the potential function computed by Dijkstra. Moreover, any path containing
    547   only such edges is a shortest one. Thus we have to compute a maximum number
    548   of edge-disjoint paths between \c s and \c t in the graph which has edge-set
    549   all the tight edges. The computation will be demonstrated on the following
    550   graph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim.
    551   The full source code is available in \ref sub_graph_adaptor_demo.cc.
    552   If you are interested in more demo programs, you can use
    553   \ref dim_to_dot.cc to generate .dot files from dimacs files.
    554   The .dot file of the following figure was generated by 
    555   the demo program \ref dim_to_dot.cc.
    556 
    557   \dot
    558   digraph lemon_dot_example {
    559   node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
    560   n0 [ label="0 (s)" ];
    561   n1 [ label="1" ];
    562   n2 [ label="2" ];
    563   n3 [ label="3" ];
    564   n4 [ label="4" ];
    565   n5 [ label="5" ];
    566   n6 [ label="6 (t)" ];
    567   edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
    568   n5 ->  n6 [ label="9, length:4" ];
    569   n4 ->  n6 [ label="8, length:2" ];
    570   n3 ->  n5 [ label="7, length:1" ];
    571   n2 ->  n5 [ label="6, length:3" ];
    572   n2 ->  n6 [ label="5, length:5" ];
    573   n2 ->  n4 [ label="4, length:2" ];
    574   n1 ->  n4 [ label="3, length:3" ];
    575   n0 ->  n3 [ label="2, length:1" ];
    576   n0 ->  n2 [ label="1, length:2" ];
    577   n0 ->  n1 [ label="0, length:3" ];
    578   }
    579   \enddot
    580 
    581   \code
    582   Graph g;
    583   Node s, t;
    584   LengthMap length(g);
    585 
    586   readDimacs(std::cin, g, length, s, t);
    587 
    588   cout << "edges with lengths (of form id, source--length->target): " << endl;
    589   for(EdgeIt e(g); e!=INVALID; ++e)
    590     cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
    591          << length[e] << "->" << g.id(g.target(e)) << endl;
    592 
    593   cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
    594   \endcode
    595   Next, the potential function is computed with Dijkstra.
    596   \code
    597   typedef Dijkstra<Graph, LengthMap> Dijkstra;
    598   Dijkstra dijkstra(g, length);
    599   dijkstra.run(s);
    600   \endcode
    601   Next, we consrtruct a map which filters the edge-set to the tight edges.
    602   \code
    603   typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
    604     TightEdgeFilter;
    605   TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
    606  
    607   typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;
    608   SubGW gw(g, tight_edge_filter);
    609   \endcode
    610   Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
    611   with a max flow algorithm Preflow.
    612   \code
    613   ConstMap<Edge, int> const_1_map(1);
    614   Graph::EdgeMap<int> flow(g, 0);
    615 
    616   Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
    617     preflow(gw, s, t, const_1_map, flow);
    618   preflow.run();
    619   \endcode
    620   Last, the output is:
    621   \code 
    622   cout << "maximum number of edge-disjoint shortest path: "
    623        << preflow.flowValue() << endl;
    624   cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
    625        << endl;
    626   for(EdgeIt e(g); e!=INVALID; ++e)
    627     if (flow[e])
    628       cout << " " << g.id(g.source(e)) << "--"
    629            << length[e] << "->" << g.id(g.target(e)) << endl;
    630   \endcode
    631   The program has the following (expected :-)) output:
    632   \code
    633   edges with lengths (of form id, source--length->target):
    634    9, 5--4->6
    635    8, 4--2->6
    636    7, 3--1->5
    637    6, 2--3->5
    638    5, 2--5->6
    639    4, 2--2->4
    640    3, 1--3->4
    641    2, 0--1->3
    642    1, 0--2->2
    643    0, 0--3->1
    644   s: 0 t: 6
    645   maximum number of edge-disjoint shortest path: 2
    646   edges of the maximum number of edge-disjoint shortest s-t paths:
    647    9, 5--4->6
    648    8, 4--2->6
    649    7, 3--1->5
    650    4, 2--2->4
    651    2, 0--1->3
    652    1, 0--2->2
    653   \endcode
    654 
    655   \author Marton Makai
    656   */
     550  //x\brief An adaptor for hiding edges from a graph.
     551  //x
     552  //x\warning Graph adaptors are in even more experimental state
     553  //xthan the other parts of the lib. Use them at you own risk.
     554  //x
     555  //xAn adaptor for hiding edges from a graph.
     556  //xThis adaptor specializes SubGraphAdaptor in the way that
     557  //xonly the edge-set
     558  //xcan be filtered. The usefulness of this adaptor is demonstrated in the
     559  //xproblem of searching a maximum number of edge-disjoint shortest paths
     560  //xbetween
     561  //xtwo nodes \c s and \c t. Shortest here means being shortest w.r.t.
     562  //xnon-negative edge-lengths. Note that
     563  //xthe comprehension of the presented solution
     564  //xneed's some elementary knowledge from combinatorial optimization.
     565  //x
     566  //xIf a single shortest path is to be
     567  //xsearched between \c s and \c t, then this can be done easily by
     568  //xapplying the Dijkstra algorithm. What happens, if a maximum number of
     569  //xedge-disjoint shortest paths is to be computed. It can be proved that an
     570  //xedge can be in a shortest path if and only
     571  //xif it is tight with respect to
     572  //xthe potential function computed by Dijkstra.
     573  //xMoreover, any path containing
     574  //xonly such edges is a shortest one.
     575  //xThus we have to compute a maximum number
     576  //xof edge-disjoint paths between \c s and \c t in
     577  //xthe graph which has edge-set
     578  //xall the tight edges. The computation will be demonstrated
     579  //xon the following
     580  //xgraph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim.
     581  //xThe full source code is available in \ref sub_graph_adaptor_demo.cc.
     582  //xIf you are interested in more demo programs, you can use
     583  //x\ref dim_to_dot.cc to generate .dot files from dimacs files.
     584  //xThe .dot file of the following figure was generated by 
     585  //xthe demo program \ref dim_to_dot.cc.
     586  //x
     587  //x\dot
     588  //xdigraph lemon_dot_example {
     589  //xnode [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
     590  //xn0 [ label="0 (s)" ];
     591  //xn1 [ label="1" ];
     592  //xn2 [ label="2" ];
     593  //xn3 [ label="3" ];
     594  //xn4 [ label="4" ];
     595  //xn5 [ label="5" ];
     596  //xn6 [ label="6 (t)" ];
     597  //xedge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
     598  //xn5 ->  n6 [ label="9, length:4" ];
     599  //xn4 ->  n6 [ label="8, length:2" ];
     600  //xn3 ->  n5 [ label="7, length:1" ];
     601  //xn2 ->  n5 [ label="6, length:3" ];
     602  //xn2 ->  n6 [ label="5, length:5" ];
     603  //xn2 ->  n4 [ label="4, length:2" ];
     604  //xn1 ->  n4 [ label="3, length:3" ];
     605  //xn0 ->  n3 [ label="2, length:1" ];
     606  //xn0 ->  n2 [ label="1, length:2" ];
     607  //xn0 ->  n1 [ label="0, length:3" ];
     608  //x}
     609  //x\enddot
     610  //x
     611  //x\code
     612  //xGraph g;
     613  //xNode s, t;
     614  //xLengthMap length(g);
     615  //x
     616  //xreadDimacs(std::cin, g, length, s, t);
     617  //x
     618  //xcout << "edges with lengths (of form id, source--length->target): " << endl;
     619  //xfor(EdgeIt e(g); e!=INVALID; ++e)
     620  //x  cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
     621  //x       << length[e] << "->" << g.id(g.target(e)) << endl;
     622  //x
     623  //xcout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
     624  //x\endcode
     625  //xNext, the potential function is computed with Dijkstra.
     626  //x\code
     627  //xtypedef Dijkstra<Graph, LengthMap> Dijkstra;
     628  //xDijkstra dijkstra(g, length);
     629  //xdijkstra.run(s);
     630  //x\endcode
     631  //xNext, we consrtruct a map which filters the edge-set to the tight edges.
     632  //x\code
     633  //xtypedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
     634  //x  TightEdgeFilter;
     635  //xTightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
     636  //x
     637  //xtypedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;
     638  //xSubGW gw(g, tight_edge_filter);
     639  //x\endcode
     640  //xThen, the maximum nimber of edge-disjoint \c s-\c t paths are computed
     641  //xwith a max flow algorithm Preflow.
     642  //x\code
     643  //xConstMap<Edge, int> const_1_map(1);
     644  //xGraph::EdgeMap<int> flow(g, 0);
     645  //x
     646  //xPreflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
     647  //x  preflow(gw, s, t, const_1_map, flow);
     648  //xpreflow.run();
     649  //x\endcode
     650  //xLast, the output is:
     651  //x\code 
     652  //xcout << "maximum number of edge-disjoint shortest path: "
     653  //x     << preflow.flowValue() << endl;
     654  //xcout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
     655  //x     << endl;
     656  //xfor(EdgeIt e(g); e!=INVALID; ++e)
     657  //x  if (flow[e])
     658  //x    cout << " " << g.id(g.source(e)) << "--"
     659  //x         << length[e] << "->" << g.id(g.target(e)) << endl;
     660  //x\endcode
     661  //xThe program has the following (expected :-)) output:
     662  //x\code
     663  //xedges with lengths (of form id, source--length->target):
     664  //x 9, 5--4->6
     665  //x 8, 4--2->6
     666  //x 7, 3--1->5
     667  //x 6, 2--3->5
     668  //x 5, 2--5->6
     669  //x 4, 2--2->4
     670  //x 3, 1--3->4
     671  //x 2, 0--1->3
     672  //x 1, 0--2->2
     673  //x 0, 0--3->1
     674  //xs: 0 t: 6
     675  //xmaximum number of edge-disjoint shortest path: 2
     676  //xedges of the maximum number of edge-disjoint shortest s-t paths:
     677  //x 9, 5--4->6
     678  //x 8, 4--2->6
     679  //x 7, 3--1->5
     680  //x 4, 2--2->4
     681  //x 2, 0--1->3
     682  //x 1, 0--2->2
     683  //x\endcode
     684  //x
     685  //x\author Marton Makai
    657686  template<typename Graph, typename EdgeFilterMap>
    658687  class EdgeSubGraphAdaptor :
     
    741770  };
    742771
    743   /// \brief An undirected graph is made from a directed graph by an adaptor
    744   ///
    745   /// Undocumented, untested!!!
    746   /// If somebody knows nice demo application, let's polulate it.
    747   ///
    748   /// \author Marton Makai
     772  //x\brief An undirected graph is made from a directed graph by an adaptor
     773  //x\ingroup graph_adaptors
     774  //x
     775  //x Undocumented, untested!!!
     776  //x If somebody knows nice demo application, let's polulate it.
     777  //x
     778  //x \author Marton Makai
    749779  template<typename _Graph>
    750780  class UGraphAdaptor :
     
    794824    typedef typename _Graph::Edge GraphEdge;
    795825    template <typename T> class EdgeMap;
    796     /// SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from
    797     /// _Graph::Edge. It contains an extra bool flag which is true
    798     /// if and only if the
    799     /// edge is the backward version of the original edge.
     826    // SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from
     827    // _Graph::Edge. It contains an extra bool flag which is true
     828    // if and only if the
     829    // edge is the backward version of the original edge.
    800830    class Edge : public _Graph::Edge {
    801831      friend class SubBidirGraphAdaptorBase<
     
    806836    public:
    807837      Edge() { }
    808       /// \todo =false is needed, or causes problems?
    809       /// If \c _backward is false, then we get an edge corresponding to the
    810       /// original one, otherwise its oppositely directed pair is obtained.
     838      // \todo =false is needed, or causes problems?
     839      // If \c _backward is false, then we get an edge corresponding to the
     840      // original one, otherwise its oppositely directed pair is obtained.
    811841      Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) :
    812842        _Graph::Edge(e), backward(_backward) { }
     
    932962      return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
    933963
    934     /// Gives back the opposite edge.
     964    //x Gives back the opposite edge.
     965
     966    //x\e
     967    //x
    935968    Edge opposite(const Edge& e) const {
    936969      Edge f=e;
     
    939972    }
    940973
    941     /// \warning This is a linear time operation and works only if
    942     /// \c Graph::EdgeIt is defined.
    943     /// \todo hmm
     974    //x\e
     975
     976    //x \warning This is a linear time operation and works only if
     977    //x \c Graph::EdgeIt is defined.
     978    //x \todo hmm
    944979    int edgeNum() const {
    945980      int i=0;
     
    952987    bool backward(const Edge& e) const { return e.backward; }
    953988
     989    //x\e
     990
     991    //x \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two
     992    //x _Graph::EdgeMap one for the forward edges and
     993    //x one for the backward edges.
    954994    template <typename T>
    955     /// \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two
    956     /// _Graph::EdgeMap one for the forward edges and
    957     /// one for the backward edges.
    958995    class EdgeMap {
    959996      template <typename TT> friend class EdgeMap;
     
    10031040
    10041041
    1005   ///\brief An adaptor for composing a subgraph of a
    1006   /// bidirected graph made from a directed one.
    1007   ///
    1008   /// An adaptor for composing a subgraph of a
    1009   /// bidirected graph made from a directed one.
    1010   ///
    1011   ///\warning Graph adaptors are in even more experimental state than the other
    1012   ///parts of the lib. Use them at you own risk.
    1013   ///
    1014   /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
    1015   /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
    1016   /// reversing its orientation. We are given moreover two bool valued
    1017   /// maps on the edge-set,
    1018   /// \f$forward\_filter\f$, and \f$backward\_filter\f$.
    1019   /// SubBidirGraphAdaptor implements the graph structure with node-set
    1020   /// \f$V\f$ and edge-set
    1021   /// \f$\{e : e\in A \mbox{ and } forward\_filter(e) \mbox{ is true}\}+\{\bar e : e\in A \mbox{ and } backward\_filter(e) \mbox{ is true}\}\f$.
    1022   /// The purpose of writing + instead of union is because parallel
    1023   /// edges can arise. (Similarly, antiparallel edges also can arise).
    1024   /// In other words, a subgraph of the bidirected graph obtained, which
    1025   /// is given by orienting the edges of the original graph in both directions.
    1026   /// As the oppositely directed edges are logically different,
    1027   /// the maps are able to attach different values for them.
    1028   ///
    1029   /// An example for such a construction is \c RevGraphAdaptor where the
    1030   /// forward_filter is everywhere false and the backward_filter is
    1031   /// everywhere true. We note that for sake of efficiency,
    1032   /// \c RevGraphAdaptor is implemented in a different way.
    1033   /// But BidirGraphAdaptor is obtained from
    1034   /// SubBidirGraphAdaptor by considering everywhere true
    1035   /// valued maps both for forward_filter and backward_filter.
    1036   ///
    1037   /// The most important application of SubBidirGraphAdaptor
    1038   /// is ResGraphAdaptor, which stands for the residual graph in directed
    1039   /// flow and circulation problems.
    1040   /// As adaptors usually, the SubBidirGraphAdaptor implements the
    1041   /// above mentioned graph structure without its physical storage,
    1042   /// that is the whole stuff is stored in constant memory.
     1042  //x\brief An adaptor for composing a subgraph of a
     1043  //x bidirected graph made from a directed one.
     1044  //x\ingroup graph_adaptors
     1045  //x
     1046  //x An adaptor for composing a subgraph of a
     1047  //x bidirected graph made from a directed one.
     1048  //x
     1049  //x\warning Graph adaptors are in even more experimental state
     1050  //xthan the other
     1051  //xparts of the lib. Use them at you own risk.
     1052  //x
     1053  //x Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
     1054  //x \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
     1055  //x reversing its orientation. We are given moreover two bool valued
     1056  //x maps on the edge-set,
     1057  //x \f$forward\_filter\f$, and \f$backward\_filter\f$.
     1058  //x SubBidirGraphAdaptor implements the graph structure with node-set
     1059  //x \f$V\f$ and edge-set
     1060  //x \f$\{e : e\in A \mbox{ and } forward\_filter(e) \mbox{ is true}\}+\{\bar e : e\in A \mbox{ and } backward\_filter(e) \mbox{ is true}\}\f$.
     1061  //x The purpose of writing + instead of union is because parallel
     1062  //x edges can arise. (Similarly, antiparallel edges also can arise).
     1063  //x In other words, a subgraph of the bidirected graph obtained, which
     1064  //x is given by orienting the edges of the original graph in both directions.
     1065  //x As the oppositely directed edges are logically different,
     1066  //x the maps are able to attach different values for them.
     1067  //x
     1068  //x An example for such a construction is \c RevGraphAdaptor where the
     1069  //x forward_filter is everywhere false and the backward_filter is
     1070  //x everywhere true. We note that for sake of efficiency,
     1071  //x \c RevGraphAdaptor is implemented in a different way.
     1072  //x But BidirGraphAdaptor is obtained from
     1073  //x SubBidirGraphAdaptor by considering everywhere true
     1074  //x valued maps both for forward_filter and backward_filter.
     1075  //x
     1076  //x The most important application of SubBidirGraphAdaptor
     1077  //x is ResGraphAdaptor, which stands for the residual graph in directed
     1078  //x flow and circulation problems.
     1079  //x As adaptors usually, the SubBidirGraphAdaptor implements the
     1080  //x above mentioned graph structure without its physical storage,
     1081  //x that is the whole stuff is stored in constant memory.
    10431082  template<typename _Graph,
    10441083           typename ForwardFilterMap, typename BackwardFilterMap>
     
    10641103
    10651104
    1066   ///\brief An adaptor for composing bidirected graph from a directed one.
    1067   ///
    1068   ///\warning Graph adaptors are in even more experimental state than the other
    1069   ///parts of the lib. Use them at you own risk.
    1070   ///
    1071   /// An adaptor for composing bidirected graph from a directed one.
    1072   /// A bidirected graph is composed over the directed one without physical
    1073   /// storage. As the oppositely directed edges are logically different ones
    1074   /// the maps are able to attach different values for them.
     1105  //x\brief An adaptor for composing bidirected graph from a directed one.
     1106  //x\ingroup graph_adaptors
     1107  //x
     1108  //x\warning Graph adaptors are in even more experimental state
     1109  //xthan the other
     1110  //xparts of the lib. Use them at you own risk.
     1111  //x
     1112  //x An adaptor for composing bidirected graph from a directed one.
     1113  //x A bidirected graph is composed over the directed one without physical
     1114  //x storage. As the oppositely directed edges are logically different ones
     1115  //x the maps are able to attach different values for them.
    10751116  template<typename Graph>
    10761117  class BidirGraphAdaptor :
     
    11401181
    11411182 
    1142   /*! \brief An adaptor for composing the residual graph for directed flow and circulation problems.
    1143 
    1144   An adaptor for composing the residual graph for directed flow and circulation problems.
    1145   Let \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a
    1146   number type. Let moreover
    1147   \f$f,c:A\to F\f$, be functions on the edge-set.
    1148   In the appications of ResGraphAdaptor, \f$f\f$ usually stands for a flow
    1149   and \f$c\f$ for a capacity function.   
    1150   Suppose that a graph instange \c g of type
    1151   \c ListGraph implements \f$G\f$.
    1152   \code
    1153   ListGraph g;
    1154   \endcode
    1155   Then RevGraphAdaptor implements the graph structure with node-set
    1156   \f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where
    1157   \f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$ and
    1158   \f$A_{backward}=\{vu : uv\in A, f(uv)>0\}\f$,
    1159   i.e. the so called residual graph.
    1160   When we take the union \f$A_{forward}\cup A_{backward}\f$,
    1161   multilicities are counted, i.e. if an edge is in both
    1162   \f$A_{forward}\f$ and \f$A_{backward}\f$, then in the adaptor it
    1163   appears twice.
    1164   The following code shows how
    1165   such an instance can be constructed.
    1166   \code
    1167   typedef ListGraph Graph;
    1168   Graph::EdgeMap<int> f(g);
    1169   Graph::EdgeMap<int> c(g);
    1170   ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
    1171   \endcode
    1172   \author Marton Makai
    1173   */
     1183  //x\brief An adaptor for composing the residual
     1184  //xgraph for directed flow and circulation problems.
     1185  //x\ingroup graph_adaptors
     1186  //x
     1187  //xAn adaptor for composing the residual graph for
     1188  //xdirected flow and circulation problems.
     1189  //xLet \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a
     1190  //xnumber type. Let moreover
     1191  //x\f$f,c:A\to F\f$, be functions on the edge-set.
     1192  //xIn the appications of ResGraphAdaptor, \f$f\f$ usually stands for a flow
     1193  //xand \f$c\f$ for a capacity function.   
     1194  //xSuppose that a graph instange \c g of type
     1195  //x\c ListGraph implements \f$G\f$ .
     1196  //x\code
     1197  //x  ListGraph g;
     1198  //x\endcode
     1199  //xThen RevGraphAdaptor implements the graph structure with node-set
     1200  //x\f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where
     1201  //x\f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$ and
     1202  //x\f$A_{backward}=\{vu : uv\in A, f(uv)>0\}\f$,
     1203  //xi.e. the so called residual graph.
     1204  //xWhen we take the union \f$A_{forward}\cup A_{backward}\f$,
     1205  //xmultilicities are counted, i.e. if an edge is in both
     1206  //x\f$A_{forward}\f$ and \f$A_{backward}\f$, then in the adaptor it
     1207  //xappears twice.
     1208  //xThe following code shows how
     1209  //xsuch an instance can be constructed.
     1210  //x\code
     1211  //xtypedef ListGraph Graph;
     1212  //xGraph::EdgeMap<int> f(g);
     1213  //xGraph::EdgeMap<int> c(g);
     1214  //xResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
     1215  //x\endcode
     1216  //x\author Marton Makai
     1217  //x
    11741218  template<typename Graph, typename Number,
    11751219           typename CapacityMap, typename FlowMap>
     
    12211265    }
    12221266
    1223     /// \brief Residual capacity map.
    1224     ///
    1225     /// In generic residual graphs the residual capacity can be obtained
    1226     /// as a map.
     1267    //x \brief Residual capacity map.
     1268    //x
     1269    //x In generic residual graphs the residual capacity can be obtained
     1270    //x as a map.
    12271271    class ResCap {
    12281272    protected:
     
    12781322
    12791323
    1280   /// For blocking flows.
    1281 
    1282   ///\warning Graph adaptors are in even more
    1283   ///experimental state than the other
    1284   ///parts of the lib. Use them at you own risk.
    1285   ///
    1286   ///This graph adaptor is used for on-the-fly
    1287   ///Dinits blocking flow computations.
    1288   ///For each node, an out-edge is stored which is used when the
    1289   ///\code OutEdgeIt& first(OutEdgeIt&, const Node&)\endcode
    1290   ///is called.
    1291   ///
    1292   ///\author Marton Makai
    1293   ///
     1324  //x\brief For blocking flows.
     1325  //x\ingroup graph_adaptors
     1326  //x
     1327  //x\warning Graph adaptors are in even more
     1328  //xexperimental state than the other
     1329  //xparts of the lib. Use them at you own risk.
     1330  //x
     1331  //xThis graph adaptor is used for on-the-fly
     1332  //xDinits blocking flow computations.
     1333  //xFor each node, an out-edge is stored which is used when the
     1334  //x\code
     1335  //xOutEdgeIt& first(OutEdgeIt&, const Node&)
     1336  //x\endcode
     1337  //xis called.
     1338  //x
     1339  //x\author Marton Makai
     1340  //x
    12941341  template <typename _Graph, typename FirstOutEdgesMap>
    12951342  class ErasingFirstGraphAdaptor :
     
    13481395    };
    13491396
    1350     /// \todo May we want VARIANT/union type
     1397    //x \todo May we want VARIANT/union type
    13511398    class Edge : public Parent::Edge {
    13521399      friend class SplitGraphAdaptorBase;
     
    16751722  };
    16761723
    1677   ///@}
    1678 
    16791724} //namespace lemon
    16801725
Note: See TracChangeset for help on using the changeset viewer.