COIN-OR::LEMON - Graph Library

Changeset 964:7fdaa05a69a1 in lemon-1.2


Ignore:
Timestamp:
09/13/12 11:56:19 (7 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Parents:
961:4bb9e72e1a41 (diff), 963:761fe0846f49 (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 #449 to branches >=1.2

Files:
54 edited

Legend:

Unmodified
Added
Removed
  • CMakeLists.txt

    r942 r964  
    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

    r953 r964  
    115115SET(LEMON_HAVE_LONG_LONG ${HAVE_LONG_LONG})
    116116
     117INCLUDE(FindPythonInterp)
     118
    117119ENABLE_TESTING()
    118120
  • lemon/adaptors.h

    r877 r964  
    13721372    /// and edge filter maps.
    13731373    SubGraph(GR& graph, NF& node_filter, EF& edge_filter) {
    1374       initialize(graph, node_filter, edge_filter);
     1374      this->initialize(graph, node_filter, edge_filter);
    13751375    }
    13761376
     
    22782278    /// Creates an undirected graph from the given digraph.
    22792279    Undirector(DGR& digraph) {
    2280       initialize(digraph);
     2280      this->initialize(digraph);
    22812281    }
    22822282
  • lemon/adaptors.h

    r963 r964  
    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).
     
    361361  /// parameter is set to be \c const.
    362362  ///
     363  /// This class provides item counting in the same time as the adapted
     364  /// digraph structure.
     365  ///
    363366  /// \tparam DGR The type of the adapted digraph.
    364367  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
     
    419422      Parent::initialize(digraph);
    420423      _node_filter = &node_filter;
    421       _arc_filter = &arc_filter;     
     424      _arc_filter = &arc_filter;
    422425    }
    423426
     
    506509
    507510    template <typename V>
    508     class NodeMap 
    509       : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>, 
    510               LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
     511    class NodeMap
     512      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
     513              LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
    511514      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    512         LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
     515        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
    513516
    514517    public:
     
    533536
    534537    template <typename V>
    535     class ArcMap 
     538    class ArcMap
    536539      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    537               LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
     540              LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
    538541      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
    539542        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
     
    580583      Parent::initialize(digraph);
    581584      _node_filter = &node_filter;
    582       _arc_filter = &arc_filter;     
     585      _arc_filter = &arc_filter;
    583586    }
    584587
     
    649652
    650653    template <typename V>
    651     class NodeMap 
     654    class NodeMap
    652655      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    653656          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
    654       typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>, 
     657      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    655658        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
    656659
     
    676679
    677680    template <typename V>
    678     class ArcMap 
     681    class ArcMap
    679682      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
    680683          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
     
    719722  /// by adding or removing nodes or arcs, unless the \c GR template
    720723  /// parameter is set to be \c const.
     724  ///
     725  /// This class provides only linear time counting for nodes and arcs.
    721726  ///
    722727  /// \tparam DGR The type of the adapted digraph.
     
    10171022
    10181023    template <typename V>
    1019     class NodeMap 
     1024    class NodeMap
    10201025      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10211026          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
    1022       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
     1027      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10231028        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
    10241029
     
    10441049
    10451050    template <typename V>
    1046     class ArcMap 
     1051    class ArcMap
    10471052      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10481053          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
    1049       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
     1054      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10501055        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
    10511056
     
    10711076
    10721077    template <typename V>
    1073     class EdgeMap 
     1078    class EdgeMap
    10741079      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10751080        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
    1076       typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>, 
     1081      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
    10771082        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
    10781083
     
    11131118    NF* _node_filter;
    11141119    EF* _edge_filter;
    1115     SubGraphBase() 
    1116           : Parent(), _node_filter(0), _edge_filter(0) { }
     1120    SubGraphBase()
     1121          : Parent(), _node_filter(0), _edge_filter(0) { }
    11171122
    11181123    void initialize(GR& graph, NF& node_filter, EF& edge_filter) {
     
    12151220
    12161221    template <typename V>
    1217     class NodeMap 
     1222    class NodeMap
    12181223      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12191224          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
    1220       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
     1225      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12211226        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
    12221227
     
    12421247
    12431248    template <typename V>
    1244     class ArcMap 
     1249    class ArcMap
    12451250      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12461251          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
    1247       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
     1252      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12481253        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
    12491254
     
    12691274
    12701275    template <typename V>
    1271     class EdgeMap 
     1276    class EdgeMap
    12721277      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
    12731278        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
    1274       typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>, 
    1275         LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
     1279      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
     1280        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
    12761281
    12771282    public:
     
    13141319  /// by adding or removing nodes or edges, unless the \c GR template
    13151320  /// parameter is set to be \c const.
     1321  ///
     1322  /// This class provides only linear time counting for nodes, edges and arcs.
    13161323  ///
    13171324  /// \tparam GR The type of the adapted graph.
     
    14711478  /// by adding or removing nodes or arcs/edges, unless the \c GR template
    14721479  /// parameter is set to be \c const.
     1480  ///
     1481  /// This class provides only linear time item counting.
    14731482  ///
    14741483  /// \tparam GR The type of the adapted digraph or graph.
     
    14961505#endif
    14971506    typedef DigraphAdaptorExtender<
    1498       SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >, 
     1507      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
    14991508                     true> > Parent;
    15001509
     
    15171526    /// Creates a subgraph for the given digraph or graph with the
    15181527    /// given node filter map.
    1519     FilterNodes(GR& graph, NF& node_filter) 
     1528    FilterNodes(GR& graph, NF& node_filter)
    15201529      : Parent(), const_true_map()
    15211530    {
     
    15551564                    typename enable_if<UndirectedTagIndicator<GR> >::type> :
    15561565    public GraphAdaptorExtender<
    1557       SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 
     1566      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
    15581567                   true> > {
    15591568
    15601569    typedef GraphAdaptorExtender<
    1561       SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >, 
     1570      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
    15621571                   true> > Parent;
    15631572
     
    16191628  /// by adding or removing nodes or arcs, unless the \c GR template
    16201629  /// parameter is set to be \c const.
     1630  ///
     1631  /// This class provides only linear time counting for nodes and arcs.
    16211632  ///
    16221633  /// \tparam DGR The type of the adapted digraph.
     
    16431654#endif
    16441655    typedef DigraphAdaptorExtender<
    1645       SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >, 
     1656      SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
    16461657                     AF, false> > Parent;
    16471658
     
    17291740  /// by adding or removing nodes or edges, unless the \c GR template
    17301741  /// parameter is set to be \c const.
     1742  ///
     1743  /// This class provides only linear time counting for nodes, edges and arcs.
    17311744  ///
    17321745  /// \tparam GR The type of the adapted graph.
     
    17491762  class FilterEdges :
    17501763    public GraphAdaptorExtender<
    1751       SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >, 
     1764      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >,
    17521765                   EF, false> > {
    17531766#endif
    17541767    typedef GraphAdaptorExtender<
    1755       SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >, 
     1768      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >,
    17561769                   EF, false> > Parent;
    17571770
     
    17781791    /// Creates a subgraph for the given graph with the given edge
    17791792    /// filter map.
    1780     FilterEdges(GR& graph, EF& edge_filter) 
     1793    FilterEdges(GR& graph, EF& edge_filter)
    17811794      : Parent(), const_true_map() {
    17821795      Parent::initialize(graph, const_true_map, edge_filter);
     
    18461859      bool _forward;
    18471860
    1848       Arc(const Edge& edge, bool forward) 
     1861      Arc(const Edge& edge, bool forward)
    18491862        : _edge(edge), _forward(forward) {}
    18501863
     
    20862099
    20872100      ArcMapBase(const UndirectorBase<DGR>& adaptor, const V& value)
    2088         : _forward(*adaptor._digraph, value), 
     2101        : _forward(*adaptor._digraph, value),
    20892102          _backward(*adaptor._digraph, value) {}
    20902103
     
    22042217    typedef typename ItemSetTraits<DGR, Edge>::ItemNotifier EdgeNotifier;
    22052218    EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
    2206    
     2219
    22072220    typedef EdgeNotifier ArcNotifier;
    22082221    ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); }
     
    22322245  /// by adding or removing nodes or edges, unless the \c GR template
    22332246  /// parameter is set to be \c const.
     2247  ///
     2248  /// This class provides item counting in the same time as the adapted
     2249  /// digraph structure.
    22342250  ///
    22352251  /// \tparam DGR The type of the adapted digraph.
     
    25352551  /// by adding or removing nodes or arcs, unless the \c GR template
    25362552  /// parameter is set to be \c const.
     2553  ///
     2554  /// This class provides item counting in the same time as the adapted
     2555  /// graph structure.
    25372556  ///
    25382557  /// \tparam GR The type of the adapted graph.
     
    26792698  /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
    26802699  ///
     2700  /// This class provides only linear time counting for nodes and arcs.
     2701  ///
    26812702  /// \tparam DGR The type of the adapted digraph.
    26822703  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
     
    27082729           typename FM = CM,
    27092730           typename TL = Tolerance<typename CM::Value> >
    2710   class ResidualDigraph 
     2731  class ResidualDigraph
    27112732    : public SubDigraph<
    27122733        Undirector<const DGR>,
     
    27652786    ResidualDigraph(const DGR& digraph, const CM& capacity,
    27662787                    FM& flow, const TL& tolerance = Tolerance())
    2767       : Parent(), _capacity(&capacity), _flow(&flow), 
     2788      : Parent(), _capacity(&capacity), _flow(&flow),
    27682789        _graph(digraph), _node_filter(),
    27692790        _forward_filter(capacity, flow, tolerance),
     
    28472868
    28482869      /// Constructor
    2849       ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor) 
     2870      ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor)
    28502871        : _adaptor(&adaptor) {}
    28512872
     
    33263347  /// in the adaptor.
    33273348  ///
     3349  /// This class provides item counting in the same time as the adapted
     3350  /// digraph structure.
     3351  ///
    33283352  /// \tparam DGR The type of the adapted digraph.
    33293353  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
     
    34243448    /// to get a node map of the split digraph.
    34253449    /// Its value type is inherited from the first node map type (\c IN).
    3426     /// \tparam IN The type of the node map for the in-nodes. 
     3450    /// \tparam IN The type of the node map for the in-nodes.
    34273451    /// \tparam OUT The type of the node map for the out-nodes.
    34283452    template <typename IN, typename OUT>
  • lemon/bfs.h

    r877 r954  
    12521252      }
    12531253      _Visitor& visitor;
     1254      Constraints() {}
    12541255    };
    12551256  };
  • lemon/bfs.h

    r953 r954  
    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/bits/edge_set_extender.h

    r942 r964  
    524524    // Returns the base node of the iterator
    525525    Node baseNode(const IncEdgeIt &e) const {
    526       return e.direction ? u(e) : v(e);
     526      return e.direction ? this->u(e) : this->v(e);
    527527    }
    528528    // Running node of the iterator
     
    530530    // Returns the running node of the iterator
    531531    Node runningNode(const IncEdgeIt &e) const {
    532       return e.direction ? v(e) : u(e);
     532      return e.direction ? this->v(e) : this->u(e);
    533533    }
    534534
  • lemon/bits/edge_set_extender.h

    r963 r964  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    6464    Node oppositeNode(const Node &n, const Arc &e) const {
    6565      if (n == Parent::source(e))
    66         return Parent::target(e);
     66        return Parent::target(e);
    6767      else if(n==Parent::target(e))
    68         return Parent::source(e);
     68        return Parent::source(e);
    6969      else
    70         return INVALID;
     70        return INVALID;
    7171    }
    7272
     
    9292    // Iterable extensions
    9393
    94     class NodeIt : public Node { 
     94    class NodeIt : public Node {
    9595      const Digraph* digraph;
    9696    public:
     
    101101
    102102      explicit NodeIt(const Digraph& _graph) : digraph(&_graph) {
    103         _graph.first(static_cast<Node&>(*this));
    104       }
    105 
    106       NodeIt(const Digraph& _graph, const Node& node) 
    107         : Node(node), digraph(&_graph) {}
    108 
    109       NodeIt& operator++() { 
    110         digraph->next(*this);
    111         return *this;
    112       }
    113 
    114     };
    115 
    116 
    117     class ArcIt : public Arc { 
     103        _graph.first(static_cast<Node&>(*this));
     104      }
     105
     106      NodeIt(const Digraph& _graph, const Node& node)
     107        : Node(node), digraph(&_graph) {}
     108
     109      NodeIt& operator++() {
     110        digraph->next(*this);
     111        return *this;
     112      }
     113
     114    };
     115
     116
     117    class ArcIt : public Arc {
    118118      const Digraph* digraph;
    119119    public:
     
    124124
    125125      explicit ArcIt(const Digraph& _graph) : digraph(&_graph) {
    126         _graph.first(static_cast<Arc&>(*this));
    127       }
    128 
    129       ArcIt(const Digraph& _graph, const Arc& e) : 
    130         Arc(e), digraph(&_graph) { }
    131 
    132       ArcIt& operator++() { 
    133         digraph->next(*this);
    134         return *this;
    135       }
    136 
    137     };
    138 
    139 
    140     class OutArcIt : public Arc { 
     126        _graph.first(static_cast<Arc&>(*this));
     127      }
     128
     129      ArcIt(const Digraph& _graph, const Arc& e) :
     130        Arc(e), digraph(&_graph) { }
     131
     132      ArcIt& operator++() {
     133        digraph->next(*this);
     134        return *this;
     135      }
     136
     137    };
     138
     139
     140    class OutArcIt : public Arc {
    141141      const Digraph* digraph;
    142142    public:
     
    146146      OutArcIt(Invalid i) : Arc(i) { }
    147147
    148       OutArcIt(const Digraph& _graph, const Node& node) 
    149         : digraph(&_graph) {
    150         _graph.firstOut(*this, node);
    151       }
    152 
    153       OutArcIt(const Digraph& _graph, const Arc& arc) 
    154         : Arc(arc), digraph(&_graph) {}
    155 
    156       OutArcIt& operator++() { 
    157         digraph->nextOut(*this);
    158         return *this;
    159       }
    160 
    161     };
    162 
    163 
    164     class InArcIt : public Arc { 
     148      OutArcIt(const Digraph& _graph, const Node& node)
     149        : digraph(&_graph) {
     150        _graph.firstOut(*this, node);
     151      }
     152
     153      OutArcIt(const Digraph& _graph, const Arc& arc)
     154        : Arc(arc), digraph(&_graph) {}
     155
     156      OutArcIt& operator++() {
     157        digraph->nextOut(*this);
     158        return *this;
     159      }
     160
     161    };
     162
     163
     164    class InArcIt : public Arc {
    165165      const Digraph* digraph;
    166166    public:
     
    170170      InArcIt(Invalid i) : Arc(i) { }
    171171
    172       InArcIt(const Digraph& _graph, const Node& node) 
    173         : digraph(&_graph) {
    174         _graph.firstIn(*this, node);
    175       }
    176 
    177       InArcIt(const Digraph& _graph, const Arc& arc) : 
    178         Arc(arc), digraph(&_graph) {}
    179 
    180       InArcIt& operator++() { 
    181         digraph->nextIn(*this);
    182         return *this;
     172      InArcIt(const Digraph& _graph, const Node& node)
     173        : digraph(&_graph) {
     174        _graph.firstIn(*this, node);
     175      }
     176
     177      InArcIt(const Digraph& _graph, const Arc& arc) :
     178        Arc(arc), digraph(&_graph) {}
     179
     180      InArcIt& operator++() {
     181        digraph->nextIn(*this);
     182        return *this;
    183183      }
    184184
     
    216216
    217217    // Mappable extension
    218    
     218
    219219    template <typename _Value>
    220     class ArcMap 
     220    class ArcMap
    221221      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
    222222      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
    223223
    224224    public:
    225       explicit ArcMap(const Digraph& _g) 
    226         : Parent(_g) {}
    227       ArcMap(const Digraph& _g, const _Value& _v) 
    228         : Parent(_g, _v) {}
     225      explicit ArcMap(const Digraph& _g)
     226        : Parent(_g) {}
     227      ArcMap(const Digraph& _g, const _Value& _v)
     228        : Parent(_g, _v) {}
    229229
    230230      ArcMap& operator=(const ArcMap& cmap) {
    231         return operator=<ArcMap>(cmap);
     231        return operator=<ArcMap>(cmap);
    232232      }
    233233
     
    235235      ArcMap& operator=(const CMap& cmap) {
    236236        Parent::operator=(cmap);
    237         return *this;
     237        return *this;
    238238      }
    239239
     
    248248      return arc;
    249249    }
    250    
     250
    251251    void clear() {
    252252      notifier(Arc()).clear();
     
    313313    Node oppositeNode(const Node &n, const Edge &e) const {
    314314      if( n == Parent::u(e))
    315         return Parent::v(e);
     315        return Parent::v(e);
    316316      else if( n == Parent::v(e))
    317         return Parent::u(e);
     317        return Parent::u(e);
    318318      else
    319         return INVALID;
     319        return INVALID;
    320320    }
    321321
     
    341341
    342342    using Parent::notifier;
    343    
     343
    344344    ArcNotifier& notifier(Arc) const {
    345345      return arc_notifier;
     
    351351
    352352
    353     class NodeIt : public Node { 
     353    class NodeIt : public Node {
    354354      const Graph* graph;
    355355    public:
     
    360360
    361361      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
    362         _graph.first(static_cast<Node&>(*this));
    363       }
    364 
    365       NodeIt(const Graph& _graph, const Node& node) 
    366         : Node(node), graph(&_graph) {}
    367 
    368       NodeIt& operator++() { 
    369         graph->next(*this);
    370         return *this;
    371       }
    372 
    373     };
    374 
    375 
    376     class ArcIt : public Arc { 
     362        _graph.first(static_cast<Node&>(*this));
     363      }
     364
     365      NodeIt(const Graph& _graph, const Node& node)
     366        : Node(node), graph(&_graph) {}
     367
     368      NodeIt& operator++() {
     369        graph->next(*this);
     370        return *this;
     371      }
     372
     373    };
     374
     375
     376    class ArcIt : public Arc {
    377377      const Graph* graph;
    378378    public:
     
    383383
    384384      explicit ArcIt(const Graph& _graph) : graph(&_graph) {
    385         _graph.first(static_cast<Arc&>(*this));
    386       }
    387 
    388       ArcIt(const Graph& _graph, const Arc& e) : 
    389         Arc(e), graph(&_graph) { }
    390 
    391       ArcIt& operator++() { 
    392         graph->next(*this);
    393         return *this;
    394       }
    395 
    396     };
    397 
    398 
    399     class OutArcIt : public Arc { 
     385        _graph.first(static_cast<Arc&>(*this));
     386      }
     387
     388      ArcIt(const Graph& _graph, const Arc& e) :
     389        Arc(e), graph(&_graph) { }
     390
     391      ArcIt& operator++() {
     392        graph->next(*this);
     393        return *this;
     394      }
     395
     396    };
     397
     398
     399    class OutArcIt : public Arc {
    400400      const Graph* graph;
    401401    public:
     
    405405      OutArcIt(Invalid i) : Arc(i) { }
    406406
    407       OutArcIt(const Graph& _graph, const Node& node) 
    408         : graph(&_graph) {
    409         _graph.firstOut(*this, node);
    410       }
    411 
    412       OutArcIt(const Graph& _graph, const Arc& arc) 
    413         : Arc(arc), graph(&_graph) {}
    414 
    415       OutArcIt& operator++() { 
    416         graph->nextOut(*this);
    417         return *this;
    418       }
    419 
    420     };
    421 
    422 
    423     class InArcIt : public Arc { 
     407      OutArcIt(const Graph& _graph, const Node& node)
     408        : graph(&_graph) {
     409        _graph.firstOut(*this, node);
     410      }
     411
     412      OutArcIt(const Graph& _graph, const Arc& arc)
     413        : Arc(arc), graph(&_graph) {}
     414
     415      OutArcIt& operator++() {
     416        graph->nextOut(*this);
     417        return *this;
     418      }
     419
     420    };
     421
     422
     423    class InArcIt : public Arc {
    424424      const Graph* graph;
    425425    public:
     
    429429      InArcIt(Invalid i) : Arc(i) { }
    430430
    431       InArcIt(const Graph& _graph, const Node& node) 
    432         : graph(&_graph) {
    433         _graph.firstIn(*this, node);
    434       }
    435 
    436       InArcIt(const Graph& _graph, const Arc& arc) : 
    437         Arc(arc), graph(&_graph) {}
    438 
    439       InArcIt& operator++() { 
    440         graph->nextIn(*this);
    441         return *this;
    442       }
    443 
    444     };
    445 
    446 
    447     class EdgeIt : public Parent::Edge { 
     431      InArcIt(const Graph& _graph, const Node& node)
     432        : graph(&_graph) {
     433        _graph.firstIn(*this, node);
     434      }
     435
     436      InArcIt(const Graph& _graph, const Arc& arc) :
     437        Arc(arc), graph(&_graph) {}
     438
     439      InArcIt& operator++() {
     440        graph->nextIn(*this);
     441        return *this;
     442      }
     443
     444    };
     445
     446
     447    class EdgeIt : public Parent::Edge {
    448448      const Graph* graph;
    449449    public:
     
    454454
    455455      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
    456         _graph.first(static_cast<Edge&>(*this));
    457       }
    458 
    459       EdgeIt(const Graph& _graph, const Edge& e) : 
    460         Edge(e), graph(&_graph) { }
    461 
    462       EdgeIt& operator++() { 
    463         graph->next(*this);
    464         return *this;
     456        _graph.first(static_cast<Edge&>(*this));
     457      }
     458
     459      EdgeIt(const Graph& _graph, const Edge& e) :
     460        Edge(e), graph(&_graph) { }
     461
     462      EdgeIt& operator++() {
     463        graph->next(*this);
     464        return *this;
    465465      }
    466466
     
    478478
    479479      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
    480         _graph.firstInc(*this, direction, n);
     480        _graph.firstInc(*this, direction, n);
    481481      }
    482482
    483483      IncEdgeIt(const Graph& _graph, const Edge &ue, const Node &n)
    484         : graph(&_graph), Edge(ue) {
    485         direction = (_graph.source(ue) == n);
     484        : graph(&_graph), Edge(ue) {
     485        direction = (_graph.source(ue) == n);
    486486      }
    487487
    488488      IncEdgeIt& operator++() {
    489         graph->nextInc(*this, direction);
    490         return *this;
     489        graph->nextInc(*this, direction);
     490        return *this;
    491491      }
    492492    };
     
    535535
    536536    template <typename _Value>
    537     class ArcMap 
     537    class ArcMap
    538538      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
    539539      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
    540540
    541541    public:
    542       explicit ArcMap(const Graph& _g) 
    543         : Parent(_g) {}
    544       ArcMap(const Graph& _g, const _Value& _v) 
    545         : Parent(_g, _v) {}
     542      explicit ArcMap(const Graph& _g)
     543        : Parent(_g) {}
     544      ArcMap(const Graph& _g, const _Value& _v)
     545        : Parent(_g, _v) {}
    546546
    547547      ArcMap& operator=(const ArcMap& cmap) {
    548         return operator=<ArcMap>(cmap);
     548        return operator=<ArcMap>(cmap);
    549549      }
    550550
     
    552552      ArcMap& operator=(const CMap& cmap) {
    553553        Parent::operator=(cmap);
    554         return *this;
     554        return *this;
    555555      }
    556556
     
    559559
    560560    template <typename _Value>
    561     class EdgeMap 
     561    class EdgeMap
    562562      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
    563563      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
    564564
    565565    public:
    566       explicit EdgeMap(const Graph& _g) 
    567         : Parent(_g) {}
    568 
    569       EdgeMap(const Graph& _g, const _Value& _v) 
    570         : Parent(_g, _v) {}
     566      explicit EdgeMap(const Graph& _g)
     567        : Parent(_g) {}
     568
     569      EdgeMap(const Graph& _g, const _Value& _v)
     570        : Parent(_g, _v) {}
    571571
    572572      EdgeMap& operator=(const EdgeMap& cmap) {
    573         return operator=<EdgeMap>(cmap);
     573        return operator=<EdgeMap>(cmap);
    574574      }
    575575
     
    577577      EdgeMap& operator=(const CMap& cmap) {
    578578        Parent::operator=(cmap);
    579         return *this;
     579        return *this;
    580580      }
    581581
     
    594594      return edge;
    595595    }
    596    
     596
    597597    void clear() {
    598598      notifier(Arc()).clear();
     
    620620      arc_notifier.clear();
    621621    }
    622    
     622
    623623  };
    624624
  • lemon/bits/graph_extender.h

    r778 r964  
    588588    // Returns the base node of the iterator
    589589    Node baseNode(const IncEdgeIt &edge) const {
    590       return edge._direction ? u(edge) : v(edge);
     590      return edge._direction ? this->u(edge) : this->v(edge);
    591591    }
    592592    // Running node of the iterator
     
    594594    // Returns the running node of the iterator
    595595    Node runningNode(const IncEdgeIt &edge) const {
    596       return edge._direction ? v(edge) : u(edge);
     596      return edge._direction ? this->v(edge) : this->u(edge);
    597597    }
    598598
  • lemon/bits/graph_extender.h

    r963 r964  
    5757    }
    5858
    59     Node fromId(int id, Node) const {
     59    static Node fromId(int id, Node) {
    6060      return Parent::nodeFromId(id);
    6161    }
    6262
    63     Arc fromId(int id, Arc) const {
     63    static Arc fromId(int id, Arc) {
    6464      return Parent::arcFromId(id);
    6565    }
     
    356356    }
    357357
    358     Node fromId(int id, Node) const {
     358    static Node fromId(int id, Node) {
    359359      return Parent::nodeFromId(id);
    360360    }
    361361
    362     Arc fromId(int id, Arc) const {
     362    static Arc fromId(int id, Arc) {
    363363      return Parent::arcFromId(id);
    364364    }
    365365
    366     Edge fromId(int id, Edge) const {
     366    static Edge fromId(int id, Edge) {
    367367      return Parent::edgeFromId(id);
    368368    }
  • lemon/bits/solver_bits.h

    r877 r956  
    4545      void clear() {
    4646        first_item = -1;
     47        last_item = -1;
    4748        first_free_item = -1;
    4849        items.clear();
  • lemon/bits/solver_bits.h

    r955 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/cbc.cc

    r746 r964  
    2626#include <coin/OsiSolverInterface.hpp>
    2727
    28 #ifdef COIN_HAS_CLP
    2928#include "coin/OsiClpSolverInterface.hpp"
    30 #endif
    31 #ifdef COIN_HAS_OSL
    32 #include "coin/OsiOslSolverInterface.hpp"
    33 #endif
    3429
    3530#include "coin/CbcCutGenerator.hpp"
     
    271266      delete _osi_solver;
    272267    }
    273 #ifdef COIN_HAS_CLP
    274268    _osi_solver = new OsiClpSolverInterface();
    275 #elif COIN_HAS_OSL
    276     _osi_solver = new OsiOslSolverInterface();
    277 #else
    278 #error Cannot instantiate Osi solver
    279 #endif
    280269
    281270    _osi_solver->loadFromCoinModel(*_prob);
     
    329318      _cbc_model->addCutGenerator(&flowGen, -1, "FlowCover");
    330319
    331 #ifdef COIN_HAS_CLP
    332320      OsiClpSolverInterface* osiclp =
    333321        dynamic_cast<OsiClpSolverInterface*>(_cbc_model->solver());
     
    335323        osiclp->setupForRepeatedUse(2, 0);
    336324      }
    337 #endif
    338325
    339326      CbcRounding heuristic1(*_cbc_model);
     
    449436
    450437    _prob = new CoinModel();
    451     rows.clear();
    452     cols.clear();
    453438  }
    454439
  • lemon/cbc.cc

    r955 r964  
    9090  }
    9191
     92  int CbcMip::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
     93    std::vector<int> indexes;
     94    std::vector<Value> values;
     95
     96    for(ExprIterator it = b; it != e; ++it) {
     97      indexes.push_back(it->first);
     98      values.push_back(it->second);
     99    }
     100
     101    _prob->addRow(values.size(), &indexes.front(), &values.front(), l, u);
     102    return _prob->numberRows() - 1;
     103  }
    92104
    93105  void CbcMip::_eraseCol(int i) {
  • lemon/circulation.h

    r877 r964  
    573573
    574574      Node act;
    575       Node bact=INVALID;
    576       Node last_activated=INVALID;
    577575      while((act=_level->highestActive())!=INVALID) {
    578576        int actlevel=(*_level)[act];
  • lemon/circulation.h

    r963 r964  
    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).
     
    6060    /// \brief The type of supply map.
    6161    ///
    62     /// The type of the map that stores the signed supply values of the 
    63     /// nodes. 
     62    /// The type of the map that stores the signed supply values of the
     63    /// nodes.
    6464    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
    6565    typedef SM SupplyMap;
     
    7373    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
    7474    /// concept.
     75#ifdef DOXYGEN
     76    typedef GR::ArcMap<Value> FlowMap;
     77#else
    7578    typedef typename Digraph::template ArcMap<Value> FlowMap;
     79#endif
    7680
    7781    /// \brief Instantiates a FlowMap.
     
    8892    /// The elevator type used by the algorithm.
    8993    ///
    90     /// \sa Elevator
    91     /// \sa LinkedElevator
     94    /// \sa Elevator, LinkedElevator
     95#ifdef DOXYGEN
     96    typedef lemon::Elevator<GR, GR::Node> Elevator;
     97#else
    9298    typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;
     99#endif
    93100
    94101    /// \brief Instantiates an Elevator.
     
    135142     \geq sup(u) \quad \forall u\in V, \f]
    136143     \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f]
    137      
     144
    138145     The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
    139146     zero or negative in order to have a feasible solution (since the sum
     
    145152     constraints have to be satisfied with equality, i.e. all demands
    146153     have to be satisfied and all supplies have to be used.
    147      
     154
    148155     If you need the opposite inequalities in the supply/demand constraints
    149156     (i.e. the total demand is less than the total supply and all the demands
     
    167174     \tparam SM The type of the supply map. The default map type is
    168175     \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".
     176     \tparam TR The traits class that defines various types used by the
     177     algorithm. By default, it is \ref CirculationDefaultTraits
     178     "CirculationDefaultTraits<GR, LM, UM, SM>".
     179     In most cases, this parameter should not be set directly,
     180     consider to use the named template parameters instead.
    169181  */
    170182#ifdef DOXYGEN
     
    300312    /// able to automatically created by the algorithm (i.e. the
    301313    /// digraph and the maximum level should be passed to it).
    302     /// However an external elevator object could also be passed to the
     314    /// However, an external elevator object could also be passed to the
    303315    /// algorithm with the \ref elevator(Elevator&) "elevator()" function
    304316    /// before calling \ref run() or \ref init().
     
    326338    /// \param graph The digraph the algorithm runs on.
    327339    /// \param lower The lower bounds for the flow values on the arcs.
    328     /// \param upper The upper bounds (capacities) for the flow values 
     340    /// \param upper The upper bounds (capacities) for the flow values
    329341    /// on the arcs.
    330342    /// \param supply The signed supply values of the nodes.
     
    451463    }
    452464
    453     /// \brief Sets the tolerance used by algorithm.
    454     ///
    455     /// Sets the tolerance used by algorithm.
     465    /// \brief Sets the tolerance used by the algorithm.
     466    ///
     467    /// Sets the tolerance object used by the algorithm.
     468    /// \return <tt>(*this)</tt>
    456469    Circulation& tolerance(const Tolerance& tolerance) {
    457470      _tol = tolerance;
     
    461474    /// \brief Returns a const reference to the tolerance.
    462475    ///
    463     /// Returns a const reference to the tolerance.
     476    /// Returns a const reference to the tolerance object used by
     477    /// the algorithm.
    464478    const Tolerance& tolerance() const {
    465479      return _tol;
     
    468482    /// \name Execution Control
    469483    /// The simplest way to execute the algorithm is to call \ref run().\n
    470     /// If you need more control on the initial solution or the execution,
    471     /// first you have to call one of the \ref init() functions, then
     484    /// If you need better control on the initial solution or the execution,
     485    /// you have to call one of the \ref init() functions first, then
    472486    /// the \ref start() function.
    473487
  • lemon/clp.cc

    r877 r956  
    438438    delete _prob;
    439439    _prob = new ClpSimplex();
    440     rows.clear();
    441     cols.clear();
    442440    _col_names_ref.clear();
    443441    _clear_temporals();
  • lemon/clp.cc

    r955 r956  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    7676  int ClpLp::_addRow() {
    7777    _prob->addRow(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX);
     78    return _prob->numberRows() - 1;
     79  }
     80
     81  int ClpLp::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
     82    std::vector<int> indexes;
     83    std::vector<Value> values;
     84
     85    for(ExprIterator it = b; it != e; ++it) {
     86      indexes.push_back(it->first);
     87      values.push_back(it->second);
     88    }
     89
     90    _prob->addRow(values.size(), &indexes.front(), &values.front(), l, u);
    7891    return _prob->numberRows() - 1;
    7992  }
  • lemon/concepts/graph_components.h

    r877 r964  
    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    };
     
    490495          _GraphItemIt it3 = it1;
    491496          _GraphItemIt it4 = INVALID;
     497          ignore_unused_variable_warning(it3);
     498          ignore_unused_variable_warning(it4);
    492499
    493500          it2 = ++it1;
     
    499506        }
    500507        const GR& g;
     508        Constraints() {}
    501509      };
    502510    };
     
    578586          _GraphIncIt it3 = it1;
    579587          _GraphIncIt it4 = INVALID;
     588          ignore_unused_variable_warning(it3);
     589          ignore_unused_variable_warning(it4);
    580590
    581591          it2 = ++it1;
     
    587597        const Base& node;
    588598        const GR& graph;
     599        Constraints() {}
    589600      };
    590601    };
     
    763774
    764775        const _Digraph& digraph;
     776        Constraints() {}
    765777      };
    766778    };
     
    887899
    888900        const _Graph& graph;
     901        Constraints() {}
    889902      };
    890903    };
     
    944957
    945958        const _Digraph& digraph;
     959        Constraints() {}
    946960      };
    947961    };
     
    985999
    9861000        const _Graph& graph;
     1001        Constraints() {}
    9871002      };
    9881003    };
     
    10621077        const GR &g;
    10631078        const typename GraphMap::Value &t;
     1079        Constraints() {}
    10641080      };
    10651081
     
    12001216
    12011217        const _Digraph& digraph;
     1218        Constraints() {}
    12021219      };
    12031220    };
     
    12851302
    12861303        const _Graph& graph;
     1304        Constraints() {}
    12871305      };
    12881306    };
     
    13291347
    13301348        _Digraph& digraph;
     1349        Constraints() {}
    13311350      };
    13321351    };
     
    13731392
    13741393        _Graph& graph;
     1394        Constraints() {}
    13751395      };
    13761396    };
     
    14121432
    14131433        _Digraph& digraph;
     1434        Constraints() {}
    14141435      };
    14151436    };
     
    14511472
    14521473        _Graph& graph;
     1474        Constraints() {}
    14531475      };
    14541476    };
     
    14791501
    14801502        _Digraph& digraph;
     1503        Constraints() {}
    14811504      };
    14821505    };
     
    15071530
    15081531        _Graph& graph;
     1532        Constraints() {}
    15091533      };
    15101534    };
  • lemon/concepts/graph_components.h

    r963 r964  
    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      ///
     
    510510    };
    511511
    512     /// \brief Concept class for \c InArcIt, \c OutArcIt and 
     512    /// \brief Concept class for \c InArcIt, \c OutArcIt and
    513513    /// \c IncEdgeIt types.
    514514    ///
    515     /// This class describes the concept of \c InArcIt, \c OutArcIt 
     515    /// This class describes the concept of \c InArcIt, \c OutArcIt
    516516    /// and \c IncEdgeIt subtypes of digraph and graph types.
    517517    ///
    518518    /// \note Since these iterator classes do not inherit from the same
    519519    /// base class, there is an additional template parameter (selector)
    520     /// \c sel. For \c InArcIt you should instantiate it with character 
     520    /// \c sel. For \c InArcIt you should instantiate it with character
    521521    /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'.
    522522    template <typename GR,
     
    539539      GraphIncIt(const GraphIncIt& it) : Item(it) {}
    540540
    541       /// \brief Constructor that sets the iterator to the first 
     541      /// \brief Constructor that sets the iterator to the first
    542542      /// incoming or outgoing arc.
    543543      ///
    544       /// Constructor that sets the iterator to the first arc 
     544      /// Constructor that sets the iterator to the first arc
    545545      /// incoming to or outgoing from the given node.
    546546      explicit GraphIncIt(const GR&, const Base&) {}
     
    817817      /// \brief Return the first edge incident to the given node.
    818818      ///
    819       /// This function gives back the first edge incident to the given 
     819      /// This function gives back the first edge incident to the given
    820820      /// node. The bool parameter gives back the direction for which the
    821       /// source node of the directed arc representing the edge is the 
     821      /// source node of the directed arc representing the edge is the
    822822      /// given node.
    823823      void firstInc(Edge&, bool&, const Node&) const {}
     
    826826      /// given node.
    827827      ///
    828       /// This function gives back the next edge incident to the given 
     828      /// This function gives back the next edge incident to the given
    829829      /// node. The bool parameter should be used as \c firstInc() use it.
    830830      void nextInc(Edge&, bool&) const {}
     
    10061006    ///
    10071007    /// This class describes the concept of standard graph maps, i.e.
    1008     /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and 
     1008    /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and
    10091009    /// graph types, which can be used for associating data to graph items.
    10101010    /// The standard graph maps must conform to the ReferenceMap concept.
     
    10611061          _Map m1(g);
    10621062          _Map m2(g,t);
    1063          
     1063
    10641064          // Copy constructor
    10651065          // _Map m3(m);
     
    10851085    ///
    10861086    /// This class describes the interface of mappable directed graphs.
    1087     /// It extends \ref BaseDigraphComponent with the standard digraph 
     1087    /// It extends \ref BaseDigraphComponent with the standard digraph
    10881088    /// map classes, namely \c NodeMap and \c ArcMap.
    10891089    /// This concept is part of the Digraph concept.
     
    12231223    ///
    12241224    /// This class describes the interface of mappable undirected graphs.
    1225     /// It extends \ref MappableDigraphComponent with the standard graph 
     1225    /// It extends \ref MappableDigraphComponent with the standard graph
    12261226    /// map class for edges (\c EdgeMap).
    12271227    /// This concept is part of the Graph concept.
     
    13091309    ///
    13101310    /// This class describes the interface of extendable directed graphs.
    1311     /// It extends \ref BaseDigraphComponent with functions for adding 
     1311    /// It extends \ref BaseDigraphComponent with functions for adding
    13121312    /// nodes and arcs to the digraph.
    13131313    /// This concept requires \ref AlterableDigraphComponent.
     
    13541354    ///
    13551355    /// This class describes the interface of extendable undirected graphs.
    1356     /// It extends \ref BaseGraphComponent with functions for adding 
     1356    /// It extends \ref BaseGraphComponent with functions for adding
    13571357    /// nodes and edges to the graph.
    13581358    /// This concept requires \ref AlterableGraphComponent.
     
    13991399    ///
    14001400    /// This class describes the interface of erasable directed graphs.
    1401     /// It extends \ref BaseDigraphComponent with functions for removing 
     1401    /// It extends \ref BaseDigraphComponent with functions for removing
    14021402    /// nodes and arcs from the digraph.
    14031403    /// This concept requires \ref AlterableDigraphComponent.
     
    14121412      /// \brief Erase a node from the digraph.
    14131413      ///
    1414       /// This function erases the given node from the digraph and all arcs 
     1414      /// This function erases the given node from the digraph and all arcs
    14151415      /// connected to the node.
    14161416      void erase(const Node&) {}
     
    14391439    ///
    14401440    /// This class describes the interface of erasable undirected graphs.
    1441     /// It extends \ref BaseGraphComponent with functions for removing 
     1441    /// It extends \ref BaseGraphComponent with functions for removing
    14421442    /// nodes and edges from the graph.
    14431443    /// This concept requires \ref AlterableGraphComponent.
  • lemon/concepts/heap.h

    r877 r954  
    315315        _Heap& heap;
    316316        ItemIntMap& map;
     317        Constraints() {}
    317318      };
    318319    };
  • lemon/concepts/heap.h

    r953 r954  
    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 r954  
    169169        }
    170170        _Path& p;
     171        PathDumperConstraints() {}
    171172      };
    172173
     
    194195        }
    195196        _Path& p;
     197        PathDumperConstraints() {}
    196198      };
    197199
  • lemon/concepts/path.h

    r953 r954  
    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/core.h

    r942 r964  
    18501850    ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough.
    18511851    ///
    1852 #ifdef DOXYGEN
    1853     Arc operator()(Node s, Node t, Arc prev=INVALID) const {}
    1854 #else
    1855     using ArcLookUp<GR>::operator() ;
    1856     Arc operator()(Node s, Node t, Arc prev) const
     1852    Arc operator()(Node s, Node t, Arc prev=INVALID) const
    18571853    {
    1858       return prev==INVALID?(*this)(s,t):_next[prev];
    1859     }
     1854      if(prev==INVALID)
     1855        {
     1856          Arc f=INVALID;
     1857          Arc e;
     1858          for(e=_head[s];
     1859              e!=INVALID&&_g.target(e)!=t;
     1860              e = t < _g.target(e)?_left[e]:_right[e]) ;
     1861          while(e!=INVALID)
     1862            if(_g.target(e)==t)
     1863              {
     1864                f = e;
     1865                e = _left[e];
     1866              }
     1867            else e = _right[e];
     1868          return f;
     1869        }
     1870      else return _next[prev];
     1871    }
     1872
     1873  };
     1874
     1875  /// @}
     1876
     1877} //namespace lemon
     1878
    18601879#endif
    1861 
    1862   };
    1863 
    1864   /// @}
    1865 
    1866 } //namespace lemon
    1867 
    1868 #endif
  • lemon/core.h

    r959 r964  
    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).
     
    12421242  protected:
    12431243
    1244     class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type {
     1244    class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type
     1245    {
    12451246      typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent;
    12461247
     
    12811282    };
    12821283
    1283   protected: 
     1284  protected:
    12841285
    12851286    const Digraph &_g;
  • lemon/cplex.cc

    r877 r956  
    471471    int status;
    472472    _prob = CPXcreateprob(cplexEnv(), &status, "Cplex problem");
    473     rows.clear();
    474     cols.clear();
    475473  }
    476474
  • lemon/cplex.cc

    r955 r956  
    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).
     
    112112  }
    113113
     114  int CplexBase::_addRow(Value lb, ExprIterator b,
     115                         ExprIterator e, Value ub) {
     116    int i = CPXgetnumrows(cplexEnv(), _prob);
     117    if (lb == -INF) {
     118      const char s = 'L';
     119      CPXnewrows(cplexEnv(), _prob, 1, &ub, &s, 0, 0);
     120    } else if (ub == INF) {
     121      const char s = 'G';
     122      CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0);
     123    } else if (lb == ub){
     124      const char s = 'E';
     125      CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0);
     126    } else {
     127      const char s = 'R';
     128      double len = ub - lb;
     129      CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, &len, 0);
     130    }
     131
     132    std::vector<int> indices;
     133    std::vector<int> rowlist;
     134    std::vector<Value> values;
     135
     136    for(ExprIterator it=b; it!=e; ++it) {
     137      indices.push_back(it->first);
     138      values.push_back(it->second);
     139      rowlist.push_back(i);
     140    }
     141
     142    CPXchgcoeflist(cplexEnv(), _prob, values.size(),
     143                   &rowlist.front(), &indices.front(), &values.front());
     144
     145    return i;
     146  }
    114147
    115148  void CplexBase::_eraseCol(int i) {
     
    455488
    456489  void CplexBase::_applyMessageLevel() {
    457     CPXsetintparam(cplexEnv(), CPX_PARAM_SCRIND, 
     490    CPXsetintparam(cplexEnv(), CPX_PARAM_SCRIND,
    458491                   _message_enabled ? CPX_ON : CPX_OFF);
    459492  }
  • lemon/dfs.h

    r942 r964  
    11941194      }
    11951195      _Visitor& visitor;
     1196      Constraints() {}
    11961197    };
    11971198  };
  • lemon/dfs.h

    r953 r964  
    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).
  • lemon/glpk.cc

    r877 r956  
    557557  void GlpkBase::_clear() {
    558558    glp_erase_prob(lp);
    559     rows.clear();
    560     cols.clear();
    561559  }
    562560
  • lemon/glpk.cc

    r955 r956  
    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).
     
    5757    int i = glp_add_rows(lp, 1);
    5858    glp_set_row_bnds(lp, i, GLP_FR, 0.0, 0.0);
     59    return i;
     60  }
     61
     62  int GlpkBase::_addRow(Value lo, ExprIterator b,
     63                        ExprIterator e, Value up) {
     64    int i = glp_add_rows(lp, 1);
     65
     66    if (lo == -INF) {
     67      if (up == INF) {
     68        glp_set_row_bnds(lp, i, GLP_FR, lo, up);
     69      } else {
     70        glp_set_row_bnds(lp, i, GLP_UP, lo, up);
     71      }
     72    } else {
     73      if (up == INF) {
     74        glp_set_row_bnds(lp, i, GLP_LO, lo, up);
     75      } else if (lo != up) {
     76        glp_set_row_bnds(lp, i, GLP_DB, lo, up);
     77      } else {
     78        glp_set_row_bnds(lp, i, GLP_FX, lo, up);
     79      }
     80    }
     81
     82    std::vector<int> indexes;
     83    std::vector<Value> values;
     84
     85    indexes.push_back(0);
     86    values.push_back(0);
     87
     88    for(ExprIterator it = b; it != e; ++it) {
     89      indexes.push_back(it->first);
     90      values.push_back(it->second);
     91    }
     92
     93    glp_set_mat_row(lp, i, values.size() - 1,
     94                    &indexes.front(), &values.front());
    5995    return i;
    6096  }
  • lemon/graph_to_eps.h

    r942 r964  
    223223  using T::_copyright;
    224224
    225   using T::NodeTextColorType;
     225  using typename T::NodeTextColorType;
    226226  using T::CUST_COL;
    227227  using T::DIST_COL;
  • lemon/graph_to_eps.h

    r963 r964  
    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).
     
    143143  ///\param gr  Reference to the graph to be printed.
    144144  ///\param ost Reference to the output stream.
    145   ///By default it is <tt>std::cout</tt>.
     145  ///By default, it is <tt>std::cout</tt>.
    146146  ///\param pros If it is \c true, then the \c ostream referenced by \c os
    147147  ///will be explicitly deallocated by the destructor.
     
    513513  ///Turn on/off pre-scaling
    514514
    515   ///By default graphToEps() rescales the whole image in order to avoid
     515  ///By default, graphToEps() rescales the whole image in order to avoid
    516516  ///very big or very small bounding boxes.
    517517  ///
     
    11151115///\param g Reference to the graph to be printed.
    11161116///\param os Reference to the output stream.
    1117 ///By default it is <tt>std::cout</tt>.
     1117///By default, it is <tt>std::cout</tt>.
    11181118///
    11191119///This function also has a lot of
     
    11271127///\endcode
    11281128///
    1129 ///For more detailed examples see the \ref graph_to_eps_demo.cc demo file.
     1129///For more detailed examples, see the \ref graph_to_eps_demo.cc demo file.
    11301130///
    11311131///\warning Don't forget to put the \ref GraphToEps::run() "run()"
  • lemon/lp_base.h

    r933 r964  
    15571557
    15581558    ///Clears the problem
    1559     void clear() { _clear(); }
     1559    void clear() { _clear(); rows.clear(); cols.clear(); }
    15601560
    15611561    /// Sets the message level of the solver
  • lemon/lp_base.h

    r955 r964  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8383      MESSAGE_VERBOSE
    8484    };
    85    
     85
    8686
    8787    ///The floating point type used by the solver
     
    115115      typedef True LpCol;
    116116      /// Default constructor
    117      
     117
    118118      /// \warning The default constructor sets the Col to an
    119119      /// undefined value.
    120120      Col() {}
    121121      /// Invalid constructor \& conversion.
    122      
     122
    123123      /// This constructor initializes the Col to be invalid.
    124       /// \sa Invalid for more details.     
     124      /// \sa Invalid for more details.
    125125      Col(const Invalid&) : _id(-1) {}
    126126      /// Equality operator
     
    147147    ///Iterator for iterate over the columns of an LP problem
    148148
    149     /// Its usage is quite simple, for example you can count the number
     149    /// Its usage is quite simple, for example, you can count the number
    150150    /// of columns in an LP \c lp:
    151151    ///\code
     
    157157    public:
    158158      /// Default constructor
    159      
     159
    160160      /// \warning The default constructor sets the iterator
    161161      /// to an undefined value.
    162162      ColIt() {}
    163163      /// Sets the iterator to the first Col
    164      
     164
    165165      /// Sets the iterator to the first Col.
    166166      ///
     
    170170      }
    171171      /// Invalid constructor \& conversion
    172      
     172
    173173      /// Initialize the iterator to be invalid.
    174174      /// \sa Invalid for more details.
    175175      ColIt(const Invalid&) : Col(INVALID) {}
    176176      /// Next column
    177      
     177
    178178      /// Assign the iterator to the next column.
    179179      ///
     
    210210      typedef True LpRow;
    211211      /// Default constructor
    212      
     212
    213213      /// \warning The default constructor sets the Row to an
    214214      /// undefined value.
    215215      Row() {}
    216216      /// Invalid constructor \& conversion.
    217      
     217
    218218      /// This constructor initializes the Row to be invalid.
    219       /// \sa Invalid for more details.     
     219      /// \sa Invalid for more details.
    220220      Row(const Invalid&) : _id(-1) {}
    221221      /// Equality operator
     
    225225      bool operator==(Row r) const  {return _id == r._id;}
    226226      /// Inequality operator
    227      
     227
    228228      /// \sa operator==(Row r)
    229229      ///
     
    242242    ///Iterator for iterate over the rows of an LP problem
    243243
    244     /// Its usage is quite simple, for example you can count the number
     244    /// Its usage is quite simple, for example, you can count the number
    245245    /// of rows in an LP \c lp:
    246246    ///\code
     
    252252    public:
    253253      /// Default constructor
    254      
     254
    255255      /// \warning The default constructor sets the iterator
    256256      /// to an undefined value.
    257257      RowIt() {}
    258258      /// Sets the iterator to the first Row
    259      
     259
    260260      /// Sets the iterator to the first Row.
    261261      ///
     
    265265      }
    266266      /// Invalid constructor \& conversion
    267      
     267
    268268      /// Initialize the iterator to be invalid.
    269269      /// \sa Invalid for more details.
    270270      RowIt(const Invalid&) : Row(INVALID) {}
    271271      /// Next row
    272      
     272
    273273      /// Assign the iterator to the next row.
    274274      ///
     
    348348      typedef True SolverExpr;
    349349      /// Default constructor
    350      
     350
    351351      /// Construct an empty expression, the coefficients and
    352352      /// the constant component are initialized to zero.
     
    449449
    450450      ///Iterator over the expression
    451      
    452       ///The iterator iterates over the terms of the expression. 
    453       /// 
     451
     452      ///The iterator iterates over the terms of the expression.
     453      ///
    454454      ///\code
    455455      ///double s=0;
     
    465465
    466466        /// Sets the iterator to the first term
    467        
     467
    468468        /// Sets the iterator to the first term of the expression.
    469469        ///
     
    482482        const Value& operator*() const { return _it->second; }
    483483        /// Next term
    484        
     484
    485485        /// Assign the iterator to the next term.
    486486        ///
     
    494494
    495495      /// Const iterator over the expression
    496      
    497       ///The iterator iterates over the terms of the expression. 
    498       /// 
     496
     497      ///The iterator iterates over the terms of the expression.
     498      ///
    499499      ///\code
    500500      ///double s=0;
     
    510510
    511511        /// Sets the iterator to the first term
    512        
     512
    513513        /// Sets the iterator to the first term of the expression.
    514514        ///
     
    525525
    526526        /// Next term
    527        
     527
    528528        /// Assign the iterator to the next term.
    529529        ///
     
    674674      typedef True SolverExpr;
    675675      /// Default constructor
    676      
     676
    677677      /// Construct an empty expression, the coefficients are
    678678      /// initialized to zero.
     
    709709      }
    710710      /// \brief Removes the coefficients which's absolute value does
    711       /// not exceed \c epsilon. 
     711      /// not exceed \c epsilon.
    712712      void simplify(Value epsilon = 0.0) {
    713713        std::map<int, Value>::iterator it=comps.begin();
     
    758758
    759759      ///Iterator over the expression
    760      
    761       ///The iterator iterates over the terms of the expression. 
    762       /// 
     760
     761      ///The iterator iterates over the terms of the expression.
     762      ///
    763763      ///\code
    764764      ///double s=0;
     
    774774
    775775        /// Sets the iterator to the first term
    776        
     776
    777777        /// Sets the iterator to the first term of the expression.
    778778        ///
     
    792792
    793793        /// Next term
    794        
     794
    795795        /// Assign the iterator to the next term.
    796796        ///
     
    804804
    805805      ///Iterator over the expression
    806      
    807       ///The iterator iterates over the terms of the expression. 
    808       /// 
     806
     807      ///The iterator iterates over the terms of the expression.
     808      ///
    809809      ///\code
    810810      ///double s=0;
     
    820820
    821821        /// Sets the iterator to the first term
    822        
     822
    823823        /// Sets the iterator to the first term of the expression.
    824824        ///
     
    835835
    836836        /// Next term
    837        
     837
    838838        /// Assign the iterator to the next term.
    839839        ///
     
    943943    virtual int _addCol() = 0;
    944944    virtual int _addRow() = 0;
     945
     946    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
     947      int row = _addRow();
     948      _setRowCoeffs(row, b, e);
     949      _setRowLowerBound(row, l);
     950      _setRowUpperBound(row, u);
     951      return row;
     952    }
    945953
    946954    virtual void _eraseCol(int col) = 0;
     
    12081216    ///\return The created row.
    12091217    Row addRow(Value l,const Expr &e, Value u) {
    1210       Row r=addRow();
    1211       row(r,l,e,u);
     1218      Row r;
     1219      e.simplify();
     1220      r._id = _addRowId(_addRow(l - *e, ExprIterator(e.comps.begin(), cols),
     1221                                ExprIterator(e.comps.end(), cols), u - *e));
    12121222      return r;
    12131223    }
     
    12181228    ///\return The created row.
    12191229    Row addRow(const Constr &c) {
    1220       Row r=addRow();
    1221       row(r,c);
     1230      Row r;
     1231      c.expr().simplify();
     1232      r._id = _addRowId(_addRow(c.lowerBounded()?c.lowerBound()-*c.expr():-INF,
     1233                                ExprIterator(c.expr().comps.begin(), cols),
     1234                                ExprIterator(c.expr().comps.end(), cols),
     1235                                c.upperBounded()?c.upperBound()-*c.expr():INF));
    12221236      return r;
    12231237    }
     
    18041818    enum VarStatus {
    18051819      /// The variable is in the basis
    1806       BASIC, 
     1820      BASIC,
    18071821      /// The variable is free, but not basic
    18081822      FREE,
    1809       /// The variable has active lower bound 
     1823      /// The variable has active lower bound
    18101824      LOWER,
    18111825      /// The variable has active upper bound
     
    18861900    }
    18871901    /// Returns a component of the primal ray
    1888    
     1902
    18891903    /// The primal ray is solution of the modified primal problem,
    18901904    /// where we change each finite bound to 0, and we looking for a
     
    19201934
    19211935    /// Returns a component of the dual ray
    1922    
     1936
    19231937    /// The dual ray is solution of the modified primal problem, where
    19241938    /// we change each finite bound to 0 (i.e. the objective function
     
    20622076    }
    20632077    ///The value of the objective function
    2064    
     2078
    20652079    ///\return
    20662080    ///- \ref INF or -\ref INF means either infeasibility or unboundedness
  • lemon/path.h

    r877 r958  
    6565    Path() {}
    6666
     67    /// \brief Copy constructor
     68    ///
     69    Path(const Path& cpath) {
     70      pathCopy(cpath, *this);
     71    }
     72
    6773    /// \brief Template copy constructor
    6874    ///
     
    7278    Path(const CPath& cpath) {
    7379      pathCopy(cpath, *this);
     80    }
     81
     82    /// \brief Copy assignment
     83    ///
     84    Path& operator=(const Path& cpath) {
     85      pathCopy(cpath, *this);
     86      return *this;
    7487    }
    7588
     
    253266    SimplePath() {}
    254267
     268    /// \brief Copy constructor
     269    ///
     270    SimplePath(const SimplePath& cpath) {
     271      pathCopy(cpath, *this);
     272    }
     273
    255274    /// \brief Template copy constructor
    256275    ///
     
    260279    SimplePath(const CPath& cpath) {
    261280      pathCopy(cpath, *this);
     281    }
     282
     283    /// \brief Copy assignment
     284    ///
     285    SimplePath& operator=(const SimplePath& cpath) {
     286      pathCopy(cpath, *this);
     287      return *this;
    262288    }
    263289
     
    432458    ListPath() : first(0), last(0) {}
    433459
     460    /// \brief Copy constructor
     461    ///
     462    ListPath(const ListPath& cpath) : first(0), last(0) {
     463      pathCopy(cpath, *this);
     464    }
     465
    434466    /// \brief Template copy constructor
    435467    ///
     
    446478    ~ListPath() {
    447479      clear();
     480    }
     481
     482    /// \brief Copy assignment
     483    ///
     484    ListPath& operator=(const ListPath& cpath) {
     485      pathCopy(cpath, *this);
     486      return *this;
    448487    }
    449488
     
    759798    StaticPath() : len(0), arcs(0) {}
    760799
     800    /// \brief Copy constructor
     801    ///
     802    StaticPath(const StaticPath& cpath) : arcs(0) {
     803      pathCopy(cpath, *this);
     804    }
     805
    761806    /// \brief Template copy constructor
    762807    ///
     
    772817    ~StaticPath() {
    773818      if (arcs) delete[] arcs;
     819    }
     820
     821    /// \brief Copy assignment
     822    ///
     823    StaticPath& operator=(const StaticPath& cpath) {
     824      pathCopy(cpath, *this);
     825      return *this;
    774826    }
    775827
  • lemon/path.h

    r957 r958  
    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).
     
    10191019    };
    10201020
    1021    
     1021
    10221022    template <typename From, typename To,
    10231023              bool revEnable = RevPathTagIndicator<From>::value>
     
    10251025      static void copy(const From& from, To& to) {
    10261026        PathCopySelectorForward<From, To>::copy(from, to);
    1027       }     
     1027      }
    10281028    };
    10291029
     
    10321032      static void copy(const From& from, To& to) {
    10331033        PathCopySelectorBackward<From, To>::copy(from, to);
    1034       }     
     1034      }
    10351035    };
    10361036
  • test/CMakeLists.txt

    r942 r964  
    1414SET(TESTS
    1515  adaptors_test
     16  arc_look_up_test
    1617  bellman_ford_test
    1718  bfs_test
     
    8788    GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
    8889    ADD_CUSTOM_COMMAND(TARGET lp_test POST_BUILD
    89       COMMAND ${CMAKE_COMMAND} -E copy ${CPLEX_BIN_DIR}/cplex91.dll ${TARGET_PATH}
     90      COMMAND ${CMAKE_COMMAND} -E copy ${CPLEX_BIN_DIR}/cplex.dll ${TARGET_PATH}
    9091    )
    9192  ENDIF()
     
    129130    GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
    130131    ADD_CUSTOM_COMMAND(TARGET mip_test POST_BUILD
    131       COMMAND ${CMAKE_COMMAND} -E copy ${CPLEX_BIN_DIR}/cplex91.dll ${TARGET_PATH}
     132      COMMAND ${CMAKE_COMMAND} -E copy ${CPLEX_BIN_DIR}/cplex.dll ${TARGET_PATH}
    132133    )
    133134  ENDIF()
  • test/CMakeLists.txt

    r959 r964  
    1515  adaptors_test
    1616  arc_look_up_test
     17  bellman_ford_test
    1718  bfs_test
    1819  circulation_test
     
    2627  error_test
    2728  euler_test
     29  fractional_matching_test
    2830  gomory_hu_test
    2931  graph_copy_test
     
    3840  min_cost_arborescence_test
    3941  min_cost_flow_test
     42  min_mean_cycle_test
    4043  path_test
     44  planarity_test
    4145  preflow_test
    4246  radix_sort_test
  • test/adaptors_test.cc

    r961 r964  
    6666  Digraph::Arc a2 = digraph.addArc(n1, n3);
    6767  Digraph::Arc a3 = digraph.addArc(n2, n3);
     68  ignore_unused_variable_warning(a3);
    6869
    6970  // Check the adaptor
     
    100101  Adaptor::Arc a7 = adaptor.addArc(n1, n4);
    101102  Adaptor::Arc a8 = adaptor.addArc(n1, n2);
     103  ignore_unused_variable_warning(a6,a7,a8);
    102104
    103105  adaptor.erase(a1);
     
    759761  Digraph::Arc a2 = digraph.addArc(n1, n3);
    760762  Digraph::Arc a3 = digraph.addArc(n2, n3);
     763  ignore_unused_variable_warning(a1,a2,a3);
    761764
    762765  checkGraphNodeList(adaptor, 6);
  • test/adaptors_test.cc

    r963 r964  
    13751375
    13761376  GridGraph::EdgeMap<bool> dir_map(graph);
    1377   dir_map[graph.right(n1)] = graph.u(graph.right(n1)) == n1;
    1378   dir_map[graph.up(n1)] = graph.u(graph.up(n1)) != n1;
    1379   dir_map[graph.left(n4)] = graph.u(graph.left(n4)) != n4;
    1380   dir_map[graph.down(n4)] = graph.u(graph.down(n4)) != n4;
     1377  dir_map[graph.right(n1)] = graph.u(graph.right(n1)) != n1;
     1378  dir_map[graph.up(n1)] = graph.u(graph.up(n1)) == n1;
     1379  dir_map[graph.left(n4)] = graph.u(graph.left(n4)) == n4;
     1380  dir_map[graph.down(n4)] = graph.u(graph.down(n4)) == n4;
    13811381
    13821382  // Apply several adaptors on the grid graph
    1383   typedef SplitNodes< ReverseDigraph< const Orienter<
    1384             const GridGraph, GridGraph::EdgeMap<bool> > > >
    1385     RevSplitGridGraph;
    1386   typedef ReverseDigraph<const RevSplitGridGraph> SplitGridGraph;
     1383  typedef Orienter< const GridGraph, GridGraph::EdgeMap<bool> >
     1384    OrientedGridGraph;
     1385  typedef SplitNodes<OrientedGridGraph> SplitGridGraph;
    13871386  typedef Undirector<const SplitGridGraph> USplitGridGraph;
    1388   typedef Undirector<const USplitGridGraph> UUSplitGridGraph;
    1389   checkConcept<concepts::Digraph, RevSplitGridGraph>();
    13901387  checkConcept<concepts::Digraph, SplitGridGraph>();
    13911388  checkConcept<concepts::Graph, USplitGridGraph>();
    1392   checkConcept<concepts::Graph, UUSplitGridGraph>();
    1393 
    1394   RevSplitGridGraph rev_adaptor =
    1395     splitNodes(reverseDigraph(orienter(graph, dir_map)));
    1396   SplitGridGraph adaptor = reverseDigraph(rev_adaptor);
     1389
     1390  OrientedGridGraph oadaptor = orienter(graph, dir_map);
     1391  SplitGridGraph adaptor = splitNodes(oadaptor);
    13971392  USplitGridGraph uadaptor = undirector(adaptor);
    1398   UUSplitGridGraph uuadaptor = undirector(uadaptor);
    13991393
    14001394  // Check adaptor
     
    14031397  checkGraphConArcList(adaptor, 8);
    14041398
    1405   checkGraphOutArcList(adaptor, rev_adaptor.inNode(n1), 1);
    1406   checkGraphOutArcList(adaptor, rev_adaptor.outNode(n1), 1);
    1407   checkGraphOutArcList(adaptor, rev_adaptor.inNode(n2), 2);
    1408   checkGraphOutArcList(adaptor, rev_adaptor.outNode(n2), 1);
    1409   checkGraphOutArcList(adaptor, rev_adaptor.inNode(n3), 1);
    1410   checkGraphOutArcList(adaptor, rev_adaptor.outNode(n3), 1);
    1411   checkGraphOutArcList(adaptor, rev_adaptor.inNode(n4), 0);
    1412   checkGraphOutArcList(adaptor, rev_adaptor.outNode(n4), 1);
    1413 
    1414   checkGraphInArcList(adaptor, rev_adaptor.inNode(n1), 1);
    1415   checkGraphInArcList(adaptor, rev_adaptor.outNode(n1), 1);
    1416   checkGraphInArcList(adaptor, rev_adaptor.inNode(n2), 1);
    1417   checkGraphInArcList(adaptor, rev_adaptor.outNode(n2), 0);
    1418   checkGraphInArcList(adaptor, rev_adaptor.inNode(n3), 1);
    1419   checkGraphInArcList(adaptor, rev_adaptor.outNode(n3), 1);
    1420   checkGraphInArcList(adaptor, rev_adaptor.inNode(n4), 1);
    1421   checkGraphInArcList(adaptor, rev_adaptor.outNode(n4), 2);
     1399  checkGraphOutArcList(adaptor, adaptor.inNode(n1), 1);
     1400  checkGraphOutArcList(adaptor, adaptor.outNode(n1), 1);
     1401  checkGraphOutArcList(adaptor, adaptor.inNode(n2), 1);
     1402  checkGraphOutArcList(adaptor, adaptor.outNode(n2), 0);
     1403  checkGraphOutArcList(adaptor, adaptor.inNode(n3), 1);
     1404  checkGraphOutArcList(adaptor, adaptor.outNode(n3), 1);
     1405  checkGraphOutArcList(adaptor, adaptor.inNode(n4), 1);
     1406  checkGraphOutArcList(adaptor, adaptor.outNode(n4), 2);
     1407
     1408  checkGraphInArcList(adaptor, adaptor.inNode(n1), 1);
     1409  checkGraphInArcList(adaptor, adaptor.outNode(n1), 1);
     1410  checkGraphInArcList(adaptor, adaptor.inNode(n2), 2);
     1411  checkGraphInArcList(adaptor, adaptor.outNode(n2), 1);
     1412  checkGraphInArcList(adaptor, adaptor.inNode(n3), 1);
     1413  checkGraphInArcList(adaptor, adaptor.outNode(n3), 1);
     1414  checkGraphInArcList(adaptor, adaptor.inNode(n4), 0);
     1415  checkGraphInArcList(adaptor, adaptor.outNode(n4), 1);
    14221416
    14231417  checkNodeIds(adaptor);
     
    14421436  checkGraphArcMap(uadaptor);
    14431437
    1444   checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n1), 2);
    1445   checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n1), 2);
    1446   checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n2), 3);
    1447   checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n2), 1);
    1448   checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n3), 2);
    1449   checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n3), 2);
    1450   checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.inNode(n4), 1);
    1451   checkGraphIncEdgeArcLists(uadaptor, rev_adaptor.outNode(n4), 3);
    1452 
    1453   // Check uuadaptor
    1454   checkGraphNodeList(uuadaptor, 8);
    1455   checkGraphEdgeList(uuadaptor, 16);
    1456   checkGraphArcList(uuadaptor, 32);
    1457   checkGraphConEdgeList(uuadaptor, 16);
    1458   checkGraphConArcList(uuadaptor, 32);
    1459 
    1460   checkNodeIds(uuadaptor);
    1461   checkEdgeIds(uuadaptor);
    1462   checkArcIds(uuadaptor);
    1463 
    1464   checkGraphNodeMap(uuadaptor);
    1465   checkGraphEdgeMap(uuadaptor);
    1466   checkGraphArcMap(uuadaptor);
     1438  checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n1), 2);
     1439  checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n1), 2);
     1440  checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n2), 3);
     1441  checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n2), 1);
     1442  checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n3), 2);
     1443  checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n3), 2);
     1444  checkGraphIncEdgeArcLists(uadaptor, adaptor.inNode(n4), 1);
     1445  checkGraphIncEdgeArcLists(uadaptor, adaptor.outNode(n4), 3);
    14671446}
    14681447
  • test/connectivity_test.cc

    r877 r964  
    6969    Graph g(d);
    7070    Digraph::Node n = d.addNode();
     71    ignore_unused_variable_warning(n);
    7172
    7273    check(stronglyConnected(d), "This digraph is strongly connected");
     
    246247    Digraph::Node watch = d.addNode();
    247248    Digraph::Node pants = d.addNode();
     249    ignore_unused_variable_warning(watch);
    248250
    249251    d.addArc(socks, shoe);
  • test/connectivity_test.cc

    r963 r964  
    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).
     
    3030  typedef ListDigraph Digraph;
    3131  typedef Undirector<Digraph> Graph;
    32  
    33   {
    34     Digraph d;
    35     Digraph::NodeMap<int> order(d);
    36     Graph g(d);
    37    
     32
     33  {
     34    Digraph d;
     35    Digraph::NodeMap<int> order(d);
     36    Graph g(d);
     37
    3838    check(stronglyConnected(d), "The empty digraph is strongly connected");
    3939    check(countStronglyConnectedComponents(d) == 0,
     
    4949    check(countBiEdgeConnectedComponents(g) == 0,
    5050          "The empty graph has 0 bi-edge-connected component");
    51          
     51
    5252    check(dag(d), "The empty digraph is DAG.");
    5353    check(checkedTopologicalSort(d, order), "The empty digraph is DAG.");
     
    8484    check(countBiEdgeConnectedComponents(g) == 1,
    8585          "This graph has 1 bi-edge-connected component");
    86          
     86
    8787    check(dag(d), "This digraph is DAG.");
    8888    check(checkedTopologicalSort(d, order), "This digraph is DAG.");
     
    103103    Digraph::NodeMap<int> order(d);
    104104    Graph g(d);
    105    
     105
    106106    Digraph::Node n1 = d.addNode();
    107107    Digraph::Node n2 = d.addNode();
     
    110110    Digraph::Node n5 = d.addNode();
    111111    Digraph::Node n6 = d.addNode();
    112    
     112
    113113    d.addArc(n1, n3);
    114114    d.addArc(n3, n2);
     
    138138    check(!parallelFree(g), "This graph is not parallel-free.");
    139139    check(!simpleGraph(g), "This graph is not simple.");
    140    
     140
    141141    d.addArc(n3, n3);
    142    
     142
    143143    check(!loopFree(d), "This digraph is not loop-free.");
    144144    check(!loopFree(g), "This graph is not loop-free.");
    145145    check(!simpleGraph(d), "This digraph is not simple.");
    146    
     146
    147147    d.addArc(n3, n2);
    148    
     148
    149149    check(!parallelFree(d), "This digraph is not parallel-free.");
    150150  }
    151  
     151
    152152  {
    153153    Digraph d;
    154154    Digraph::ArcMap<bool> cutarcs(d, false);
    155155    Graph g(d);
    156    
     156
    157157    Digraph::Node n1 = d.addNode();
    158158    Digraph::Node n2 = d.addNode();
     
    174174    d.addArc(n6, n7);
    175175    d.addArc(n7, n6);
    176    
     176
    177177    check(!stronglyConnected(d), "This digraph is not strongly connected");
    178178    check(countStronglyConnectedComponents(d) == 3,
     
    237237    Digraph d;
    238238    Digraph::NodeMap<int> order(d);
    239    
     239
    240240    Digraph::Node belt = d.addNode();
    241241    Digraph::Node trousers = d.addNode();
     
    258258    d.addArc(shirt, necktie);
    259259    d.addArc(necktie, coat);
    260    
     260
    261261    check(dag(d), "This digraph is DAG.");
    262262    topologicalSort(d, order);
     
    270270    ListGraph g;
    271271    ListGraph::NodeMap<bool> map(g);
    272    
     272
    273273    ListGraph::Node n1 = g.addNode();
    274274    ListGraph::Node n2 = g.addNode();
     
    286286    g.addEdge(n4, n7);
    287287    g.addEdge(n5, n7);
    288    
     288
    289289    check(bipartite(g), "This graph is bipartite");
    290290    check(bipartitePartitions(g, map), "This graph is bipartite");
    291    
     291
    292292    check(map[n1] == map[n2] && map[n1] == map[n6] && map[n1] == map[n7],
    293293          "Wrong bipartitePartitions()");
  • test/digraph_test.cc

    r877 r964  
    6565      a3 = G.addArc(n2, n3),
    6666      a4 = G.addArc(n2, n3);
     67  ignore_unused_variable_warning(a2,a3,a4);
    6768
    6869  checkGraphNodeList(G, 3);
     
    9394  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
    9495      a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
     96  ignore_unused_variable_warning(a1,a2,a3,a4);
    9597
    9698  Node n4 = G.split(n2);
     
    126128      a3 = G.addArc(n4, n3), a4 = G.addArc(n4, n3),
    127129      a5 = G.addArc(n2, n4);
     130  ignore_unused_variable_warning(a1,a2,a3,a5);
    128131
    129132  checkGraphNodeList(G, 4);
     
    205208      a3 = G.addArc(n4, n3), a4 = G.addArc(n3, n1),
    206209      a5 = G.addArc(n2, n4);
     210  ignore_unused_variable_warning(a2,a3,a4,a5);
    207211
    208212  // Check arc deletion
     
    252256  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
    253257      a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
     258  ignore_unused_variable_warning(a1,a2,a3,a4);
    254259
    255260  typename Digraph::Snapshot snapshot(G);
     
    352357    e1 = g.addArc(n1, n2),
    353358    e2 = g.addArc(n2, n3);
     359  ignore_unused_variable_warning(e2);
    354360
    355361  check(g.valid(n1), "Wrong validity check");
  • test/digraph_test.cc

    r963 r964  
    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).
     
    2020#include <lemon/list_graph.h>
    2121#include <lemon/smart_graph.h>
     22#include <lemon/static_graph.h>
    2223#include <lemon/full_graph.h>
    2324
     
    3536  checkGraphNodeList(G, 0);
    3637  checkGraphArcList(G, 0);
     38
     39  G.reserveNode(3);
     40  G.reserveArc(4);
    3741
    3842  Node
     
    289293
    290294  snapshot.restore();
     295  snapshot.save(G);
     296
     297  checkGraphNodeList(G, 4);
     298  checkGraphArcList(G, 4);
     299
     300  G.addArc(G.addNode(), G.addNode());
     301
     302  snapshot.restore();
    291303
    292304  checkGraphNodeList(G, 4);
     
    323335    checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
    324336  }
     337  { // Checking StaticDigraph
     338    checkConcept<Digraph, StaticDigraph>();
     339    checkConcept<ClearableDigraphComponent<>, StaticDigraph>();
     340  }
    325341  { // Checking FullDigraph
    326342    checkConcept<Digraph, FullDigraph>();
     
    379395}
    380396
     397void checkStaticDigraph() {
     398  SmartDigraph g;
     399  SmartDigraph::NodeMap<StaticDigraph::Node> nref(g);
     400  SmartDigraph::ArcMap<StaticDigraph::Arc> aref(g);
     401
     402  StaticDigraph G;
     403
     404  checkGraphNodeList(G, 0);
     405  checkGraphArcList(G, 0);
     406
     407  G.build(g, nref, aref);
     408
     409  checkGraphNodeList(G, 0);
     410  checkGraphArcList(G, 0);
     411
     412  SmartDigraph::Node
     413    n1 = g.addNode(),
     414    n2 = g.addNode(),
     415    n3 = g.addNode();
     416
     417  G.build(g, nref, aref);
     418
     419  checkGraphNodeList(G, 3);
     420  checkGraphArcList(G, 0);
     421
     422  SmartDigraph::Arc a1 = g.addArc(n1, n2);
     423
     424  G.build(g, nref, aref);
     425
     426  check(G.source(aref[a1]) == nref[n1] && G.target(aref[a1]) == nref[n2],
     427        "Wrong arc or wrong references");
     428  checkGraphNodeList(G, 3);
     429  checkGraphArcList(G, 1);
     430
     431  checkGraphOutArcList(G, nref[n1], 1);
     432  checkGraphOutArcList(G, nref[n2], 0);
     433  checkGraphOutArcList(G, nref[n3], 0);
     434
     435  checkGraphInArcList(G, nref[n1], 0);
     436  checkGraphInArcList(G, nref[n2], 1);
     437  checkGraphInArcList(G, nref[n3], 0);
     438
     439  checkGraphConArcList(G, 1);
     440
     441  SmartDigraph::Arc
     442    a2 = g.addArc(n2, n1),
     443    a3 = g.addArc(n2, n3),
     444    a4 = g.addArc(n2, n3);
     445
     446  digraphCopy(g, G).nodeRef(nref).run();
     447
     448  checkGraphNodeList(G, 3);
     449  checkGraphArcList(G, 4);
     450
     451  checkGraphOutArcList(G, nref[n1], 1);
     452  checkGraphOutArcList(G, nref[n2], 3);
     453  checkGraphOutArcList(G, nref[n3], 0);
     454
     455  checkGraphInArcList(G, nref[n1], 1);
     456  checkGraphInArcList(G, nref[n2], 1);
     457  checkGraphInArcList(G, nref[n3], 2);
     458
     459  checkGraphConArcList(G, 4);
     460
     461  std::vector<std::pair<int,int> > arcs;
     462  arcs.push_back(std::make_pair(0,1));
     463  arcs.push_back(std::make_pair(0,2));
     464  arcs.push_back(std::make_pair(1,3));
     465  arcs.push_back(std::make_pair(1,2));
     466  arcs.push_back(std::make_pair(3,0));
     467  arcs.push_back(std::make_pair(3,3));
     468  arcs.push_back(std::make_pair(4,2));
     469  arcs.push_back(std::make_pair(4,3));
     470  arcs.push_back(std::make_pair(4,1));
     471
     472  G.build(6, arcs.begin(), arcs.end());
     473
     474  checkGraphNodeList(G, 6);
     475  checkGraphArcList(G, 9);
     476
     477  checkGraphOutArcList(G, G.node(0), 2);
     478  checkGraphOutArcList(G, G.node(1), 2);
     479  checkGraphOutArcList(G, G.node(2), 0);
     480  checkGraphOutArcList(G, G.node(3), 2);
     481  checkGraphOutArcList(G, G.node(4), 3);
     482  checkGraphOutArcList(G, G.node(5), 0);
     483
     484  checkGraphInArcList(G, G.node(0), 1);
     485  checkGraphInArcList(G, G.node(1), 2);
     486  checkGraphInArcList(G, G.node(2), 3);
     487  checkGraphInArcList(G, G.node(3), 3);
     488  checkGraphInArcList(G, G.node(4), 0);
     489  checkGraphInArcList(G, G.node(5), 0);
     490
     491  checkGraphConArcList(G, 9);
     492
     493  checkNodeIds(G);
     494  checkArcIds(G);
     495  checkGraphNodeMap(G);
     496  checkGraphArcMap(G);
     497
     498  int n = G.nodeNum();
     499  int m = G.arcNum();
     500  check(G.index(G.node(n-1)) == n-1, "Wrong index.");
     501  check(G.index(G.arc(m-1)) == m-1, "Wrong index.");
     502}
     503
    381504void checkFullDigraph(int num) {
    382505  typedef FullDigraph Digraph;
    383506  DIGRAPH_TYPEDEFS(Digraph);
     507
    384508  Digraph G(num);
     509  check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size");
     510
     511  G.resize(num);
     512  check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size");
    385513
    386514  checkGraphNodeList(G, num);
     
    426554    checkDigraphValidity<SmartDigraph>();
    427555  }
     556  { // Checking StaticDigraph
     557    checkStaticDigraph();
     558  }
    428559  { // Checking FullDigraph
    429560    checkFullDigraph(8);
  • test/edge_set_test.cc

    r877 r964  
    4545
    4646  Digraph::Arc ga1 = digraph.addArc(n1, n2);
     47  ignore_unused_variable_warning(ga1);
    4748
    4849  ArcSet arc_set(digraph);
    4950
    5051  Digraph::Arc ga2 = digraph.addArc(n2, n1);
     52  ignore_unused_variable_warning(ga2);
    5153
    5254  checkGraphNodeList(arc_set, 2);
     
    7678    a3 = arc_set.addArc(n2, n3),
    7779    a4 = arc_set.addArc(n2, n3);
     80  ignore_unused_variable_warning(a2,a3,a4);
     81
    7882  checkGraphNodeList(arc_set, 3);
    7983  checkGraphArcList(arc_set, 4);
     
    111115
    112116  Digraph::Arc ga1 = digraph.addArc(n1, n2);
     117  ignore_unused_variable_warning(ga1);
    113118
    114119  ArcSet arc_set(digraph);
    115120
    116121  Digraph::Arc ga2 = digraph.addArc(n2, n1);
     122  ignore_unused_variable_warning(ga2);
    117123
    118124  checkGraphNodeList(arc_set, 2);
     
    142148    a3 = arc_set.addArc(n2, n3),
    143149    a4 = arc_set.addArc(n2, n3);
     150  ignore_unused_variable_warning(a2,a3,a4);
     151
    144152  checkGraphNodeList(arc_set, 3);
    145153  checkGraphArcList(arc_set, 4);
     
    191199
    192200  Digraph::Arc ga1 = digraph.addArc(n1, n2);
     201  ignore_unused_variable_warning(ga1);
    193202
    194203  EdgeSet edge_set(digraph);
    195204
    196205  Digraph::Arc ga2 = digraph.addArc(n2, n1);
     206  ignore_unused_variable_warning(ga2);
    197207
    198208  checkGraphNodeList(edge_set, 2);
     
    231241    e3 = edge_set.addEdge(n2, n3),
    232242    e4 = edge_set.addEdge(n2, n3);
     243  ignore_unused_variable_warning(e2,e3,e4);
     244
    233245  checkGraphNodeList(edge_set, 3);
    234246  checkGraphEdgeList(edge_set, 4);
     
    275287
    276288  Digraph::Arc ga1 = digraph.addArc(n1, n2);
     289  ignore_unused_variable_warning(ga1);
    277290
    278291  EdgeSet edge_set(digraph);
    279292
    280293  Digraph::Arc ga2 = digraph.addArc(n2, n1);
     294  ignore_unused_variable_warning(ga2);
    281295
    282296  checkGraphNodeList(edge_set, 2);
     
    315329    e3 = edge_set.addEdge(n2, n3),
    316330    e4 = edge_set.addEdge(n2, n3);
     331  ignore_unused_variable_warning(e2,e3,e4);
     332
    317333  checkGraphNodeList(edge_set, 3);
    318334  checkGraphEdgeList(edge_set, 4);
  • test/edge_set_test.cc

    r963 r964  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • test/euler_test.cc

    r877 r964  
    102102    Graph g(d);
    103103    Digraph::Node n = d.addNode();
    104 
     104    ignore_unused_variable_warning(n);
     105 
    105106    checkDiEulerIt(d);
    106107    checkDiEulerIt(g);
     
    190191    Digraph::Node n4 = d.addNode();
    191192    Digraph::Node n5 = d.addNode();
     193    ignore_unused_variable_warning(n0,n4,n5);
    192194
    193195    d.addArc(n1, n2);
  • test/euler_test.cc

    r963 r964  
    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).
     
    8686  typedef ListDigraph Digraph;
    8787  typedef Undirector<Digraph> Graph;
    88  
    89   {
    90     Digraph d;
    91     Graph g(d);
    92    
     88
     89  {
     90    Digraph d;
     91    Graph g(d);
     92
    9393    checkDiEulerIt(d);
    9494    checkDiEulerIt(g);
     
    130130    Digraph::Node n2 = d.addNode();
    131131    Digraph::Node n3 = d.addNode();
    132    
     132
    133133    d.addArc(n1, n2);
    134134    d.addArc(n2, n1);
     
    155155    Digraph::Node n5 = d.addNode();
    156156    Digraph::Node n6 = d.addNode();
    157    
     157
    158158    d.addArc(n1, n2);
    159159    d.addArc(n2, n4);
     
    214214    Digraph::Node n2 = d.addNode();
    215215    Digraph::Node n3 = d.addNode();
    216    
     216
    217217    d.addArc(n1, n2);
    218218    d.addArc(n2, n3);
  • test/graph_test.cc

    r877 r964  
    6767  Edge e2 = G.addEdge(n2, n1),
    6868       e3 = G.addEdge(n2, n3);
     69  ignore_unused_variable_warning(e2,e3);
    6970
    7071  checkGraphNodeList(G, 3);
     
    99100       e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
    100101       e5 = G.addEdge(n4, n3);
     102  ignore_unused_variable_warning(e1,e3,e4,e5);
    101103
    102104  checkGraphNodeList(G, 4);
     
    178180       e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
    179181       e5 = G.addEdge(n4, n3);
     182  ignore_unused_variable_warning(e1,e3,e4,e5);
    180183
    181184  // Check edge deletion
     
    218221  Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
    219222       e3 = G.addEdge(n2, n3);
     223  ignore_unused_variable_warning(e1,e2,e3);
    220224
    221225  checkGraphNodeList(G, 3);
     
    382386    e1 = g.addEdge(n1, n2),
    383387    e2 = g.addEdge(n2, n3);
     388  ignore_unused_variable_warning(e2);
    384389
    385390  check(g.valid(n1), "Wrong validity check");
     
    520525
    521526  Node n = G.nodeFromId(dim);
     527  ignore_unused_variable_warning(n);
    522528
    523529  for (NodeIt n(G); n != INVALID; ++n) {
  • test/graph_test.cc

    r963 r964  
    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).
     
    3939  checkGraphArcList(G, 0);
    4040
     41  G.reserveNode(3);
     42  G.reserveEdge(3);
     43
    4144  Node
    4245    n1 = G.addNode(),
     
    261264
    262265  snapshot.restore();
     266  snapshot.save(G);
    263267
    264268  checkGraphNodeList(G, 4);
    265269  checkGraphEdgeList(G, 3);
    266270  checkGraphArcList(G, 6);
     271
     272  G.addEdge(G.addNode(), G.addNode());
     273
     274  snapshot.restore();
     275
     276  checkGraphNodeList(G, 4);
     277  checkGraphEdgeList(G, 3);
     278  checkGraphArcList(G, 6);
    267279}
    268280
     
    272284
    273285  Graph G(num);
     286  check(G.nodeNum() == num && G.edgeNum() == num * (num - 1) / 2,
     287        "Wrong size");
     288
     289  G.resize(num);
     290  check(G.nodeNum() == num && G.edgeNum() == num * (num - 1) / 2,
     291        "Wrong size");
     292
    274293  checkGraphNodeList(G, num);
    275294  checkGraphEdgeList(G, num * (num - 1) / 2);
     
    417436  check(G.height() == height, "Wrong row number");
    418437
     438  G.resize(width, height);
     439  check(G.width() == width, "Wrong column number");
     440  check(G.height() == height, "Wrong row number");
     441
    419442  for (int i = 0; i < width; ++i) {
    420443    for (int j = 0; j < height; ++j) {
     
    492515
    493516  HypercubeGraph G(dim);
     517  check(G.dimension() == dim, "Wrong dimension");
     518
     519  G.resize(dim);
     520  check(G.dimension() == dim, "Wrong dimension");
     521
    494522  checkGraphNodeList(G, 1 << dim);
    495523  checkGraphEdgeList(G, dim * (1 << (dim-1)));
  • test/maps_test.cc

    r915 r964  
    104104    NullMap<A,B> map1;
    105105    NullMap<A,B> map2 = map1;
     106    ignore_unused_variable_warning(map2);
    106107    map1 = nullMap<A,B>();
    107108  }
     
    114115    ConstMap<A,B> map2 = B();
    115116    ConstMap<A,B> map3 = map1;
     117    ignore_unused_variable_warning(map2,map3);
     118
    116119    map1 = constMap<A>(B());
    117120    map1 = constMap<A,B>();
     
    119122    ConstMap<A,C> map4(C(1));
    120123    ConstMap<A,C> map5 = map4;
     124    ignore_unused_variable_warning(map5);
     125
    121126    map4 = constMap<A>(C(2));
    122127    map4.setAll(C(3));
     
    139144    IdentityMap<A> map1;
    140145    IdentityMap<A> map2 = map1;
     146    ignore_unused_variable_warning(map2);
     147
    141148    map1 = identityMap<A>();
    142149
     
    198205    checkConcept<ReadMap<B,double>, CompMap>();
    199206    CompMap map1 = CompMap(DoubleMap(),ReadMap<B,A>());
     207    ignore_unused_variable_warning(map1);
    200208    CompMap map2 = composeMap(DoubleMap(), ReadMap<B,A>());
     209    ignore_unused_variable_warning(map2);
    201210
    202211    SparseMap<double, bool> m1(false); m1[3.14] = true;
     
    211220    checkConcept<ReadMap<A,double>, CombMap>();
    212221    CombMap map1 = CombMap(DoubleMap(), DoubleMap());
     222    ignore_unused_variable_warning(map1);
    213223    CombMap map2 = combineMap(DoubleMap(), DoubleMap(), std::plus<double>());
     224    ignore_unused_variable_warning(map2);
    214225
    215226    check(combineMap(constMap<B,int,2>(), identityMap<B>(), &binc)[B()] == 3,
     
    223234    FunctorToMap<F> map1;
    224235    FunctorToMap<F> map2 = FunctorToMap<F>(F());
     236    ignore_unused_variable_warning(map2);
     237
    225238    B b = functorToMap(F())[A()];
     239    ignore_unused_variable_warning(b);
    226240
    227241    checkConcept<ReadMap<A,B>, MapToFunctor<ReadMap<A,B> > >();
    228242    MapToFunctor<ReadMap<A,B> > map =
    229243      MapToFunctor<ReadMap<A,B> >(ReadMap<A,B>());
     244    ignore_unused_variable_warning(map);
    230245
    231246    check(functorToMap(&func)[A()] == 3,
     
    245260      ConvertMap<ReadMap<double, int>, double> >();
    246261    ConvertMap<RangeMap<bool>, int> map1(rangeMap(1, true));
     262    ignore_unused_variable_warning(map1);
    247263    ConvertMap<RangeMap<bool>, int> map2 = convertMap<int>(rangeMap(2, false));
     264    ignore_unused_variable_warning(map2);
     265
    248266  }
    249267
  • test/maps_test.cc

    r963 r964  
    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).
     
    2424#include <lemon/maps.h>
    2525#include <lemon/list_graph.h>
     26#include <lemon/smart_graph.h>
     27#include <lemon/adaptors.h>
     28#include <lemon/dfs.h>
     29#include <algorithm>
    2630
    2731#include "test_tools.h"
     
    3539
    3640class C {
    37   int x;
     41  int _x;
    3842public:
    39   C(int _x) : x(_x) {}
     43  C(int x) : _x(x) {}
     44  int get() const { return _x; }
     45};
     46inline bool operator<(C c1, C c2) { return c1.get() < c2.get(); }
     47inline bool operator==(C c1, C c2) { return c1.get() == c2.get(); }
     48
     49C createC(int x) { return C(x); }
     50
     51template <typename T>
     52class Less {
     53  T _t;
     54public:
     55  Less(T t): _t(t) {}
     56  bool operator()(const T& t) const { return t < _t; }
    4057};
    4158
     
    5370
    5471int binc(int a, B) { return a+1; }
     72
     73template <typename T>
     74class Sum {
     75  T& _sum;
     76public:
     77  Sum(T& sum) : _sum(sum) {}
     78  void operator()(const T& t) { _sum += t; }
     79};
    5580
    5681typedef ReadMap<A, double> DoubleMap;
     
    349374  {
    350375    typedef std::vector<int> vec;
     376    checkConcept<WriteMap<int, bool>, LoggerBoolMap<vec::iterator> >();
     377    checkConcept<WriteMap<int, bool>,
     378                 LoggerBoolMap<std::back_insert_iterator<vec> > >();
     379
    351380    vec v1;
    352381    vec v2(10);
     
    368397          it != map2.end(); ++it )
    369398      check(v1[i++] == *it, "Something is wrong with LoggerBoolMap");
    370   }
    371  
    372   // CrossRefMap
    373   {
     399
    374400    typedef ListDigraph Graph;
    375401    DIGRAPH_TYPEDEFS(Graph);
     402    Graph gr;
     403
     404    Node n0 = gr.addNode();
     405    Node n1 = gr.addNode();
     406    Node n2 = gr.addNode();
     407    Node n3 = gr.addNode();
     408
     409    gr.addArc(n3, n0);
     410    gr.addArc(n3, n2);
     411    gr.addArc(n0, n2);
     412    gr.addArc(n2, n1);
     413    gr.addArc(n0, n1);
     414
     415    {
     416      std::vector<Node> v;
     417      dfs(gr).processedMap(loggerBoolMap(std::back_inserter(v))).run();
     418
     419      check(v.size()==4 && v[0]==n1 && v[1]==n2 && v[2]==n0 && v[3]==n3,
     420            "Something is wrong with LoggerBoolMap");
     421    }
     422    {
     423      std::vector<Node> v(countNodes(gr));
     424      dfs(gr).processedMap(loggerBoolMap(v.begin())).run();
     425
     426      check(v.size()==4 && v[0]==n1 && v[1]==n2 && v[2]==n0 && v[3]==n3,
     427            "Something is wrong with LoggerBoolMap");
     428    }
     429  }
     430
     431  // IdMap, RangeIdMap
     432  {
     433    typedef ListDigraph Graph;
     434    DIGRAPH_TYPEDEFS(Graph);
     435
     436    checkConcept<ReadMap<Node, int>, IdMap<Graph, Node> >();
     437    checkConcept<ReadMap<Arc, int>, IdMap<Graph, Arc> >();
     438    checkConcept<ReadMap<Node, int>, RangeIdMap<Graph, Node> >();
     439    checkConcept<ReadMap<Arc, int>, RangeIdMap<Graph, Arc> >();
     440
     441    Graph gr;
     442    IdMap<Graph, Node> nmap(gr);
     443    IdMap<Graph, Arc> amap(gr);
     444    RangeIdMap<Graph, Node> nrmap(gr);
     445    RangeIdMap<Graph, Arc> armap(gr);
     446
     447    Node n0 = gr.addNode();
     448    Node n1 = gr.addNode();
     449    Node n2 = gr.addNode();
     450
     451    Arc a0 = gr.addArc(n0, n1);
     452    Arc a1 = gr.addArc(n0, n2);
     453    Arc a2 = gr.addArc(n2, n1);
     454    Arc a3 = gr.addArc(n2, n0);
     455
     456    check(nmap[n0] == gr.id(n0) && nmap(gr.id(n0)) == n0, "Wrong IdMap");
     457    check(nmap[n1] == gr.id(n1) && nmap(gr.id(n1)) == n1, "Wrong IdMap");
     458    check(nmap[n2] == gr.id(n2) && nmap(gr.id(n2)) == n2, "Wrong IdMap");
     459
     460    check(amap[a0] == gr.id(a0) && amap(gr.id(a0)) == a0, "Wrong IdMap");
     461    check(amap[a1] == gr.id(a1) && amap(gr.id(a1)) == a1, "Wrong IdMap");
     462    check(amap[a2] == gr.id(a2) && amap(gr.id(a2)) == a2, "Wrong IdMap");
     463    check(amap[a3] == gr.id(a3) && amap(gr.id(a3)) == a3, "Wrong IdMap");
     464
     465    check(nmap.inverse()[gr.id(n0)] == n0, "Wrong IdMap::InverseMap");
     466    check(amap.inverse()[gr.id(a0)] == a0, "Wrong IdMap::InverseMap");
     467
     468    check(nrmap.size() == 3 && armap.size() == 4,
     469          "Wrong RangeIdMap::size()");
     470
     471    check(nrmap[n0] == 0 && nrmap(0) == n0, "Wrong RangeIdMap");
     472    check(nrmap[n1] == 1 && nrmap(1) == n1, "Wrong RangeIdMap");
     473    check(nrmap[n2] == 2 && nrmap(2) == n2, "Wrong RangeIdMap");
     474
     475    check(armap[a0] == 0 && armap(0) == a0, "Wrong RangeIdMap");
     476    check(armap[a1] == 1 && armap(1) == a1, "Wrong RangeIdMap");
     477    check(armap[a2] == 2 && armap(2) == a2, "Wrong RangeIdMap");
     478    check(armap[a3] == 3 && armap(3) == a3, "Wrong RangeIdMap");
     479
     480    check(nrmap.inverse()[0] == n0, "Wrong RangeIdMap::InverseMap");
     481    check(armap.inverse()[0] == a0, "Wrong RangeIdMap::InverseMap");
     482
     483    gr.erase(n1);
     484
     485    if (nrmap[n0] == 1) nrmap.swap(n0, n2);
     486    nrmap.swap(n2, n0);
     487    if (armap[a1] == 1) armap.swap(a1, a3);
     488    armap.swap(a3, a1);
     489
     490    check(nrmap.size() == 2 && armap.size() == 2,
     491          "Wrong RangeIdMap::size()");
     492
     493    check(nrmap[n0] == 1 && nrmap(1) == n0, "Wrong RangeIdMap");
     494    check(nrmap[n2] == 0 && nrmap(0) == n2, "Wrong RangeIdMap");
     495
     496    check(armap[a1] == 1 && armap(1) == a1, "Wrong RangeIdMap");
     497    check(armap[a3] == 0 && armap(0) == a3, "Wrong RangeIdMap");
     498
     499    check(nrmap.inverse()[0] == n2, "Wrong RangeIdMap::InverseMap");
     500    check(armap.inverse()[0] == a3, "Wrong RangeIdMap::InverseMap");
     501  }
     502
     503  // SourceMap, TargetMap, ForwardMap, BackwardMap, InDegMap, OutDegMap
     504  {
     505    typedef ListGraph Graph;
     506    GRAPH_TYPEDEFS(Graph);
     507
     508    checkConcept<ReadMap<Arc, Node>, SourceMap<Graph> >();
     509    checkConcept<ReadMap<Arc, Node>, TargetMap<Graph> >();
     510    checkConcept<ReadMap<Edge, Arc>, ForwardMap<Graph> >();
     511    checkConcept<ReadMap<Edge, Arc>, BackwardMap<Graph> >();
     512    checkConcept<ReadMap<Node, int>, InDegMap<Graph> >();
     513    checkConcept<ReadMap<Node, int>, OutDegMap<Graph> >();
     514
     515    Graph gr;
     516    Node n0 = gr.addNode();
     517    Node n1 = gr.addNode();
     518    Node n2 = gr.addNode();
     519
     520    gr.addEdge(n0,n1);
     521    gr.addEdge(n1,n2);
     522    gr.addEdge(n0,n2);
     523    gr.addEdge(n2,n1);
     524    gr.addEdge(n1,n2);
     525    gr.addEdge(n0,n1);
     526
     527    for (EdgeIt e(gr); e != INVALID; ++e) {
     528      check(forwardMap(gr)[e] == gr.direct(e, true), "Wrong ForwardMap");
     529      check(backwardMap(gr)[e] == gr.direct(e, false), "Wrong BackwardMap");
     530    }
     531
     532    check(mapCompare(gr,
     533          sourceMap(orienter(gr, constMap<Edge, bool>(true))),
     534          targetMap(orienter(gr, constMap<Edge, bool>(false)))),
     535          "Wrong SourceMap or TargetMap");
     536
     537    typedef Orienter<Graph, const ConstMap<Edge, bool> > Digraph;
     538    Digraph dgr(gr, constMap<Edge, bool>(true));
     539    OutDegMap<Digraph> odm(dgr);
     540    InDegMap<Digraph> idm(dgr);
     541
     542    check(odm[n0] == 3 && odm[n1] == 2 && odm[n2] == 1, "Wrong OutDegMap");
     543    check(idm[n0] == 0 && idm[n1] == 3 && idm[n2] == 3, "Wrong InDegMap");
     544
     545    gr.addEdge(n2, n0);
     546
     547    check(odm[n0] == 3 && odm[n1] == 2 && odm[n2] == 2, "Wrong OutDegMap");
     548    check(idm[n0] == 1 && idm[n1] == 3 && idm[n2] == 3, "Wrong InDegMap");
     549  }
     550
     551  // CrossRefMap
     552  {
     553    typedef ListDigraph Graph;
     554    DIGRAPH_TYPEDEFS(Graph);
    376555
    377556    checkConcept<ReadWriteMap<Node, int>,
    378557                 CrossRefMap<Graph, Node, int> >();
    379    
     558    checkConcept<ReadWriteMap<Node, bool>,
     559                 CrossRefMap<Graph, Node, bool> >();
     560    checkConcept<ReadWriteMap<Node, double>,
     561                 CrossRefMap<Graph, Node, double> >();
     562
     563    Graph gr;
     564    typedef CrossRefMap<Graph, Node, char> CRMap;
     565    CRMap map(gr);
     566
     567    Node n0 = gr.addNode();
     568    Node n1 = gr.addNode();
     569    Node n2 = gr.addNode();
     570
     571    map.set(n0, 'A');
     572    map.set(n1, 'B');
     573    map.set(n2, 'C');
     574
     575    check(map[n0] == 'A' && map('A') == n0 && map.inverse()['A'] == n0,
     576          "Wrong CrossRefMap");
     577    check(map[n1] == 'B' && map('B') == n1 && map.inverse()['B'] == n1,
     578          "Wrong CrossRefMap");
     579    check(map[n2] == 'C' && map('C') == n2 && map.inverse()['C'] == n2,
     580          "Wrong CrossRefMap");
     581    check(map.count('A') == 1 && map.count('B') == 1 && map.count('C') == 1,
     582          "Wrong CrossRefMap::count()");
     583
     584    CRMap::ValueIt it = map.beginValue();
     585    check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&
     586          it == map.endValue(), "Wrong value iterator");
     587
     588    map.set(n2, 'A');
     589
     590    check(map[n0] == 'A' && map[n1] == 'B' && map[n2] == 'A',
     591          "Wrong CrossRefMap");
     592    check(map('A') == n0 && map.inverse()['A'] == n0, "Wrong CrossRefMap");
     593    check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap");
     594    check(map('C') == INVALID && map.inverse()['C'] == INVALID,
     595          "Wrong CrossRefMap");
     596    check(map.count('A') == 2 && map.count('B') == 1 && map.count('C') == 0,
     597          "Wrong CrossRefMap::count()");
     598
     599    it = map.beginValue();
     600    check(*it++ == 'A' && *it++ == 'A' && *it++ == 'B' &&
     601          it == map.endValue(), "Wrong value iterator");
     602
     603    map.set(n0, 'C');
     604
     605    check(map[n0] == 'C' && map[n1] == 'B' && map[n2] == 'A',
     606          "Wrong CrossRefMap");
     607    check(map('A') == n2 && map.inverse()['A'] == n2, "Wrong CrossRefMap");
     608    check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap");
     609    check(map('C') == n0 && map.inverse()['C'] == n0, "Wrong CrossRefMap");
     610    check(map.count('A') == 1 && map.count('B') == 1 && map.count('C') == 1,
     611          "Wrong CrossRefMap::count()");
     612
     613    it = map.beginValue();
     614    check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&
     615          it == map.endValue(), "Wrong value iterator");
     616  }
     617
     618  // CrossRefMap
     619  {
     620    typedef SmartDigraph Graph;
     621    DIGRAPH_TYPEDEFS(Graph);
     622
     623    checkConcept<ReadWriteMap<Node, int>,
     624                 CrossRefMap<Graph, Node, int> >();
     625
    380626    Graph gr;
    381627    typedef CrossRefMap<Graph, Node, char> CRMap;
    382628    typedef CRMap::ValueIterator ValueIt;
    383629    CRMap map(gr);
    384    
     630
    385631    Node n0 = gr.addNode();
    386632    Node n1 = gr.addNode();
    387633    Node n2 = gr.addNode();
    388    
     634
    389635    map.set(n0, 'A');
    390636    map.set(n1, 'B');
     
    404650  }
    405651
     652  // Iterable bool map
     653  {
     654    typedef SmartGraph Graph;
     655    typedef SmartGraph::Node Item;
     656
     657    typedef IterableBoolMap<SmartGraph, SmartGraph::Node> Ibm;
     658    checkConcept<ReferenceMap<Item, bool, bool&, const bool&>, Ibm>();
     659
     660    const int num = 10;
     661    Graph g;
     662    Ibm map0(g, true);
     663    std::vector<Item> items;
     664    for (int i = 0; i < num; ++i) {
     665      items.push_back(g.addNode());
     666    }
     667
     668    Ibm map1(g, true);
     669    int n = 0;
     670    for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
     671      check(map1[static_cast<Item>(it)], "Wrong TrueIt");
     672      ++n;
     673    }
     674    check(n == num, "Wrong number");
     675
     676    n = 0;
     677    for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) {
     678        check(map1[static_cast<Item>(it)], "Wrong ItemIt for true");
     679        ++n;
     680    }
     681    check(n == num, "Wrong number");
     682    check(Ibm::FalseIt(map1) == INVALID, "Wrong FalseIt");
     683    check(Ibm::ItemIt(map1, false) == INVALID, "Wrong ItemIt for false");
     684
     685    map1[items[5]] = true;
     686
     687    n = 0;
     688    for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) {
     689        check(map1[static_cast<Item>(it)], "Wrong ItemIt for true");
     690        ++n;
     691    }
     692    check(n == num, "Wrong number");
     693
     694    map1[items[num / 2]] = false;
     695    check(map1[items[num / 2]] == false, "Wrong map value");
     696
     697    n = 0;
     698    for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
     699        check(map1[static_cast<Item>(it)], "Wrong TrueIt for true");
     700        ++n;
     701    }
     702    check(n == num - 1, "Wrong number");
     703
     704    n = 0;
     705    for (Ibm::FalseIt it(map1); it != INVALID; ++it) {
     706        check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true");
     707        ++n;
     708    }
     709    check(n == 1, "Wrong number");
     710
     711    map1[items[0]] = false;
     712    check(map1[items[0]] == false, "Wrong map value");
     713
     714    map1[items[num - 1]] = false;
     715    check(map1[items[num - 1]] == false, "Wrong map value");
     716
     717    n = 0;
     718    for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
     719        check(map1[static_cast<Item>(it)], "Wrong TrueIt for true");
     720        ++n;
     721    }
     722    check(n == num - 3, "Wrong number");
     723    check(map1.trueNum() == num - 3, "Wrong number");
     724
     725    n = 0;
     726    for (Ibm::FalseIt it(map1); it != INVALID; ++it) {
     727        check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true");
     728        ++n;
     729    }
     730    check(n == 3, "Wrong number");
     731    check(map1.falseNum() == 3, "Wrong number");
     732  }
     733
     734  // Iterable int map
     735  {
     736    typedef SmartGraph Graph;
     737    typedef SmartGraph::Node Item;
     738    typedef IterableIntMap<SmartGraph, SmartGraph::Node> Iim;
     739
     740    checkConcept<ReferenceMap<Item, int, int&, const int&>, Iim>();
     741
     742    const int num = 10;
     743    Graph g;
     744    Iim map0(g, 0);
     745    std::vector<Item> items;
     746    for (int i = 0; i < num; ++i) {
     747      items.push_back(g.addNode());
     748    }
     749
     750    Iim map1(g);
     751    check(map1.size() == 0, "Wrong size");
     752
     753    for (int i = 0; i < num; ++i) {
     754      map1[items[i]] = i;
     755    }
     756    check(map1.size() == num, "Wrong size");
     757
     758    for (int i = 0; i < num; ++i) {
     759      Iim::ItemIt it(map1, i);
     760      check(static_cast<Item>(it) == items[i], "Wrong value");
     761      ++it;
     762      check(static_cast<Item>(it) == INVALID, "Wrong value");
     763    }
     764
     765    for (int i = 0; i < num; ++i) {
     766      map1[items[i]] = i % 2;
     767    }
     768    check(map1.size() == 2, "Wrong size");
     769
     770    int n = 0;
     771    for (Iim::ItemIt it(map1, 0); it != INVALID; ++it) {
     772      check(map1[static_cast<Item>(it)] == 0, "Wrong value");
     773      ++n;
     774    }
     775    check(n == (num + 1) / 2, "Wrong number");
     776
     777    for (Iim::ItemIt it(map1, 1); it != INVALID; ++it) {
     778      check(map1[static_cast<Item>(it)] == 1, "Wrong value");
     779      ++n;
     780    }
     781    check(n == num, "Wrong number");
     782
     783  }
     784
     785  // Iterable value map
     786  {
     787    typedef SmartGraph Graph;
     788    typedef SmartGraph::Node Item;
     789    typedef IterableValueMap<SmartGraph, SmartGraph::Node, double> Ivm;
     790
     791    checkConcept<ReadWriteMap<Item, double>, Ivm>();
     792
     793    const int num = 10;
     794    Graph g;
     795    Ivm map0(g, 0.0);
     796    std::vector<Item> items;
     797    for (int i = 0; i < num; ++i) {
     798      items.push_back(g.addNode());
     799    }
     800
     801    Ivm map1(g, 0.0);
     802    check(distance(map1.beginValue(), map1.endValue()) == 1, "Wrong size");
     803    check(*map1.beginValue() == 0.0, "Wrong value");
     804
     805    for (int i = 0; i < num; ++i) {
     806      map1.set(items[i], static_cast<double>(i));
     807    }
     808    check(distance(map1.beginValue(), map1.endValue()) == num, "Wrong size");
     809
     810    for (int i = 0; i < num; ++i) {
     811      Ivm::ItemIt it(map1, static_cast<double>(i));
     812      check(static_cast<Item>(it) == items[i], "Wrong value");
     813      ++it;
     814      check(static_cast<Item>(it) == INVALID, "Wrong value");
     815    }
     816
     817    for (Ivm::ValueIt vit = map1.beginValue();
     818         vit != map1.endValue(); ++vit) {
     819      check(map1[static_cast<Item>(Ivm::ItemIt(map1, *vit))] == *vit,
     820            "Wrong ValueIt");
     821    }
     822
     823    for (int i = 0; i < num; ++i) {
     824      map1.set(items[i], static_cast<double>(i % 2));
     825    }
     826    check(distance(map1.beginValue(), map1.endValue()) == 2, "Wrong size");
     827
     828    int n = 0;
     829    for (Ivm::ItemIt it(map1, 0.0); it != INVALID; ++it) {
     830      check(map1[static_cast<Item>(it)] == 0.0, "Wrong value");
     831      ++n;
     832    }
     833    check(n == (num + 1) / 2, "Wrong number");
     834
     835    for (Ivm::ItemIt it(map1, 1.0); it != INVALID; ++it) {
     836      check(map1[static_cast<Item>(it)] == 1.0, "Wrong value");
     837      ++n;
     838    }
     839    check(n == num, "Wrong number");
     840
     841  }
     842
     843  // Graph map utilities:
     844  // mapMin(), mapMax(), mapMinValue(), mapMaxValue()
     845  // mapFind(), mapFindIf(), mapCount(), mapCountIf()
     846  // mapCopy(), mapCompare(), mapFill()
     847  {
     848    DIGRAPH_TYPEDEFS(SmartDigraph);
     849
     850    SmartDigraph g;
     851    Node n1 = g.addNode();
     852    Node n2 = g.addNode();
     853    Node n3 = g.addNode();
     854
     855    SmartDigraph::NodeMap<int> map1(g);
     856    SmartDigraph::ArcMap<char> map2(g);
     857    ConstMap<Node, A> cmap1 = A();
     858    ConstMap<Arc, C> cmap2 = C(0);
     859
     860    map1[n1] = 10;
     861    map1[n2] = 5;
     862    map1[n3] = 12;
     863
     864    // mapMin(), mapMax(), mapMinValue(), mapMaxValue()
     865    check(mapMin(g, map1) == n2, "Wrong mapMin()");
     866    check(mapMax(g, map1) == n3, "Wrong mapMax()");
     867    check(mapMin(g, map1, std::greater<int>()) == n3, "Wrong mapMin()");
     868    check(mapMax(g, map1, std::greater<int>()) == n2, "Wrong mapMax()");
     869    check(mapMinValue(g, map1) == 5, "Wrong mapMinValue()");
     870    check(mapMaxValue(g, map1) == 12, "Wrong mapMaxValue()");
     871
     872    check(mapMin(g, map2) == INVALID, "Wrong mapMin()");
     873    check(mapMax(g, map2) == INVALID, "Wrong mapMax()");
     874
     875    check(mapMin(g, cmap1) != INVALID, "Wrong mapMin()");
     876    check(mapMax(g, cmap2) == INVALID, "Wrong mapMax()");
     877
     878    Arc a1 = g.addArc(n1, n2);
     879    Arc a2 = g.addArc(n1, n3);
     880    Arc a3 = g.addArc(n2, n3);
     881    Arc a4 = g.addArc(n3, n1);
     882
     883    map2[a1] = 'b';
     884    map2[a2] = 'a';
     885    map2[a3] = 'b';
     886    map2[a4] = 'c';
     887
     888    // mapMin(), mapMax(), mapMinValue(), mapMaxValue()
     889    check(mapMin(g, map2) == a2, "Wrong mapMin()");
     890    check(mapMax(g, map2) == a4, "Wrong mapMax()");
     891    check(mapMin(g, map2, std::greater<int>()) == a4, "Wrong mapMin()");
     892    check(mapMax(g, map2, std::greater<int>()) == a2, "Wrong mapMax()");
     893    check(mapMinValue(g, map2, std::greater<int>()) == 'c',
     894          "Wrong mapMinValue()");
     895    check(mapMaxValue(g, map2, std::greater<int>()) == 'a',
     896          "Wrong mapMaxValue()");
     897
     898    check(mapMin(g, cmap1) != INVALID, "Wrong mapMin()");
     899    check(mapMax(g, cmap2) != INVALID, "Wrong mapMax()");
     900    check(mapMaxValue(g, cmap2) == C(0), "Wrong mapMaxValue()");
     901
     902    check(mapMin(g, composeMap(functorToMap(&createC), map2)) == a2,
     903          "Wrong mapMin()");
     904    check(mapMax(g, composeMap(functorToMap(&createC), map2)) == a4,
     905          "Wrong mapMax()");
     906    check(mapMinValue(g, composeMap(functorToMap(&createC), map2)) == C('a'),
     907          "Wrong mapMinValue()");
     908    check(mapMaxValue(g, composeMap(functorToMap(&createC), map2)) == C('c'),
     909          "Wrong mapMaxValue()");
     910
     911    // mapFind(), mapFindIf()
     912    check(mapFind(g, map1, 5) == n2, "Wrong mapFind()");
     913    check(mapFind(g, map1, 6) == INVALID, "Wrong mapFind()");
     914    check(mapFind(g, map2, 'a') == a2, "Wrong mapFind()");
     915    check(mapFind(g, map2, 'e') == INVALID, "Wrong mapFind()");
     916    check(mapFind(g, cmap2, C(0)) == ArcIt(g), "Wrong mapFind()");
     917    check(mapFind(g, cmap2, C(1)) == INVALID, "Wrong mapFind()");
     918
     919    check(mapFindIf(g, map1, Less<int>(7)) == n2,
     920          "Wrong mapFindIf()");
     921    check(mapFindIf(g, map1, Less<int>(5)) == INVALID,
     922          "Wrong mapFindIf()");
     923    check(mapFindIf(g, map2, Less<char>('d')) == ArcIt(g),
     924          "Wrong mapFindIf()");
     925    check(mapFindIf(g, map2, Less<char>('a')) == INVALID,
     926          "Wrong mapFindIf()");
     927
     928    // mapCount(), mapCountIf()
     929    check(mapCount(g, map1, 5) == 1, "Wrong mapCount()");
     930    check(mapCount(g, map1, 6) == 0, "Wrong mapCount()");
     931    check(mapCount(g, map2, 'a') == 1, "Wrong mapCount()");
     932    check(mapCount(g, map2, 'b') == 2, "Wrong mapCount()");
     933    check(mapCount(g, map2, 'e') == 0, "Wrong mapCount()");
     934    check(mapCount(g, cmap2, C(0)) == 4, "Wrong mapCount()");
     935    check(mapCount(g, cmap2, C(1)) == 0, "Wrong mapCount()");
     936
     937    check(mapCountIf(g, map1, Less<int>(11)) == 2,
     938          "Wrong mapCountIf()");
     939    check(mapCountIf(g, map1, Less<int>(13)) == 3,
     940          "Wrong mapCountIf()");
     941    check(mapCountIf(g, map1, Less<int>(5)) == 0,
     942          "Wrong mapCountIf()");
     943    check(mapCountIf(g, map2, Less<char>('d')) == 4,
     944          "Wrong mapCountIf()");
     945    check(mapCountIf(g, map2, Less<char>('c')) == 3,
     946          "Wrong mapCountIf()");
     947    check(mapCountIf(g, map2, Less<char>('a')) == 0,
     948          "Wrong mapCountIf()");
     949
     950    // MapIt, ConstMapIt
     951/*
     952These tests can be used after applying bugfix #330
     953    typedef SmartDigraph::NodeMap<int>::MapIt MapIt;
     954    typedef SmartDigraph::NodeMap<int>::ConstMapIt ConstMapIt;
     955    check(*std::min_element(MapIt(map1), MapIt(INVALID)) == 5,
     956          "Wrong NodeMap<>::MapIt");
     957    check(*std::max_element(ConstMapIt(map1), ConstMapIt(INVALID)) == 12,
     958          "Wrong NodeMap<>::MapIt");
     959
     960    int sum = 0;
     961    std::for_each(MapIt(map1), MapIt(INVALID), Sum<int>(sum));
     962    check(sum == 27, "Wrong NodeMap<>::MapIt");
     963    std::for_each(ConstMapIt(map1), ConstMapIt(INVALID), Sum<int>(sum));
     964    check(sum == 54, "Wrong NodeMap<>::ConstMapIt");
     965*/
     966
     967    // mapCopy(), mapCompare(), mapFill()
     968    check(mapCompare(g, map1, map1), "Wrong mapCompare()");
     969    check(mapCompare(g, cmap2, cmap2), "Wrong mapCompare()");
     970    check(mapCompare(g, map1, shiftMap(map1, 0)), "Wrong mapCompare()");
     971    check(mapCompare(g, map2, scaleMap(map2, 1)), "Wrong mapCompare()");
     972    check(!mapCompare(g, map1, shiftMap(map1, 1)), "Wrong mapCompare()");
     973
     974    SmartDigraph::NodeMap<int> map3(g, 0);
     975    SmartDigraph::ArcMap<char> map4(g, 'a');
     976
     977    check(!mapCompare(g, map1, map3), "Wrong mapCompare()");
     978    check(!mapCompare(g, map2, map4), "Wrong mapCompare()");
     979
     980    mapCopy(g, map1, map3);
     981    mapCopy(g, map2, map4);
     982
     983    check(mapCompare(g, map1, map3), "Wrong mapCompare() or mapCopy()");
     984    check(mapCompare(g, map2, map4), "Wrong mapCompare() or mapCopy()");
     985
     986    Undirector<SmartDigraph> ug(g);
     987    Undirector<SmartDigraph>::EdgeMap<char> umap1(ug, 'x');
     988    Undirector<SmartDigraph>::ArcMap<double> umap2(ug, 3.14);
     989
     990    check(!mapCompare(g, map2, umap1), "Wrong mapCompare() or mapCopy()");
     991    check(!mapCompare(g, umap1, map2), "Wrong mapCompare() or mapCopy()");
     992    check(!mapCompare(ug, map2, umap1), "Wrong mapCompare() or mapCopy()");
     993    check(!mapCompare(ug, umap1, map2), "Wrong mapCompare() or mapCopy()");
     994
     995    mapCopy(g, map2, umap1);
     996
     997    check(mapCompare(g, map2, umap1), "Wrong mapCompare() or mapCopy()");
     998    check(mapCompare(g, umap1, map2), "Wrong mapCompare() or mapCopy()");
     999    check(mapCompare(ug, map2, umap1), "Wrong mapCompare() or mapCopy()");
     1000    check(mapCompare(ug, umap1, map2), "Wrong mapCompare() or mapCopy()");
     1001
     1002    mapCopy(g, map2, umap1);
     1003    mapCopy(g, umap1, map2);
     1004    mapCopy(ug, map2, umap1);
     1005    mapCopy(ug, umap1, map2);
     1006
     1007    check(!mapCompare(ug, umap1, umap2), "Wrong mapCompare() or mapCopy()");
     1008    mapCopy(ug, umap1, umap2);
     1009    check(mapCompare(ug, umap1, umap2), "Wrong mapCompare() or mapCopy()");
     1010
     1011    check(!mapCompare(g, map1, constMap<Node>(2)), "Wrong mapCompare()");
     1012    mapFill(g, map1, 2);
     1013    check(mapCompare(g, constMap<Node>(2), map1), "Wrong mapFill()");
     1014
     1015    check(!mapCompare(g, map2, constMap<Arc>('z')), "Wrong mapCompare()");
     1016    mapCopy(g, constMap<Arc>('z'), map2);
     1017    check(mapCompare(g, constMap<Arc>('z'), map2), "Wrong mapCopy()");
     1018  }
     1019
    4061020  return 0;
    4071021}
Note: See TracChangeset for help on using the changeset viewer.