COIN-OR::LEMON - Graph Library

Ignore:
Files:
1 deleted
14 edited

Legend:

Unmodified
Added
Removed
  • CMakeLists.txt

    r519 r515  
    1111
    1212SET(CMAKE_MODULE_PATH ${CMAKE_SOURCE_DIR}/cmake)
    13 
    14 IF(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
    21 ENDIF(MSVC)
    2213
    2314INCLUDE(FindDoxygen)
  • NEWS

    r505 r322  
    1 2009-01-23 Version 1.0.2 released
    2 
    3         Bugfix release.
    4 
    5         #193: Bugfix in GraphReader::skipSection()
    6         #195: Bugfix in ConEdgeIt()
    7         #197: Bugfix in heap unionfind
    8               * This bug affects Edmond's general matching algorithms.
    9                 (Not available in this release.)
    10         #207: Fix 'make install' without 'make html' using CMAKE
    11         #208: Suppress or fix VS2008 compilation warnings
    12         ----: Update the LEMON icon
    13         ----: Enable the component-based installer
    14               (in installers made by CPACK)
    15         ----: Set the proper version for CMAKE in the tarballs
    16               (made by autotools).
    17 
    18 2008-12-06 Version 1.0.1 released
    19 
    20         Bugfix release.
    21 
    22         #170: Bugfix SmartDigraph::split()
    23         #171: Bugfix in SmartGraph::restoreSnapshot()
    24         #172: Extended test cases for graphs and digraphs
    25         #173: Bugfix in Random
    26               * operator()s always return a double now
    27               * the faulty real<Num>(Num) and real<Num>(Num,Num)
    28                 have been removed
    29         #187: Remove DijkstraWidestPathOperationTraits
    30         #61:  Bugfix in DfsVisit
    31 
    3212008-10-13 Version 1.0 released
    332
  • doc/groups.dox

    r330 r318  
    4141some graph features like arc/edge or node deletion.
    4242
     43Alteration of standard containers need a very limited number of
     44operations, these together satisfy the everyday requirements.
     45In the case of graph structures, different operations are needed which do
     46not alter the physical graph, but gives another view. If some nodes or
     47arcs have to be hidden or the reverse oriented graph have to be used, then
     48this is the case. It also may happen that in a flow implementation
     49the residual graph can be accessed by another algorithm, or a node-set
     50is to be shrunk for another algorithm.
     51LEMON also provides a variety of graphs for these requirements called
     52\ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only
     53in conjunction with other graph representations.
     54
    4355You are free to use the graph structure that fit your requirements
    4456the best, most graph algorithms and auxiliary data structures can be used
     
    4658
    4759<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
     67This group describes some graph types between real graphs and graph adaptors.
     68These classes wrap graphs to give new functionality as the adaptors do it.
     69On the other hand they are not light-weight structures as the adaptors.
    4870*/
    4971
     
    134156
    135157/**
     158@defgroup matrices Matrices
     159@ingroup datas
     160\brief Two dimensional data storages implemented in LEMON.
     161
     162This group describes two dimensional data storages implemented in LEMON.
     163*/
     164
     165/**
    136166@defgroup paths Path Structures
    137167@ingroup datas
     
    185215
    186216/**
     217@defgroup max_flow Maximum Flow Algorithms
     218@ingroup algs
     219\brief Algorithms for finding maximum flows.
     220
     221This group describes the algorithms for finding maximum flows and
     222feasible circulations.
     223
     224The maximum flow problem is to find a flow between a single source and
     225a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
     226directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
     227function and given \f$s, t \in V\f$ source and target node. The
     228maximum 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
     235LEMON 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
     241In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
     242fastest method to compute the maximum flow. All impelementations
     243provides functions to query the minimum cut, which is the dual linear
     244programming 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
     253This group describes the algorithms for finding minimum cost flows and
     254circulations.
     255*/
     256
     257/**
     258@defgroup min_cut Minimum Cut Algorithms
     259@ingroup algs
     260
     261\brief Algorithms for finding minimum cut in graphs.
     262
     263This group describes the algorithms for finding minimum cut in graphs.
     264
     265The 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
     267outgoing 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
     269cut 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
     274LEMON 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
     283If you want to find minimum cut just between two distinict nodes,
     284please 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
     292This group describes the algorithms for discovering the graph properties
     293like 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
     304This group describes the algorithms for planarity checking,
     305embedding 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
     316This group contains algorithm objects and functions to calculate
     317matchings in graphs and bipartite graphs. The general matching problem is
     318finding a subset of the arcs which does not shares common endpoints.
     319
     320There are several different algorithms for calculate matchings in
     321graphs.  The matching problems in bipartite graphs are generally
     322easier than in general graphs. The goal of the matching optimization
     323can be the finding maximum cardinality, maximum weight or minimum cost
     324matching. The search can be constrained to find perfect or
     325maximum cardinality matching.
     326
     327LEMON 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/**
    187353@defgroup spantree Minimum Spanning Tree Algorithms
    188354@ingroup algs
     
    191357This group describes the algorithms for finding a minimum cost spanning
    192358tree in a graph
     359*/
     360
     361/**
     362@defgroup auxalg Auxiliary Algorithms
     363@ingroup algs
     364\brief Auxiliary algorithms implemented in LEMON.
     365
     366This group describes some algorithms implemented in LEMON
     367in 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
     375This group describes the approximation and heuristic algorithms
     376implemented in LEMON.
     377*/
     378
     379/**
     380@defgroup gen_opt_group General Optimization Tools
     381\brief This group describes some general optimization frameworks
     382implemented in LEMON.
     383
     384This group describes some general optimization frameworks
     385implemented 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
     393This group describes Lp and Mip solver interfaces for LEMON. The
     394various LP solvers could be used in the same manner with this
     395interface.
     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
     403This group adds some helper tools to general optimization framework
     404implemented in LEMON.
     405*/
     406
     407/**
     408@defgroup metah Metaheuristics
     409@ingroup gen_opt_group
     410\brief Metaheuristics for LEMON library.
     411
     412This group describes some metaheuristic optimization tools.
    193413*/
    194414
     
    239459
    240460This group describes the tools for importing and exporting graphs
    241 and graph related data. Now it supports the LEMON format
    242 and the encapsulated postscript (EPS) format.
     461and graph related data. Now it supports the \ref lgf-format
     462"LEMON Graph Format", the \c DIMACS format and the encapsulated
    243463postscript (EPS) format.
    244464*/
     
    304524@ingroup concept
    305525\brief Skeleton and concept checking classes for maps
    306  
     526
    307527This group describes the skeletons and concept checking classes of maps.
    308528*/
     
    319539build the library.
    320540*/
     541
     542/**
     543@defgroup tools Standalone utility applications
     544
     545Some utility applications are listed here.
     546
     547The standard compilation procedure (<tt>./configure;make</tt>) will compile
     548them, as well.
     549*/
     550
  • doc/mainpage.dox

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

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

    r436 r319  
    14141414          } else {
    14151415            _visitor->leave(s);
    1416             _visitor->stop(s);
    14171416          }
    14181417        }
  • lemon/lgf_reader.h

    r519 r517  
    848848        readLine();
    849849      }
    850       if (readSuccess()) {
    851         line.putback(c);
    852       }
     850      line.putback(c);
    853851    }
    854852
     
    16901688        readLine();
    16911689      }
    1692       if (readSuccess()) {
    1693         line.putback(c);
    1694       }
     1690      line.putback(c);
    16951691    }
    16961692
     
    22492245        readLine();
    22502246      }
    2251       if (readSuccess()) {
    2252         line.putback(c);
    2253       }
     2247      line.putback(c);
    22542248    }
    22552249
     
    25922586        readLine();
    25932587      }
    2594       if (readSuccess()) {
    2595         line.putback(c);
    2596       }
     2588      line.putback(c);
    25972589    }
    25982590
  • lemon/maps.h

    r327 r314  
    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    }
    18582259  };
    18592260
  • lemon/smart_graph.h

    r386 r313  
    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].next_out) {
    309         arcs[i].source=b._id;
    310       }
     308      for(int i=nodes[b._id].first_out;i!=-1;i++) arcs[i].source=b._id;
    311309      if(connect) addArc(n,b);
    312310      return b;
     
    731729        dir.push_back(arcFromId(n-1));
    732730        Parent::notifier(Arc()).erase(dir);
    733         nodes[arcs[n-1].target].first_out=arcs[n].next_out;
    734         nodes[arcs[n].target].first_out=arcs[n-1].next_out;
     731        nodes[arcs[n].target].first_out=arcs[n].next_out;
     732        nodes[arcs[n-1].target].first_out=arcs[n-1].next_out;
    735733        arcs.pop_back();
    736734        arcs.pop_back();
  • test/digraph_test.cc

    r387 r228  
    3030
    3131template <class Digraph>
    32 void checkDigraphBuild() {
     32void checkDigraph() {
    3333  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    3434  Digraph G;
     
    5959  checkGraphConArcList(G, 1);
    6060
    61   Arc a2 = G.addArc(n2, n1),
    62       a3 = G.addArc(n2, n3),
    63       a4 = G.addArc(n2, n3);
    64 
    65   checkGraphNodeList(G, 3);
    66   checkGraphArcList(G, 4);
    67 
    68   checkGraphOutArcList(G, n1, 1);
    69   checkGraphOutArcList(G, n2, 3);
    70   checkGraphOutArcList(G, n3, 0);
    71 
    72   checkGraphInArcList(G, n1, 1);
    73   checkGraphInArcList(G, n2, 1);
    74   checkGraphInArcList(G, n3, 2);
    75 
    76   checkGraphConArcList(G, 4);
    77 
    78   checkNodeIds(G);
    79   checkArcIds(G);
    80   checkGraphNodeMap(G);
    81   checkGraphArcMap(G);
    82 }
    83 
    84 template <class Digraph>
    85 void 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 
    115 template <class Digraph>
    116 void 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 
    194 template <class Digraph>
    195 void 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 
    243 template <class Digraph>
    244 void 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 
     61  Arc a2 = G.addArc(n2, n1), a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3);
    26362  checkGraphNodeList(G, 3);
    26463  checkGraphArcList(G, 4);
     
    27978  checkGraphArcMap(G);
    28079
    281   G.addNode();
    282   snapshot.save(G);
     80}
    28381
    284   G.addArc(G.addNode(), G.addNode());
    285 
    286   snapshot.restore();
    287 
    288   checkGraphNodeList(G, 4);
    289   checkGraphArcList(G, 4);
    290 }
    29182
    29283void checkConcepts() {
     
    379170void checkDigraphs() {
    380171  { // Checking ListDigraph
    381     checkDigraphBuild<ListDigraph>();
    382     checkDigraphSplit<ListDigraph>();
    383     checkDigraphAlter<ListDigraph>();
    384     checkDigraphErase<ListDigraph>();
    385     checkDigraphSnapshot<ListDigraph>();
     172    checkDigraph<ListDigraph>();
    386173    checkDigraphValidityErase<ListDigraph>();
    387174  }
    388175  { // Checking SmartDigraph
    389     checkDigraphBuild<SmartDigraph>();
    390     checkDigraphSplit<SmartDigraph>();
    391     checkDigraphSnapshot<SmartDigraph>();
     176    checkDigraph<SmartDigraph>();
    392177    checkDigraphValidity<SmartDigraph>();
    393178  }
  • test/graph_test.cc

    r387 r228  
    3030
    3131template <class Graph>
    32 void checkGraphBuild() {
     32void checkGraph() {
    3333  TEMPLATE_GRAPH_TYPEDEFS(Graph);
    3434
     
    3636  checkGraphNodeList(G, 0);
    3737  checkGraphEdgeList(G, 0);
    38   checkGraphArcList(G, 0);
    3938
    4039  Node
     
    4443  checkGraphNodeList(G, 3);
    4544  checkGraphEdgeList(G, 0);
    46   checkGraphArcList(G, 0);
    4745
    4846  Edge e1 = G.addEdge(n1, n2);
    4947  check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1),
    5048        "Wrong edge");
    51 
    5249  checkGraphNodeList(G, 3);
     50  checkGraphArcList(G, 2);
    5351  checkGraphEdgeList(G, 1);
    54   checkGraphArcList(G, 2);
    55 
    56   checkGraphIncEdgeArcLists(G, n1, 1);
    57   checkGraphIncEdgeArcLists(G, n2, 1);
    58   checkGraphIncEdgeArcLists(G, n3, 0);
    59 
     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
     65  checkGraphConArcList(G, 2);
    6066  checkGraphConEdgeList(G, 1);
    61   checkGraphConArcList(G, 2);
    62 
    63   Edge e2 = G.addEdge(n2, n1),
    64        e3 = G.addEdge(n2, n3);
    65 
     67
     68  Edge e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3);
    6669  checkGraphNodeList(G, 3);
     70  checkGraphArcList(G, 6);
    6771  checkGraphEdgeList(G, 3);
    68   checkGraphArcList(G, 6);
    69 
    70   checkGraphIncEdgeArcLists(G, n1, 2);
    71   checkGraphIncEdgeArcLists(G, n2, 3);
    72   checkGraphIncEdgeArcLists(G, n3, 1);
    73 
     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
     85  checkGraphConArcList(G, 6);
    7486  checkGraphConEdgeList(G, 3);
    75   checkGraphConArcList(G, 6);
    7687
    7788  checkArcDirections(G);
     
    8394  checkGraphArcMap(G);
    8495  checkGraphEdgeMap(G);
    85 }
    86 
    87 template <class Graph>
    88 void 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 
    166 template <class Graph>
    167 void 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 
    208 template <class Graph>
    209 void 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);
    26296}
    26397
     
    401235void checkGraphs() {
    402236  { // Checking ListGraph
    403     checkGraphBuild<ListGraph>();
    404     checkGraphAlter<ListGraph>();
    405     checkGraphErase<ListGraph>();
    406     checkGraphSnapshot<ListGraph>();
     237    checkGraph<ListGraph>();
    407238    checkGraphValidityErase<ListGraph>();
    408239  }
    409240  { // Checking SmartGraph
    410     checkGraphBuild<SmartGraph>();
    411     checkGraphSnapshot<SmartGraph>();
     241    checkGraph<SmartGraph>();
    412242    checkGraphValidity<SmartGraph>();
    413243  }
  • test/graph_test.h

    r387 r263  
    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);
    126117  }
    127118
  • test/graph_utils_test.cc

    r324 r220  
    3636  {
    3737    Digraph digraph;
    38     typename Digraph::template NodeMap<int> nodes(digraph);
    39     std::vector<Node> invNodes;
    4038    for (int i = 0; i < 10; ++i) {
    41       invNodes.push_back(digraph.addNode());
    42       nodes[invNodes.back()]=invNodes.size()-1;
    43     }
     39      digraph.addNode();
     40    }
     41    DescriptorMap<Digraph, Node> nodes(digraph);
     42    typename DescriptorMap<Digraph, Node>::InverseMap invNodes(nodes);
    4443    for (int i = 0; i < 100; ++i) {
    4544      int src = rnd[invNodes.size()];
     
    4847    }
    4948    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;
    115113  for (int i = 0; i < 10; ++i) {
    116     invNodes.push_back(graph.addNode());
    117     nodes[invNodes.back()]=invNodes.size()-1;
    118   }
     114    graph.addNode();
     115  }
     116  DescriptorMap<Graph, Node> nodes(graph);
     117  typename DescriptorMap<Graph, Node>::InverseMap invNodes(nodes);
    119118  for (int i = 0; i < 100; ++i) {
    120119    int src = rnd[invNodes.size()];
     
    123122  }
    124123  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

    r500 r210  
    171171    typedef ComposeMap<DoubleMap, ReadMap<B,A> > CompMap;
    172172    checkConcept<ReadMap<B,double>, CompMap>();
    173     CompMap map1 = CompMap(DoubleMap(),ReadMap<B,A>());
     173    CompMap map1(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 = CombMap(DoubleMap(), DoubleMap());
     186    CombMap map1(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 = FunctorToMap<F>(F());
     198    FunctorToMap<F> map2(F());
    199199    B b = functorToMap(F())[A()];
    200200
    201201    checkConcept<ReadMap<A,B>, MapToFunctor<ReadMap<A,B> > >();
    202     MapToFunctor<ReadMap<A,B> > map = MapToFunctor<ReadMap<A,B> >(ReadMap<A,B>());
     202    MapToFunctor<ReadMap<A,B> > map(ReadMap<A,B>());
    203203
    204204    check(functorToMap(&func)[A()] == 3,
Note: See TracChangeset for help on using the changeset viewer.