17 */ |
17 */ |
18 |
18 |
19 #ifndef LEMON_GRAPH_ADAPTOR_H |
19 #ifndef LEMON_GRAPH_ADAPTOR_H |
20 #define LEMON_GRAPH_ADAPTOR_H |
20 #define LEMON_GRAPH_ADAPTOR_H |
21 |
21 |
22 /// \ingroup graph_adaptors |
22 ///\ingroup graph_adaptors |
23 /// \file |
23 ///\file |
24 /// \brief Several graph adaptors. |
24 ///\brief Several graph adaptors. |
25 /// |
25 /// |
26 /// This file contains several useful graph adaptor functions. |
26 ///This file contains several useful graph adaptor functions. |
27 /// |
27 /// |
28 /// \author Marton Makai and Balazs Dezso |
28 ///\author Marton Makai and Balazs Dezso |
29 |
29 |
30 #include <lemon/bits/invalid.h> |
30 #include <lemon/bits/invalid.h> |
31 #include <lemon/maps.h> |
31 #include <lemon/maps.h> |
32 |
32 |
33 #include <lemon/bits/base_extender.h> |
33 #include <lemon/bits/base_extender.h> |
1477 }; |
1474 }; |
1478 |
1475 |
1479 |
1476 |
1480 ///\brief An adaptor for composing the residual |
1477 ///\brief An adaptor for composing the residual |
1481 ///graph for directed flow and circulation problems. |
1478 ///graph for directed flow and circulation problems. |
|
1479 /// |
1482 ///\ingroup graph_adaptors |
1480 ///\ingroup graph_adaptors |
1483 /// |
1481 /// |
1484 ///An adaptor for composing the residual graph for |
1482 ///An adaptor for composing the residual graph for |
1485 ///directed flow and circulation problems. |
1483 ///directed flow and circulation problems. |
1486 ///Let \f$ G=(V, A) \f$ be a directed graph and let \f$ F \f$ be a |
1484 // ///Let \f$ G=(V, A) \f$ be a directed graph and let \f$ F \f$ be a |
1487 ///number type. Let moreover |
1485 // ///number type. Let moreover |
1488 ///\f$ f,c:A\to F \f$, be functions on the edge-set. |
1486 // ///\f$ f,c:A\to F \f$, be functions on the edge-set. |
1489 ///In the appications of ResGraphAdaptor, \f$ f \f$ usually stands for a flow |
1487 // ///In the appications of ResGraphAdaptor, \f$ f \f$ usually stands for a |
1490 ///and \f$ c \f$ for a capacity function. |
1488 // ///flow and \f$ c \f$ for a capacity function. |
1491 ///Suppose that a graph instange \c g of type |
1489 // ///Suppose that a graph instange \c g of type |
1492 ///\c ListGraph implements \f$ G \f$. |
1490 // ///\c ListGraph implements \f$ G \f$. |
1493 ///\code |
1491 // ///\code |
1494 /// ListGraph g; |
1492 // /// ListGraph g; |
1495 ///\endcode |
1493 // ///\endcode |
1496 ///Then RevGraphAdaptor implements the graph structure with node-set |
1494 // ///Then RevGraphAdaptor implements the graph structure with node-set |
1497 ///\f$ V \f$ and edge-set \f$ A_{forward}\cup A_{backward} \f$, where |
1495 // ///\f$ V \f$ and edge-set \f$ A_{forward}\cup A_{backward} \f$, where |
1498 ///\f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and |
1496 // ///\f$ A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\} \f$ and |
1499 ///\f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, |
1497 // ///\f$ A_{backward}=\{vu : uv\in A, f(uv)>0\} \f$, |
1500 ///i.e. the so called residual graph. |
1498 // ///i.e. the so called residual graph. |
1501 ///When we take the union \f$ A_{forward}\cup A_{backward} \f$, |
1499 // ///When we take the union \f$ A_{forward}\cup A_{backward} \f$, |
1502 ///multilicities are counted, i.e. if an edge is in both |
1500 // ///multilicities are counted, i.e. if an edge is in both |
1503 ///\f$ A_{forward} \f$ and \f$ A_{backward} \f$, then in the adaptor it |
1501 // ///\f$ A_{forward} \f$ and \f$ A_{backward} \f$, then in the adaptor it |
1504 ///appears twice. |
1502 // ///appears twice. The following code shows how such an instance can be |
1505 ///The following code shows how |
1503 // ///constructed. |
1506 ///such an instance can be constructed. |
1504 // ///\code |
1507 ///\code |
1505 // /// typedef ListGraph Graph; |
1508 ///typedef ListGraph Graph; |
1506 // /// Graph::EdgeMap<int> f(g); |
1509 ///Graph::EdgeMap<int> f(g); |
1507 // /// Graph::EdgeMap<int> c(g); |
1510 ///Graph::EdgeMap<int> c(g); |
1508 // /// ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > ga(g); |
1511 ///ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > ga(g); |
1509 // ///\endcode |
1512 ///\endcode |
1510 // ///\author Marton Makai |
1513 ///\author Marton Makai |
1511 // /// |
1514 /// |
|
1515 template<typename Graph, typename Number, |
1512 template<typename Graph, typename Number, |
1516 typename CapacityMap, typename FlowMap, |
1513 typename CapacityMap, typename FlowMap, |
1517 typename Tolerance = Tolerance<Number> > |
1514 typename Tolerance = Tolerance<Number> > |
1518 class ResGraphAdaptor : |
1515 class ResGraphAdaptor : |
1519 public EdgeSubGraphAdaptor< |
1516 public EdgeSubGraphAdaptor< |