lemon/graph_adaptor.h
changeset 2037 32e4bebee616
parent 2034 b71f8ff62046
child 2042 bdc953f2a449
equal deleted inserted replaced
31:7a9ebf595e60 32:bb4caa63aa8c
    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>
    72     void setGraph(Graph& _graph) { graph=&_graph; }
    72     void setGraph(Graph& _graph) { graph=&_graph; }
    73 
    73 
    74   public:
    74   public:
    75     GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }
    75     GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }
    76 
    76 
    77     Graph& getGraph() { return *graph; }
       
    78     const Graph& getGraph() const { return *graph; }
       
    79  
       
    80     typedef typename Graph::Node Node;
    77     typedef typename Graph::Node Node;
    81     typedef typename Graph::Edge Edge;
    78     typedef typename Graph::Edge Edge;
    82    
    79    
    83     void first(Node& i) const { graph->first(i); }
    80     void first(Node& i) const { graph->first(i); }
    84     void first(Edge& i) const { graph->first(i); }
    81     void first(Edge& i) const { graph->first(i); }
  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< 
  1558       forward_filter.setFlow(_flow);
  1555       forward_filter.setFlow(_flow);
  1559       backward_filter.setFlow(_flow);
  1556       backward_filter.setFlow(_flow);
  1560     }
  1557     }
  1561 
  1558 
  1562   public:
  1559   public:
  1563 
       
  1564     const Graph& getGraph() const { return ugraph.getGraph(); }
       
  1565 
  1560 
  1566     /// \brief Constructor of the residual graph.
  1561     /// \brief Constructor of the residual graph.
  1567     ///
  1562     ///
  1568     /// Constructor of the residual graph. The parameters are the graph type,
  1563     /// Constructor of the residual graph. The parameters are the graph type,
  1569     /// the flow map, the capacity map and a tolerance object.
  1564     /// the flow map, the capacity map and a tolerance object.