COIN-OR::LEMON - Graph Library

Changes in / [595:16d7255a6849:600:0ba8dfce7259] in lemon-1.2


Ignore:
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • lemon/gomory_hu.h

    r581 r596  
    4343  /// between these nodes. Moreover the components obtained by removing
    4444  /// this edge from the tree determine the corresponding minimum cut.
    45   ///
    4645  /// Therefore once this tree is computed, the minimum cut between any pair
    4746  /// of nodes can easily be obtained.
    4847  ///
    4948  /// The algorithm calculates \e n-1 distinct minimum cuts (currently with
    50   /// the \ref Preflow algorithm), therefore the algorithm has
    51   /// \f$(O(n^3\sqrt{e})\f$ overall time complexity. It calculates a
    52   /// rooted Gomory-Hu tree, its structure and the weights can be obtained
    53   /// by \c predNode(), \c predValue() and \c rootDist().
    54   ///
    55   /// The members \c minCutMap() and \c minCutValue() calculate
     49  /// the \ref Preflow algorithm), thus it has \f$O(n^3\sqrt{e})\f$ overall
     50  /// time complexity. It calculates a rooted Gomory-Hu tree.
     51  /// The structure of the tree and the edge weights can be
     52  /// obtained using \c predNode(), \c predValue() and \c rootDist().
     53  /// The functions \c minCutMap() and \c minCutValue() calculate
    5654  /// the minimum cut and the minimum cut value between any two nodes
    5755  /// in the graph. You can also list (iterate on) the nodes and the
     
    5957  ///
    6058  /// \tparam GR The type of the undirected graph the algorithm runs on.
    61   /// \tparam CAP The type of the edge map describing the edge capacities.
    62   /// It is \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>" by default.
     59  /// \tparam CAP The type of the edge map containing the capacities.
     60  /// The default map type is \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
    6361#ifdef DOXYGEN
    6462  template <typename GR,
     
    7169  public:
    7270
    73     /// The graph type
     71    /// The graph type of the algorithm
    7472    typedef GR Graph;
    75     /// The type of the edge capacity map
     73    /// The capacity map type of the algorithm
    7674    typedef CAP Capacity;
    7775    /// The value type of capacities
     
    118116    /// \brief Constructor
    119117    ///
    120     /// Constructor
     118    /// Constructor.
    121119    /// \param graph The undirected graph the algorithm runs on.
    122120    /// \param capacity The edge capacity map.
     
    131129    /// \brief Destructor
    132130    ///
    133     /// Destructor
     131    /// Destructor.
    134132    ~GomoryHu() {
    135133      destroyStructures();
     
    216214    ///The results of the algorithm can be obtained using these
    217215    ///functions.\n
    218     ///\ref run() "run()" should be called before using them.\n
     216    ///\ref run() should be called before using them.\n
    219217    ///See also \ref MinCutNodeIt and \ref MinCutEdgeIt.
    220218
     
    223221    /// \brief Return the predecessor node in the Gomory-Hu tree.
    224222    ///
    225     /// This function returns the predecessor node in the Gomory-Hu tree.
    226     /// If the node is
    227     /// the root of the Gomory-Hu tree, then it returns \c INVALID.
    228     Node predNode(const Node& node) {
     223    /// This function returns the predecessor node of the given node
     224    /// in the Gomory-Hu tree.
     225    /// If \c node is the root of the tree, then it returns \c INVALID.
     226    ///
     227    /// \pre \ref run() must be called before using this function.
     228    Node predNode(const Node& node) const {
    229229      return (*_pred)[node];
    230     }
    231 
    232     /// \brief Return the distance from the root node in the Gomory-Hu tree.
    233     ///
    234     /// This function returns the distance of \c node from the root node
    235     /// in the Gomory-Hu tree.
    236     int rootDist(const Node& node) {
    237       return (*_order)[node];
    238230    }
    239231
     
    241233    /// Gomory-Hu tree.
    242234    ///
    243     /// This function returns the weight of the predecessor edge in the
    244     /// Gomory-Hu tree.  If the node is the root, the result is undefined.
    245     Value predValue(const Node& node) {
     235    /// This function returns the weight of the predecessor edge of the
     236    /// given node in the Gomory-Hu tree.
     237    /// If \c node is the root of the tree, the result is undefined.
     238    ///
     239    /// \pre \ref run() must be called before using this function.
     240    Value predValue(const Node& node) const {
    246241      return (*_weight)[node];
    247242    }
    248243
     244    /// \brief Return the distance from the root node in the Gomory-Hu tree.
     245    ///
     246    /// This function returns the distance of the given node from the root
     247    /// node in the Gomory-Hu tree.
     248    ///
     249    /// \pre \ref run() must be called before using this function.
     250    int rootDist(const Node& node) const {
     251      return (*_order)[node];
     252    }
     253
    249254    /// \brief Return the minimum cut value between two nodes
    250255    ///
    251     /// This function returns the minimum cut value between two nodes. The
    252     /// algorithm finds the nearest common ancestor in the Gomory-Hu
    253     /// tree and calculates the minimum weight edge on the paths to
    254     /// the ancestor.
     256    /// This function returns the minimum cut value between the nodes
     257    /// \c s and \c t.
     258    /// It finds the nearest common ancestor of the given nodes in the
     259    /// Gomory-Hu tree and calculates the minimum weight edge on the
     260    /// paths to the ancestor.
     261    ///
     262    /// \pre \ref run() must be called before using this function.
    255263    Value minCutValue(const Node& s, const Node& t) const {
    256264      Node sn = s, tn = t;
     
    275283    /// \c s to \c true and the other nodes to \c false.
    276284    ///
    277     /// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt.
     285    /// For higher level interfaces see MinCutNodeIt and MinCutEdgeIt.
     286    ///
     287    /// \param s The base node.
     288    /// \param t The node you want to separate from node \c s.
     289    /// \param cutMap The cut will be returned in this map.
     290    /// It must be a \c bool (or convertible) \ref concepts::ReadWriteMap
     291    /// "ReadWriteMap" on the graph nodes.
     292    ///
     293    /// \return The value of the minimum cut between \c s and \c t.
     294    ///
     295    /// \pre \ref run() must be called before using this function.
    278296    template <typename CutMap>
    279     Value minCutMap(const Node& s, ///< The base node.
     297    Value minCutMap(const Node& s, ///<
    280298                    const Node& t,
    281                     ///< The node you want to separate from node \c s.
     299                    ///<
    282300                    CutMap& cutMap
    283                     ///< The cut will be returned in this map.
    284                     /// It must be a \c bool (or convertible)
    285                     /// \ref concepts::ReadWriteMap "ReadWriteMap"
    286                     /// on the graph nodes.
     301                    ///<
    287302                    ) const {
    288303      Node sn = s, tn = t;
     
    339354   
    340355    /// This iterator class lists the nodes of a minimum cut found by
    341     /// GomoryHu. Before using it, you must allocate a GomoryHu class,
     356    /// GomoryHu. Before using it, you must allocate a GomoryHu class
    342357    /// and call its \ref GomoryHu::run() "run()" method.
    343358    ///
     
    436451   
    437452    /// This iterator class lists the edges of a minimum cut found by
    438     /// GomoryHu. Before using it, you must allocate a GomoryHu class,
     453    /// GomoryHu. Before using it, you must allocate a GomoryHu class
    439454    /// and call its \ref GomoryHu::run() "run()" method.
    440455    ///
     
    448463    ///   value+=capacities[e];
    449464    /// \endcode
    450     /// the result will be the same as it is returned by
    451     /// \ref GomoryHu::minCutValue() "gom.minCutValue(s,t)"
     465    /// The result will be the same as the value returned by
     466    /// \ref GomoryHu::minCutValue() "gom.minCutValue(s,t)".
    452467    class MinCutEdgeIt
    453468    {
     
    469484     
    470485    public:
     486      /// Constructor
     487
     488      /// Constructor.
     489      ///
    471490      MinCutEdgeIt(GomoryHu const &gomory,
    472491                   ///< The GomoryHu class. You must call its
     
    479498                   ///< If it is \c true (default) then the listed arcs
    480499                   ///  will be oriented from the
    481                    ///  the nodes of the component containing \c s,
     500                   ///  nodes of the component containing \c s,
    482501                   ///  otherwise they will be oriented in the opposite
    483502                   ///  direction.
  • lemon/hao_orlin.h

    r581 r597  
    3232/// \brief Implementation of the Hao-Orlin algorithm.
    3333///
    34 /// Implementation of the Hao-Orlin algorithm class for testing network
    35 /// reliability.
     34/// Implementation of the Hao-Orlin algorithm for finding a minimum cut
     35/// in a digraph.
    3636
    3737namespace lemon {
     
    3939  /// \ingroup min_cut
    4040  ///
    41   /// \brief %Hao-Orlin algorithm to find a minimum cut in directed graphs.
     41  /// \brief Hao-Orlin algorithm for finding a minimum cut in a digraph.
    4242  ///
    43   /// Hao-Orlin calculates a minimum cut in a directed graph
    44   /// \f$D=(V,A)\f$. It takes a fixed node \f$ source \in V \f$ and
     43  /// This class implements the Hao-Orlin algorithm for finding a minimum
     44  /// value cut in a directed graph \f$D=(V,A)\f$.
     45  /// It takes a fixed node \f$ source \in V \f$ and
    4546  /// consists of two phases: in the first phase it determines a
    4647  /// minimum cut with \f$ source \f$ on the source-side (i.e. a set
    47   /// \f$ X\subsetneq V \f$ with \f$ source \in X \f$ and minimal
    48   /// out-degree) and in the second phase it determines a minimum cut
     48  /// \f$ X\subsetneq V \f$ with \f$ source \in X \f$ and minimal outgoing
     49  /// capacity) and in the second phase it determines a minimum cut
    4950  /// with \f$ source \f$ on the sink-side (i.e. a set
    50   /// \f$ X\subsetneq V \f$ with \f$ source \notin X \f$ and minimal
    51   /// out-degree). Obviously, the smaller of these two cuts will be a
     51  /// \f$ X\subsetneq V \f$ with \f$ source \notin X \f$ and minimal outgoing
     52  /// capacity). Obviously, the smaller of these two cuts will be a
    5253  /// minimum cut of \f$ D \f$. The algorithm is a modified
    53   /// push-relabel preflow algorithm and our implementation calculates
     54  /// preflow push-relabel algorithm. Our implementation calculates
    5455  /// the minimum cut in \f$ O(n^2\sqrt{m}) \f$ time (we use the
    5556  /// highest-label rule), or in \f$O(nm)\f$ for unit capacities. The
    56   /// purpose of such algorithm is testing network reliability. For an
    57   /// undirected graph you can run just the first phase of the
    58   /// algorithm or you can use the algorithm of Nagamochi and Ibaraki
    59   /// which solves the undirected problem in
    60   /// \f$ O(nm + n^2 \log n) \f$ time: it is implemented in the
    61   /// NagamochiIbaraki algorithm class.
     57  /// purpose of such algorithm is e.g. testing network reliability.
    6258  ///
    63   /// \param GR The digraph class the algorithm runs on.
    64   /// \param CAP An arc map of capacities which can be any numreric type.
    65   /// The default type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
    66   /// \param TOL Tolerance class for handling inexact computations. The
     59  /// For an undirected graph you can run just the first phase of the
     60  /// algorithm or you can use the algorithm of Nagamochi and Ibaraki,
     61  /// which solves the undirected problem in \f$ O(nm + n^2 \log n) \f$
     62  /// time. It is implemented in the NagamochiIbaraki algorithm class.
     63  ///
     64  /// \tparam GR The type of the digraph the algorithm runs on.
     65  /// \tparam CAP The type of the arc map containing the capacities,
     66  /// which can be any numreric type. The default map type is
     67  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
     68  /// \tparam TOL Tolerance class for handling inexact computations. The
    6769  /// default tolerance type is \ref Tolerance "Tolerance<CAP::Value>".
    6870#ifdef DOXYGEN
     
    7476#endif
    7577  class HaoOrlin {
     78  public:
     79   
     80    /// The digraph type of the algorithm
     81    typedef GR Digraph;
     82    /// The capacity map type of the algorithm
     83    typedef CAP CapacityMap;
     84    /// The tolerance type of the algorithm
     85    typedef TOL Tolerance;
     86
    7687  private:
    7788
    78     typedef GR Digraph;
    79     typedef CAP CapacityMap;
    80     typedef TOL Tolerance;
    81 
    8289    typedef typename CapacityMap::Value Value;
    8390
    84     TEMPLATE_GRAPH_TYPEDEFS(Digraph);
     91    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    8592
    8693    const Digraph& _graph;
     
    220227      for (NodeIt n(_graph); n != INVALID; ++n) {
    221228        (*_excess)[n] = 0;
     229        (*_source_set)[n] = false;
    222230      }
    223231
     
    519527      for (NodeIt n(_graph); n != INVALID; ++n) {
    520528        (*_excess)[n] = 0;
     529        (*_source_set)[n] = false;
    521530      }
    522531
     
    816825  public:
    817826
    818     /// \name Execution control
     827    /// \name Execution Control
    819828    /// The simplest way to execute the algorithm is to use
    820829    /// one of the member functions called \ref run().
    821830    /// \n
    822     /// If you need more control on the execution,
    823     /// first you must call \ref init(), then the \ref calculateIn() or
    824     /// \ref calculateOut() functions.
     831    /// If you need better control on the execution,
     832    /// you have to call one of the \ref init() functions first, then
     833    /// \ref calculateOut() and/or \ref calculateIn().
    825834
    826835    /// @{
    827836
    828     /// \brief Initializes the internal data structures.
    829     ///
    830     /// Initializes the internal data structures. It creates
    831     /// the maps, residual graph adaptors and some bucket structures
    832     /// for the algorithm.
     837    /// \brief Initialize the internal data structures.
     838    ///
     839    /// This function initializes the internal data structures. It creates
     840    /// the maps and some bucket structures for the algorithm.
     841    /// The first node is used as the source node for the push-relabel
     842    /// algorithm.
    833843    void init() {
    834844      init(NodeIt(_graph));
    835845    }
    836846
    837     /// \brief Initializes the internal data structures.
    838     ///
    839     /// Initializes the internal data structures. It creates
    840     /// the maps, residual graph adaptor and some bucket structures
    841     /// for the algorithm. Node \c source  is used as the push-relabel
    842     /// algorithm's source.
     847    /// \brief Initialize the internal data structures.
     848    ///
     849    /// This function initializes the internal data structures. It creates
     850    /// the maps and some bucket structures for the algorithm.
     851    /// The given node is used as the source node for the push-relabel
     852    /// algorithm.
    843853    void init(const Node& source) {
    844854      _source = source;
     
    880890
    881891
    882     /// \brief Calculates a minimum cut with \f$ source \f$ on the
     892    /// \brief Calculate a minimum cut with \f$ source \f$ on the
    883893    /// source-side.
    884894    ///
    885     /// Calculates a minimum cut with \f$ source \f$ on the
     895    /// This function calculates a minimum cut with \f$ source \f$ on the
    886896    /// source-side (i.e. a set \f$ X\subsetneq V \f$ with
    887     /// \f$ source \in X \f$ and minimal out-degree).
     897    /// \f$ source \in X \f$ and minimal outgoing capacity).
     898    ///
     899    /// \pre \ref init() must be called before using this function.
    888900    void calculateOut() {
    889901      findMinCutOut();
    890902    }
    891903
    892     /// \brief Calculates a minimum cut with \f$ source \f$ on the
    893     /// target-side.
    894     ///
    895     /// Calculates a minimum cut with \f$ source \f$ on the
    896     /// target-side (i.e. a set \f$ X\subsetneq V \f$ with
    897     /// \f$ source \in X \f$ and minimal out-degree).
     904    /// \brief Calculate a minimum cut with \f$ source \f$ on the
     905    /// sink-side.
     906    ///
     907    /// This function calculates a minimum cut with \f$ source \f$ on the
     908    /// sink-side (i.e. a set \f$ X\subsetneq V \f$ with
     909    /// \f$ source \notin X \f$ and minimal outgoing capacity).
     910    ///
     911    /// \pre \ref init() must be called before using this function.
    898912    void calculateIn() {
    899913      findMinCutIn();
     
    901915
    902916
    903     /// \brief Runs the algorithm.
    904     ///
    905     /// Runs the algorithm. It finds nodes \c source and \c target
    906     /// arbitrarily and then calls \ref init(), \ref calculateOut()
     917    /// \brief Run the algorithm.
     918    ///
     919    /// This function runs the algorithm. It finds nodes \c source and
     920    /// \c target arbitrarily and then calls \ref init(), \ref calculateOut()
    907921    /// and \ref calculateIn().
    908922    void run() {
     
    912926    }
    913927
    914     /// \brief Runs the algorithm.
    915     ///
    916     /// Runs the algorithm. It uses the given \c source node, finds a
    917     /// proper \c target and then calls the \ref init(), \ref
    918     /// calculateOut() and \ref calculateIn().
     928    /// \brief Run the algorithm.
     929    ///
     930    /// This function runs the algorithm. It uses the given \c source node,
     931    /// finds a proper \c target node and then calls the \ref init(),
     932    /// \ref calculateOut() and \ref calculateIn().
    919933    void run(const Node& s) {
    920934      init(s);
     
    927941    /// \name Query Functions
    928942    /// The result of the %HaoOrlin algorithm
    929     /// can be obtained using these functions.
    930     /// \n
    931     /// Before using these functions, either \ref run(), \ref
    932     /// calculateOut() or \ref calculateIn() must be called.
     943    /// can be obtained using these functions.\n
     944    /// \ref run(), \ref calculateOut() or \ref calculateIn()
     945    /// should be called before using them.
    933946
    934947    /// @{
    935948
    936     /// \brief Returns the value of the minimum value cut.
    937     ///
    938     /// Returns the value of the minimum value cut.
     949    /// \brief Return the value of the minimum cut.
     950    ///
     951    /// This function returns the value of the minimum cut.
     952    ///
     953    /// \pre \ref run(), \ref calculateOut() or \ref calculateIn()
     954    /// must be called before using this function.
    939955    Value minCutValue() const {
    940956      return _min_cut;
     
    942958
    943959
    944     /// \brief Returns a minimum cut.
    945     ///
    946     /// Sets \c nodeMap to the characteristic vector of a minimum
    947     /// value cut: it will give a nonempty set \f$ X\subsetneq V \f$
    948     /// with minimal out-degree (i.e. \c nodeMap will be true exactly
    949     /// for the nodes of \f$ X \f$).  \pre nodeMap should be a
    950     /// bool-valued node-map.
    951     template <typename NodeMap>
    952     Value minCutMap(NodeMap& nodeMap) const {
     960    /// \brief Return a minimum cut.
     961    ///
     962    /// This function sets \c cutMap to the characteristic vector of a
     963    /// minimum value cut: it will give a non-empty set \f$ X\subsetneq V \f$
     964    /// with minimal outgoing capacity (i.e. \c cutMap will be \c true exactly
     965    /// for the nodes of \f$ X \f$).
     966    ///
     967    /// \param cutMap A \ref concepts::WriteMap "writable" node map with
     968    /// \c bool (or convertible) value type.
     969    ///
     970    /// \return The value of the minimum cut.
     971    ///
     972    /// \pre \ref run(), \ref calculateOut() or \ref calculateIn()
     973    /// must be called before using this function.
     974    template <typename CutMap>
     975    Value minCutMap(CutMap& cutMap) const {
    953976      for (NodeIt it(_graph); it != INVALID; ++it) {
    954         nodeMap.set(it, (*_min_cut_map)[it]);
     977        cutMap.set(it, (*_min_cut_map)[it]);
    955978      }
    956979      return _min_cut;
     
    961984  }; //class HaoOrlin
    962985
    963 
    964986} //namespace lemon
    965987
  • lemon/lgf_reader.h

    r584 r599  
    102102    };
    103103
    104     template <typename _Graph, bool _dir, typename _Map,
     104    template <typename _GR, bool _dir, typename _Map,
    105105              typename _Converter = DefaultConverter<typename _Map::Value> >
    106     class GraphArcMapStorage : public MapStorageBase<typename _Graph::Edge> {
     106    class GraphArcMapStorage : public MapStorageBase<typename _GR::Edge> {
    107107    public:
    108108      typedef _Map Map;
    109109      typedef _Converter Converter;
    110       typedef _Graph Graph;
    111       typedef typename Graph::Edge Item;
     110      typedef _GR GR;
     111      typedef typename GR::Edge Item;
    112112      static const bool dir = _dir;
    113113
    114114    private:
    115       const Graph& _graph;
     115      const GR& _graph;
    116116      Map& _map;
    117117      Converter _converter;
    118118
    119119    public:
    120       GraphArcMapStorage(const Graph& graph, Map& map,
     120      GraphArcMapStorage(const GR& graph, Map& map,
    121121                         const Converter& converter = Converter())
    122122        : _graph(graph), _map(map), _converter(converter) {}
     
    174174    };
    175175
    176     template <typename Graph>
     176    template <typename GR>
    177177    struct GraphArcLookUpConverter {
    178       const Graph& _graph;
    179       const std::map<std::string, typename Graph::Edge>& _map;
    180 
    181       GraphArcLookUpConverter(const Graph& graph,
     178      const GR& _graph;
     179      const std::map<std::string, typename GR::Edge>& _map;
     180
     181      GraphArcLookUpConverter(const GR& graph,
    182182                              const std::map<std::string,
    183                                              typename Graph::Edge>& map)
     183                                             typename GR::Edge>& map)
    184184        : _graph(graph), _map(map) {}
    185185
    186       typename Graph::Arc operator()(const std::string& str) {
     186      typename GR::Arc operator()(const std::string& str) {
    187187        if (str.empty() || (str[0] != '+' && str[0] != '-')) {
    188188          throw FormatError("Item must start with '+' or '-'");
    189189        }
    190         typename std::map<std::string, typename Graph::Edge>
     190        typename std::map<std::string, typename GR::Edge>
    191191          ::const_iterator it = _map.find(str.substr(1));
    192192        if (it == _map.end()) {
     
    388388  }
    389389
    390   template <typename Digraph>
     390  template <typename DGR>
    391391  class DigraphReader;
    392392
    393   template <typename Digraph>
    394   DigraphReader<Digraph> digraphReader(Digraph& digraph,
    395                                        std::istream& is = std::cin);
    396   template <typename Digraph>
    397   DigraphReader<Digraph> digraphReader(Digraph& digraph, const std::string& fn);
    398   template <typename Digraph>
    399   DigraphReader<Digraph> digraphReader(Digraph& digraph, const char *fn);
     393  template <typename TDGR>
     394  DigraphReader<TDGR> digraphReader(TDGR& digraph, std::istream& is = std::cin);
     395  template <typename TDGR>
     396  DigraphReader<TDGR> digraphReader(TDGR& digraph, const std::string& fn);
     397  template <typename TDGR>
     398  DigraphReader<TDGR> digraphReader(TDGR& digraph, const char *fn);
    400399
    401400  /// \ingroup lemon_io
     
    420419  ///
    421420  ///\code
    422   /// DigraphReader<Digraph>(digraph, std::cin).
     421  /// DigraphReader<DGR>(digraph, std::cin).
    423422  ///   nodeMap("coordinates", coord_map).
    424423  ///   arcMap("capacity", cap_map).
     
    449448  /// a single pass, because the arcs are not constructed when the node
    450449  /// maps are read.
    451   template <typename GR>
     450  template <typename DGR>
    452451  class DigraphReader {
    453452  public:
    454453
    455     typedef GR Digraph;
     454    typedef DGR Digraph;
    456455
    457456  private:
    458457
    459     TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
     458    TEMPLATE_DIGRAPH_TYPEDEFS(DGR);
    460459
    461460    std::istream* _is;
     
    463462    std::string _filename;
    464463
    465     Digraph& _digraph;
     464    DGR& _digraph;
    466465
    467466    std::string _nodes_caption;
     
    501500    /// Construct a directed graph reader, which reads from the given
    502501    /// input stream.
    503     DigraphReader(Digraph& digraph, std::istream& is = std::cin)
     502    DigraphReader(DGR& digraph, std::istream& is = std::cin)
    504503      : _is(&is), local_is(false), _digraph(digraph),
    505504        _use_nodes(false), _use_arcs(false),
     
    510509    /// Construct a directed graph reader, which reads from the given
    511510    /// file.
    512     DigraphReader(Digraph& digraph, const std::string& fn)
     511    DigraphReader(DGR& digraph, const std::string& fn)
    513512      : _is(new std::ifstream(fn.c_str())), local_is(true),
    514513        _filename(fn), _digraph(digraph),
     
    525524    /// Construct a directed graph reader, which reads from the given
    526525    /// file.
    527     DigraphReader(Digraph& digraph, const char* fn)
     526    DigraphReader(DGR& digraph, const char* fn)
    528527      : _is(new std::ifstream(fn)), local_is(true),
    529528        _filename(fn), _digraph(digraph),
     
    561560  private:
    562561
    563     template <typename DGR>
    564     friend DigraphReader<DGR> digraphReader(DGR& digraph, std::istream& is);
    565     template <typename DGR>
    566     friend DigraphReader<DGR> digraphReader(DGR& digraph,
    567                                             const std::string& fn);
    568     template <typename DGR>
    569     friend DigraphReader<DGR> digraphReader(DGR& digraph, const char *fn);
     562    template <typename TDGR>
     563    friend DigraphReader<TDGR> digraphReader(TDGR& digraph, std::istream& is);
     564    template <typename TDGR>
     565    friend DigraphReader<TDGR> digraphReader(TDGR& digraph,
     566                                             const std::string& fn);
     567    template <typename TDGR>
     568    friend DigraphReader<TDGR> digraphReader(TDGR& digraph, const char *fn);
    570569
    571570    DigraphReader(DigraphReader& other)
     
    11891188
    11901189  };
     1190 
     1191  /// \ingroup lemon_io
     1192  ///
     1193  /// \brief Return a \ref DigraphReader class
     1194  ///
     1195  /// This function just returns a \ref DigraphReader class.
     1196  ///
     1197  /// With this function a digraph can be read from an
     1198  /// \ref lgf-format "LGF" file or input stream with several maps and
     1199  /// attributes. For example, there is network flow problem on a
     1200  /// digraph, i.e. a digraph with a \e capacity map on the arcs and
     1201  /// \e source and \e target nodes. This digraph can be read with the
     1202  /// following code:
     1203  ///
     1204  ///\code
     1205  ///ListDigraph digraph;
     1206  ///ListDigraph::ArcMap<int> cm(digraph);
     1207  ///ListDigraph::Node src, trg;
     1208  ///digraphReader(digraph, std::cin).
     1209  ///  arcMap("capacity", cap).
     1210  ///  node("source", src).
     1211  ///  node("target", trg).
     1212  ///  run();
     1213  ///\endcode
     1214  ///
     1215  /// For a complete documentation, please see the \ref DigraphReader
     1216  /// class documentation.
     1217  /// \warning Don't forget to put the \ref DigraphReader::run() "run()"
     1218  /// to the end of the parameter list.
     1219  /// \relates DigraphReader
     1220  /// \sa digraphReader(TDGR& digraph, const std::string& fn)
     1221  /// \sa digraphReader(TDGR& digraph, const char* fn)
     1222  template <typename TDGR>
     1223  DigraphReader<TDGR> digraphReader(TDGR& digraph, std::istream& is) {
     1224    DigraphReader<TDGR> tmp(digraph, is);
     1225    return tmp;
     1226  }
    11911227
    11921228  /// \brief Return a \ref DigraphReader class
     
    11941230  /// This function just returns a \ref DigraphReader class.
    11951231  /// \relates DigraphReader
    1196   template <typename Digraph>
    1197   DigraphReader<Digraph> digraphReader(Digraph& digraph, std::istream& is) {
    1198     DigraphReader<Digraph> tmp(digraph, is);
     1232  /// \sa digraphReader(TDGR& digraph, std::istream& is)
     1233  template <typename TDGR>
     1234  DigraphReader<TDGR> digraphReader(TDGR& digraph, const std::string& fn) {
     1235    DigraphReader<TDGR> tmp(digraph, fn);
    11991236    return tmp;
    12001237  }
     
    12041241  /// This function just returns a \ref DigraphReader class.
    12051242  /// \relates DigraphReader
    1206   template <typename Digraph>
    1207   DigraphReader<Digraph> digraphReader(Digraph& digraph,
    1208                                        const std::string& fn) {
    1209     DigraphReader<Digraph> tmp(digraph, fn);
     1243  /// \sa digraphReader(TDGR& digraph, std::istream& is)
     1244  template <typename TDGR>
     1245  DigraphReader<TDGR> digraphReader(TDGR& digraph, const char* fn) {
     1246    DigraphReader<TDGR> tmp(digraph, fn);
    12101247    return tmp;
    12111248  }
    12121249
    1213   /// \brief Return a \ref DigraphReader class
    1214   ///
    1215   /// This function just returns a \ref DigraphReader class.
    1216   /// \relates DigraphReader
    1217   template <typename Digraph>
    1218   DigraphReader<Digraph> digraphReader(Digraph& digraph, const char* fn) {
    1219     DigraphReader<Digraph> tmp(digraph, fn);
    1220     return tmp;
    1221   }
    1222 
    1223   template <typename Graph>
     1250  template <typename GR>
    12241251  class GraphReader;
    12251252 
    1226   template <typename Graph>
    1227   GraphReader<Graph> graphReader(Graph& graph,
    1228                                  std::istream& is = std::cin);
    1229   template <typename Graph>
    1230   GraphReader<Graph> graphReader(Graph& graph, const std::string& fn);
    1231   template <typename Graph>
    1232   GraphReader<Graph> graphReader(Graph& graph, const char *fn);
     1253  template <typename TGR>
     1254  GraphReader<TGR> graphReader(TGR& graph, std::istream& is = std::cin);
     1255  template <typename TGR>
     1256  GraphReader<TGR> graphReader(TGR& graph, const std::string& fn);
     1257  template <typename TGR>
     1258  GraphReader<TGR> graphReader(TGR& graph, const char *fn);
    12331259
    12341260  /// \ingroup lemon_io
     
    12551281  private:
    12561282
    1257     TEMPLATE_GRAPH_TYPEDEFS(Graph);
     1283    TEMPLATE_GRAPH_TYPEDEFS(GR);
    12581284
    12591285    std::istream* _is;
     
    12611287    std::string _filename;
    12621288
    1263     Graph& _graph;
     1289    GR& _graph;
    12641290
    12651291    std::string _nodes_caption;
     
    12991325    /// Construct an undirected graph reader, which reads from the given
    13001326    /// input stream.
    1301     GraphReader(Graph& graph, std::istream& is = std::cin)
     1327    GraphReader(GR& graph, std::istream& is = std::cin)
    13021328      : _is(&is), local_is(false), _graph(graph),
    13031329        _use_nodes(false), _use_edges(false),
     
    13081334    /// Construct an undirected graph reader, which reads from the given
    13091335    /// file.
    1310     GraphReader(Graph& graph, const std::string& fn)
     1336    GraphReader(GR& graph, const std::string& fn)
    13111337      : _is(new std::ifstream(fn.c_str())), local_is(true),
    13121338        _filename(fn), _graph(graph),
     
    13231349    /// Construct an undirected graph reader, which reads from the given
    13241350    /// file.
    1325     GraphReader(Graph& graph, const char* fn)
     1351    GraphReader(GR& graph, const char* fn)
    13261352      : _is(new std::ifstream(fn)), local_is(true),
    13271353        _filename(fn), _graph(graph),
     
    13581384
    13591385  private:
    1360     template <typename Graph>
    1361     friend GraphReader<Graph> graphReader(Graph& graph, std::istream& is);
    1362     template <typename Graph>
    1363     friend GraphReader<Graph> graphReader(Graph& graph, const std::string& fn);
    1364     template <typename Graph>
    1365     friend GraphReader<Graph> graphReader(Graph& graph, const char *fn);
     1386    template <typename TGR>
     1387    friend GraphReader<TGR> graphReader(TGR& graph, std::istream& is);
     1388    template <typename TGR>
     1389    friend GraphReader<TGR> graphReader(TGR& graph, const std::string& fn);
     1390    template <typename TGR>
     1391    friend GraphReader<TGR> graphReader(TGR& graph, const char *fn);
    13661392
    13671393    GraphReader(GraphReader& other)
     
    14551481      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
    14561482      _reader_bits::MapStorageBase<Edge>* backward_storage =
    1457         new _reader_bits::GraphArcMapStorage<Graph, false, Map>(_graph, map);
     1483        new _reader_bits::GraphArcMapStorage<GR, false, Map>(_graph, map);
    14581484      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
    14591485      return *this;
     
    14691495      checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
    14701496      _reader_bits::MapStorageBase<Edge>* forward_storage =
    1471         new _reader_bits::GraphArcMapStorage<Graph, true, Map, Converter>
     1497        new _reader_bits::GraphArcMapStorage<GR, true, Map, Converter>
    14721498        (_graph, map, converter);
    14731499      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
    14741500      _reader_bits::MapStorageBase<Edge>* backward_storage =
    1475         new _reader_bits::GraphArcMapStorage<Graph, false, Map, Converter>
     1501        new _reader_bits::GraphArcMapStorage<GR, false, Map, Converter>
    14761502        (_graph, map, converter);
    14771503      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
     
    15311557    /// Add an arc reading rule to reader.
    15321558    GraphReader& arc(const std::string& caption, Arc& arc) {
    1533       typedef _reader_bits::GraphArcLookUpConverter<Graph> Converter;
     1559      typedef _reader_bits::GraphArcLookUpConverter<GR> Converter;
    15341560      Converter converter(_graph, _edge_index);
    15351561      _reader_bits::ValueStorageBase* storage =
     
    20342060  };
    20352061
     2062  /// \ingroup lemon_io
     2063  ///
     2064  /// \brief Return a \ref GraphReader class
     2065  ///
     2066  /// This function just returns a \ref GraphReader class.
     2067  ///
     2068  /// With this function a graph can be read from an
     2069  /// \ref lgf-format "LGF" file or input stream with several maps and
     2070  /// attributes. For example, there is weighted matching problem on a
     2071  /// graph, i.e. a graph with a \e weight map on the edges. This
     2072  /// graph can be read with the following code:
     2073  ///
     2074  ///\code
     2075  ///ListGraph graph;
     2076  ///ListGraph::EdgeMap<int> weight(graph);
     2077  ///graphReader(graph, std::cin).
     2078  ///  edgeMap("weight", weight).
     2079  ///  run();
     2080  ///\endcode
     2081  ///
     2082  /// For a complete documentation, please see the \ref GraphReader
     2083  /// class documentation.
     2084  /// \warning Don't forget to put the \ref GraphReader::run() "run()"
     2085  /// to the end of the parameter list.
     2086  /// \relates GraphReader
     2087  /// \sa graphReader(TGR& graph, const std::string& fn)
     2088  /// \sa graphReader(TGR& graph, const char* fn)
     2089  template <typename TGR>
     2090  GraphReader<TGR> graphReader(TGR& graph, std::istream& is) {
     2091    GraphReader<TGR> tmp(graph, is);
     2092    return tmp;
     2093  }
     2094
    20362095  /// \brief Return a \ref GraphReader class
    20372096  ///
    20382097  /// This function just returns a \ref GraphReader class.
    20392098  /// \relates GraphReader
    2040   template <typename Graph>
    2041   GraphReader<Graph> graphReader(Graph& graph, std::istream& is) {
    2042     GraphReader<Graph> tmp(graph, is);
     2099  /// \sa graphReader(TGR& graph, std::istream& is)
     2100  template <typename TGR>
     2101  GraphReader<TGR> graphReader(TGR& graph, const std::string& fn) {
     2102    GraphReader<TGR> tmp(graph, fn);
    20432103    return tmp;
    20442104  }
     
    20482108  /// This function just returns a \ref GraphReader class.
    20492109  /// \relates GraphReader
    2050   template <typename Graph>
    2051   GraphReader<Graph> graphReader(Graph& graph, const std::string& fn) {
    2052     GraphReader<Graph> tmp(graph, fn);
    2053     return tmp;
    2054   }
    2055 
    2056   /// \brief Return a \ref GraphReader class
    2057   ///
    2058   /// This function just returns a \ref GraphReader class.
    2059   /// \relates GraphReader
    2060   template <typename Graph>
    2061   GraphReader<Graph> graphReader(Graph& graph, const char* fn) {
    2062     GraphReader<Graph> tmp(graph, fn);
     2110  /// \sa graphReader(TGR& graph, std::istream& is)
     2111  template <typename TGR>
     2112  GraphReader<TGR> graphReader(TGR& graph, const char* fn) {
     2113    GraphReader<TGR> tmp(graph, fn);
    20632114    return tmp;
    20642115  }
     
    23172368  };
    23182369
     2370  /// \ingroup lemon_io
     2371  ///
    23192372  /// \brief Return a \ref SectionReader class
    23202373  ///
    23212374  /// This function just returns a \ref SectionReader class.
     2375  ///
     2376  /// Please see SectionReader documentation about the custom section
     2377  /// input.
     2378  ///
    23222379  /// \relates SectionReader
     2380  /// \sa sectionReader(const std::string& fn)
     2381  /// \sa sectionReader(const char *fn)
    23232382  inline SectionReader sectionReader(std::istream& is) {
    23242383    SectionReader tmp(is);
     
    23302389  /// This function just returns a \ref SectionReader class.
    23312390  /// \relates SectionReader
     2391  /// \sa sectionReader(std::istream& is)
    23322392  inline SectionReader sectionReader(const std::string& fn) {
    23332393    SectionReader tmp(fn);
     
    23392399  /// This function just returns a \ref SectionReader class.
    23402400  /// \relates SectionReader
     2401  /// \sa sectionReader(std::istream& is)
    23412402  inline SectionReader sectionReader(const char* fn) {
    23422403    SectionReader tmp(fn);
  • lemon/lgf_writer.h

    r584 r599  
    348348  }
    349349
    350   template <typename Digraph>
     350  template <typename DGR>
    351351  class DigraphWriter;
    352352
    353   template <typename Digraph>
    354   DigraphWriter<Digraph> digraphWriter(const Digraph& digraph,
    355                                        std::ostream& os = std::cout);
    356   template <typename Digraph>
    357   DigraphWriter<Digraph> digraphWriter(const Digraph& digraph,
    358                                        const std::string& fn);
    359 
    360   template <typename Digraph>
    361   DigraphWriter<Digraph> digraphWriter(const Digraph& digraph,
    362                                        const char* fn);
     353  template <typename TDGR>
     354  DigraphWriter<TDGR> digraphWriter(const TDGR& digraph,
     355                                   std::ostream& os = std::cout);
     356  template <typename TDGR>
     357  DigraphWriter<TDGR> digraphWriter(const TDGR& digraph, const std::string& fn);
     358
     359  template <typename TDGR>
     360  DigraphWriter<TDGR> digraphWriter(const TDGR& digraph, const char* fn);
    363361
    364362
     
    382380  ///
    383381  ///\code
    384   /// DigraphWriter<Digraph>(digraph, std::cout).
     382  /// DigraphWriter<DGR>(digraph, std::cout).
    385383  ///   nodeMap("coordinates", coord_map).
    386384  ///   nodeMap("size", size).
     
    407405  /// the \c ostream() function, hence the second pass can append its
    408406  /// output to the output of the first pass.
    409   template <typename GR>
     407  template <typename DGR>
    410408  class DigraphWriter {
    411409  public:
    412410
    413     typedef GR Digraph;
    414     TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
     411    typedef DGR Digraph;
     412    TEMPLATE_DIGRAPH_TYPEDEFS(DGR);
    415413
    416414  private:
     
    420418    bool local_os;
    421419
    422     const Digraph& _digraph;
     420    const DGR& _digraph;
    423421
    424422    std::string _nodes_caption;
     
    452450    /// Construct a directed graph writer, which writes to the given
    453451    /// output stream.
    454     DigraphWriter(const Digraph& digraph, std::ostream& os = std::cout)
     452    DigraphWriter(const DGR& digraph, std::ostream& os = std::cout)
    455453      : _os(&os), local_os(false), _digraph(digraph),
    456454        _skip_nodes(false), _skip_arcs(false) {}
     
    460458    /// Construct a directed graph writer, which writes to the given
    461459    /// output file.
    462     DigraphWriter(const Digraph& digraph, const std::string& fn)
     460    DigraphWriter(const DGR& digraph, const std::string& fn)
    463461      : _os(new std::ofstream(fn.c_str())), local_os(true), _digraph(digraph),
    464462        _skip_nodes(false), _skip_arcs(false) {
     
    473471    /// Construct a directed graph writer, which writes to the given
    474472    /// output file.
    475     DigraphWriter(const Digraph& digraph, const char* fn)
     473    DigraphWriter(const DGR& digraph, const char* fn)
    476474      : _os(new std::ofstream(fn)), local_os(true), _digraph(digraph),
    477475        _skip_nodes(false), _skip_arcs(false) {
     
    506504  private:
    507505
    508     template <typename DGR>
    509     friend DigraphWriter<DGR> digraphWriter(const DGR& digraph,
    510                                             std::ostream& os);
    511     template <typename DGR>
    512     friend DigraphWriter<DGR> digraphWriter(const DGR& digraph,
    513                                             const std::string& fn);
    514     template <typename DGR>
    515     friend DigraphWriter<DGR> digraphWriter(const DGR& digraph,
    516                                             const char *fn);
     506    template <typename TDGR>
     507    friend DigraphWriter<TDGR> digraphWriter(const TDGR& digraph,
     508                                             std::ostream& os);
     509    template <typename TDGR>
     510    friend DigraphWriter<TDGR> digraphWriter(const TDGR& digraph,
     511                                             const std::string& fn);
     512    template <typename TDGR>
     513    friend DigraphWriter<TDGR> digraphWriter(const TDGR& digraph,
     514                                             const char *fn);
    517515
    518516    DigraphWriter(DigraphWriter& other)
     
    725723
    726724      if (label == 0) {
    727         IdMap<Digraph, Node> id_map(_digraph);
    728         _writer_bits::MapLess<IdMap<Digraph, Node> > id_less(id_map);
     725        IdMap<DGR, Node> id_map(_digraph);
     726        _writer_bits::MapLess<IdMap<DGR, Node> > id_less(id_map);
    729727        std::sort(nodes.begin(), nodes.end(), id_less);
    730728      } else {
     
    810808
    811809      if (label == 0) {
    812         IdMap<Digraph, Arc> id_map(_digraph);
    813         _writer_bits::MapLess<IdMap<Digraph, Arc> > id_less(id_map);
     810        IdMap<DGR, Arc> id_map(_digraph);
     811        _writer_bits::MapLess<IdMap<DGR, Arc> > id_less(id_map);
    814812        std::sort(arcs.begin(), arcs.end(), id_less);
    815813      } else {
     
    916914  };
    917915
     916  /// \ingroup lemon_io
     917  ///
     918  /// \brief Return a \ref DigraphWriter class
     919  ///
     920  /// This function just returns a \ref DigraphWriter class.
     921  ///
     922  /// With this function a digraph can be write to a file or output
     923  /// stream in \ref lgf-format "LGF" format with several maps and
     924  /// attributes. For example, with the following code a network flow
     925  /// problem can be written to the standard output, i.e. a digraph
     926  /// with a \e capacity map on the arcs and \e source and \e target
     927  /// nodes:
     928  ///
     929  ///\code
     930  ///ListDigraph digraph;
     931  ///ListDigraph::ArcMap<int> cap(digraph);
     932  ///ListDigraph::Node src, trg;
     933  ///  // Setting the capacity map and source and target nodes
     934  ///digraphWriter(digraph, std::cout).
     935  ///  arcMap("capacity", cap).
     936  ///  node("source", src).
     937  ///  node("target", trg).
     938  ///  run();
     939  ///\endcode
     940  ///
     941  /// For a complete documentation, please see the \ref DigraphWriter
     942  /// class documentation.
     943  /// \warning Don't forget to put the \ref DigraphWriter::run() "run()"
     944  /// to the end of the parameter list.
     945  /// \relates DigraphWriter
     946  /// \sa digraphWriter(const TDGR& digraph, const std::string& fn)
     947  /// \sa digraphWriter(const TDGR& digraph, const char* fn)
     948  template <typename TDGR>
     949  DigraphWriter<TDGR> digraphWriter(const TDGR& digraph, std::ostream& os) {
     950    DigraphWriter<TDGR> tmp(digraph, os);
     951    return tmp;
     952  }
     953
    918954  /// \brief Return a \ref DigraphWriter class
    919955  ///
    920956  /// This function just returns a \ref DigraphWriter class.
    921957  /// \relates DigraphWriter
    922   template <typename Digraph>
    923   DigraphWriter<Digraph> digraphWriter(const Digraph& digraph,
    924                                        std::ostream& os) {
    925     DigraphWriter<Digraph> tmp(digraph, os);
     958  /// \sa digraphWriter(const TDGR& digraph, std::ostream& os)
     959  template <typename TDGR>
     960  DigraphWriter<TDGR> digraphWriter(const TDGR& digraph,
     961                                    const std::string& fn) {
     962    DigraphWriter<TDGR> tmp(digraph, fn);
    926963    return tmp;
    927964  }
     
    931968  /// This function just returns a \ref DigraphWriter class.
    932969  /// \relates DigraphWriter
    933   template <typename Digraph>
    934   DigraphWriter<Digraph> digraphWriter(const Digraph& digraph,
    935                                        const std::string& fn) {
    936     DigraphWriter<Digraph> tmp(digraph, fn);
     970  /// \sa digraphWriter(const TDGR& digraph, std::ostream& os)
     971  template <typename TDGR>
     972  DigraphWriter<TDGR> digraphWriter(const TDGR& digraph, const char* fn) {
     973    DigraphWriter<TDGR> tmp(digraph, fn);
    937974    return tmp;
    938975  }
    939976
    940   /// \brief Return a \ref DigraphWriter class
    941   ///
    942   /// This function just returns a \ref DigraphWriter class.
    943   /// \relates DigraphWriter
    944   template <typename Digraph>
    945   DigraphWriter<Digraph> digraphWriter(const Digraph& digraph,
    946                                        const char* fn) {
    947     DigraphWriter<Digraph> tmp(digraph, fn);
    948     return tmp;
    949   }
    950 
    951   template <typename Graph>
     977  template <typename GR>
    952978  class GraphWriter;
    953979
    954   template <typename Graph>
    955   GraphWriter<Graph> graphWriter(const Graph& graph,
    956                                  std::ostream& os = std::cout);
    957   template <typename Graph>
    958   GraphWriter<Graph> graphWriter(const Graph& graph, const std::string& fn);
    959   template <typename Graph>
    960   GraphWriter<Graph> graphWriter(const Graph& graph, const char* fn);
     980  template <typename TGR>
     981  GraphWriter<TGR> graphWriter(const TGR& graph, std::ostream& os = std::cout);
     982  template <typename TGR>
     983  GraphWriter<TGR> graphWriter(const TGR& graph, const std::string& fn);
     984  template <typename TGR>
     985  GraphWriter<TGR> graphWriter(const TGR& graph, const char* fn);
    961986
    962987  /// \ingroup lemon_io
     
    9801005
    9811006    typedef GR Graph;
    982     TEMPLATE_GRAPH_TYPEDEFS(Graph);
     1007    TEMPLATE_GRAPH_TYPEDEFS(GR);
    9831008
    9841009  private:
     
    9881013    bool local_os;
    9891014
    990     const Graph& _graph;
     1015    const GR& _graph;
    9911016
    9921017    std::string _nodes_caption;
     
    10201045    /// Construct a directed graph writer, which writes to the given
    10211046    /// output stream.
    1022     GraphWriter(const Graph& graph, std::ostream& os = std::cout)
     1047    GraphWriter(const GR& graph, std::ostream& os = std::cout)
    10231048      : _os(&os), local_os(false), _graph(graph),
    10241049        _skip_nodes(false), _skip_edges(false) {}
     
    10281053    /// Construct a directed graph writer, which writes to the given
    10291054    /// output file.
    1030     GraphWriter(const Graph& graph, const std::string& fn)
     1055    GraphWriter(const GR& graph, const std::string& fn)
    10311056      : _os(new std::ofstream(fn.c_str())), local_os(true), _graph(graph),
    10321057        _skip_nodes(false), _skip_edges(false) {
     
    10411066    /// Construct a directed graph writer, which writes to the given
    10421067    /// output file.
    1043     GraphWriter(const Graph& graph, const char* fn)
     1068    GraphWriter(const GR& graph, const char* fn)
    10441069      : _os(new std::ofstream(fn)), local_os(true), _graph(graph),
    10451070        _skip_nodes(false), _skip_edges(false) {
     
    10741099  private:
    10751100
    1076     template <typename Graph>
    1077     friend GraphWriter<Graph> graphWriter(const Graph& graph,
    1078                                           std::ostream& os);
    1079     template <typename Graph>
    1080     friend GraphWriter<Graph> graphWriter(const Graph& graph,
    1081                                           const std::string& fn);
    1082     template <typename Graph>
    1083     friend GraphWriter<Graph> graphWriter(const Graph& graph,
    1084                                           const char *fn);
     1101    template <typename TGR>
     1102    friend GraphWriter<TGR> graphWriter(const TGR& graph, std::ostream& os);
     1103    template <typename TGR>
     1104    friend GraphWriter<TGR> graphWriter(const TGR& graph,
     1105                                        const std::string& fn);
     1106    template <typename TGR>
     1107    friend GraphWriter<TGR> graphWriter(const TGR& graph, const char *fn);
    10851108   
    10861109    GraphWriter(GraphWriter& other)
     
    11691192      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
    11701193      _writer_bits::MapStorageBase<Edge>* forward_storage =
    1171         new _writer_bits::GraphArcMapStorage<Graph, true, Map>(_graph, map);
     1194        new _writer_bits::GraphArcMapStorage<GR, true, Map>(_graph, map);
    11721195      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
    11731196      _writer_bits::MapStorageBase<Edge>* backward_storage =
    1174         new _writer_bits::GraphArcMapStorage<Graph, false, Map>(_graph, map);
     1197        new _writer_bits::GraphArcMapStorage<GR, false, Map>(_graph, map);
    11751198      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
    11761199      return *this;
     
    11861209      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
    11871210      _writer_bits::MapStorageBase<Edge>* forward_storage =
    1188         new _writer_bits::GraphArcMapStorage<Graph, true, Map, Converter>
     1211        new _writer_bits::GraphArcMapStorage<GR, true, Map, Converter>
    11891212        (_graph, map, converter);
    11901213      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
    11911214      _writer_bits::MapStorageBase<Edge>* backward_storage =
    1192         new _writer_bits::GraphArcMapStorage<Graph, false, Map, Converter>
     1215        new _writer_bits::GraphArcMapStorage<GR, false, Map, Converter>
    11931216        (_graph, map, converter);
    11941217      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
     
    12481271    /// Add an arc writing rule to writer.
    12491272    GraphWriter& arc(const std::string& caption, const Arc& arc) {
    1250       typedef _writer_bits::GraphArcLookUpConverter<Graph> Converter;
     1273      typedef _writer_bits::GraphArcLookUpConverter<GR> Converter;
    12511274      Converter converter(_graph, _edge_index);
    12521275      _writer_bits::ValueStorageBase* storage =
     
    13391362
    13401363      if (label == 0) {
    1341         IdMap<Graph, Node> id_map(_graph);
    1342         _writer_bits::MapLess<IdMap<Graph, Node> > id_less(id_map);
     1364        IdMap<GR, Node> id_map(_graph);
     1365        _writer_bits::MapLess<IdMap<GR, Node> > id_less(id_map);
    13431366        std::sort(nodes.begin(), nodes.end(), id_less);
    13441367      } else {
     
    14241447
    14251448      if (label == 0) {
    1426         IdMap<Graph, Edge> id_map(_graph);
    1427         _writer_bits::MapLess<IdMap<Graph, Edge> > id_less(id_map);
     1449        IdMap<GR, Edge> id_map(_graph);
     1450        _writer_bits::MapLess<IdMap<GR, Edge> > id_less(id_map);
    14281451        std::sort(edges.begin(), edges.end(), id_less);
    14291452      } else {
     
    15301553  };
    15311554
     1555  /// \ingroup lemon_io
     1556  ///
     1557  /// \brief Return a \ref GraphWriter class
     1558  ///
     1559  /// This function just returns a \ref GraphWriter class.
     1560  ///
     1561  /// With this function a graph can be write to a file or output
     1562  /// stream in \ref lgf-format "LGF" format with several maps and
     1563  /// attributes. For example, with the following code a weighted
     1564  /// matching problem can be written to the standard output, i.e. a
     1565  /// graph with a \e weight map on the edges:
     1566  ///
     1567  ///\code
     1568  ///ListGraph graph;
     1569  ///ListGraph::EdgeMap<int> weight(graph);
     1570  ///  // Setting the weight map
     1571  ///graphWriter(graph, std::cout).
     1572  ///  edgeMap("weight", weight).
     1573  ///  run();
     1574  ///\endcode
     1575  ///
     1576  /// For a complete documentation, please see the \ref GraphWriter
     1577  /// class documentation.
     1578  /// \warning Don't forget to put the \ref GraphWriter::run() "run()"
     1579  /// to the end of the parameter list.
     1580  /// \relates GraphWriter
     1581  /// \sa graphWriter(const TGR& graph, const std::string& fn)
     1582  /// \sa graphWriter(const TGR& graph, const char* fn)
     1583  template <typename TGR>
     1584  GraphWriter<TGR> graphWriter(const TGR& graph, std::ostream& os) {
     1585    GraphWriter<TGR> tmp(graph, os);
     1586    return tmp;
     1587  }
     1588
    15321589  /// \brief Return a \ref GraphWriter class
    15331590  ///
    15341591  /// This function just returns a \ref GraphWriter class.
    15351592  /// \relates GraphWriter
    1536   template <typename Graph>
    1537   GraphWriter<Graph> graphWriter(const Graph& graph,
    1538                                  std::ostream& os) {
    1539     GraphWriter<Graph> tmp(graph, os);
     1593  /// \sa graphWriter(const TGR& graph, std::ostream& os)
     1594  template <typename TGR>
     1595  GraphWriter<TGR> graphWriter(const TGR& graph, const std::string& fn) {
     1596    GraphWriter<TGR> tmp(graph, fn);
    15401597    return tmp;
    15411598  }
     
    15451602  /// This function just returns a \ref GraphWriter class.
    15461603  /// \relates GraphWriter
    1547   template <typename Graph>
    1548   GraphWriter<Graph> graphWriter(const Graph& graph, const std::string& fn) {
    1549     GraphWriter<Graph> tmp(graph, fn);
    1550     return tmp;
    1551   }
    1552 
    1553   /// \brief Return a \ref GraphWriter class
    1554   ///
    1555   /// This function just returns a \ref GraphWriter class.
    1556   /// \relates GraphWriter
    1557   template <typename Graph>
    1558   GraphWriter<Graph> graphWriter(const Graph& graph, const char* fn) {
    1559     GraphWriter<Graph> tmp(graph, fn);
     1604  /// \sa graphWriter(const TGR& graph, std::ostream& os)
     1605  template <typename TGR>
     1606  GraphWriter<TGR> graphWriter(const TGR& graph, const char* fn) {
     1607    GraphWriter<TGR> tmp(graph, fn);
    15601608    return tmp;
    15611609  }
     
    17471795  };
    17481796
     1797  /// \ingroup lemon_io
     1798  ///
    17491799  /// \brief Return a \ref SectionWriter class
    17501800  ///
    17511801  /// This function just returns a \ref SectionWriter class.
     1802  ///
     1803  /// Please see SectionWriter documentation about the custom section
     1804  /// output.
     1805  ///
    17521806  /// \relates SectionWriter
     1807  /// \sa sectionWriter(const std::string& fn)
     1808  /// \sa sectionWriter(const char *fn)
    17531809  inline SectionWriter sectionWriter(std::ostream& os) {
    17541810    SectionWriter tmp(os);
     
    17601816  /// This function just returns a \ref SectionWriter class.
    17611817  /// \relates SectionWriter
     1818  /// \sa sectionWriter(std::ostream& os)
    17621819  inline SectionWriter sectionWriter(const std::string& fn) {
    17631820    SectionWriter tmp(fn);
     
    17691826  /// This function just returns a \ref SectionWriter class.
    17701827  /// \relates SectionWriter
     1828  /// \sa sectionWriter(std::ostream& os)
    17711829  inline SectionWriter sectionWriter(const char* fn) {
    17721830    SectionWriter tmp(fn);
  • test/gomory_hu_test.cc

    r546 r596  
    33#include "test_tools.h"
    44#include <lemon/smart_graph.h>
     5#include <lemon/concepts/graph.h>
     6#include <lemon/concepts/maps.h>
    57#include <lemon/lgf_reader.h>
    68#include <lemon/gomory_hu.h>
     
    3335  "target 3\n";
    3436 
     37void checkGomoryHuCompile()
     38{
     39  typedef int Value;
     40  typedef concepts::Graph Graph;
     41
     42  typedef Graph::Node Node;
     43  typedef Graph::Edge Edge;
     44  typedef concepts::ReadMap<Edge, Value> CapMap;
     45  typedef concepts::ReadWriteMap<Node, bool> CutMap;
     46
     47  Graph g;
     48  Node n;
     49  CapMap cap;
     50  CutMap cut;
     51  Value v;
     52  int d;
     53
     54  GomoryHu<Graph, CapMap> gh_test(g, cap);
     55  const GomoryHu<Graph, CapMap>&
     56    const_gh_test = gh_test;
     57
     58  gh_test.run();
     59
     60  n = const_gh_test.predNode(n);
     61  v = const_gh_test.predValue(n);
     62  d = const_gh_test.rootDist(n);
     63  v = const_gh_test.minCutValue(n, n);
     64  v = const_gh_test.minCutMap(n, n, cut);
     65}
     66
    3567GRAPH_TYPEDEFS(Graph);
    3668typedef Graph::EdgeMap<int> IntEdgeMap;
     
    71103      ght.minCutMap(u, v, cm);
    72104      check(pf.flowValue() == ght.minCutValue(u, v), "Wrong cut 1");
    73       check(cm[u] != cm[v], "Wrong cut 3");
    74       check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 2");
     105      check(cm[u] != cm[v], "Wrong cut 2");
     106      check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 3");
    75107
    76108      int sum=0;
     
    85117        sum++;
    86118      check(sum == countNodes(graph), "Problem with MinCutNodeIt");
    87      
    88119    }
    89120  }
  • test/hao_orlin_test.cc

    r440 r597  
    2020
    2121#include <lemon/smart_graph.h>
     22#include <lemon/adaptors.h>
     23#include <lemon/concepts/digraph.h>
     24#include <lemon/concepts/maps.h>
     25#include <lemon/lgf_reader.h>
    2226#include <lemon/hao_orlin.h>
    2327
    24 #include <lemon/lgf_reader.h>
    2528#include "test_tools.h"
    2629
     
    3841  "5\n"
    3942  "@edges\n"
    40   "     label  capacity\n"
    41   "0 1  0      2\n"
    42   "1 2  1      2\n"
    43   "2 0  2      2\n"
    44   "3 4  3      2\n"
    45   "4 5  4      2\n"
    46   "5 3  5      2\n"
    47   "2 3  6      3\n";
     43  "     cap1 cap2 cap3\n"
     44  "0 1  1    1    1   \n"
     45  "0 2  2    2    4   \n"
     46  "1 2  4    4    4   \n"
     47  "3 4  1    1    1   \n"
     48  "3 5  2    2    4   \n"
     49  "4 5  4    4    4   \n"
     50  "5 4  4    4    4   \n"
     51  "2 3  1    6    6   \n"
     52  "4 0  1    6    6   \n";
     53
     54void checkHaoOrlinCompile()
     55{
     56  typedef int Value;
     57  typedef concepts::Digraph Digraph;
     58
     59  typedef Digraph::Node Node;
     60  typedef Digraph::Arc Arc;
     61  typedef concepts::ReadMap<Arc, Value> CapMap;
     62  typedef concepts::WriteMap<Node, bool> CutMap;
     63
     64  Digraph g;
     65  Node n;
     66  CapMap cap;
     67  CutMap cut;
     68  Value v;
     69
     70  HaoOrlin<Digraph, CapMap> ho_test(g, cap);
     71  const HaoOrlin<Digraph, CapMap>&
     72    const_ho_test = ho_test;
     73
     74  ho_test.init();
     75  ho_test.init(n);
     76  ho_test.calculateOut();
     77  ho_test.calculateIn();
     78  ho_test.run();
     79  ho_test.run(n);
     80
     81  v = const_ho_test.minCutValue();
     82  v = const_ho_test.minCutMap(cut);
     83}
     84
     85template <typename Graph, typename CapMap, typename CutMap>
     86typename CapMap::Value
     87  cutValue(const Graph& graph, const CapMap& cap, const CutMap& cut)
     88{
     89  typename CapMap::Value sum = 0;
     90  for (typename Graph::ArcIt a(graph); a != INVALID; ++a) {
     91    if (cut[graph.source(a)] && !cut[graph.target(a)])
     92      sum += cap[a];
     93  }
     94  return sum;
     95}
    4896
    4997int main() {
    50   SmartGraph graph;
    51   SmartGraph::EdgeMap<int> capacity(graph);
     98  SmartDigraph graph;
     99  SmartDigraph::ArcMap<int> cap1(graph), cap2(graph), cap3(graph);
     100  SmartDigraph::NodeMap<bool> cut(graph);
    52101
    53   istringstream lgfs(lgf);
    54   graphReader(graph, lgfs).
    55     edgeMap("capacity", capacity).run();
     102  istringstream input(lgf);
     103  digraphReader(graph, input)
     104    .arcMap("cap1", cap1)
     105    .arcMap("cap2", cap2)
     106    .arcMap("cap3", cap3)
     107    .run();
    56108
    57   HaoOrlin<SmartGraph, SmartGraph::EdgeMap<int> > ho(graph, capacity);
    58   ho.run();
     109  {
     110    HaoOrlin<SmartDigraph> ho(graph, cap1);
     111    ho.run();
     112    ho.minCutMap(cut);
     113   
     114    check(ho.minCutValue() == 1, "Wrong cut value");
     115    check(ho.minCutValue() == cutValue(graph, cap1, cut), "Wrong cut value");
     116  }
     117  {
     118    HaoOrlin<SmartDigraph> ho(graph, cap2);
     119    ho.run();
     120    ho.minCutMap(cut);
    59121
    60   check(ho.minCutValue() == 3, "Wrong cut value");
     122    check(ho.minCutValue() == 1, "Wrong cut value");
     123    check(ho.minCutValue() == cutValue(graph, cap2, cut), "Wrong cut value");
     124  }
     125  {
     126    HaoOrlin<SmartDigraph> ho(graph, cap3);
     127    ho.run();
     128    ho.minCutMap(cut);
     129   
     130    check(ho.minCutValue() == 1, "Wrong cut value");
     131    check(ho.minCutValue() == cutValue(graph, cap3, cut), "Wrong cut value");
     132  }
     133 
     134  typedef Undirector<SmartDigraph> UGraph;
     135  UGraph ugraph(graph);
     136 
     137  {
     138    HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap1);
     139    ho.run();
     140    ho.minCutMap(cut);
     141   
     142    check(ho.minCutValue() == 2, "Wrong cut value");
     143    check(ho.minCutValue() == cutValue(ugraph, cap1, cut), "Wrong cut value");
     144  }
     145  {
     146    HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap2);
     147    ho.run();
     148    ho.minCutMap(cut);
     149   
     150    check(ho.minCutValue() == 5, "Wrong cut value");
     151    check(ho.minCutValue() == cutValue(ugraph, cap2, cut), "Wrong cut value");
     152  }
     153  {
     154    HaoOrlin<UGraph, SmartDigraph::ArcMap<int> > ho(ugraph, cap3);
     155    ho.run();
     156    ho.minCutMap(cut);
     157   
     158    check(ho.minCutValue() == 5, "Wrong cut value");
     159    check(ho.minCutValue() == cutValue(ugraph, cap3, cut), "Wrong cut value");
     160  }
    61161
    62162  return 0;
Note: See TracChangeset for help on using the changeset viewer.