COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 976:426a704d7483 in lemon-main


Ignore:
Timestamp:
01/20/12 19:23:48 (13 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Parents:
974:b1744d7bdb47 (diff), 975:b873350e6258 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge Intel C++ compatibility fixes

Files:
12 edited

Legend:

Unmodified
Added
Removed

  • CMakeLists.txt

    r966 r976  
    6767    # C4996: 'function': was declared deprecated
    6868  ELSE()
    69     SET(CXX_WARNING "-Wall -W")
     69    SET(CXX_WARNING "-Wall")
    7070  ENDIF()
    7171ENDIF()
    … …  
    7474SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} ${LEMON_CXX_WARNING_FLAGS}")
    7575
    76 SET( CMAKE_CXX_FLAGS_MAINTAINER "-Werror -ggdb" CACHE STRING
     76SET( CMAKE_CXX_FLAGS_MAINTAINER "-Werror -ggdb -O0" CACHE STRING
    7777    "Flags used by the C++ compiler during maintainer builds."
    7878    FORCE )
    79 SET( CMAKE_C_FLAGS_MAINTAINER "-Werror" CACHE STRING
     79SET( CMAKE_C_FLAGS_MAINTAINER "-Werror -O0" CACHE STRING
    8080    "Flags used by the C compiler during maintainer builds."
    8181    FORCE )

  • CMakeLists.txt

    r975 r976  
    125125ADD_SUBDIRECTORY(lemon)
    126126IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
     127  ADD_SUBDIRECTORY(contrib)
    127128  ADD_SUBDIRECTORY(demo)
    128129  ADD_SUBDIRECTORY(tools)

  • lemon/bfs.h

    r877 r976  
    12521252      }
    12531253      _Visitor& visitor;
     1254      Constraints() {}
    12541255    };
    12551256  };

  • lemon/bfs.h

    r975 r976  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    4848    ///The type of the map that stores the predecessor
    4949    ///arcs of the shortest paths.
    50     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     50    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    5151    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    5252    ///Instantiates a \c PredMap.
    … …  
    6363
    6464    ///The type of the map that indicates which nodes are processed.
    65     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     65    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     66    ///By default, it is a NullMap.
    6667    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    6768    ///Instantiates a \c ProcessedMap.
    … …  
    8283
    8384    ///The type of the map that indicates which nodes are reached.
    84     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     85    ///It must conform to
     86    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8587    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    8688    ///Instantiates a \c ReachedMap.
    … …  
    9799
    98100    ///The type of the map that stores the distances of the nodes.
    99     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     101    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    100102    typedef typename Digraph::template NodeMap<int> DistMap;
    101103    ///Instantiates a \c DistMap.
    … …  
    121123  ///\tparam GR The type of the digraph the algorithm runs on.
    122124  ///The default type is \ref ListDigraph.
     125  ///\tparam TR The traits class that defines various types used by the
     126  ///algorithm. By default, it is \ref BfsDefaultTraits
     127  ///"BfsDefaultTraits<GR>".
     128  ///In most cases, this parameter should not be set directly,
     129  ///consider to use the named template parameters instead.
    123130#ifdef DOXYGEN
    124131  template <typename GR,
    … …  
    226233    ///\ref named-templ-param "Named parameter" for setting
    227234    ///\c PredMap type.
    228     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     235    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    229236    template <class T>
    230237    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
    … …  
    246253    ///\ref named-templ-param "Named parameter" for setting
    247254    ///\c DistMap type.
    248     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     255    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    249256    template <class T>
    250257    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
    … …  
    266273    ///\ref named-templ-param "Named parameter" for setting
    267274    ///\c ReachedMap type.
    268     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     275    ///It must conform to
     276    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    269277    template <class T>
    270278    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
    … …  
    286294    ///\ref named-templ-param "Named parameter" for setting
    287295    ///\c ProcessedMap type.
    288     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     296    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    289297    template <class T>
    290298    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
    … …  
    414422    ///The simplest way to execute the BFS algorithm is to use one of the
    415423    ///member functions called \ref run(Node) "run()".\n
    416     ///If you need more control on the execution, first you have to call
    417     ///\ref init(), then you can add several source nodes with
     424    ///If you need better control on the execution, you have to call
     425    ///\ref init() first, then you can add several source nodes with
    418426    ///\ref addSource(). Finally the actual path computation can be
    419427    ///performed with one of the \ref start() functions.
    … …  
    701709    ///Runs the algorithm to visit all nodes in the digraph.
    702710
    703     ///This method runs the %BFS algorithm in order to
    704     ///compute the shortest path to each node.
    705     ///
    706     ///The algorithm computes
    707     ///- the shortest path tree (forest),
    708     ///- the distance of each node from the root(s).
     711    ///This method runs the %BFS algorithm in order to visit all nodes
     712    ///in the digraph.
    709713    ///
    710714    ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
    … …  
    738742    ///@{
    739743
    740     ///The shortest path to a node.
    741 
    742     ///Returns the shortest path to a node.
     744    ///The shortest path to the given node.
     745
     746    ///Returns the shortest path to the given node from the root(s).
    743747    ///
    744748    ///\warning \c t should be reached from the root(s).
    … …  
    748752    Path path(Node t) const { return Path(*G, *_pred, t); }
    749753
    750     ///The distance of a node from the root(s).
    751 
    752     ///Returns the distance of a node from the root(s).
     754    ///The distance of the given node from the root(s).
     755
     756    ///Returns the distance of the given node from the root(s).
    753757    ///
    754758    ///\warning If node \c v is not reached from the root(s), then
    … …  
    759763    int dist(Node v) const { return (*_dist)[v]; }
    760764
    761     ///Returns the 'previous arc' of the shortest path tree for a node.
    762 
     765    ///\brief Returns the 'previous arc' of the shortest path tree for
     766    ///the given node.
     767    ///
    763768    ///This function returns the 'previous arc' of the shortest path
    764769    ///tree for the node \c v, i.e. it returns the last arc of a
    … …  
    767772    ///
    768773    ///The shortest path tree used here is equal to the shortest path
    769     ///tree used in \ref predNode().
     774    ///tree used in \ref predNode() and \ref predMap().
    770775    ///
    771776    ///\pre Either \ref run(Node) "run()" or \ref init()
    … …  
    773778    Arc predArc(Node v) const { return (*_pred)[v];}
    774779
    775     ///Returns the 'previous node' of the shortest path tree for a node.
    776 
     780    ///\brief Returns the 'previous node' of the shortest path tree for
     781    ///the given node.
     782    ///
    777783    ///This function returns the 'previous node' of the shortest path
    778784    ///tree for the node \c v, i.e. it returns the last but one node
    779     ///from a shortest path from a root to \c v. It is \c INVALID
     785    ///of a shortest path from a root to \c v. It is \c INVALID
    780786    ///if \c v is not reached from the root(s) or if \c v is a root.
    781787    ///
    782788    ///The shortest path tree used here is equal to the shortest path
    783     ///tree used in \ref predArc().
     789    ///tree used in \ref predArc() and \ref predMap().
    784790    ///
    785791    ///\pre Either \ref run(Node) "run()" or \ref init()
    … …  
    802808    ///
    803809    ///Returns a const reference to the node map that stores the predecessor
    804     ///arcs, which form the shortest path tree.
     810    ///arcs, which form the shortest path tree (forest).
    805811    ///
    806812    ///\pre Either \ref run(Node) "run()" or \ref init()
    … …  
    808814    const PredMap &predMap() const { return *_pred;}
    809815
    810     ///Checks if a node is reached from the root(s).
     816    ///Checks if the given node is reached from the root(s).
    811817
    812818    ///Returns \c true if \c v is reached from the root(s).
    … …  
    834840    ///The type of the map that stores the predecessor
    835841    ///arcs of the shortest paths.
    836     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     842    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    837843    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    838844    ///Instantiates a PredMap.
    … …  
    849855
    850856    ///The type of the map that indicates which nodes are processed.
    851     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    852     ///By default it is a NullMap.
     857    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     858    ///By default, it is a NullMap.
    853859    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    854860    ///Instantiates a ProcessedMap.
    … …  
    869875
    870876    ///The type of the map that indicates which nodes are reached.
    871     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     877    ///It must conform to
     878    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    872879    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    873880    ///Instantiates a ReachedMap.
    … …  
    884891
    885892    ///The type of the map that stores the distances of the nodes.
    886     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     893    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    887894    typedef typename Digraph::template NodeMap<int> DistMap;
    888895    ///Instantiates a DistMap.
    … …  
    899906
    900907    ///The type of the shortest paths.
    901     ///It must meet the \ref concepts::Path "Path" concept.
     908    ///It must conform to the \ref concepts::Path "Path" concept.
    902909    typedef lemon::Path<Digraph> Path;
    903910  };
    … …  
    905912  /// Default traits class used by BfsWizard
    906913
    907   /// To make it easier to use Bfs algorithm
    908   /// we have created a wizard class.
    909   /// This \ref BfsWizard class needs default traits,
    910   /// as well as the \ref Bfs class.
    911   /// The \ref BfsWizardBase is a class to be the default traits of the
    912   /// \ref BfsWizard class.
     914  /// Default traits class used by BfsWizard.
     915  /// \tparam GR The type of the digraph.
    913916  template<class GR>
    914917  class BfsWizardBase : public BfsWizardDefaultTraits<GR>
    … …  
    938941    /// Constructor.
    939942
    940     /// This constructor does not require parameters, therefore it initiates
     943    /// This constructor does not require parameters, it initiates
    941944    /// all of the attributes to \c 0.
    942945    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
    … …  
    963966  /// This class should only be used through the \ref bfs() function,
    964967  /// which makes it easier to use the algorithm.
     968  ///
     969  /// \tparam TR The traits class that defines various types used by the
     970  /// algorithm.
    965971  template<class TR>
    966972  class BfsWizard : public TR
    … …  
    968974    typedef TR Base;
    969975
    970     ///The type of the digraph the algorithm runs on.
    971976    typedef typename TR::Digraph Digraph;
    972977
    … …  
    976981    typedef typename Digraph::OutArcIt OutArcIt;
    977982
    978     ///\brief The type of the map that stores the predecessor
    979     ///arcs of the shortest paths.
    980983    typedef typename TR::PredMap PredMap;
    981     ///\brief The type of the map that stores the distances of the nodes.
    982984    typedef typename TR::DistMap DistMap;
    983     ///\brief The type of the map that indicates which nodes are reached.
    984985    typedef typename TR::ReachedMap ReachedMap;
    985     ///\brief The type of the map that indicates which nodes are processed.
    986986    typedef typename TR::ProcessedMap ProcessedMap;
    987     ///The type of the shortest paths
    988987    typedef typename TR::Path Path;
    989988
    … …  
    10551054    ///Runs BFS algorithm to visit all nodes in the digraph.
    10561055
    1057     ///This method runs BFS algorithm in order to compute
    1058     ///the shortest path to each node.
     1056    ///This method runs BFS algorithm in order to visit all nodes
     1057    ///in the digraph.
    10591058    void run()
    10601059    {
    … …  
    10681067      SetPredMapBase(const TR &b) : TR(b) {}
    10691068    };
    1070     ///\brief \ref named-func-param "Named parameter"
    1071     ///for setting PredMap object.
    1072     ///
    1073     ///\ref named-func-param "Named parameter"
    1074     ///for setting PredMap object.
     1069
     1070    ///\brief \ref named-templ-param "Named parameter" for setting
     1071    ///the predecessor map.
     1072    ///
     1073    ///\ref named-templ-param "Named parameter" function for setting
     1074    ///the map that stores the predecessor arcs of the nodes.
    10751075    template<class T>
    10761076    BfsWizard<SetPredMapBase<T> > predMap(const T &t)
    … …  
    10861086      SetReachedMapBase(const TR &b) : TR(b) {}
    10871087    };
    1088     ///\brief \ref named-func-param "Named parameter"
    1089     ///for setting ReachedMap object.
    1090     ///
    1091     /// \ref named-func-param "Named parameter"
    1092     ///for setting ReachedMap object.
     1088
     1089    ///\brief \ref named-templ-param "Named parameter" for setting
     1090    ///the reached map.
     1091    ///
     1092    ///\ref named-templ-param "Named parameter" function for setting
     1093    ///the map that indicates which nodes are reached.
    10931094    template<class T>
    10941095    BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
    … …  
    11041105      SetDistMapBase(const TR &b) : TR(b) {}
    11051106    };
    1106     ///\brief \ref named-func-param "Named parameter"
    1107     ///for setting DistMap object.
    1108     ///
    1109     /// \ref named-func-param "Named parameter"
    1110     ///for setting DistMap object.
     1107
     1108    ///\brief \ref named-templ-param "Named parameter" for setting
     1109    ///the distance map.
     1110    ///
     1111    ///\ref named-templ-param "Named parameter" function for setting
     1112    ///the map that stores the distances of the nodes calculated
     1113    ///by the algorithm.
    11111114    template<class T>
    11121115    BfsWizard<SetDistMapBase<T> > distMap(const T &t)
    … …  
    11221125      SetProcessedMapBase(const TR &b) : TR(b) {}
    11231126    };
    1124     ///\brief \ref named-func-param "Named parameter"
    1125     ///for setting ProcessedMap object.
    1126     ///
    1127     /// \ref named-func-param "Named parameter"
    1128     ///for setting ProcessedMap object.
     1127
     1128    ///\brief \ref named-func-param "Named parameter" for setting
     1129    ///the processed map.
     1130    ///
     1131    ///\ref named-templ-param "Named parameter" function for setting
     1132    ///the map that indicates which nodes are processed.
    11291133    template<class T>
    11301134    BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
    … …  
    12661270    ///
    12671271    /// The type of the map that indicates which nodes are reached.
    1268     /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     1272    /// It must conform to
     1273    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    12691274    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    12701275
    … …  
    13041309  /// does not observe the BFS events. If you want to observe the BFS
    13051310  /// events, you should implement your own visitor class.
    1306   /// \tparam TR Traits class to set various data types used by the
    1307   /// algorithm. The default traits class is
    1308   /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>".
    1309   /// See \ref BfsVisitDefaultTraits for the documentation of
    1310   /// a BFS visit traits class.
     1311  /// \tparam TR The traits class that defines various types used by the
     1312  /// algorithm. By default, it is \ref BfsVisitDefaultTraits
     1313  /// "BfsVisitDefaultTraits<GR>".
     1314  /// In most cases, this parameter should not be set directly,
     1315  /// consider to use the named template parameters instead.
    13111316#ifdef DOXYGEN
    13121317  template <typename GR, typename VS, typename TR>
    … …  
    14271432    /// The simplest way to execute the BFS algorithm is to use one of the
    14281433    /// member functions called \ref run(Node) "run()".\n
    1429     /// If you need more control on the execution, first you have to call
    1430     /// \ref init(), then you can add several source nodes with
     1434    /// If you need better control on the execution, you have to call
     1435    /// \ref init() first, then you can add several source nodes with
    14311436    /// \ref addSource(). Finally the actual path computation can be
    14321437    /// performed with one of the \ref start() functions.
    … …  
    17001705    /// \brief Runs the algorithm to visit all nodes in the digraph.
    17011706    ///
    1702     /// This method runs the %BFS algorithm in order to
    1703     /// compute the shortest path to each node.
    1704     ///
    1705     /// The algorithm computes
    1706     /// - the shortest path tree (forest),
    1707     /// - the distance of each node from the root(s).
     1707    /// This method runs the %BFS algorithm in order to visit all nodes
     1708    /// in the digraph.
    17081709    ///
    17091710    /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
    … …  
    17371738    ///@{
    17381739
    1739     /// \brief Checks if a node is reached from the root(s).
     1740    /// \brief Checks if the given node is reached from the root(s).
    17401741    ///
    17411742    /// Returns \c true if \c v is reached from the root(s).

  • lemon/concepts/graph_components.h

    r877 r976  
    116116        const _GraphItem &ia;
    117117        const _GraphItem &ib;
     118        Constraints() {}
    118119      };
    119120    };
    … …  
    175176
    176177        const _Digraph& digraph;
     178        Constraints() {}
    177179      };
    178180    };
    … …  
    291293
    292294        const _Graph& graph;
     295      Constraints() {}
    293296      };
    294297
    … …  
    370373
    371374        const _Digraph& digraph;
     375        Constraints() {}
    372376      };
    373377    };
    … …  
    422426
    423427        const _Graph& graph;
     428        Constraints() {}
    424429      };
    425430    };
    … …  
    499504        }
    500505        const GR& g;
     506        Constraints() {}
    501507      };
    502508    };
    … …  
    587593        const Base& node;
    588594        const GR& graph;
     595        Constraints() {}
    589596      };
    590597    };
    … …  
    763770
    764771        const _Digraph& digraph;
     772        Constraints() {}
    765773      };
    766774    };
    … …  
    887895
    888896        const _Graph& graph;
     897        Constraints() {}
    889898      };
    890899    };
    … …  
    944953
    945954        const _Digraph& digraph;
     955        Constraints() {}
    946956      };
    947957    };
    … …  
    985995
    986996        const _Graph& graph;
     997        Constraints() {}
    987998      };
    988999    };
    … …  
    10621073        const GR &g;
    10631074        const typename GraphMap::Value &t;
     1075        Constraints() {}
    10641076      };
    10651077
    … …  
    12001212
    12011213        const _Digraph& digraph;
     1214        Constraints() {}
    12021215      };
    12031216    };
    … …  
    12851298
    12861299        const _Graph& graph;
     1300        Constraints() {}
    12871301      };
    12881302    };
    … …  
    13291343
    13301344        _Digraph& digraph;
     1345        Constraints() {}
    13311346      };
    13321347    };
    … …  
    13731388
    13741389        _Graph& graph;
     1390        Constraints() {}
    13751391      };
    13761392    };
    … …  
    14121428
    14131429        _Digraph& digraph;
     1430        Constraints() {}
    14141431      };
    14151432    };
    … …  
    14511468
    14521469        _Graph& graph;
     1470        Constraints() {}
    14531471      };
    14541472    };
    … …  
    14791497
    14801498        _Digraph& digraph;
     1499        Constraints() {}
    14811500      };
    14821501    };
    … …  
    15071526
    15081527        _Graph& graph;
     1528        Constraints() {}
    15091529      };
    15101530    };

  • lemon/concepts/graph_components.h

    r975 r976  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    1919///\ingroup graph_concepts
    2020///\file
    21 ///\brief The concept of graph components.
     21///\brief The concepts of graph components.
    2222
    2323#ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H
    … …  
    3939    /// \note This class is a template class so that we can use it to
    4040    /// create graph skeleton classes. The reason for this is that \c Node
    41     /// and \c Arc (or \c Edge) types should \e not derive from the same 
     41    /// and \c Arc (or \c Edge) types should \e not derive from the same
    4242    /// base class. For \c Node you should instantiate it with character
    4343    /// \c 'n', for \c Arc with \c 'a' and for \c Edge with \c 'e'.
    … …  
    9090      ///
    9191      /// This operator defines an ordering of the items.
    92       /// It makes possible to use graph item types as key types in 
     92      /// It makes possible to use graph item types as key types in
    9393      /// associative containers (e.g. \c std::map).
    9494      ///
    95       /// \note This operator only have to define some strict ordering of
     95      /// \note This operator only has to define some strict ordering of
    9696      /// the items; this order has nothing to do with the iteration
    9797      /// ordering of the items.
    … …  
    124124    /// This class describes the base interface of directed graph types.
    125125    /// All digraph %concepts have to conform to this class.
    126     /// It just provides types for nodes and arcs and functions 
     126    /// It just provides types for nodes and arcs and functions
    127127    /// to get the source and the target nodes of arcs.
    128128    class BaseDigraphComponent {
    … …  
    432432    /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.
    433433    ///
    434     /// This class describes the concept of \c NodeIt, \c ArcIt and 
     434    /// This class describes the concept of \c NodeIt, \c ArcIt and
    435435    /// \c EdgeIt subtypes of digraph and graph types.
    436436    template <typename GR, typename Item>
    … …  
    472472      /// next item.
    473473      GraphItemIt& operator++() { return *this; }
    474  
     474
    475475      /// \brief Equality operator
    476476      ///
    … …  
    508508    };
    509509
    510     /// \brief Concept class for \c InArcIt, \c OutArcIt and 
     510    /// \brief Concept class for \c InArcIt, \c OutArcIt and
    511511    /// \c IncEdgeIt types.
    512512    ///
    513     /// This class describes the concept of \c InArcIt, \c OutArcIt 
     513    /// This class describes the concept of \c InArcIt, \c OutArcIt
    514514    /// and \c IncEdgeIt subtypes of digraph and graph types.
    515515    ///
    516516    /// \note Since these iterator classes do not inherit from the same
    517517    /// base class, there is an additional template parameter (selector)
    518     /// \c sel. For \c InArcIt you should instantiate it with character 
     518    /// \c sel. For \c InArcIt you should instantiate it with character
    519519    /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'.
    520520    template <typename GR,
    … …  
    537537      GraphIncIt(const GraphIncIt& it) : Item(it) {}
    538538
    539       /// \brief Constructor that sets the iterator to the first 
     539      /// \brief Constructor that sets the iterator to the first
    540540      /// incoming or outgoing arc.
    541541      ///
    542       /// Constructor that sets the iterator to the first arc 
     542      /// Constructor that sets the iterator to the first arc
    543543      /// incoming to or outgoing from the given node.
    544544      explicit GraphIncIt(const GR&, const Base&) {}
    … …  
    813813      /// \brief Return the first edge incident to the given node.
    814814      ///
    815       /// This function gives back the first edge incident to the given 
     815      /// This function gives back the first edge incident to the given
    816816      /// node. The bool parameter gives back the direction for which the
    817       /// source node of the directed arc representing the edge is the 
     817      /// source node of the directed arc representing the edge is the
    818818      /// given node.
    819819      void firstInc(Edge&, bool&, const Node&) const {}
    … …  
    822822      /// given node.
    823823      ///
    824       /// This function gives back the next edge incident to the given 
     824      /// This function gives back the next edge incident to the given
    825825      /// node. The bool parameter should be used as \c firstInc() use it.
    826826      void nextInc(Edge&, bool&) const {}
    … …  
    10021002    ///
    10031003    /// This class describes the concept of standard graph maps, i.e.
    1004     /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and 
     1004    /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and
    10051005    /// graph types, which can be used for associating data to graph items.
    10061006    /// The standard graph maps must conform to the ReferenceMap concept.
    … …  
    10571057          _Map m1(g);
    10581058          _Map m2(g,t);
    1059          
     1059
    10601060          // Copy constructor
    10611061          // _Map m3(m);
    … …  
    10811081    ///
    10821082    /// This class describes the interface of mappable directed graphs.
    1083     /// It extends \ref BaseDigraphComponent with the standard digraph 
     1083    /// It extends \ref BaseDigraphComponent with the standard digraph
    10841084    /// map classes, namely \c NodeMap and \c ArcMap.
    10851085    /// This concept is part of the Digraph concept.
    … …  
    12191219    ///
    12201220    /// This class describes the interface of mappable undirected graphs.
    1221     /// It extends \ref MappableDigraphComponent with the standard graph 
     1221    /// It extends \ref MappableDigraphComponent with the standard graph
    12221222    /// map class for edges (\c EdgeMap).
    12231223    /// This concept is part of the Graph concept.
    … …  
    13051305    ///
    13061306    /// This class describes the interface of extendable directed graphs.
    1307     /// It extends \ref BaseDigraphComponent with functions for adding 
     1307    /// It extends \ref BaseDigraphComponent with functions for adding
    13081308    /// nodes and arcs to the digraph.
    13091309    /// This concept requires \ref AlterableDigraphComponent.
    … …  
    13501350    ///
    13511351    /// This class describes the interface of extendable undirected graphs.
    1352     /// It extends \ref BaseGraphComponent with functions for adding 
     1352    /// It extends \ref BaseGraphComponent with functions for adding
    13531353    /// nodes and edges to the graph.
    13541354    /// This concept requires \ref AlterableGraphComponent.
    … …  
    13951395    ///
    13961396    /// This class describes the interface of erasable directed graphs.
    1397     /// It extends \ref BaseDigraphComponent with functions for removing 
     1397    /// It extends \ref BaseDigraphComponent with functions for removing
    13981398    /// nodes and arcs from the digraph.
    13991399    /// This concept requires \ref AlterableDigraphComponent.
    … …  
    14081408      /// \brief Erase a node from the digraph.
    14091409      ///
    1410       /// This function erases the given node from the digraph and all arcs 
     1410      /// This function erases the given node from the digraph and all arcs
    14111411      /// connected to the node.
    14121412      void erase(const Node&) {}
    … …  
    14351435    ///
    14361436    /// This class describes the interface of erasable undirected graphs.
    1437     /// It extends \ref BaseGraphComponent with functions for removing 
     1437    /// It extends \ref BaseGraphComponent with functions for removing
    14381438    /// nodes and edges from the graph.
    14391439    /// This concept requires \ref AlterableGraphComponent.

  • lemon/concepts/heap.h

    r877 r976  
    315315        _Heap& heap;
    316316        ItemIntMap& map;
     317        Constraints() {}
    317318      };
    318319    };

  • lemon/concepts/heap.h

    r975 r976  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    1717 */
    1818
     19#ifndef LEMON_CONCEPTS_HEAP_H
     20#define LEMON_CONCEPTS_HEAP_H
     21
    1922///\ingroup concept
    2023///\file
    2124///\brief The concept of heaps.
    2225
    23 #ifndef LEMON_CONCEPTS_HEAP_H
    24 #define LEMON_CONCEPTS_HEAP_H
    25 
    2626#include <lemon/core.h>
    2727#include <lemon/concept_check.h>
    … …  
    3636    /// \brief The heap concept.
    3737    ///
    38     /// Concept class describing the main interface of heaps. A \e heap
    39     /// is a data structure for storing items with specified values called
    40     /// \e priorities in such a way that finding the item with minimum
    41     /// priority is efficient. In a heap one can change the priority of an
    42     /// item, add or erase an item, etc.
     38    /// This concept class describes the main interface of heaps.
     39    /// The various \ref heaps "heap structures" are efficient
     40    /// implementations of the abstract data type \e priority \e queue.
     41    /// They store items with specified values called \e priorities
     42    /// in such a way that finding and removing the item with minimum
     43    /// priority are efficient. The basic operations are adding and
     44    /// erasing items, changing the priority of an item, etc.
    4345    ///
    44     /// \tparam PR Type of the priority of the items.
    45     /// \tparam IM A read and writable item map with int values, used
     46    /// Heaps are crucial in several algorithms, such as Dijkstra and Prim.
     47    /// Any class that conforms to this concept can be used easily in such
     48    /// algorithms.
     49    ///
     50    /// \tparam PR Type of the priorities of the items.
     51    /// \tparam IM A read-writable item map with \c int values, used
    4652    /// internally to handle the cross references.
    47     /// \tparam Comp A functor class for the ordering of the priorities.
     53    /// \tparam CMP A functor class for comparing the priorities.
    4854    /// The default is \c std::less<PR>.
    4955#ifdef DOXYGEN
    50     template <typename PR, typename IM, typename Comp = std::less<PR> >
    51 #else
    52     template <typename PR, typename IM>
     56    template <typename PR, typename IM, typename CMP>
     57#else
     58    template <typename PR, typename IM, typename CMP = std::less<PR> >
    5359#endif
    5460    class Heap {
    … …  
    6571      ///
    6672      /// Each item has a state associated to it. It can be "in heap",
    67       /// "pre heap" or "post heap". The later two are indifferent
    68       /// from the point of view of the heap, but may be useful for
    69       /// the user.
     73      /// "pre-heap" or "post-heap". The latter two are indifferent from the
     74      /// heap's point of view, but may be useful to the user.
    7075      ///
    7176      /// The item-int map must be initialized in such way that it assigns
    … …  
    7378      enum State {
    7479        IN_HEAP = 0,    ///< = 0. The "in heap" state constant.
    75         PRE_HEAP = -1,  ///< = -1. The "pre heap" state constant.
    76         POST_HEAP = -2  ///< = -2. The "post heap" state constant.
     80        PRE_HEAP = -1,  ///< = -1. The "pre-heap" state constant.
     81        POST_HEAP = -2  ///< = -2. The "post-heap" state constant.
    7782      };
    7883
    79       /// \brief The constructor.
    80       ///
    81       /// The constructor.
     84      /// \brief Constructor.
     85      ///
     86      /// Constructor.
    8287      /// \param map A map that assigns \c int values to keys of type
    8388      /// \c Item. It is used internally by the heap implementations to
    8489      /// handle the cross references. The assigned value must be
    85       /// \c PRE_HEAP (<tt>-1</tt>) for every item.
     90      /// \c PRE_HEAP (<tt>-1</tt>) for each item.
     91#ifdef DOXYGEN
    8692      explicit Heap(ItemIntMap &map) {}
     93#else
     94      explicit Heap(ItemIntMap&) {}
     95#endif
     96
     97      /// \brief Constructor.
     98      ///
     99      /// Constructor.
     100      /// \param map A map that assigns \c int values to keys of type
     101      /// \c Item. It is used internally by the heap implementations to
     102      /// handle the cross references. The assigned value must be
     103      /// \c PRE_HEAP (<tt>-1</tt>) for each item.
     104      /// \param comp The function object used for comparing the priorities.
     105#ifdef DOXYGEN
     106      explicit Heap(ItemIntMap &map, const CMP &comp) {}
     107#else
     108      explicit Heap(ItemIntMap&, const CMP&) {}
     109#endif
    87110
    88111      /// \brief The number of items stored in the heap.
    89112      ///
    90       /// Returns the number of items stored in the heap.
     113      /// This function returns the number of items stored in the heap.
    91114      int size() const { return 0; }
    92115
    93       /// \brief Checks if the heap is empty.
    94       ///
    95       /// Returns \c true if the heap is empty.
     116      /// \brief Check if the heap is empty.
     117      ///
     118      /// This function returns \c true if the heap is empty.
    96119      bool empty() const { return false; }
    97120
    98       /// \brief Makes the heap empty.
    99       ///
    100       /// Makes the heap empty.
    101       void clear();
    102 
    103       /// \brief Inserts an item into the heap with the given priority.
    104       ///
    105       /// Inserts the given item into the heap with the given priority.
     121      /// \brief Make the heap empty.
     122      ///
     123      /// This functon makes the heap empty.
     124      /// It does not change the cross reference map. If you want to reuse
     125      /// a heap that is not surely empty, you should first clear it and
     126      /// then you should set the cross reference map to \c PRE_HEAP
     127      /// for each item.
     128      void clear() {}
     129
     130      /// \brief Insert an item into the heap with the given priority.
     131      ///
     132      /// This function inserts the given item into the heap with the
     133      /// given priority.
    106134      /// \param i The item to insert.
    107135      /// \param p The priority of the item.
     136      /// \pre \e i must not be stored in the heap.
     137#ifdef DOXYGEN
    108138      void push(const Item &i, const Prio &p) {}
    109 
    110       /// \brief Returns the item having minimum priority.
    111       ///
    112       /// Returns the item having minimum priority.
     139#else
     140      void push(const Item&, const Prio&) {}
     141#endif
     142
     143      /// \brief Return the item having minimum priority.
     144      ///
     145      /// This function returns the item having minimum priority.
    113146      /// \pre The heap must be non-empty.
    114       Item top() const {}
     147      Item top() const { return Item(); }
    115148
    116149      /// \brief The minimum priority.
    117150      ///
    118       /// Returns the minimum priority.
     151      /// This function returns the minimum priority.
    119152      /// \pre The heap must be non-empty.
    120       Prio prio() const {}
    121 
    122       /// \brief Removes the item having minimum priority.
    123       ///
    124       /// Removes the item having minimum priority.
     153      Prio prio() const { return Prio(); }
     154
     155      /// \brief Remove the item having minimum priority.
     156      ///
     157      /// This function removes the item having minimum priority.
    125158      /// \pre The heap must be non-empty.
    126159      void pop() {}
    127160
    128       /// \brief Removes an item from the heap.
    129       ///
    130       /// Removes the given item from the heap if it is already stored.
     161      /// \brief Remove the given item from the heap.
     162      ///
     163      /// This function removes the given item from the heap if it is
     164      /// already stored.
    131165      /// \param i The item to delete.
     166      /// \pre \e i must be in the heap.
     167#ifdef DOXYGEN
    132168      void erase(const Item &i) {}
    133 
    134       /// \brief The priority of an item.
    135       ///
    136       /// Returns the priority of the given item.
    137       /// \param i The item.
    138       /// \pre \c i must be in the heap.
     169#else
     170      void erase(const Item&) {}
     171#endif
     172
     173      /// \brief The priority of the given item.
     174      ///
     175      /// This function returns the priority of the given item.
     176      /// \param i The item.
     177      /// \pre \e i must be in the heap.
     178#ifdef DOXYGEN
    139179      Prio operator[](const Item &i) const {}
    140 
    141       /// \brief Sets the priority of an item or inserts it, if it is
     180#else
     181      Prio operator[](const Item&) const { return Prio(); }
     182#endif
     183
     184      /// \brief Set the priority of an item or insert it, if it is
    142185      /// not stored in the heap.
    143186      ///
    144187      /// This method sets the priority of the given item if it is
    145       /// already stored in the heap.
    146       /// Otherwise it inserts the given item with the given priority.
     188      /// already stored in the heap. Otherwise it inserts the given
     189      /// item into the heap with the given priority.
    147190      ///
    148191      /// \param i The item.
    149192      /// \param p The priority.
     193#ifdef DOXYGEN
    150194      void set(const Item &i, const Prio &p) {}
    151 
    152       /// \brief Decreases the priority of an item to the given value.
    153       ///
    154       /// Decreases the priority of an item to the given value.
     195#else
     196      void set(const Item&, const Prio&) {}
     197#endif
     198
     199      /// \brief Decrease the priority of an item to the given value.
     200      ///
     201      /// This function decreases the priority of an item to the given value.
    155202      /// \param i The item.
    156203      /// \param p The priority.
    157       /// \pre \c i must be stored in the heap with priority at least \c p.
     204      /// \pre \e i must be stored in the heap with priority at least \e p.
     205#ifdef DOXYGEN
    158206      void decrease(const Item &i, const Prio &p) {}
    159 
    160       /// \brief Increases the priority of an item to the given value.
    161       ///
    162       /// Increases the priority of an item to the given value.
     207#else
     208      void decrease(const Item&, const Prio&) {}
     209#endif
     210
     211      /// \brief Increase the priority of an item to the given value.
     212      ///
     213      /// This function increases the priority of an item to the given value.
    163214      /// \param i The item.
    164215      /// \param p The priority.
    165       /// \pre \c i must be stored in the heap with priority at most \c p.
     216      /// \pre \e i must be stored in the heap with priority at most \e p.
     217#ifdef DOXYGEN
    166218      void increase(const Item &i, const Prio &p) {}
    167 
    168       /// \brief Returns if an item is in, has already been in, or has
    169       /// never been in the heap.
     219#else
     220      void increase(const Item&, const Prio&) {}
     221#endif
     222
     223      /// \brief Return the state of an item.
    170224      ///
    171225      /// This method returns \c PRE_HEAP if the given item has never
    … …  
    175229      /// to the heap again.
    176230      /// \param i The item.
     231#ifdef DOXYGEN
    177232      State state(const Item &i) const {}
    178 
    179       /// \brief Sets the state of an item in the heap.
    180       ///
    181       /// Sets the state of the given item in the heap. It can be used
    182       /// to manually clear the heap when it is important to achive the
    183       /// better time complexity.
     233#else
     234      State state(const Item&) const { return PRE_HEAP; }
     235#endif
     236
     237      /// \brief Set the state of an item in the heap.
     238      ///
     239      /// This function sets the state of the given item in the heap.
     240      /// It can be used to manually clear the heap when it is important
     241      /// to achive better time complexity.
    184242      /// \param i The item.
    185243      /// \param st The state. It should not be \c IN_HEAP.
     244#ifdef DOXYGEN
    186245      void state(const Item& i, State st) {}
     246#else
     247      void state(const Item&, State) {}
     248#endif
    187249
    188250

  • lemon/concepts/path.h

    r785 r976  
    169169        }
    170170        _Path& p;
     171        PathDumperConstraints() {}
    171172      };
    172173
    … …  
    194195        }
    195196        _Path& p;
     197        PathDumperConstraints() {}
    196198      };
    197199

  • lemon/concepts/path.h

    r975 r976  
    1919///\ingroup concept
    2020///\file
    21 ///\brief Classes for representing paths in digraphs.
     21///\brief The concept of paths
    2222///
    2323
    … …  
    3939    /// A skeleton structure for representing directed paths in a
    4040    /// digraph.
     41    /// In a sense, a path can be treated as a list of arcs.
     42    /// LEMON path types just store this list. As a consequence, they cannot
     43    /// enumerate the nodes on the path directly and a zero length path
     44    /// cannot store its source node.
     45    ///
     46    /// The arcs of a path should be stored in the order of their directions,
     47    /// i.e. the target node of each arc should be the same as the source
     48    /// node of the next arc. This consistency could be checked using
     49    /// \ref checkPath().
     50    /// The source and target nodes of a (consistent) path can be obtained
     51    /// using \ref pathSource() and \ref pathTarget().
     52    ///
     53    /// A path can be constructed from another path of any type using the
     54    /// copy constructor or the assignment operator.
     55    ///
    4156    /// \tparam GR The digraph type in which the path is.
    42     ///
    43     /// In a sense, the path can be treated as a list of arcs. The
    44     /// lemon path type stores just this list. As a consequence it
    45     /// cannot enumerate the nodes in the path and the zero length
    46     /// paths cannot store the source.
    47     ///
    4857    template <typename GR>
    4958    class Path {
    … …  
    6069      Path() {}
    6170
    62       /// \brief Template constructor
     71      /// \brief Template copy constructor
    6372      template <typename CPath>
    6473      Path(const CPath& cpath) {}
    6574
    66       /// \brief Template assigment
     75      /// \brief Template assigment operator
    6776      template <typename CPath>
    6877      Path& operator=(const CPath& cpath) {
    … …  
    7180      }
    7281
    73       /// Length of the path ie. the number of arcs in the path.
     82      /// Length of the path, i.e. the number of arcs on the path.
    7483      int length() const { return 0;}
    7584
    … …  
    8089      void clear() {}
    8190
    82       /// \brief LEMON style iterator for path arcs
     91      /// \brief LEMON style iterator for enumerating the arcs of a path.
    8392      ///
    84       /// This class is used to iterate on the arcs of the paths.
     93      /// LEMON style iterator class for enumerating the arcs of a path.
    8594      class ArcIt {
    8695      public:
    … …  
    8998        /// Invalid constructor
    9099        ArcIt(Invalid) {}
    91         /// Constructor for first arc
     100        /// Sets the iterator to the first arc of the given path
    92101        ArcIt(const Path &) {}
    93102
    94         /// Conversion to Arc
     103        /// Conversion to \c Arc
    95104        operator Arc() const { return INVALID; }
    96105
    … …  
    195204    ///
    196205    /// A skeleton structure for path dumpers. The path dumpers are
    197     /// the generalization of the paths. The path dumpers can
    198     /// enumerate the arcs of the path wheter in forward or in
    199     /// backward order.  In most time these classes are not used
    200     /// directly rather it used to assign a dumped class to a real
    201     /// path type.
     206    /// the generalization of the paths, they can enumerate the arcs
     207    /// of the path either in forward or in backward order.
     208    /// These classes are typically not used directly, they are rather
     209    /// used to be assigned to a real path type.
    202210    ///
    203211    /// The main purpose of this concept is that the shortest path
    204     /// algorithms can enumerate easily the arcs in reverse order.
    205     /// If we would like to give back a real path from these
    206     /// algorithms then we should create a temporarly path object. In
    207     /// LEMON such algorithms gives back a path dumper what can
    208     /// assigned to a real path and the dumpers can be implemented as
     212    /// algorithms can enumerate the arcs easily in reverse order.
     213    /// In LEMON, such algorithms give back a (reverse) path dumper that
     214    /// can be assigned to a real path. The dumpers can be implemented as
    209215    /// an adaptor class to the predecessor map.
    210216    ///
    211217    /// \tparam GR The digraph type in which the path is.
    212     ///
    213     /// The paths can be constructed from any path type by a
    214     /// template constructor or a template assignment operator.
    215218    template <typename GR>
    216219    class PathDumper {
    … …  
    222225      typedef typename Digraph::Arc Arc;
    223226
    224       /// Length of the path ie. the number of arcs in the path.
     227      /// Length of the path, i.e. the number of arcs on the path.
    225228      int length() const { return 0;}
    226229
    … …  
    230233      /// \brief Forward or reverse dumping
    231234      ///
    232       /// If the RevPathTag is defined and true then reverse dumping
    233       /// is provided in the path dumper. In this case instead of the
    234       /// ArcIt the RevArcIt iterator should be implemented in the
    235       /// dumper.
     235      /// If this tag is defined to be \c True, then reverse dumping
     236      /// is provided in the path dumper. In this case, \c RevArcIt
     237      /// iterator should be implemented instead of \c ArcIt iterator.
    236238      typedef False RevPathTag;
    237239
    238       /// \brief LEMON style iterator for path arcs
     240      /// \brief LEMON style iterator for enumerating the arcs of a path.
    239241      ///
    240       /// This class is used to iterate on the arcs of the paths.
     242      /// LEMON style iterator class for enumerating the arcs of a path.
    241243      class ArcIt {
    242244      public:
    … …  
    245247        /// Invalid constructor
    246248        ArcIt(Invalid) {}
    247         /// Constructor for first arc
     249        /// Sets the iterator to the first arc of the given path
    248250        ArcIt(const PathDumper&) {}
    249251
    250         /// Conversion to Arc
     252        /// Conversion to \c Arc
    251253        operator Arc() const { return INVALID; }
    252254
    … …  
    263265      };
    264266
    265       /// \brief LEMON style iterator for path arcs
     267      /// \brief LEMON style iterator for enumerating the arcs of a path
     268      /// in reverse direction.
    266269      ///
    267       /// This class is used to iterate on the arcs of the paths in
    268       /// reverse direction.
     270      /// LEMON style iterator class for enumerating the arcs of a path
     271      /// in reverse direction.
    269272      class RevArcIt {
    270273      public:
    … …  
    273276        /// Invalid constructor
    274277        RevArcIt(Invalid) {}
    275         /// Constructor for first arc
     278        /// Sets the iterator to the last arc of the given path
    276279        RevArcIt(const PathDumper &) {}
    277280
    278         /// Conversion to Arc
     281        /// Conversion to \c Arc
    279282        operator Arc() const { return INVALID; }
    280283

  • lemon/dfs.h

    r966 r976  
    11941194      }
    11951195      _Visitor& visitor;
     1196      Constraints() {}
    11961197    };
    11971198  };

  • lemon/dfs.h

    r975 r976  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
    … …  
    4848    ///The type of the map that stores the predecessor
    4949    ///arcs of the %DFS paths.
    50     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     50    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    5151    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    5252    ///Instantiates a \c PredMap.
    … …  
    6363
    6464    ///The type of the map that indicates which nodes are processed.
    65     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     65    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     66    ///By default, it is a NullMap.
    6667    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    6768    ///Instantiates a \c ProcessedMap.
    … …  
    8283
    8384    ///The type of the map that indicates which nodes are reached.
    84     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     85    ///It must conform to
     86    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8587    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    8688    ///Instantiates a \c ReachedMap.
    … …  
    9799
    98100    ///The type of the map that stores the distances of the nodes.
    99     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     101    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    100102    typedef typename Digraph::template NodeMap<int> DistMap;
    101103    ///Instantiates a \c DistMap.
    … …  
    121123  ///\tparam GR The type of the digraph the algorithm runs on.
    122124  ///The default type is \ref ListDigraph.
     125  ///\tparam TR The traits class that defines various types used by the
     126  ///algorithm. By default, it is \ref DfsDefaultTraits
     127  ///"DfsDefaultTraits<GR>".
     128  ///In most cases, this parameter should not be set directly,
     129  ///consider to use the named template parameters instead.
    123130#ifdef DOXYGEN
    124131  template <typename GR,
    … …  
    225232    ///\ref named-templ-param "Named parameter" for setting
    226233    ///\c PredMap type.
    227     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     234    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    228235    template <class T>
    229236    struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
    … …  
    245252    ///\ref named-templ-param "Named parameter" for setting
    246253    ///\c DistMap type.
    247     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     254    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    248255    template <class T>
    249256    struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
    … …  
    265272    ///\ref named-templ-param "Named parameter" for setting
    266273    ///\c ReachedMap type.
    267     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     274    ///It must conform to
     275    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    268276    template <class T>
    269277    struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
    … …  
    285293    ///\ref named-templ-param "Named parameter" for setting
    286294    ///\c ProcessedMap type.
    287     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     295    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    288296    template <class T>
    289297    struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
    … …  
    412420    ///The simplest way to execute the DFS algorithm is to use one of the
    413421    ///member functions called \ref run(Node) "run()".\n
    414     ///If you need more control on the execution, first you have to call
    415     ///\ref init(), then you can add a source node with \ref addSource()
     422    ///If you need better control on the execution, you have to call
     423    ///\ref init() first, then you can add a source node with \ref addSource()
    416424    ///and perform the actual computation with \ref start().
    417425    ///This procedure can be repeated if there are nodes that have not
    … …  
    633641    ///Runs the algorithm to visit all nodes in the digraph.
    634642
    635     ///This method runs the %DFS algorithm in order to compute the
    636     ///%DFS path to each node.
    637     ///
    638     ///The algorithm computes
    639     ///- the %DFS tree (forest),
    640     ///- the distance of each node from the root(s) in the %DFS tree.
     643    ///This method runs the %DFS algorithm in order to visit all nodes
     644    ///in the digraph.
    641645    ///
    642646    ///\note <tt>d.run()</tt> is just a shortcut of the following code.
    … …  
    670674    ///@{
    671675
    672     ///The DFS path to a node.
    673 
    674     ///Returns the DFS path to a node.
     676    ///The DFS path to the given node.
     677
     678    ///Returns the DFS path to the given node from the root(s).
    675679    ///
    676680    ///\warning \c t should be reached from the root(s).
    … …  
    680684    Path path(Node t) const { return Path(*G, *_pred, t); }
    681685
    682     ///The distance of a node from the root(s).
    683 
    684     ///Returns the distance of a node from the root(s).
     686    ///The distance of the given node from the root(s).
     687
     688    ///Returns the distance of the given node from the root(s).
    685689    ///
    686690    ///\warning If node \c v is not reached from the root(s), then
    … …  
    691695    int dist(Node v) const { return (*_dist)[v]; }
    692696
    693     ///Returns the 'previous arc' of the %DFS tree for a node.
     697    ///Returns the 'previous arc' of the %DFS tree for the given node.
    694698
    695699    ///This function returns the 'previous arc' of the %DFS tree for the
    … …  
    699703    ///
    700704    ///The %DFS tree used here is equal to the %DFS tree used in
    701     ///\ref predNode().
     705    ///\ref predNode() and \ref predMap().
    702706    ///
    703707    ///\pre Either \ref run(Node) "run()" or \ref init()
    … …  
    705709    Arc predArc(Node v) const { return (*_pred)[v];}
    706710
    707     ///Returns the 'previous node' of the %DFS tree.
     711    ///Returns the 'previous node' of the %DFS tree for the given node.
    708712
    709713    ///This function returns the 'previous node' of the %DFS
    710714    ///tree for the node \c v, i.e. it returns the last but one node
    711     ///from a %DFS path from a root to \c v. It is \c INVALID
     715    ///of a %DFS path from a root to \c v. It is \c INVALID
    712716    ///if \c v is not reached from the root(s) or if \c v is a root.
    713717    ///
    714718    ///The %DFS tree used here is equal to the %DFS tree used in
    715     ///\ref predArc().
     719    ///\ref predArc() and \ref predMap().
    716720    ///
    717721    ///\pre Either \ref run(Node) "run()" or \ref init()
    … …  
    734738    ///
    735739    ///Returns a const reference to the node map that stores the predecessor
    736     ///arcs, which form the DFS tree.
     740    ///arcs, which form the DFS tree (forest).
    737741    ///
    738742    ///\pre Either \ref run(Node) "run()" or \ref init()
    … …  
    740744    const PredMap &predMap() const { return *_pred;}
    741745
    742     ///Checks if a node is reached from the root(s).
     746    ///Checks if the given node. node is reached from the root(s).
    743747
    744748    ///Returns \c true if \c v is reached from the root(s).
    … …  
    766770    ///The type of the map that stores the predecessor
    767771    ///arcs of the %DFS paths.
    768     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     772    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    769773    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    770774    ///Instantiates a PredMap.
    … …  
    781785
    782786    ///The type of the map that indicates which nodes are processed.
    783     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    784     ///By default it is a NullMap.
     787    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
     788    ///By default, it is a NullMap.
    785789    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    786790    ///Instantiates a ProcessedMap.
    … …  
    801805
    802806    ///The type of the map that indicates which nodes are reached.
    803     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     807    ///It must conform to
     808    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    804809    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    805810    ///Instantiates a ReachedMap.
    … …  
    816821
    817822    ///The type of the map that stores the distances of the nodes.
    818     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     823    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    819824    typedef typename Digraph::template NodeMap<int> DistMap;
    820825    ///Instantiates a DistMap.
    … …  
    831836
    832837    ///The type of the DFS paths.
    833     ///It must meet the \ref concepts::Path "Path" concept.
     838    ///It must conform to the \ref concepts::Path "Path" concept.
    834839    typedef lemon::Path<Digraph> Path;
    835840  };
    … …  
    837842  /// Default traits class used by DfsWizard
    838843
    839   /// To make it easier to use Dfs algorithm
    840   /// we have created a wizard class.
    841   /// This \ref DfsWizard class needs default traits,
    842   /// as well as the \ref Dfs class.
    843   /// The \ref DfsWizardBase is a class to be the default traits of the
    844   /// \ref DfsWizard class.
     844  /// Default traits class used by DfsWizard.
     845  /// \tparam GR The type of the digraph.
    845846  template<class GR>
    846847  class DfsWizardBase : public DfsWizardDefaultTraits<GR>
    … …  
    870871    /// Constructor.
    871872
    872     /// This constructor does not require parameters, therefore it initiates
     873    /// This constructor does not require parameters, it initiates
    873874    /// all of the attributes to \c 0.
    874875    DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
    … …  
    895896  /// This class should only be used through the \ref dfs() function,
    896897  /// which makes it easier to use the algorithm.
     898  ///
     899  /// \tparam TR The traits class that defines various types used by the
     900  /// algorithm.
    897901  template<class TR>
    898902  class DfsWizard : public TR
    … …  
    900904    typedef TR Base;
    901905
    902     ///The type of the digraph the algorithm runs on.
    903906    typedef typename TR::Digraph Digraph;
    904907
    … …  
    908911    typedef typename Digraph::OutArcIt OutArcIt;
    909912
    910     ///\brief The type of the map that stores the predecessor
    911     ///arcs of the DFS paths.
    912913    typedef typename TR::PredMap PredMap;
    913     ///\brief The type of the map that stores the distances of the nodes.
    914914    typedef typename TR::DistMap DistMap;
    915     ///\brief The type of the map that indicates which nodes are reached.
    916915    typedef typename TR::ReachedMap ReachedMap;
    917     ///\brief The type of the map that indicates which nodes are processed.
    918916    typedef typename TR::ProcessedMap ProcessedMap;
    919     ///The type of the DFS paths
    920917    typedef typename TR::Path Path;
    921918
    … …  
    987984    ///Runs DFS algorithm to visit all nodes in the digraph.
    988985
    989     ///This method runs DFS algorithm in order to compute
    990     ///the DFS path to each node.
     986    ///This method runs DFS algorithm in order to visit all nodes
     987    ///in the digraph.
    991988    void run()
    992989    {
    … …  
    1000997      SetPredMapBase(const TR &b) : TR(b) {}
    1001998    };
    1002     ///\brief \ref named-func-param "Named parameter"
    1003     ///for setting PredMap object.
    1004     ///
    1005     ///\ref named-func-param "Named parameter"
    1006     ///for setting PredMap object.
     999
     1000    ///\brief \ref named-templ-param "Named parameter" for setting
     1001    ///the predecessor map.
     1002    ///
     1003    ///\ref named-templ-param "Named parameter" function for setting
     1004    ///the map that stores the predecessor arcs of the nodes.
    10071005    template<class T>
    10081006    DfsWizard<SetPredMapBase<T> > predMap(const T &t)
    … …  
    10181016      SetReachedMapBase(const TR &b) : TR(b) {}
    10191017    };
    1020     ///\brief \ref named-func-param "Named parameter"
    1021     ///for setting ReachedMap object.
    1022     ///
    1023     /// \ref named-func-param "Named parameter"
    1024     ///for setting ReachedMap object.
     1018
     1019    ///\brief \ref named-templ-param "Named parameter" for setting
     1020    ///the reached map.
     1021    ///
     1022    ///\ref named-templ-param "Named parameter" function for setting
     1023    ///the map that indicates which nodes are reached.
    10251024    template<class T>
    10261025    DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
    … …  
    10361035      SetDistMapBase(const TR &b) : TR(b) {}
    10371036    };
    1038     ///\brief \ref named-func-param "Named parameter"
    1039     ///for setting DistMap object.
    1040     ///
    1041     /// \ref named-func-param "Named parameter"
    1042     ///for setting DistMap object.
     1037
     1038    ///\brief \ref named-templ-param "Named parameter" for setting
     1039    ///the distance map.
     1040    ///
     1041    ///\ref named-templ-param "Named parameter" function for setting
     1042    ///the map that stores the distances of the nodes calculated
     1043    ///by the algorithm.
    10431044    template<class T>
    10441045    DfsWizard<SetDistMapBase<T> > distMap(const T &t)
    … …  
    10541055      SetProcessedMapBase(const TR &b) : TR(b) {}
    10551056    };
    1056     ///\brief \ref named-func-param "Named parameter"
    1057     ///for setting ProcessedMap object.
    1058     ///
    1059     /// \ref named-func-param "Named parameter"
    1060     ///for setting ProcessedMap object.
     1057
     1058    ///\brief \ref named-func-param "Named parameter" for setting
     1059    ///the processed map.
     1060    ///
     1061    ///\ref named-templ-param "Named parameter" function for setting
     1062    ///the map that indicates which nodes are processed.
    10611063    template<class T>
    10621064    DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
    … …  
    12101212    ///
    12111213    /// The type of the map that indicates which nodes are reached.
    1212     /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     1214    /// It must conform to the
     1215    /// \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    12131216    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    12141217
    … …  
    12481251  /// does not observe the DFS events. If you want to observe the DFS
    12491252  /// events, you should implement your own visitor class.
    1250   /// \tparam TR Traits class to set various data types used by the
    1251   /// algorithm. The default traits class is
    1252   /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<GR>".
    1253   /// See \ref DfsVisitDefaultTraits for the documentation of
    1254   /// a DFS visit traits class.
     1253  /// \tparam TR The traits class that defines various types used by the
     1254  /// algorithm. By default, it is \ref DfsVisitDefaultTraits
     1255  /// "DfsVisitDefaultTraits<GR>".
     1256  /// In most cases, this parameter should not be set directly,
     1257  /// consider to use the named template parameters instead.
    12551258#ifdef DOXYGEN
    12561259  template <typename GR, typename VS, typename TR>
    … …  
    13711374    /// The simplest way to execute the DFS algorithm is to use one of the
    13721375    /// member functions called \ref run(Node) "run()".\n
    1373     /// If you need more control on the execution, first you have to call
    1374     /// \ref init(), then you can add a source node with \ref addSource()
     1376    /// If you need better control on the execution, you have to call
     1377    /// \ref init() first, then you can add a source node with \ref addSource()
    13751378    /// and perform the actual computation with \ref start().
    13761379    /// This procedure can be repeated if there are nodes that have not
    … …  
    15851588    /// \brief Runs the algorithm to visit all nodes in the digraph.
    15861589
    1587     /// This method runs the %DFS algorithm in order to
    1588     /// compute the %DFS path to each node.
    1589     ///
    1590     /// The algorithm computes
    1591     /// - the %DFS tree (forest),
    1592     /// - the distance of each node from the root(s) in the %DFS tree.
     1590    /// This method runs the %DFS algorithm in order to visit all nodes
     1591    /// in the digraph.
    15931592    ///
    15941593    /// \note <tt>d.run()</tt> is just a shortcut of the following code.
    … …  
    16221621    ///@{
    16231622
    1624     /// \brief Checks if a node is reached from the root(s).
     1623    /// \brief Checks if the given node is reached from the root(s).
    16251624    ///
    16261625    /// Returns \c true if \c v is reached from the root(s).
Note: See TracChangeset for help on using the changeset viewer.