COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 81:7ff1c348ae0c in lemon-main


Ignore:
Timestamp:
03/15/08 21:24:43 (17 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Remove maps having unclear purposes or little use

File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/maps.h

    r80 r81  
    774774
    775775
    776   /// Simple wrapping of a map
    777 
    778   /// This \ref concepts::ReadMap "read only map" returns the simple
    779   /// wrapping of the given map. Sometimes the reference maps cannot be
    780   /// combined with simple read maps. This map adaptor wraps the given
    781   /// map to simple read map.
    782   ///
    783   /// The simplest way of using this map is through the wrapMap()
    784   /// function.
    785   ///
    786   /// \sa WrapWriteMap
    787   template<typename M>
    788   class WrapMap : public MapBase<typename M::Key, typename M::Value> {
    789     const M &_m;
    790   public:
    791     typedef MapBase<typename M::Key, typename M::Value> Parent;
    792     typedef typename Parent::Key Key;
    793     typedef typename Parent::Value Value;
    794 
    795     /// Constructor
    796     WrapMap(const M &m) : _m(m) {}
    797     /// \e
    798     Value operator[](const Key &k) const { return _m[k]; }
    799   };
    800 
    801   /// Returns a \ref WrapMap class
    802 
    803   /// This function just returns a \ref WrapMap class.
    804   /// \relates WrapMap
    805   template<typename M>
    806   inline WrapMap<M> wrapMap(const M &map) {
    807     return WrapMap<M>(map);
    808   }
    809 
    810 
    811   /// Simple writable wrapping of a map
    812 
    813   /// This \ref concepts::ReadWriteMap "read-write map" returns the simple
    814   /// wrapping of the given map. Sometimes the reference maps cannot be
    815   /// combined with simple read-write maps. This map adaptor wraps the
    816   /// given map to simple read-write map.
    817   ///
    818   /// The simplest way of using this map is through the wrapWriteMap()
    819   /// function.
    820   ///
    821   /// \sa WrapMap
    822   template<typename M>
    823   class WrapWriteMap : public MapBase<typename M::Key, typename M::Value> {
    824     M &_m;
    825   public:
    826     typedef MapBase<typename M::Key, typename M::Value> Parent;
    827     typedef typename Parent::Key Key;
    828     typedef typename Parent::Value Value;
    829 
    830     /// Constructor
    831     WrapWriteMap(M &m) : _m(m) {}
    832     /// \e
    833     Value operator[](const Key &k) const { return _m[k]; }
    834     /// \e
    835     void set(const Key &k, const Value &c) { _m.set(k, c); }
    836   };
    837 
    838   ///Returns a \ref WrapWriteMap class
    839 
    840   ///This function just returns a \ref WrapWriteMap class.
    841   ///\relates WrapWriteMap
    842   template<typename M>
    843   inline WrapWriteMap<M> wrapWriteMap(M &map) {
    844     return WrapWriteMap<M>(map);
    845   }
    846 
    847 
    848776  /// Sum of two maps
    849777
    … …  
    14641392  }
    14651393
    1466 
    1467   namespace _maps_bits {
    1468 
    1469     template <typename Value>
    1470     struct Identity {
    1471       typedef Value argument_type;
    1472       typedef Value result_type;
    1473       Value operator()(const Value& val) const {
    1474         return val;
    1475       }
    1476     };
    1477 
    1478     template <typename _Iterator, typename Enable = void>
    1479     struct IteratorTraits {
    1480       typedef typename std::iterator_traits<_Iterator>::value_type Value;
    1481     };
    1482 
    1483     template <typename _Iterator>
    1484     struct IteratorTraits<_Iterator,
    1485       typename exists<typename _Iterator::container_type>::type>
    1486     {
    1487       typedef typename _Iterator::container_type::value_type Value;
    1488     };
    1489 
    1490   }
    1491 
    1492 
    1493   /// \brief Writable bool map for logging each \c true assigned element
    1494   ///
    1495   /// A \ref concepts::ReadWriteMap "read-write" bool map for logging
    1496   /// each \c true assigned element, i.e it copies all the keys set
    1497   /// to \c true to the given iterator.
    1498   ///
    1499   /// \note The container of the iterator should contain space
    1500   /// for each element.
    1501   ///
    1502   /// The following example shows how you can write the edges found by
    1503   /// the \ref Prim algorithm directly to the standard output.
    1504   /// \code
    1505   ///   typedef IdMap<Graph, Edge> EdgeIdMap;
    1506   ///   EdgeIdMap edgeId(graph);
    1507   ///
    1508   ///   typedef MapToFunctor<EdgeIdMap> EdgeIdFunctor;
    1509   ///   EdgeIdFunctor edgeIdFunctor(edgeId);
    1510   ///
    1511   ///   StoreBoolMap<ostream_iterator<int>, EdgeIdFunctor>
    1512   ///     writerMap(ostream_iterator<int>(cout, " "), edgeIdFunctor);
    1513   ///
    1514   ///   prim(graph, cost, writerMap);
    1515   /// \endcode
    1516   ///
    1517   /// \sa BackInserterBoolMap
    1518   /// \sa FrontInserterBoolMap
    1519   /// \sa InserterBoolMap
    1520   ///
    1521   /// \todo Revise the name of this class and the related ones.
    1522   template <typename _Iterator,
    1523             typename _Functor =
    1524             _maps_bits::Identity<typename _maps_bits::
    1525                                  IteratorTraits<_Iterator>::Value> >
    1526   class StoreBoolMap {
    1527   public:
    1528     typedef _Iterator Iterator;
    1529 
    1530     typedef typename _Functor::argument_type Key;
    1531     typedef bool Value;
    1532 
    1533     typedef _Functor Functor;
    1534 
    1535     /// Constructor
    1536     StoreBoolMap(Iterator it, const Functor& functor = Functor())
    1537       : _begin(it), _end(it), _functor(functor) {}
    1538 
    1539     /// Gives back the given iterator set for the first key
    1540     Iterator begin() const {
    1541       return _begin;
    1542     }
    1543 
    1544     /// Gives back the the 'after the last' iterator
    1545     Iterator end() const {
    1546       return _end;
    1547     }
    1548 
    1549     /// The set function of the map
    1550     void set(const Key& key, Value value) const {
    1551       if (value) {
    1552         *_end++ = _functor(key);
    1553       }
    1554     }
    1555 
    1556   private:
    1557     Iterator _begin;
    1558     mutable Iterator _end;
    1559     Functor _functor;
    1560   };
    1561 
    1562   /// \brief Writable bool map for logging each \c true assigned element in
    1563   /// a back insertable container.
    1564   ///
    1565   /// Writable bool map for logging each \c true assigned element by pushing
    1566   /// them into a back insertable container.
    1567   /// It can be used to retrieve the items into a standard
    1568   /// container. The next example shows how you can store the
    1569   /// edges found by the Prim algorithm in a vector.
    1570   ///
    1571   /// \code
    1572   ///   vector<Edge> span_tree_edges;
    1573   ///   BackInserterBoolMap<vector<Edge> > inserter_map(span_tree_edges);
    1574   ///   prim(graph, cost, inserter_map);
    1575   /// \endcode
    1576   ///
    1577   /// \sa StoreBoolMap
    1578   /// \sa FrontInserterBoolMap
    1579   /// \sa InserterBoolMap
    1580   template <typename Container,
    1581             typename Functor =
    1582             _maps_bits::Identity<typename Container::value_type> >
    1583   class BackInserterBoolMap {
    1584   public:
    1585     typedef typename Functor::argument_type Key;
    1586     typedef bool Value;
    1587 
    1588     /// Constructor
    1589     BackInserterBoolMap(Container& _container,
    1590                         const Functor& _functor = Functor())
    1591       : container(_container), functor(_functor) {}
    1592 
    1593     /// The set function of the map
    1594     void set(const Key& key, Value value) {
    1595       if (value) {
    1596         container.push_back(functor(key));
    1597       }
    1598     }
    1599 
    1600   private:
    1601     Container& container;
    1602     Functor functor;
    1603   };
    1604 
    1605   /// \brief Writable bool map for logging each \c true assigned element in
    1606   /// a front insertable container.
    1607   ///
    1608   /// Writable bool map for logging each \c true assigned element by pushing
    1609   /// them into a front insertable container.
    1610   /// It can be used to retrieve the items into a standard
    1611   /// container. For example see \ref BackInserterBoolMap.
    1612   ///
    1613   /// \sa BackInserterBoolMap
    1614   /// \sa InserterBoolMap
    1615   template <typename Container,
    1616             typename Functor =
    1617             _maps_bits::Identity<typename Container::value_type> >
    1618   class FrontInserterBoolMap {
    1619   public:
    1620     typedef typename Functor::argument_type Key;
    1621     typedef bool Value;
    1622 
    1623     /// Constructor
    1624     FrontInserterBoolMap(Container& _container,
    1625                          const Functor& _functor = Functor())
    1626       : container(_container), functor(_functor) {}
    1627 
    1628     /// The set function of the map
    1629     void set(const Key& key, Value value) {
    1630       if (value) {
    1631         container.push_front(functor(key));
    1632       }
    1633     }
    1634 
    1635   private:
    1636     Container& container;
    1637     Functor functor;
    1638   };
    1639 
    1640   /// \brief Writable bool map for storing each \c true assigned element in
    1641   /// an insertable container.
    1642   ///
    1643   /// Writable bool map for storing each \c true assigned element in an
    1644   /// insertable container. It will insert all the keys set to \c true into
    1645   /// the container.
    1646   ///
    1647   /// For example, if you want to store the cut arcs of the strongly
    1648   /// connected components in a set you can use the next code:
    1649   ///
    1650   /// \code
    1651   ///   set<Arc> cut_arcs;
    1652   ///   InserterBoolMap<set<Arc> > inserter_map(cut_arcs);
    1653   ///   stronglyConnectedCutArcs(digraph, cost, inserter_map);
    1654   /// \endcode
    1655   ///
    1656   /// \sa BackInserterBoolMap
    1657   /// \sa FrontInserterBoolMap
    1658   template <typename Container,
    1659             typename Functor =
    1660             _maps_bits::Identity<typename Container::value_type> >
    1661   class InserterBoolMap {
    1662   public:
    1663     typedef typename Container::value_type Key;
    1664     typedef bool Value;
    1665 
    1666     /// Constructor with specified iterator
    1667 
    1668     /// Constructor with specified iterator.
    1669     /// \param _container The container for storing the elements.
    1670     /// \param _it The elements will be inserted before this iterator.
    1671     /// \param _functor The functor that is used when an element is stored.
    1672     InserterBoolMap(Container& _container, typename Container::iterator _it,
    1673                     const Functor& _functor = Functor())
    1674       : container(_container), it(_it), functor(_functor) {}
    1675 
    1676     /// Constructor
    1677 
    1678     /// Constructor without specified iterator.
    1679     /// The elements will be inserted before <tt>_container.end()</tt>.
    1680     /// \param _container The container for storing the elements.
    1681     /// \param _functor The functor that is used when an element is stored.
    1682     InserterBoolMap(Container& _container, const Functor& _functor = Functor())
    1683       : container(_container), it(_container.end()), functor(_functor) {}
    1684 
    1685     /// The set function of the map
    1686     void set(const Key& key, Value value) {
    1687       if (value) {
    1688         it = container.insert(it, functor(key));
    1689         ++it;
    1690       }
    1691     }
    1692 
    1693   private:
    1694     Container& container;
    1695     typename Container::iterator it;
    1696     Functor functor;
    1697   };
    1698 
    1699   /// \brief Writable bool map for filling each \c true assigned element with a
    1700   /// given value.
    1701   ///
    1702   /// Writable bool map for filling each \c true assigned element with a
    1703   /// given value. The value can set the container.
    1704   ///
    1705   /// The following code finds the connected components of a graph
    1706   /// and stores it in the \c comp map:
    1707   /// \code
    1708   ///   typedef Graph::NodeMap<int> ComponentMap;
    1709   ///   ComponentMap comp(graph);
    1710   ///   typedef FillBoolMap<Graph::NodeMap<int> > ComponentFillerMap;
    1711   ///   ComponentFillerMap filler(comp, 0);
    1712   ///
    1713   ///   Dfs<Graph>::DefProcessedMap<ComponentFillerMap>::Create dfs(graph);
    1714   ///   dfs.processedMap(filler);
    1715   ///   dfs.init();
    1716   ///   for (NodeIt it(graph); it != INVALID; ++it) {
    1717   ///     if (!dfs.reached(it)) {
    1718   ///       dfs.addSource(it);
    1719   ///       dfs.start();
    1720   ///       ++filler.fillValue();
    1721   ///     }
    1722   ///   }
    1723   /// \endcode
    1724   template <typename Map>
    1725   class FillBoolMap {
    1726   public:
    1727     typedef typename Map::Key Key;
    1728     typedef bool Value;
    1729 
    1730     /// Constructor
    1731     FillBoolMap(Map& _map, const typename Map::Value& _fill)
    1732       : map(_map), fill(_fill) {}
    1733 
    1734     /// Constructor
    1735     FillBoolMap(Map& _map)
    1736       : map(_map), fill() {}
    1737 
    1738     /// Gives back the current fill value
    1739     const typename Map::Value& fillValue() const {
    1740       return fill;
    1741     }
    1742 
    1743     /// Gives back the current fill value
    1744     typename Map::Value& fillValue() {
    1745       return fill;
    1746     }
    1747 
    1748     /// Sets the current fill value
    1749     void fillValue(const typename Map::Value& _fill) {
    1750       fill = _fill;
    1751     }
    1752 
    1753     /// The set function of the map
    1754     void set(const Key& key, Value value) {
    1755       if (value) {
    1756         map.set(key, fill);
    1757       }
    1758     }
    1759 
    1760   private:
    1761     Map& map;
    1762     typename Map::Value fill;
    1763   };
    1764 
    1765 
    1766   /// \brief Writable bool map for storing the sequence number of
    1767   /// \c true assignments.
    1768   ///
    1769   /// Writable bool map that stores for each \c true assigned elements
    1770   /// the sequence number of this setting.
    1771   /// It makes it easy to calculate the leaving
    1772   /// order of the nodes in the \ref Dfs algorithm.
    1773   ///
    1774   /// \code
    1775   ///   typedef Digraph::NodeMap<int> OrderMap;
    1776   ///   OrderMap order(digraph);
    1777   ///   typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
    1778   ///   OrderSetterMap setter(order);
    1779   ///   Dfs<Digraph>::DefProcessedMap<OrderSetterMap>::Create dfs(digraph);
    1780   ///   dfs.processedMap(setter);
    1781   ///   dfs.init();
    1782   ///   for (NodeIt it(digraph); it != INVALID; ++it) {
    1783   ///     if (!dfs.reached(it)) {
    1784   ///       dfs.addSource(it);
    1785   ///       dfs.start();
    1786   ///     }
    1787   ///   }
    1788   /// \endcode
    1789   ///
    1790   /// The storing of the discovering order is more difficult because the
    1791   /// ReachedMap should be readable in the dfs algorithm but the setting
    1792   /// order map is not readable. Thus we must use the fork map:
    1793   ///
    1794   /// \code
    1795   ///   typedef Digraph::NodeMap<int> OrderMap;
    1796   ///   OrderMap order(digraph);
    1797   ///   typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
    1798   ///   OrderSetterMap setter(order);
    1799   ///   typedef Digraph::NodeMap<bool> StoreMap;
    1800   ///   StoreMap store(digraph);
    1801   ///
    1802   ///   typedef ForkMap<StoreMap, OrderSetterMap> ReachedMap;
    1803   ///   ReachedMap reached(store, setter);
    1804   ///
    1805   ///   Dfs<Digraph>::DefReachedMap<ReachedMap>::Create dfs(digraph);
    1806   ///   dfs.reachedMap(reached);
    1807   ///   dfs.init();
    1808   ///   for (NodeIt it(digraph); it != INVALID; ++it) {
    1809   ///     if (!dfs.reached(it)) {
    1810   ///       dfs.addSource(it);
    1811   ///       dfs.start();
    1812   ///     }
    1813   ///   }
    1814   /// \endcode
    1815   template <typename Map>
    1816   class SettingOrderBoolMap {
    1817   public:
    1818     typedef typename Map::Key Key;
    1819     typedef bool Value;
    1820 
    1821     /// Constructor
    1822     SettingOrderBoolMap(Map& _map)
    1823       : map(_map), counter(0) {}
    1824 
    1825     /// Number of set operations.
    1826     int num() const {
    1827       return counter;
    1828     }
    1829 
    1830     /// The set function of the map
    1831     void set(const Key& key, Value value) {
    1832       if (value) {
    1833         map.set(key, counter++);
    1834       }
    1835     }
    1836 
    1837   private:
    1838     Map& map;
    1839     int counter;
    1840   };
    1841 
    18421394  /// @}
    18431395}
Note: See TracChangeset for help on using the changeset viewer.