COIN-OR::LEMON - Graph Library

Changeset 1951:cb7a6e0573bc in lemon-0.x for lemon


Ignore:
Timestamp:
02/03/06 15:07:52 (14 years ago)
Author:
Mihaly Barasz
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2526
Message:

graph_adaptor.h: probably a doxygen bug: in tex formulas there should be

whitespace after the opening and before the closing \f$

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/graph_adaptor.h

    r1949 r1951  
    3939namespace lemon {
    4040
    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
     41  ///\brief Base type for the Graph Adaptors
     42  ///\ingroup graph_adaptors
     43  ///
     44  ///Base type for the Graph Adaptors
     45  ///
     46  ///\warning Graph adaptors are in even
     47  ///more experimental state than the other
     48  ///parts of the lib. Use them at you own risk.
     49  ///
     50  ///This is the base type for most of LEMON graph adaptors.
     51  ///This class implements a trivial graph adaptor i.e. it only wraps the
     52  ///functions and types of the graph. The purpose of this class is to
     53  ///make easier implementing graph adaptors. E.g. if an adaptor is
     54  ///considered which differs from the wrapped graph only in some of its
     55  ///functions or types, then it can be derived from GraphAdaptor,
     56  ///and only the
     57  ///differences should be implemented.
     58  ///
     59  ///author Marton Makai
    6060  template<typename _Graph>
    6161  class GraphAdaptorBase {
     
    281281    }
    282282
    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.
     283    ///\e
     284
     285    /// This function hides \c n in the graph, i.e. the iteration
     286    /// jumps over it. This is done by simply setting the value of \c n 
     287    /// to be false in the corresponding node-map.
    288288    void hide(const Node& n) const { node_filter_map->set(n, false); }
    289289
    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.
     290    ///\e
     291
     292    /// This function hides \c e in the graph, i.e. the iteration
     293    /// jumps over it. This is done by simply setting the value of \c e 
     294    /// to be false in the corresponding edge-map.
    295295    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
    296296
    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
     297    ///\e
     298
     299    /// The value of \c n is set to be true in the node-map which stores
     300    /// hide information. If \c n was hidden previuosly, then it is shown
     301    /// again
    302302     void unHide(const Node& n) const { node_filter_map->set(n, true); }
    303303
    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
     304    ///\e
     305
     306    /// The value of \c e is set to be true in the edge-map which stores
     307    /// hide information. If \c e was hidden previuosly, then it is shown
     308    /// again
    309309    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
    310310
    311     //x Returns true if \c n is hidden.
     311    /// Returns true if \c n is hidden.
    312312   
    313     //x\e
    314     //x
     313    ///\e
     314    ///
    315315    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
    316316
    317     //x Returns true if \c n is hidden.
     317    /// Returns true if \c n is hidden.
    318318   
    319     //x\e
    320     //x
     319    ///\e
     320    ///
    321321    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
    322322
     
    387387    }
    388388
    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.
     389    ///\e
     390
     391    /// This function hides \c n in the graph, i.e. the iteration
     392    /// jumps over it. This is done by simply setting the value of \c n 
     393    /// to be false in the corresponding node-map.
    394394    void hide(const Node& n) const { node_filter_map->set(n, false); }
    395395
    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.
     396    ///\e
     397
     398    /// This function hides \c e in the graph, i.e. the iteration
     399    /// jumps over it. This is done by simply setting the value of \c e 
     400    /// to be false in the corresponding edge-map.
    401401    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
    402402
    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
     403    ///\e
     404
     405    /// The value of \c n is set to be true in the node-map which stores
     406    /// hide information. If \c n was hidden previuosly, then it is shown
     407    /// again
    408408     void unHide(const Node& n) const { node_filter_map->set(n, true); }
    409409
    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
     410    ///\e
     411
     412    /// The value of \c e is set to be true in the edge-map which stores
     413    /// hide information. If \c e was hidden previuosly, then it is shown
     414    /// again
    415415    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
    416416
    417     //x Returns true if \c n is hidden.
     417    /// Returns true if \c n is hidden.
    418418   
    419     //x\e
    420     //x
     419    ///\e
     420    ///
    421421    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
    422422
    423     //x Returns true if \c n is hidden.
     423    /// Returns true if \c n is hidden.
    424424   
    425     //x\e
    426     //x
     425    ///\e
     426    ///
    427427    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
    428428
     
    431431  };
    432432
    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
     433  /// \brief A graph adaptor for hiding nodes and edges from a graph.
     434  /// \ingroup graph_adaptors
     435  ///
     436  /// \warning Graph adaptors are in even more experimental state than the
     437  /// other parts of the lib. Use them at you own risk.
     438  ///
     439  /// SubGraphAdaptor shows the graph with filtered node-set and
     440  /// edge-set. If the \c checked parameter is true then it filters the edgeset
     441  /// to do not get invalid edges without source or target.
     442  /// Let  \f$  G=(V, A)  \f$  be a directed graph
     443  /// and suppose that the graph instance \c g of type ListGraph
     444  /// implements  \f$  G  \f$ .
     445  /// Let moreover  \f$  b_V  \f$  and  \f$  b_A  \f$  be bool-valued functions resp.
     446  /// on the node-set and edge-set.
     447  /// SubGraphAdaptor<...>::NodeIt iterates
     448  /// on the node-set  \f$ \{v\in V : b_V(v)=true\} \f$  and
     449  /// SubGraphAdaptor<...>::EdgeIt iterates
     450  /// on the edge-set  \f$ \{e\in A : b_A(e)=true\} \f$ . Similarly,
     451  /// SubGraphAdaptor<...>::OutEdgeIt and
     452  /// SubGraphAdaptor<...>::InEdgeIt iterates
     453  /// only on edges leaving and entering a specific node which have true value.
     454  ///
     455  /// If the \c checked template parameter is false then we have to note that
     456  /// the node-iterator cares only the filter on the node-set, and the
     457  /// edge-iterator cares only the filter on the edge-set.
     458  /// This way the edge-map
     459  /// should filter all edges which's source or target is filtered by the
     460  /// node-filter.
     461  /// \code
     462  /// typedef ListGraph Graph;
     463  /// Graph g;
     464  /// typedef Graph::Node Node;
     465  /// typedef Graph::Edge Edge;
     466  /// Node u=g.addNode(); //node of id 0
     467  /// Node v=g.addNode(); //node of id 1
     468  /// Node e=g.addEdge(u, v); //edge of id 0
     469  /// Node f=g.addEdge(v, u); //edge of id 1
     470  /// Graph::NodeMap<bool> nm(g, true);
     471  /// nm.set(u, false);
     472  /// Graph::EdgeMap<bool> em(g, true);
     473  /// em.set(e, false);
     474  /// typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
     475  /// SubGW gw(g, nm, em);
     476  /// for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
     477  /// std::cout << ":-)" << std::endl;
     478  /// for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
     479  /// \endcode
     480  /// The output of the above code is the following.
     481  /// \code
     482  /// 1
     483  /// :-)
     484  /// 1
     485  /// \endcode
     486  /// Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
     487  /// \c Graph::Node that is why \c g.id(n) can be applied.
     488  ///
     489  /// For other examples see also the documentation of NodeSubGraphAdaptor and
     490  /// EdgeSubGraphAdaptor.
     491  ///
     492  /// \author Marton Makai
    494493
    495494  template<typename _Graph, typename NodeFilterMap,
     
    515514
    516515
    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
     516  ///\brief An adaptor for hiding nodes from a graph.
     517  ///\ingroup graph_adaptors
     518  ///
     519  ///\warning Graph adaptors are in even more experimental state
     520  ///than the other
     521  ///parts of the lib. Use them at you own risk.
     522  ///
     523  ///An adaptor for hiding nodes from a graph.
     524  ///This adaptor specializes SubGraphAdaptor in the way that only
     525  ///the node-set
     526  ///can be filtered. In usual case the checked parameter is true, we get the
     527  ///induced subgraph. But if the checked parameter is false then we can only
     528  ///filter only isolated nodes.
     529  ///\author Marton Makai
    531530  template<typename Graph, typename NodeFilterMap, bool checked = true>
    532531  class NodeSubGraphAdaptor :
     
    548547
    549548
    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
     549  ///\brief An adaptor for hiding edges from a graph.
     550  ///
     551  ///\warning Graph adaptors are in even more experimental state
     552  ///than the other parts of the lib. Use them at you own risk.
     553  ///
     554  ///An adaptor for hiding edges from a graph.
     555  ///This adaptor specializes SubGraphAdaptor in the way that
     556  ///only the edge-set
     557  ///can be filtered. The usefulness of this adaptor is demonstrated in the
     558  ///problem of searching a maximum number of edge-disjoint shortest paths
     559  ///between
     560  ///two nodes \c s and \c t. Shortest here means being shortest w.r.t.
     561  ///non-negative edge-lengths. Note that
     562  ///the comprehension of the presented solution
     563  ///need's some elementary knowledge from combinatorial optimization.
     564  ///
     565  ///If a single shortest path is to be
     566  ///searched between \c s and \c t, then this can be done easily by
     567  ///applying the Dijkstra algorithm. What happens, if a maximum number of
     568  ///edge-disjoint shortest paths is to be computed. It can be proved that an
     569  ///edge can be in a shortest path if and only
     570  ///if it is tight with respect to
     571  ///the potential function computed by Dijkstra.
     572  ///Moreover, any path containing
     573  ///only such edges is a shortest one.
     574  ///Thus we have to compute a maximum number
     575  ///of edge-disjoint paths between \c s and \c t in
     576  ///the graph which has edge-set
     577  ///all the tight edges. The computation will be demonstrated
     578  ///on the following
     579  ///graph, which is read from the dimacs file \c sub_graph_adaptor_demo.dim.
     580  ///The full source code is available in \ref sub_graph_adaptor_demo.cc.
     581  ///If you are interested in more demo programs, you can use
     582  ///\ref dim_to_dot.cc to generate .dot files from dimacs files.
     583  ///The .dot file of the following figure was generated by 
     584  ///the demo program \ref dim_to_dot.cc.
     585  ///
     586  ///\dot
     587  ///digraph lemon_dot_example {
     588  ///node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
     589  ///n0 [ label="0 (s)" ];
     590  ///n1 [ label="1" ];
     591  ///n2 [ label="2" ];
     592  ///n3 [ label="3" ];
     593  ///n4 [ label="4" ];
     594  ///n5 [ label="5" ];
     595  ///n6 [ label="6 (t)" ];
     596  ///edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
     597  ///n5 ->  n6 [ label="9, length:4" ];
     598  ///n4 ->  n6 [ label="8, length:2" ];
     599  ///n3 ->  n5 [ label="7, length:1" ];
     600  ///n2 ->  n5 [ label="6, length:3" ];
     601  ///n2 ->  n6 [ label="5, length:5" ];
     602  ///n2 ->  n4 [ label="4, length:2" ];
     603  ///n1 ->  n4 [ label="3, length:3" ];
     604  ///n0 ->  n3 [ label="2, length:1" ];
     605  ///n0 ->  n2 [ label="1, length:2" ];
     606  ///n0 ->  n1 [ label="0, length:3" ];
     607  ///}
     608  ///\enddot
     609  ///
     610  ///\code
     611  ///Graph g;
     612  ///Node s, t;
     613  ///LengthMap length(g);
     614  ///
     615  ///readDimacs(std::cin, g, length, s, t);
     616  ///
     617  ///cout << "edges with lengths (of form id, source--length->target): " << endl;
     618  ///for(EdgeIt e(g); e!=INVALID; ++e)
     619  ///  cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
     620  ///       << length[e] << "->" << g.id(g.target(e)) << endl;
     621  ///
     622  ///cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
     623  ///\endcode
     624  ///Next, the potential function is computed with Dijkstra.
     625  ///\code
     626  ///typedef Dijkstra<Graph, LengthMap> Dijkstra;
     627  ///Dijkstra dijkstra(g, length);
     628  ///dijkstra.run(s);
     629  ///\endcode
     630  ///Next, we consrtruct a map which filters the edge-set to the tight edges.
     631  ///\code
     632  ///typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
     633  ///  TightEdgeFilter;
     634  ///TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
     635  ///
     636  ///typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;
     637  ///SubGW gw(g, tight_edge_filter);
     638  ///\endcode
     639  ///Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
     640  ///with a max flow algorithm Preflow.
     641  ///\code
     642  ///ConstMap<Edge, int> const_1_map(1);
     643  ///Graph::EdgeMap<int> flow(g, 0);
     644  ///
     645  ///Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
     646  ///  preflow(gw, s, t, const_1_map, flow);
     647  ///preflow.run();
     648  ///\endcode
     649  ///Last, the output is:
     650  ///\code 
     651  ///cout << "maximum number of edge-disjoint shortest path: "
     652  ///     << preflow.flowValue() << endl;
     653  ///cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
     654  ///     << endl;
     655  ///for(EdgeIt e(g); e!=INVALID; ++e)
     656  ///  if (flow[e])
     657  ///    cout << " " << g.id(g.source(e)) << "--"
     658  ///         << length[e] << "->" << g.id(g.target(e)) << endl;
     659  ///\endcode
     660  ///The program has the following (expected :-)) output:
     661  ///\code
     662  ///edges with lengths (of form id, source--length->target):
     663  /// 9, 5--4->6
     664  /// 8, 4--2->6
     665  /// 7, 3--1->5
     666  /// 6, 2--3->5
     667  /// 5, 2--5->6
     668  /// 4, 2--2->4
     669  /// 3, 1--3->4
     670  /// 2, 0--1->3
     671  /// 1, 0--2->2
     672  /// 0, 0--3->1
     673  ///s: 0 t: 6
     674  ///maximum number of edge-disjoint shortest path: 2
     675  ///edges of the maximum number of edge-disjoint shortest s-t paths:
     676  /// 9, 5--4->6
     677  /// 8, 4--2->6
     678  /// 7, 3--1->5
     679  /// 4, 2--2->4
     680  /// 2, 0--1->3
     681  /// 1, 0--2->2
     682  ///\endcode
     683  ///
     684  ///\author Marton Makai
    686685  template<typename Graph, typename EdgeFilterMap>
    687686  class EdgeSubGraphAdaptor :
     
    770769  };
    771770
    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
     771  ///\brief An undirected graph is made from a directed graph by an adaptor
     772  ///\ingroup graph_adaptors
     773  ///
     774  /// Undocumented, untested!!!
     775  /// If somebody knows nice demo application, let's polulate it.
     776  ///
     777  /// \author Marton Makai
    779778  template<typename _Graph>
    780779  class UGraphAdaptor :
     
    962961      return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
    963962
    964     //x Gives back the opposite edge.
    965 
    966     //x\e
    967     //x
     963    /// Gives back the opposite edge.
     964
     965    ///\e
     966    ///
    968967    Edge opposite(const Edge& e) const {
    969968      Edge f=e;
     
    972971    }
    973972
    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
     973    ///\e
     974
     975    /// \warning This is a linear time operation and works only if
     976    /// \c Graph::EdgeIt is defined.
     977    /// \todo hmm
    979978    int edgeNum() const {
    980979      int i=0;
     
    987986    bool backward(const Edge& e) const { return e.backward; }
    988987
    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.
     988    ///\e
     989
     990    /// \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two
     991    /// _Graph::EdgeMap one for the forward edges and
     992    /// one for the backward edges.
    994993    template <typename T>
    995994    class EdgeMap {
     
    10401039
    10411040
    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.
     1041  ///\brief An adaptor for composing a subgraph of a
     1042  /// bidirected graph made from a directed one.
     1043  ///\ingroup graph_adaptors
     1044  ///
     1045  /// An adaptor for composing a subgraph of a
     1046  /// bidirected graph made from a directed one.
     1047  ///
     1048  ///\warning Graph adaptors are in even more experimental state
     1049  ///than the other
     1050  ///parts of the lib. Use them at you own risk.
     1051  ///
     1052  /// Let  \f$  G=(V, A)  \f$ be a directed graph and for each directed edge
     1053  ///  \f$  e\in A  \f$ , let  \f$  \bar e  \f$ denote the edge obtained by
     1054  /// reversing its orientation. We are given moreover two bool valued
     1055  /// maps on the edge-set,
     1056  ///  \f$  forward\_filter  \f$ , and  \f$  backward\_filter  \f$ .
     1057  /// SubBidirGraphAdaptor implements the graph structure with node-set
     1058  ///  \f$  V  \f$ and edge-set
     1059  ///  \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$ .
     1060  /// The purpose of writing + instead of union is because parallel
     1061  /// edges can arise. (Similarly, antiparallel edges also can arise).
     1062  /// In other words, a subgraph of the bidirected graph obtained, which
     1063  /// is given by orienting the edges of the original graph in both directions.
     1064  /// As the oppositely directed edges are logically different,
     1065  /// the maps are able to attach different values for them.
     1066  ///
     1067  /// An example for such a construction is \c RevGraphAdaptor where the
     1068  /// forward_filter is everywhere false and the backward_filter is
     1069  /// everywhere true. We note that for sake of efficiency,
     1070  /// \c RevGraphAdaptor is implemented in a different way.
     1071  /// But BidirGraphAdaptor is obtained from
     1072  /// SubBidirGraphAdaptor by considering everywhere true
     1073  /// valued maps both for forward_filter and backward_filter.
     1074  ///
     1075  /// The most important application of SubBidirGraphAdaptor
     1076  /// is ResGraphAdaptor, which stands for the residual graph in directed
     1077  /// flow and circulation problems.
     1078  /// As adaptors usually, the SubBidirGraphAdaptor implements the
     1079  /// above mentioned graph structure without its physical storage,
     1080  /// that is the whole stuff is stored in constant memory.
    10821081  template<typename _Graph,
    10831082           typename ForwardFilterMap, typename BackwardFilterMap>
     
    11031102
    11041103
    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.
     1104  ///\brief An adaptor for composing bidirected graph from a directed one.
     1105  ///\ingroup graph_adaptors
     1106  ///
     1107  ///\warning Graph adaptors are in even more experimental state
     1108  ///than the other
     1109  ///parts of the lib. Use them at you own risk.
     1110  ///
     1111  /// An adaptor for composing bidirected graph from a directed one.
     1112  /// A bidirected graph is composed over the directed one without physical
     1113  /// storage. As the oppositely directed edges are logically different ones
     1114  /// the maps are able to attach different values for them.
    11161115  template<typename Graph>
    11171116  class BidirGraphAdaptor :
     
    11811180
    11821181 
    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
     1182  ///\brief An adaptor for composing the residual
     1183  ///graph for directed flow and circulation problems.
     1184  ///\ingroup graph_adaptors
     1185  ///
     1186  ///An adaptor for composing the residual graph for
     1187  ///directed flow and circulation problems.
     1188  ///Let  \f$ G=(V, A) \f$  be a directed graph and let  \f$ F \f$ be a
     1189  ///number type. Let moreover
     1190  /// \f$ f,c:A\to F \f$ , be functions on the edge-set.
     1191  ///In the appications of ResGraphAdaptor,  \f$ f \f$ usually stands for a flow
     1192  ///and  \f$ c \f$ for a capacity function.   
     1193  ///Suppose that a graph instange \c g of type
     1194  ///\c ListGraph implements  \f$ G \f$ .
     1195  ///\code
     1196  ///  ListGraph g;
     1197  ///\endcode
     1198  ///Then RevGraphAdaptor implements the graph structure with node-set
     1199  /// \f$ V \f$  and edge-set  \f$ A_{forward}\cup A_{backward} \f$ , where
     1200  /// \f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and
     1201  /// \f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$ ,
     1202  ///i.e. the so called residual graph.
     1203  ///When we take the union  \f$ A_{forward}\cup A_{backward} \f$ ,
     1204  ///multilicities are counted, i.e. if an edge is in both
     1205  /// \f$ A_{forward} \f$  and  \f$ A_{backward} \f$ , then in the adaptor it
     1206  ///appears twice.
     1207  ///The following code shows how
     1208  ///such an instance can be constructed.
     1209  ///\code
     1210  ///typedef ListGraph Graph;
     1211  ///Graph::EdgeMap<int> f(g);
     1212  ///Graph::EdgeMap<int> c(g);
     1213  ///ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
     1214  ///\endcode
     1215  ///\author Marton Makai
     1216  ///
    12181217  template<typename Graph, typename Number,
    12191218           typename CapacityMap, typename FlowMap>
     
    12651264    }
    12661265
    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.
     1266    /// \brief Residual capacity map.
     1267    ///
     1268    /// In generic residual graphs the residual capacity can be obtained
     1269    /// as a map.
    12711270    class ResCap {
    12721271    protected:
     
    13221321
    13231322
    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
     1323  ///\brief For blocking flows.
     1324  ///\ingroup graph_adaptors
     1325  ///
     1326  ///\warning Graph adaptors are in even more
     1327  ///experimental state than the other
     1328  ///parts of the lib. Use them at you own risk.
     1329  ///
     1330  ///This graph adaptor is used for on-the-fly
     1331  ///Dinits blocking flow computations.
     1332  ///For each node, an out-edge is stored which is used when the
     1333  ///\code
     1334  ///OutEdgeIt& first(OutEdgeIt&, const Node&)
     1335  ///\endcode
     1336  ///is called.
     1337  ///
     1338  ///\author Marton Makai
     1339  ///
    13411340  template <typename _Graph, typename FirstOutEdgesMap>
    13421341  class ErasingFirstGraphAdaptor :
     
    13951394    };
    13961395
    1397     //x \todo May we want VARIANT/union type
     1396    /// \todo May we want VARIANT/union type
    13981397    class Edge : public Parent::Edge {
    13991398      friend class SplitGraphAdaptorBase;
Note: See TracChangeset for help on using the changeset viewer.