COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
Files:
1 added
16 edited

Legend:

Unmodified
Added
Removed

  • CMakeLists.txt

    r540 r541  
    1111
    1212SET(CMAKE_MODULE_PATH ${CMAKE_SOURCE_DIR}/cmake)
     13
     14IF(MSVC)
     15  SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} /wd4250 /wd4355 /wd4800 /wd4996")
     16# Suppressed warnings:
     17# C4250: 'class1' : inherits 'class2::member' via dominance
     18# C4355: 'this' : used in base member initializer list
     19# C4800: 'type' : forcing value to bool 'true' or 'false' (performance warning)
     20# C4996: 'function': was declared deprecated
     21ENDIF(MSVC)
    1322
    1423INCLUDE(FindDoxygen)

  • NEWS

    r534 r937  
     12010-03-08 Version 1.0.5 released
     2
     3        Bugfix release.
     4
     5        #250: Fix in pathSource() and pathTarget()
     6        #321: Use pathCopy(from,to) instead of copyPath(to,from)
     7        #330: Bug fix in map_extender.h
     8        #335: Fix clear() function in ExtendFindEnum (#335)
     9        #336: Fix the date field comment of graphToEps() output
     10
     112009-05-05 Version 1.0.4 released
     12
     13        Bugfix release.
     14
     15        #274,#280: Install lemon/config.h and fix its bad include by core.h
     16        #275: Prefix macro names with LEMON_ in lemon/config.h
     17        ----: Small script for making the release tarballs added
     18        ----: Minor improvement in unify-sources.sh (a76f55d7d397)
     19
    1202009-03-27 LEMON joins to the COIN-OR initiative
    221
    … …  
    524        development of open-source software for the operations research
    625        community.
     26
     272009-03-26 Version 1.0.3 released
     28
     29        Bugfix release, mainly targeting better AIX/xlC and WIN32
     30        compatibility.
     31
     32        ----: Minor clarification in the LICENSE file
     33        ----: Add missing unistd.h include to time_measure.h
     34        #204: Compilation bug fixed in graph_to_eps.h with VS2005
     35        #214,#215: windows.h is never be included by lemon headers
     36        #230: Build systems check the availability of 'long long' type
     37        #229: Default implementation of Tolerance<> is used for integer types
     38        #211,#212: Various fixes for compiling on AIX
     39        ----: Improvements in CMAKE config
     40              - docs is installed in share/doc/
     41              - detects newer versions of Ghostscript
     42        #239: Fix missing 'inline' specifier in time_measure.h
     43       
     442009-01-23 Version 1.0.2 released
     45
     46        Bugfix release.
     47
     48        #193: Bugfix in GraphReader::skipSection()
     49        #195: Bugfix in ConEdgeIt()
     50        #197: Bugfix in heap unionfind
     51              * This bug affects Edmond's general matching algorithms.
     52                (Not available in this release.)
     53        #207: Fix 'make install' without 'make html' using CMAKE
     54        #208: Suppress or fix VS2008 compilation warnings
     55        ----: Update the LEMON icon
     56        ----: Enable the component-based installer
     57              (in installers made by CPACK)
     58        ----: Set the proper version for CMAKE in the tarballs
     59              (made by autotools).
     60
     612008-12-06 Version 1.0.1 released
     62
     63        Bugfix release.
     64
     65        #170: Bugfix SmartDigraph::split()
     66        #171: Bugfix in SmartGraph::restoreSnapshot()
     67        #172: Extended test cases for graphs and digraphs
     68        #173: Bugfix in Random
     69              * operator()s always return a double now
     70              * the faulty real<Num>(Num) and real<Num>(Num,Num)
     71                have been removed
     72        #187: Remove DijkstraWidestPathOperationTraits
     73        #61:  Bugfix in DfsVisit
    774
    8752008-10-13 Version 1.0 released

  • doc/groups.dox

    r318 r330  
    4141some graph features like arc/edge or node deletion.
    4242
    43 Alteration of standard containers need a very limited number of
    44 operations, these together satisfy the everyday requirements.
    45 In the case of graph structures, different operations are needed which do
    46 not alter the physical graph, but gives another view. If some nodes or
    47 arcs have to be hidden or the reverse oriented graph have to be used, then
    48 this is the case. It also may happen that in a flow implementation
    49 the residual graph can be accessed by another algorithm, or a node-set
    50 is to be shrunk for another algorithm.
    51 LEMON also provides a variety of graphs for these requirements called
    52 \ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only
    53 in conjunction with other graph representations.
    54 
    5543You are free to use the graph structure that fit your requirements
    5644the best, most graph algorithms and auxiliary data structures can be used
    … …  
    5846
    5947<b>See also:</b> \ref graph_concepts "Graph Structure Concepts".
    60 */
    61 
    62 /**
    63 @defgroup semi_adaptors Semi-Adaptor Classes for Graphs
    64 @ingroup graphs
    65 \brief Graph types between real graphs and graph adaptors.
    66 
    67 This group describes some graph types between real graphs and graph adaptors.
    68 These classes wrap graphs to give new functionality as the adaptors do it.
    69 On the other hand they are not light-weight structures as the adaptors.
    7048*/
    7149
    … …  
    156134
    157135/**
    158 @defgroup matrices Matrices
    159 @ingroup datas
    160 \brief Two dimensional data storages implemented in LEMON.
    161 
    162 This group describes two dimensional data storages implemented in LEMON.
    163 */
    164 
    165 /**
    166136@defgroup paths Path Structures
    167137@ingroup datas
    … …  
    215185
    216186/**
    217 @defgroup max_flow Maximum Flow Algorithms
    218 @ingroup algs
    219 \brief Algorithms for finding maximum flows.
    220 
    221 This group describes the algorithms for finding maximum flows and
    222 feasible circulations.
    223 
    224 The maximum flow problem is to find a flow between a single source and
    225 a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
    226 directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
    227 function and given \f$s, t \in V\f$ source and target node. The
    228 maximum flow is the \f$f_a\f$ solution of the next optimization problem:
    229 
    230 \f[ 0 \le f_a \le c_a \f]
    231 \f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv}
    232 \qquad \forall u \in V \setminus \{s,t\}\f]
    233 \f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
    234 
    235 LEMON contains several algorithms for solving maximum flow problems:
    236 - \ref lemon::EdmondsKarp "Edmonds-Karp"
    237 - \ref lemon::Preflow "Goldberg's Preflow algorithm"
    238 - \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
    239 - \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
    240 
    241 In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
    242 fastest method to compute the maximum flow. All impelementations
    243 provides functions to query the minimum cut, which is the dual linear
    244 programming problem of the maximum flow.
    245 */
    246 
    247 /**
    248 @defgroup min_cost_flow Minimum Cost Flow Algorithms
    249 @ingroup algs
    250 
    251 \brief Algorithms for finding minimum cost flows and circulations.
    252 
    253 This group describes the algorithms for finding minimum cost flows and
    254 circulations.
    255 */
    256 
    257 /**
    258 @defgroup min_cut Minimum Cut Algorithms
    259 @ingroup algs
    260 
    261 \brief Algorithms for finding minimum cut in graphs.
    262 
    263 This group describes the algorithms for finding minimum cut in graphs.
    264 
    265 The minimum cut problem is to find a non-empty and non-complete
    266 \f$X\f$ subset of the vertices with minimum overall capacity on
    267 outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an
    268 \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
    269 cut is the \f$X\f$ solution of the next optimization problem:
    270 
    271 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
    272 \sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
    273 
    274 LEMON contains several algorithms related to minimum cut problems:
    275 
    276 - \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut
    277   in directed graphs
    278 - \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to
    279   calculate minimum cut in undirected graphs
    280 - \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all
    281   pairs minimum cut in undirected graphs
    282 
    283 If you want to find minimum cut just between two distinict nodes,
    284 please see the \ref max_flow "Maximum Flow page".
    285 */
    286 
    287 /**
    288 @defgroup graph_prop Connectivity and Other Graph Properties
    289 @ingroup algs
    290 \brief Algorithms for discovering the graph properties
    291 
    292 This group describes the algorithms for discovering the graph properties
    293 like connectivity, bipartiteness, euler property, simplicity etc.
    294 
    295 \image html edge_biconnected_components.png
    296 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
    297 */
    298 
    299 /**
    300 @defgroup planar Planarity Embedding and Drawing
    301 @ingroup algs
    302 \brief Algorithms for planarity checking, embedding and drawing
    303 
    304 This group describes the algorithms for planarity checking,
    305 embedding and drawing.
    306 
    307 \image html planar.png
    308 \image latex planar.eps "Plane graph" width=\textwidth
    309 */
    310 
    311 /**
    312 @defgroup matching Matching Algorithms
    313 @ingroup algs
    314 \brief Algorithms for finding matchings in graphs and bipartite graphs.
    315 
    316 This group contains algorithm objects and functions to calculate
    317 matchings in graphs and bipartite graphs. The general matching problem is
    318 finding a subset of the arcs which does not shares common endpoints.
    319 
    320 There are several different algorithms for calculate matchings in
    321 graphs.  The matching problems in bipartite graphs are generally
    322 easier than in general graphs. The goal of the matching optimization
    323 can be the finding maximum cardinality, maximum weight or minimum cost
    324 matching. The search can be constrained to find perfect or
    325 maximum cardinality matching.
    326 
    327 LEMON contains the next algorithms:
    328 - \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
    329   augmenting path algorithm for calculate maximum cardinality matching in
    330   bipartite graphs
    331 - \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel
    332   algorithm for calculate maximum cardinality matching in bipartite graphs
    333 - \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"
    334   Successive shortest path algorithm for calculate maximum weighted matching
    335   and maximum weighted bipartite matching in bipartite graph
    336 - \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
    337   Successive shortest path algorithm for calculate minimum cost maximum
    338   matching in bipartite graph
    339 - \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
    340   for calculate maximum cardinality matching in general graph
    341 - \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom
    342   shrinking algorithm for calculate maximum weighted matching in general
    343   graph
    344 - \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"
    345   Edmond's blossom shrinking algorithm for calculate maximum weighted
    346   perfect matching in general graph
    347 
    348 \image html bipartite_matching.png
    349 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
    350 */
    351 
    352 /**
    353187@defgroup spantree Minimum Spanning Tree Algorithms
    354188@ingroup algs
    … …  
    360194
    361195/**
    362 @defgroup auxalg Auxiliary Algorithms
    363 @ingroup algs
    364 \brief Auxiliary algorithms implemented in LEMON.
    365 
    366 This group describes some algorithms implemented in LEMON
    367 in order to make it easier to implement complex algorithms.
    368 */
    369 
    370 /**
    371 @defgroup approx Approximation Algorithms
    372 @ingroup algs
    373 \brief Approximation algorithms.
    374 
    375 This group describes the approximation and heuristic algorithms
    376 implemented in LEMON.
    377 */
    378 
    379 /**
    380 @defgroup gen_opt_group General Optimization Tools
    381 \brief This group describes some general optimization frameworks
    382 implemented in LEMON.
    383 
    384 This group describes some general optimization frameworks
    385 implemented in LEMON.
    386 */
    387 
    388 /**
    389 @defgroup lp_group Lp and Mip Solvers
    390 @ingroup gen_opt_group
    391 \brief Lp and Mip solver interfaces for LEMON.
    392 
    393 This group describes Lp and Mip solver interfaces for LEMON. The
    394 various LP solvers could be used in the same manner with this
    395 interface.
    396 */
    397 
    398 /**
    399 @defgroup lp_utils Tools for Lp and Mip Solvers
    400 @ingroup lp_group
    401 \brief Helper tools to the Lp and Mip solvers.
    402 
    403 This group adds some helper tools to general optimization framework
    404 implemented in LEMON.
    405 */
    406 
    407 /**
    408 @defgroup metah Metaheuristics
    409 @ingroup gen_opt_group
    410 \brief Metaheuristics for LEMON library.
    411 
    412 This group describes some metaheuristic optimization tools.
    413 */
    414 
    415 /**
    416196@defgroup utils Tools and Utilities
    417197\brief Tools and utilities for programming in LEMON
    … …  
    459239
    460240This group describes the tools for importing and exporting graphs
    461 and graph related data. Now it supports the \ref lgf-format
    462 "LEMON Graph Format", the \c DIMACS format and the encapsulated
     241and graph related data. Now it supports the LEMON format
     242and the encapsulated postscript (EPS) format.
    463243postscript (EPS) format.
    464244*/
    … …  
    524304@ingroup concept
    525305\brief Skeleton and concept checking classes for maps
    526 
     306 
    527307This group describes the skeletons and concept checking classes of maps.
    528308*/
    … …  
    539319build the library.
    540320*/
    541 
    542 /**
    543 @defgroup tools Standalone utility applications
    544 
    545 Some utility applications are listed here.
    546 
    547 The standard compilation procedure (<tt>./configure;make</tt>) will compile
    548 them, as well.
    549 */
    550 

  • doc/mainpage.dox

    r314 r332  
    4242\subsection howtoread How to read the documentation
    4343
    44 If you want to get a quick start and see the most important features then
    45 take a look at our \ref quicktour
    46 "Quick Tour to LEMON" which will guide you along.
    47 
    48 If you already feel like using our library, see the page that tells you
    49 \ref getstart "How to start using LEMON".
    50 
    51 If you
    52 want to see how LEMON works, see
    53 some \ref demoprograms "demo programs".
    54 
    5544If you know what you are looking for then try to find it under the
    5645<a class="el" href="modules.html">Modules</a>

  • lemon/base.cc

    r220 r500  
    2424namespace lemon {
    2525
    26   float Tolerance<float>::def_epsilon = 1e-4;
     26  float Tolerance<float>::def_epsilon = static_cast<float>(1e-4);
    2727  double Tolerance<double>::def_epsilon = 1e-10;
    2828  long double Tolerance<long double>::def_epsilon = 1e-14;

  • lemon/dfs.h

    r319 r436  
    14141414          } else {
    14151415            _visitor->leave(s);
     1416            _visitor->stop(s);
    14161417          }
    14171418        }

  • lemon/lgf_reader.h

    r517 r519  
    848848        readLine();
    849849      }
    850       line.putback(c);
     850      if (readSuccess()) {
     851        line.putback(c);
     852      }
    851853    }
    852854
    … …  
    16881690        readLine();
    16891691      }
    1690       line.putback(c);
     1692      if (readSuccess()) {
     1693        line.putback(c);
     1694      }
    16911695    }
    16921696
    … …  
    22452249        readLine();
    22462250      }
    2247       line.putback(c);
     2251      if (readSuccess()) {
     2252        line.putback(c);
     2253      }
    22482254    }
    22492255
    … …  
    25862592        readLine();
    25872593      }
    2588       line.putback(c);
     2594      if (readSuccess()) {
     2595        line.putback(c);
     2596      }
    25892597    }
    25902598

  • lemon/maps.h

    r314 r327  
    18561856    InverseMap inverse() const { return InverseMap(*_graph);}
    18571857
    1858   };
    1859 
    1860 
    1861   /// \brief General invertable graph-map type.
    1862 
    1863   /// This type provides simple invertable graph-maps.
    1864   /// The InvertableMap wraps an arbitrary ReadWriteMap
    1865   /// and if a key is set to a new value then store it
    1866   /// in the inverse map.
    1867   ///
    1868   /// The values of the map can be accessed
    1869   /// with stl compatible forward iterator.
    1870   ///
    1871   /// \tparam _Graph The graph type.
    1872   /// \tparam _Item The item type of the graph.
    1873   /// \tparam _Value The value type of the map.
    1874   ///
    1875   /// \see IterableValueMap
    1876   template <typename _Graph, typename _Item, typename _Value>
    1877   class InvertableMap
    1878     : protected ItemSetTraits<_Graph, _Item>::template Map<_Value>::Type {
    1879   private:
    1880 
    1881     typedef typename ItemSetTraits<_Graph, _Item>::
    1882     template Map<_Value>::Type Map;
    1883     typedef _Graph Graph;
    1884 
    1885     typedef std::map<_Value, _Item> Container;
    1886     Container _inv_map;
    1887 
    1888   public:
    1889 
    1890     /// The key type of InvertableMap (Node, Arc, Edge).
    1891     typedef typename Map::Key Key;
    1892     /// The value type of the InvertableMap.
    1893     typedef typename Map::Value Value;
    1894 
    1895     /// \brief Constructor.
    1896     ///
    1897     /// Construct a new InvertableMap for the graph.
    1898     ///
    1899     explicit InvertableMap(const Graph& graph) : Map(graph) {}
    1900 
    1901     /// \brief Forward iterator for values.
    1902     ///
    1903     /// This iterator is an stl compatible forward
    1904     /// iterator on the values of the map. The values can
    1905     /// be accessed in the [beginValue, endValue) range.
    1906     ///
    1907     class ValueIterator
    1908       : public std::iterator<std::forward_iterator_tag, Value> {
    1909       friend class InvertableMap;
    1910     private:
    1911       ValueIterator(typename Container::const_iterator _it)
    1912         : it(_it) {}
    1913     public:
    1914 
    1915       ValueIterator() {}
    1916 
    1917       ValueIterator& operator++() { ++it; return *this; }
    1918       ValueIterator operator++(int) {
    1919         ValueIterator tmp(*this);
    1920         operator++();
    1921         return tmp;
    1922       }
    1923 
    1924       const Value& operator*() const { return it->first; }
    1925       const Value* operator->() const { return &(it->first); }
    1926 
    1927       bool operator==(ValueIterator jt) const { return it == jt.it; }
    1928       bool operator!=(ValueIterator jt) const { return it != jt.it; }
    1929 
    1930     private:
    1931       typename Container::const_iterator it;
    1932     };
    1933 
    1934     /// \brief Returns an iterator to the first value.
    1935     ///
    1936     /// Returns an stl compatible iterator to the
    1937     /// first value of the map. The values of the
    1938     /// map can be accessed in the [beginValue, endValue)
    1939     /// range.
    1940     ValueIterator beginValue() const {
    1941       return ValueIterator(_inv_map.begin());
    1942     }
    1943 
    1944     /// \brief Returns an iterator after the last value.
    1945     ///
    1946     /// Returns an stl compatible iterator after the
    1947     /// last value of the map. The values of the
    1948     /// map can be accessed in the [beginValue, endValue)
    1949     /// range.
    1950     ValueIterator endValue() const {
    1951       return ValueIterator(_inv_map.end());
    1952     }
    1953 
    1954     /// \brief The setter function of the map.
    1955     ///
    1956     /// Sets the mapped value.
    1957     void set(const Key& key, const Value& val) {
    1958       Value oldval = Map::operator[](key);
    1959       typename Container::iterator it = _inv_map.find(oldval);
    1960       if (it != _inv_map.end() && it->second == key) {
    1961         _inv_map.erase(it);
    1962       }
    1963       _inv_map.insert(make_pair(val, key));
    1964       Map::set(key, val);
    1965     }
    1966 
    1967     /// \brief The getter function of the map.
    1968     ///
    1969     /// It gives back the value associated with the key.
    1970     typename MapTraits<Map>::ConstReturnValue
    1971     operator[](const Key& key) const {
    1972       return Map::operator[](key);
    1973     }
    1974 
    1975     /// \brief Gives back the item by its value.
    1976     ///
    1977     /// Gives back the item by its value.
    1978     Key operator()(const Value& key) const {
    1979       typename Container::const_iterator it = _inv_map.find(key);
    1980       return it != _inv_map.end() ? it->second : INVALID;
    1981     }
    1982 
    1983   protected:
    1984 
    1985     /// \brief Erase the key from the map.
    1986     ///
    1987     /// Erase the key to the map. It is called by the
    1988     /// \c AlterationNotifier.
    1989     virtual void erase(const Key& key) {
    1990       Value val = Map::operator[](key);
    1991       typename Container::iterator it = _inv_map.find(val);
    1992       if (it != _inv_map.end() && it->second == key) {
    1993         _inv_map.erase(it);
    1994       }
    1995       Map::erase(key);
    1996     }
    1997 
    1998     /// \brief Erase more keys from the map.
    1999     ///
    2000     /// Erase more keys from the map. It is called by the
    2001     /// \c AlterationNotifier.
    2002     virtual void erase(const std::vector<Key>& keys) {
    2003       for (int i = 0; i < int(keys.size()); ++i) {
    2004         Value val = Map::operator[](keys[i]);
    2005         typename Container::iterator it = _inv_map.find(val);
    2006         if (it != _inv_map.end() && it->second == keys[i]) {
    2007           _inv_map.erase(it);
    2008         }
    2009       }
    2010       Map::erase(keys);
    2011     }
    2012 
    2013     /// \brief Clear the keys from the map and inverse map.
    2014     ///
    2015     /// Clear the keys from the map and inverse map. It is called by the
    2016     /// \c AlterationNotifier.
    2017     virtual void clear() {
    2018       _inv_map.clear();
    2019       Map::clear();
    2020     }
    2021 
    2022   public:
    2023 
    2024     /// \brief The inverse map type.
    2025     ///
    2026     /// The inverse of this map. The subscript operator of the map
    2027     /// gives back always the item what was last assigned to the value.
    2028     class InverseMap {
    2029     public:
    2030       /// \brief Constructor of the InverseMap.
    2031       ///
    2032       /// Constructor of the InverseMap.
    2033       explicit InverseMap(const InvertableMap& inverted)
    2034         : _inverted(inverted) {}
    2035 
    2036       /// The value type of the InverseMap.
    2037       typedef typename InvertableMap::Key Value;
    2038       /// The key type of the InverseMap.
    2039       typedef typename InvertableMap::Value Key;
    2040 
    2041       /// \brief Subscript operator.
    2042       ///
    2043       /// Subscript operator. It gives back always the item
    2044       /// what was last assigned to the value.
    2045       Value operator[](const Key& key) const {
    2046         return _inverted(key);
    2047       }
    2048 
    2049     private:
    2050       const InvertableMap& _inverted;
    2051     };
    2052 
    2053     /// \brief It gives back the just readable inverse map.
    2054     ///
    2055     /// It gives back the just readable inverse map.
    2056     InverseMap inverse() const {
    2057       return InverseMap(*this);
    2058     }
    2059 
    2060   };
    2061 
    2062   /// \brief Provides a mutable, continuous and unique descriptor for each
    2063   /// item in the graph.
    2064   ///
    2065   /// The DescriptorMap class provides a unique and continuous (but mutable)
    2066   /// descriptor (id) for each item of the same type (e.g. node) in the
    2067   /// graph. This id is <ul><li>\b unique: different items (nodes) get
    2068   /// different ids <li>\b continuous: the range of the ids is the set of
    2069   /// integers between 0 and \c n-1, where \c n is the number of the items of
    2070   /// this type (e.g. nodes) (so the id of a node can change if you delete an
    2071   /// other node, i.e. this id is mutable).  </ul> This map can be inverted
    2072   /// with its member class \c InverseMap, or with the \c operator() member.
    2073   ///
    2074   /// \tparam _Graph The graph class the \c DescriptorMap belongs to.
    2075   /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or
    2076   /// Edge.
    2077   template <typename _Graph, typename _Item>
    2078   class DescriptorMap
    2079     : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Type {
    2080 
    2081     typedef _Item Item;
    2082     typedef typename ItemSetTraits<_Graph, _Item>::template Map<int>::Type Map;
    2083 
    2084   public:
    2085     /// The graph class of DescriptorMap.
    2086     typedef _Graph Graph;
    2087 
    2088     /// The key type of DescriptorMap (Node, Arc, Edge).
    2089     typedef typename Map::Key Key;
    2090     /// The value type of DescriptorMap.
    2091     typedef typename Map::Value Value;
    2092 
    2093     /// \brief Constructor.
    2094     ///
    2095     /// Constructor for descriptor map.
    2096     explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
    2097       Item it;
    2098       const typename Map::Notifier* nf = Map::notifier();
    2099       for (nf->first(it); it != INVALID; nf->next(it)) {
    2100         Map::set(it, _inv_map.size());
    2101         _inv_map.push_back(it);
    2102       }
    2103     }
    2104 
    2105   protected:
    2106 
    2107     /// \brief Add a new key to the map.
    2108     ///
    2109     /// Add a new key to the map. It is called by the
    2110     /// \c AlterationNotifier.
    2111     virtual void add(const Item& item) {
    2112       Map::add(item);
    2113       Map::set(item, _inv_map.size());
    2114       _inv_map.push_back(item);
    2115     }
    2116 
    2117     /// \brief Add more new keys to the map.
    2118     ///
    2119     /// Add more new keys to the map. It is called by the
    2120     /// \c AlterationNotifier.
    2121     virtual void add(const std::vector<Item>& items) {
    2122       Map::add(items);
    2123       for (int i = 0; i < int(items.size()); ++i) {
    2124         Map::set(items[i], _inv_map.size());
    2125         _inv_map.push_back(items[i]);
    2126       }
    2127     }
    2128 
    2129     /// \brief Erase the key from the map.
    2130     ///
    2131     /// Erase the key from the map. It is called by the
    2132     /// \c AlterationNotifier.
    2133     virtual void erase(const Item& item) {
    2134       Map::set(_inv_map.back(), Map::operator[](item));
    2135       _inv_map[Map::operator[](item)] = _inv_map.back();
    2136       _inv_map.pop_back();
    2137       Map::erase(item);
    2138     }
    2139 
    2140     /// \brief Erase more keys from the map.
    2141     ///
    2142     /// Erase more keys from the map. It is called by the
    2143     /// \c AlterationNotifier.
    2144     virtual void erase(const std::vector<Item>& items) {
    2145       for (int i = 0; i < int(items.size()); ++i) {
    2146         Map::set(_inv_map.back(), Map::operator[](items[i]));
    2147         _inv_map[Map::operator[](items[i])] = _inv_map.back();
    2148         _inv_map.pop_back();
    2149       }
    2150       Map::erase(items);
    2151     }
    2152 
    2153     /// \brief Build the unique map.
    2154     ///
    2155     /// Build the unique map. It is called by the
    2156     /// \c AlterationNotifier.
    2157     virtual void build() {
    2158       Map::build();
    2159       Item it;
    2160       const typename Map::Notifier* nf = Map::notifier();
    2161       for (nf->first(it); it != INVALID; nf->next(it)) {
    2162         Map::set(it, _inv_map.size());
    2163         _inv_map.push_back(it);
    2164       }
    2165     }
    2166 
    2167     /// \brief Clear the keys from the map.
    2168     ///
    2169     /// Clear the keys from the map. It is called by the
    2170     /// \c AlterationNotifier.
    2171     virtual void clear() {
    2172       _inv_map.clear();
    2173       Map::clear();
    2174     }
    2175 
    2176   public:
    2177 
    2178     /// \brief Returns the maximal value plus one.
    2179     ///
    2180     /// Returns the maximal value plus one in the map.
    2181     unsigned int size() const {
    2182       return _inv_map.size();
    2183     }
    2184 
    2185     /// \brief Swaps the position of the two items in the map.
    2186     ///
    2187     /// Swaps the position of the two items in the map.
    2188     void swap(const Item& p, const Item& q) {
    2189       int pi = Map::operator[](p);
    2190       int qi = Map::operator[](q);
    2191       Map::set(p, qi);
    2192       _inv_map[qi] = p;
    2193       Map::set(q, pi);
    2194       _inv_map[pi] = q;
    2195     }
    2196 
    2197     /// \brief Gives back the \e descriptor of the item.
    2198     ///
    2199     /// Gives back the mutable and unique \e descriptor of the map.
    2200     int operator[](const Item& item) const {
    2201       return Map::operator[](item);
    2202     }
    2203 
    2204     /// \brief Gives back the item by its descriptor.
    2205     ///
    2206     /// Gives back th item by its descriptor.
    2207     Item operator()(int id) const {
    2208       return _inv_map[id];
    2209     }
    2210 
    2211   private:
    2212 
    2213     typedef std::vector<Item> Container;
    2214     Container _inv_map;
    2215 
    2216   public:
    2217     /// \brief The inverse map type of DescriptorMap.
    2218     ///
    2219     /// The inverse map type of DescriptorMap.
    2220     class InverseMap {
    2221     public:
    2222       /// \brief Constructor of the InverseMap.
    2223       ///
    2224       /// Constructor of the InverseMap.
    2225       explicit InverseMap(const DescriptorMap& inverted)
    2226         : _inverted(inverted) {}
    2227 
    2228 
    2229       /// The value type of the InverseMap.
    2230       typedef typename DescriptorMap::Key Value;
    2231       /// The key type of the InverseMap.
    2232       typedef typename DescriptorMap::Value Key;
    2233 
    2234       /// \brief Subscript operator.
    2235       ///
    2236       /// Subscript operator. It gives back the item
    2237       /// that the descriptor belongs to currently.
    2238       Value operator[](const Key& key) const {
    2239         return _inverted(key);
    2240       }
    2241 
    2242       /// \brief Size of the map.
    2243       ///
    2244       /// Returns the size of the map.
    2245       unsigned int size() const {
    2246         return _inverted.size();
    2247       }
    2248 
    2249     private:
    2250       const DescriptorMap& _inverted;
    2251     };
    2252 
    2253     /// \brief Gives back the inverse of the map.
    2254     ///
    2255     /// Gives back the inverse of the map.
    2256     const InverseMap inverse() const {
    2257       return InverseMap(*this);
    2258     }
    22591858  };
    22601859

  • lemon/smart_graph.h

    r313 r386  
    306306      nodes[b._id].first_out=nodes[n._id].first_out;
    307307      nodes[n._id].first_out=-1;
    308       for(int i=nodes[b._id].first_out;i!=-1;i++) arcs[i].source=b._id;
     308      for(int i=nodes[b._id].first_out; i!=-1; i=arcs[i].next_out) {
     309        arcs[i].source=b._id;
     310      }
    309311      if(connect) addArc(n,b);
    310312      return b;
    … …  
    729731        dir.push_back(arcFromId(n-1));
    730732        Parent::notifier(Arc()).erase(dir);
    731         nodes[arcs[n].target].first_out=arcs[n].next_out;
    732         nodes[arcs[n-1].target].first_out=arcs[n-1].next_out;
     733        nodes[arcs[n-1].target].first_out=arcs[n].next_out;
     734        nodes[arcs[n].target].first_out=arcs[n-1].next_out;
    733735        arcs.pop_back();
    734736        arcs.pop_back();

  • lemon/unionfind.h

    r460 r893  
    734734    void clear() {
    735735      items.clear();
    736       classes.clear;
     736      classes.clear();
    737737      firstClass = firstFreeClass = firstFreeItem = -1;
    738738    }

  • scripts/unify-sources.sh

    r208 r538  
    11#!/bin/bash
    22
    3 YEAR=`date +2003-%Y`
     3YEAR=`date +%Y`
    44HGROOT=`hg root`
     5
     6function hg_year() {
     7    if [ -n "$(hg st $1)" ]; then
     8        echo $YEAR
     9    else
     10        hg log -l 1 --template='{date|isodate}\n' $1 |
     11        cut -d '-' -f 1
     12    fi
     13}
    514
    615function update_header() {
    … …  
    1221 * This file is a part of LEMON, a generic C++ optimization library.
    1322 *
    14  * Copyright (C) "$YEAR"
     23 * Copyright (C) 2003-"$(hg_year $1)"
    1524 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    1625 * (Egervary Research Group on Combinatorial Optimization, EGRES).

  • test/digraph_test.cc

    r228 r387  
    3030
    3131template <class Digraph>
    32 void checkDigraph() {
     32void checkDigraphBuild() {
    3333  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    3434  Digraph G;
    … …  
    5959  checkGraphConArcList(G, 1);
    6060
    61   Arc a2 = G.addArc(n2, n1), a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
     61  Arc a2 = G.addArc(n2, n1),
     62      a3 = G.addArc(n2, n3),
     63      a4 = G.addArc(n2, n3);
     64
    6265  checkGraphNodeList(G, 3);
    6366  checkGraphArcList(G, 4);
    … …  
    7780  checkGraphNodeMap(G);
    7881  checkGraphArcMap(G);
    79 
    80 }
    81 
     82}
     83
     84template <class Digraph>
     85void checkDigraphSplit() {
     86  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
     87
     88  Digraph G;
     89  Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
     90  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
     91      a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
     92
     93  Node n4 = G.split(n2);
     94
     95  check(G.target(OutArcIt(G, n2)) == n4 &&
     96        G.source(InArcIt(G, n4)) == n2,
     97        "Wrong split.");
     98
     99  checkGraphNodeList(G, 4);
     100  checkGraphArcList(G, 5);
     101
     102  checkGraphOutArcList(G, n1, 1);
     103  checkGraphOutArcList(G, n2, 1);
     104  checkGraphOutArcList(G, n3, 0);
     105  checkGraphOutArcList(G, n4, 3);
     106
     107  checkGraphInArcList(G, n1, 1);
     108  checkGraphInArcList(G, n2, 1);
     109  checkGraphInArcList(G, n3, 2);
     110  checkGraphInArcList(G, n4, 1);
     111
     112  checkGraphConArcList(G, 5);
     113}
     114
     115template <class Digraph>
     116void checkDigraphAlter() {
     117  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
     118
     119  Digraph G;
     120  Node n1 = G.addNode(), n2 = G.addNode(),
     121       n3 = G.addNode(), n4 = G.addNode();
     122  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),
     123      a3 = G.addArc(n4, n3), a4 = G.addArc(n4, n3),
     124      a5 = G.addArc(n2, n4);
     125
     126  checkGraphNodeList(G, 4);
     127  checkGraphArcList(G, 5);
     128
     129  // Check changeSource() and changeTarget()
     130  G.changeTarget(a4, n1);
     131
     132  checkGraphNodeList(G, 4);
     133  checkGraphArcList(G, 5);
     134
     135  checkGraphOutArcList(G, n1, 1);
     136  checkGraphOutArcList(G, n2, 1);
     137  checkGraphOutArcList(G, n3, 0);
     138  checkGraphOutArcList(G, n4, 3);
     139
     140  checkGraphInArcList(G, n1, 2);
     141  checkGraphInArcList(G, n2, 1);
     142  checkGraphInArcList(G, n3, 1);
     143  checkGraphInArcList(G, n4, 1);
     144
     145  checkGraphConArcList(G, 5);
     146
     147  G.changeSource(a4, n3);
     148
     149  checkGraphNodeList(G, 4);
     150  checkGraphArcList(G, 5);
     151
     152  checkGraphOutArcList(G, n1, 1);
     153  checkGraphOutArcList(G, n2, 1);
     154  checkGraphOutArcList(G, n3, 1);
     155  checkGraphOutArcList(G, n4, 2);
     156
     157  checkGraphInArcList(G, n1, 2);
     158  checkGraphInArcList(G, n2, 1);
     159  checkGraphInArcList(G, n3, 1);
     160  checkGraphInArcList(G, n4, 1);
     161
     162  checkGraphConArcList(G, 5);
     163
     164  // Check contract()
     165  G.contract(n2, n4, false);
     166
     167  checkGraphNodeList(G, 3);
     168  checkGraphArcList(G, 5);
     169
     170  checkGraphOutArcList(G, n1, 1);
     171  checkGraphOutArcList(G, n2, 3);
     172  checkGraphOutArcList(G, n3, 1);
     173
     174  checkGraphInArcList(G, n1, 2);
     175  checkGraphInArcList(G, n2, 2);
     176  checkGraphInArcList(G, n3, 1);
     177
     178  checkGraphConArcList(G, 5);
     179
     180  G.contract(n2, n1);
     181
     182  checkGraphNodeList(G, 2);
     183  checkGraphArcList(G, 3);
     184
     185  checkGraphOutArcList(G, n2, 2);
     186  checkGraphOutArcList(G, n3, 1);
     187
     188  checkGraphInArcList(G, n2, 2);
     189  checkGraphInArcList(G, n3, 1);
     190
     191  checkGraphConArcList(G, 3);
     192}
     193
     194template <class Digraph>
     195void checkDigraphErase() {
     196  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
     197
     198  Digraph G;
     199  Node n1 = G.addNode(), n2 = G.addNode(),
     200       n3 = G.addNode(), n4 = G.addNode();
     201  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n4, n1),
     202      a3 = G.addArc(n4, n3), a4 = G.addArc(n3, n1),
     203      a5 = G.addArc(n2, n4);
     204
     205  // Check arc deletion
     206  G.erase(a1);
     207
     208  checkGraphNodeList(G, 4);
     209  checkGraphArcList(G, 4);
     210
     211  checkGraphOutArcList(G, n1, 0);
     212  checkGraphOutArcList(G, n2, 1);
     213  checkGraphOutArcList(G, n3, 1);
     214  checkGraphOutArcList(G, n4, 2);
     215
     216  checkGraphInArcList(G, n1, 2);
     217  checkGraphInArcList(G, n2, 0);
     218  checkGraphInArcList(G, n3, 1);
     219  checkGraphInArcList(G, n4, 1);
     220
     221  checkGraphConArcList(G, 4);
     222
     223  // Check node deletion
     224  G.erase(n4);
     225
     226  checkGraphNodeList(G, 3);
     227  checkGraphArcList(G, 1);
     228
     229  checkGraphOutArcList(G, n1, 0);
     230  checkGraphOutArcList(G, n2, 0);
     231  checkGraphOutArcList(G, n3, 1);
     232  checkGraphOutArcList(G, n4, 0);
     233
     234  checkGraphInArcList(G, n1, 1);
     235  checkGraphInArcList(G, n2, 0);
     236  checkGraphInArcList(G, n3, 0);
     237  checkGraphInArcList(G, n4, 0);
     238
     239  checkGraphConArcList(G, 1);
     240}
     241
     242
     243template <class Digraph>
     244void checkDigraphSnapshot() {
     245  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
     246
     247  Digraph G;
     248  Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
     249  Arc a1 = G.addArc(n1, n2), a2 = G.addArc(n2, n1),
     250      a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
     251
     252  typename Digraph::Snapshot snapshot(G);
     253
     254  Node n = G.addNode();
     255  G.addArc(n3, n);
     256  G.addArc(n, n3);
     257
     258  checkGraphNodeList(G, 4);
     259  checkGraphArcList(G, 6);
     260
     261  snapshot.restore();
     262
     263  checkGraphNodeList(G, 3);
     264  checkGraphArcList(G, 4);
     265
     266  checkGraphOutArcList(G, n1, 1);
     267  checkGraphOutArcList(G, n2, 3);
     268  checkGraphOutArcList(G, n3, 0);
     269
     270  checkGraphInArcList(G, n1, 1);
     271  checkGraphInArcList(G, n2, 1);
     272  checkGraphInArcList(G, n3, 2);
     273
     274  checkGraphConArcList(G, 4);
     275
     276  checkNodeIds(G);
     277  checkArcIds(G);
     278  checkGraphNodeMap(G);
     279  checkGraphArcMap(G);
     280
     281  G.addNode();
     282  snapshot.save(G);
     283
     284  G.addArc(G.addNode(), G.addNode());
     285
     286  snapshot.restore();
     287
     288  checkGraphNodeList(G, 4);
     289  checkGraphArcList(G, 4);
     290}
    82291
    83292void checkConcepts() {
    … …  
    170379void checkDigraphs() {
    171380  { // Checking ListDigraph
    172     checkDigraph<ListDigraph>();
     381    checkDigraphBuild<ListDigraph>();
     382    checkDigraphSplit<ListDigraph>();
     383    checkDigraphAlter<ListDigraph>();
     384    checkDigraphErase<ListDigraph>();
     385    checkDigraphSnapshot<ListDigraph>();
    173386    checkDigraphValidityErase<ListDigraph>();
    174387  }
    175388  { // Checking SmartDigraph
    176     checkDigraph<SmartDigraph>();
     389    checkDigraphBuild<SmartDigraph>();
     390    checkDigraphSplit<SmartDigraph>();
     391    checkDigraphSnapshot<SmartDigraph>();
    177392    checkDigraphValidity<SmartDigraph>();
    178393  }

  • test/graph_test.cc

    r228 r387  
    3030
    3131template <class Graph>
    32 void checkGraph() {
     32void checkGraphBuild() {
    3333  TEMPLATE_GRAPH_TYPEDEFS(Graph);
    3434
    … …  
    3636  checkGraphNodeList(G, 0);
    3737  checkGraphEdgeList(G, 0);
     38  checkGraphArcList(G, 0);
    3839
    3940  Node
    … …  
    4344  checkGraphNodeList(G, 3);
    4445  checkGraphEdgeList(G, 0);
     46  checkGraphArcList(G, 0);
    4547
    4648  Edge e1 = G.addEdge(n1, n2);
    4749  check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1),
    4850        "Wrong edge");
    49   checkGraphNodeList(G, 3);
     51
     52  checkGraphNodeList(G, 3);
     53  checkGraphEdgeList(G, 1);
    5054  checkGraphArcList(G, 2);
    51   checkGraphEdgeList(G, 1);
    52 
    53   checkGraphOutArcList(G, n1, 1);
    54   checkGraphOutArcList(G, n2, 1);
    55   checkGraphOutArcList(G, n3, 0);
    56 
    57   checkGraphInArcList(G, n1, 1);
    58   checkGraphInArcList(G, n2, 1);
    59   checkGraphInArcList(G, n3, 0);
    60 
    61   checkGraphIncEdgeList(G, n1, 1);
    62   checkGraphIncEdgeList(G, n2, 1);
    63   checkGraphIncEdgeList(G, n3, 0);
    64 
     55
     56  checkGraphIncEdgeArcLists(G, n1, 1);
     57  checkGraphIncEdgeArcLists(G, n2, 1);
     58  checkGraphIncEdgeArcLists(G, n3, 0);
     59
     60  checkGraphConEdgeList(G, 1);
    6561  checkGraphConArcList(G, 2);
    66   checkGraphConEdgeList(G, 1);
    67 
    68   Edge e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3);
    69   checkGraphNodeList(G, 3);
     62
     63  Edge e2 = G.addEdge(n2, n1),
     64       e3 = G.addEdge(n2, n3);
     65
     66  checkGraphNodeList(G, 3);
     67  checkGraphEdgeList(G, 3);
    7068  checkGraphArcList(G, 6);
    71   checkGraphEdgeList(G, 3);
    72 
    73   checkGraphOutArcList(G, n1, 2);
    74   checkGraphOutArcList(G, n2, 3);
    75   checkGraphOutArcList(G, n3, 1);
    76 
    77   checkGraphInArcList(G, n1, 2);
    78   checkGraphInArcList(G, n2, 3);
    79   checkGraphInArcList(G, n3, 1);
    80 
    81   checkGraphIncEdgeList(G, n1, 2);
    82   checkGraphIncEdgeList(G, n2, 3);
    83   checkGraphIncEdgeList(G, n3, 1);
    84 
     69
     70  checkGraphIncEdgeArcLists(G, n1, 2);
     71  checkGraphIncEdgeArcLists(G, n2, 3);
     72  checkGraphIncEdgeArcLists(G, n3, 1);
     73
     74  checkGraphConEdgeList(G, 3);
    8575  checkGraphConArcList(G, 6);
    86   checkGraphConEdgeList(G, 3);
    8776
    8877  checkArcDirections(G);
    … …  
    9483  checkGraphArcMap(G);
    9584  checkGraphEdgeMap(G);
     85}
     86
     87template <class Graph>
     88void checkGraphAlter() {
     89  TEMPLATE_GRAPH_TYPEDEFS(Graph);
     90
     91  Graph G;
     92  Node n1 = G.addNode(), n2 = G.addNode(),
     93       n3 = G.addNode(), n4 = G.addNode();
     94  Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
     95       e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
     96       e5 = G.addEdge(n4, n3);
     97
     98  checkGraphNodeList(G, 4);
     99  checkGraphEdgeList(G, 5);
     100  checkGraphArcList(G, 10);
     101
     102  // Check changeU() and changeV()
     103  if (G.u(e2) == n2) {
     104    G.changeU(e2, n3);
     105  } else {
     106    G.changeV(e2, n3);
     107  }
     108
     109  checkGraphNodeList(G, 4);
     110  checkGraphEdgeList(G, 5);
     111  checkGraphArcList(G, 10);
     112
     113  checkGraphIncEdgeArcLists(G, n1, 3);
     114  checkGraphIncEdgeArcLists(G, n2, 2);
     115  checkGraphIncEdgeArcLists(G, n3, 3);
     116  checkGraphIncEdgeArcLists(G, n4, 2);
     117
     118  checkGraphConEdgeList(G, 5);
     119  checkGraphConArcList(G, 10);
     120
     121  if (G.u(e2) == n1) {
     122    G.changeU(e2, n2);
     123  } else {
     124    G.changeV(e2, n2);
     125  }
     126
     127  checkGraphNodeList(G, 4);
     128  checkGraphEdgeList(G, 5);
     129  checkGraphArcList(G, 10);
     130
     131  checkGraphIncEdgeArcLists(G, n1, 2);
     132  checkGraphIncEdgeArcLists(G, n2, 3);
     133  checkGraphIncEdgeArcLists(G, n3, 3);
     134  checkGraphIncEdgeArcLists(G, n4, 2);
     135
     136  checkGraphConEdgeList(G, 5);
     137  checkGraphConArcList(G, 10);
     138
     139  // Check contract()
     140  G.contract(n1, n4, false);
     141
     142  checkGraphNodeList(G, 3);
     143  checkGraphEdgeList(G, 5);
     144  checkGraphArcList(G, 10);
     145
     146  checkGraphIncEdgeArcLists(G, n1, 4);
     147  checkGraphIncEdgeArcLists(G, n2, 3);
     148  checkGraphIncEdgeArcLists(G, n3, 3);
     149
     150  checkGraphConEdgeList(G, 5);
     151  checkGraphConArcList(G, 10);
     152
     153  G.contract(n2, n3);
     154
     155  checkGraphNodeList(G, 2);
     156  checkGraphEdgeList(G, 3);
     157  checkGraphArcList(G, 6);
     158
     159  checkGraphIncEdgeArcLists(G, n1, 4);
     160  checkGraphIncEdgeArcLists(G, n2, 2);
     161
     162  checkGraphConEdgeList(G, 3);
     163  checkGraphConArcList(G, 6);
     164}
     165
     166template <class Graph>
     167void checkGraphErase() {
     168  TEMPLATE_GRAPH_TYPEDEFS(Graph);
     169
     170  Graph G;
     171  Node n1 = G.addNode(), n2 = G.addNode(),
     172       n3 = G.addNode(), n4 = G.addNode();
     173  Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
     174       e3 = G.addEdge(n2, n3), e4 = G.addEdge(n1, n4),
     175       e5 = G.addEdge(n4, n3);
     176
     177  // Check edge deletion
     178  G.erase(e2);
     179
     180  checkGraphNodeList(G, 4);
     181  checkGraphEdgeList(G, 4);
     182  checkGraphArcList(G, 8);
     183
     184  checkGraphIncEdgeArcLists(G, n1, 2);
     185  checkGraphIncEdgeArcLists(G, n2, 2);
     186  checkGraphIncEdgeArcLists(G, n3, 2);
     187  checkGraphIncEdgeArcLists(G, n4, 2);
     188
     189  checkGraphConEdgeList(G, 4);
     190  checkGraphConArcList(G, 8);
     191
     192  // Check node deletion
     193  G.erase(n3);
     194
     195  checkGraphNodeList(G, 3);
     196  checkGraphEdgeList(G, 2);
     197  checkGraphArcList(G, 4);
     198
     199  checkGraphIncEdgeArcLists(G, n1, 2);
     200  checkGraphIncEdgeArcLists(G, n2, 1);
     201  checkGraphIncEdgeArcLists(G, n4, 1);
     202
     203  checkGraphConEdgeList(G, 2);
     204  checkGraphConArcList(G, 4);
     205}
     206
     207
     208template <class Graph>
     209void checkGraphSnapshot() {
     210  TEMPLATE_GRAPH_TYPEDEFS(Graph);
     211
     212  Graph G;
     213  Node n1 = G.addNode(), n2 = G.addNode(), n3 = G.addNode();
     214  Edge e1 = G.addEdge(n1, n2), e2 = G.addEdge(n2, n1),
     215       e3 = G.addEdge(n2, n3);
     216
     217  checkGraphNodeList(G, 3);
     218  checkGraphEdgeList(G, 3);
     219  checkGraphArcList(G, 6);
     220
     221  typename Graph::Snapshot snapshot(G);
     222
     223  Node n = G.addNode();
     224  G.addEdge(n3, n);
     225  G.addEdge(n, n3);
     226  G.addEdge(n3, n2);
     227
     228  checkGraphNodeList(G, 4);
     229  checkGraphEdgeList(G, 6);
     230  checkGraphArcList(G, 12);
     231
     232  snapshot.restore();
     233
     234  checkGraphNodeList(G, 3);
     235  checkGraphEdgeList(G, 3);
     236  checkGraphArcList(G, 6);
     237
     238  checkGraphIncEdgeArcLists(G, n1, 2);
     239  checkGraphIncEdgeArcLists(G, n2, 3);
     240  checkGraphIncEdgeArcLists(G, n3, 1);
     241
     242  checkGraphConEdgeList(G, 3);
     243  checkGraphConArcList(G, 6);
     244
     245  checkNodeIds(G);
     246  checkEdgeIds(G);
     247  checkArcIds(G);
     248  checkGraphNodeMap(G);
     249  checkGraphEdgeMap(G);
     250  checkGraphArcMap(G);
     251
     252  G.addNode();
     253  snapshot.save(G);
     254
     255  G.addEdge(G.addNode(), G.addNode());
     256
     257  snapshot.restore();
     258
     259  checkGraphNodeList(G, 4);
     260  checkGraphEdgeList(G, 3);
     261  checkGraphArcList(G, 6);
    96262}
    97263
    … …  
    235401void checkGraphs() {
    236402  { // Checking ListGraph
    237     checkGraph<ListGraph>();
     403    checkGraphBuild<ListGraph>();
     404    checkGraphAlter<ListGraph>();
     405    checkGraphErase<ListGraph>();
     406    checkGraphSnapshot<ListGraph>();
    238407    checkGraphValidityErase<ListGraph>();
    239408  }
    240409  { // Checking SmartGraph
    241     checkGraph<SmartGraph>();
     410    checkGraphBuild<SmartGraph>();
     411    checkGraphSnapshot<SmartGraph>();
    242412    checkGraphValidity<SmartGraph>();
    243413  }

  • test/graph_test.h

    r263 r387  
    115115    check(e==INVALID,"Wrong IncEdge list linking.");
    116116    check(countIncEdges(G,n)==cnt,"Wrong IncEdge number.");
     117  }
     118
     119  template <class Graph>
     120  void checkGraphIncEdgeArcLists(const Graph &G, typename Graph::Node n,
     121                                 int cnt)
     122  {
     123    checkGraphIncEdgeList(G, n, cnt);
     124    checkGraphOutArcList(G, n, cnt);
     125    checkGraphInArcList(G, n, cnt);
    117126  }
    118127

  • test/graph_utils_test.cc

    r220 r324  
    3636  {
    3737    Digraph digraph;
     38    typename Digraph::template NodeMap<int> nodes(digraph);
     39    std::vector<Node> invNodes;
    3840    for (int i = 0; i < 10; ++i) {
    39       digraph.addNode();
    40     }
    41     DescriptorMap<Digraph, Node> nodes(digraph);
    42     typename DescriptorMap<Digraph, Node>::InverseMap invNodes(nodes);
     41      invNodes.push_back(digraph.addNode());
     42      nodes[invNodes.back()]=invNodes.size()-1;
     43    }
    4344    for (int i = 0; i < 100; ++i) {
    4445      int src = rnd[invNodes.size()];
    … …  
    4748    }
    4849    typename Digraph::template ArcMap<bool> found(digraph, false);
    49     DescriptorMap<Digraph, Arc> arcs(digraph);
    5050    for (NodeIt src(digraph); src != INVALID; ++src) {
    5151      for (NodeIt trg(digraph); trg != INVALID; ++trg) {
    … …  
    111111  TEMPLATE_GRAPH_TYPEDEFS(Graph);
    112112  Graph graph;
     113  typename Graph::template NodeMap<int> nodes(graph);
     114  std::vector<Node> invNodes;
    113115  for (int i = 0; i < 10; ++i) {
    114     graph.addNode();
    115   }
    116   DescriptorMap<Graph, Node> nodes(graph);
    117   typename DescriptorMap<Graph, Node>::InverseMap invNodes(nodes);
     116    invNodes.push_back(graph.addNode());
     117    nodes[invNodes.back()]=invNodes.size()-1;
     118  }
    118119  for (int i = 0; i < 100; ++i) {
    119120    int src = rnd[invNodes.size()];
    … …  
    122123  }
    123124  typename Graph::template EdgeMap<int> found(graph, 0);
    124   DescriptorMap<Graph, Edge> edges(graph);
    125125  for (NodeIt src(graph); src != INVALID; ++src) {
    126126    for (NodeIt trg(graph); trg != INVALID; ++trg) {

  • test/maps_test.cc

    r210 r500  
    171171    typedef ComposeMap<DoubleMap, ReadMap<B,A> > CompMap;
    172172    checkConcept<ReadMap<B,double>, CompMap>();
    173     CompMap map1(DoubleMap(),ReadMap<B,A>());
     173    CompMap map1 = CompMap(DoubleMap(),ReadMap<B,A>());
    174174    CompMap map2 = composeMap(DoubleMap(), ReadMap<B,A>());
    175175
    … …  
    184184    typedef CombineMap<DoubleMap, DoubleMap, std::plus<double> > CombMap;
    185185    checkConcept<ReadMap<A,double>, CombMap>();
    186     CombMap map1(DoubleMap(), DoubleMap());
     186    CombMap map1 = CombMap(DoubleMap(), DoubleMap());
    187187    CombMap map2 = combineMap(DoubleMap(), DoubleMap(), std::plus<double>());
    188188
    … …  
    196196    checkConcept<ReadMap<A,B>, FunctorToMap<F> >();
    197197    FunctorToMap<F> map1;
    198     FunctorToMap<F> map2(F());
     198    FunctorToMap<F> map2 = FunctorToMap<F>(F());
    199199    B b = functorToMap(F())[A()];
    200200
    201201    checkConcept<ReadMap<A,B>, MapToFunctor<ReadMap<A,B> > >();
    202     MapToFunctor<ReadMap<A,B> > map(ReadMap<A,B>());
     202    MapToFunctor<ReadMap<A,B> > map = MapToFunctor<ReadMap<A,B> >(ReadMap<A,B>());
    203203
    204204    check(functorToMap(&func)[A()] == 3,
Note: See TracChangeset for help on using the changeset viewer.