1.1 --- a/lemon/graph_utils.h Wed Nov 23 11:20:14 2005 +0000
1.2 +++ b/lemon/graph_utils.h Wed Nov 23 15:42:36 2005 +0000
1.3 @@ -110,8 +110,7 @@
1.4 // Node counting:
1.5
1.6 template <typename Graph>
1.7 - inline
1.8 - typename enable_if<typename Graph::NodeNumTag, int>::type
1.9 + inline typename enable_if<typename Graph::NodeNumTag, int>::type
1.10 _countNodes(const Graph &g) {
1.11 return g.nodeNum();
1.12 }
1.13 @@ -137,8 +136,7 @@
1.14 // Edge counting:
1.15
1.16 template <typename Graph>
1.17 - inline
1.18 - typename enable_if<typename Graph::EdgeNumTag, int>::type
1.19 + inline typename enable_if<typename Graph::EdgeNumTag, int>::type
1.20 _countEdges(const Graph &g) {
1.21 return g.edgeNum();
1.22 }
1.23 @@ -420,7 +418,7 @@
1.24 /// It increments the iterator and gives back the next edge.
1.25 ConUndirEdgeIt& operator++() {
1.26 Parent::operator=(findUndirEdge(graph, graph.source(*this),
1.27 - graph.target(*this), *this));
1.28 + graph.target(*this), *this));
1.29 return *this;
1.30 }
1.31 private:
1.32 @@ -938,14 +936,6 @@
1.33
1.34 protected:
1.35
1.36 - /// \brief Add a new key to the map.
1.37 - ///
1.38 - /// Add a new key to the map. It is called by the
1.39 - /// \c AlterationNotifier.
1.40 - virtual void add(const Key& key) {
1.41 - Map::add(key);
1.42 - }
1.43 -
1.44 /// \brief Erase the key from the map.
1.45 ///
1.46 /// Erase the key to the map. It is called by the
1.47 @@ -959,6 +949,21 @@
1.48 Map::erase(key);
1.49 }
1.50
1.51 + /// \brief Erase more keys from the map.
1.52 + ///
1.53 + /// Erase more keys from the map. It is called by the
1.54 + /// \c AlterationNotifier.
1.55 + virtual void erase(const std::vector<Key>& keys) {
1.56 + for (int i = 0; i < (int)keys.size(); ++i) {
1.57 + Value val = Map::operator[](keys[i]);
1.58 + typename Container::iterator it = invMap.find(val);
1.59 + if (it != invMap.end() && it->second == keys[i]) {
1.60 + invMap.erase(it);
1.61 + }
1.62 + }
1.63 + Map::erase(keys);
1.64 + }
1.65 +
1.66 /// \brief Clear the keys from the map and inverse map.
1.67 ///
1.68 /// Clear the keys from the map and inverse map. It is called by the
1.69 @@ -1070,9 +1075,21 @@
1.70 invMap.push_back(item);
1.71 }
1.72
1.73 + /// \brief Add more new keys to the map.
1.74 + ///
1.75 + /// Add more new keys to the map. It is called by the
1.76 + /// \c AlterationNotifier.
1.77 + virtual void add(const std::vector<Item>& items) {
1.78 + Map::add(items);
1.79 + for (int i = 0; i < (int)items.size(); ++i) {
1.80 + Map::set(items[i], invMap.size());
1.81 + invMap.push_back(items[i]);
1.82 + }
1.83 + }
1.84 +
1.85 /// \brief Erase the key from the map.
1.86 ///
1.87 - /// Erase the key to the map. It is called by the
1.88 + /// Erase the key from the map. It is called by the
1.89 /// \c AlterationNotifier.
1.90 virtual void erase(const Item& item) {
1.91 Map::set(invMap.back(), Map::operator[](item));
1.92 @@ -1081,6 +1098,19 @@
1.93 Map::erase(item);
1.94 }
1.95
1.96 + /// \brief Erase more keys from the map.
1.97 + ///
1.98 + /// Erase more keys from the map. It is called by the
1.99 + /// \c AlterationNotifier.
1.100 + virtual void erase(const std::vector<Item>& items) {
1.101 + for (int i = 0; i < (int)items.size(); ++i) {
1.102 + Map::set(invMap.back(), Map::operator[](items[i]));
1.103 + invMap[Map::operator[](items[i])] = invMap.back();
1.104 + invMap.pop_back();
1.105 + }
1.106 + Map::erase(items);
1.107 + }
1.108 +
1.109 /// \brief Build the unique map.
1.110 ///
1.111 /// Build the unique map. It is called by the
1.112 @@ -1379,8 +1409,8 @@
1.113 ///
1.114 /// \warning Besides addNode() and addEdge(), a graph structure may provide
1.115 /// alternative ways to modify the graph. The correct behavior of InDegMap
1.116 - /// is not guarantied if these additional featureas are used. For example
1.117 - /// the funstions \ref ListGraph::changeSource() "changeSource()",
1.118 + /// is not guarantied if these additional features are used. For example
1.119 + /// the functions \ref ListGraph::changeSource() "changeSource()",
1.120 /// \ref ListGraph::changeTarget() "changeTarget()" and
1.121 /// \ref ListGraph::reverseEdge() "reverseEdge()"
1.122 /// of \ref ListGraph will \e not update the degree values correctly.
1.123 @@ -1409,10 +1439,16 @@
1.124
1.125 AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
1.126
1.127 - void add(const Key& key) {
1.128 + virtual void add(const Key& key) {
1.129 Parent::add(key);
1.130 Parent::set(key, 0);
1.131 }
1.132 + virtual void add(const std::vector<Key>& keys) {
1.133 + Parent::add(keys);
1.134 + for (int i = 0; i < (int)keys.size(); ++i) {
1.135 + Parent::set(keys[i], 0);
1.136 + }
1.137 + }
1.138 };
1.139
1.140 public:
1.141 @@ -1451,14 +1487,6 @@
1.142 --deg[graph.target(edge)];
1.143 }
1.144
1.145 - virtual void signalChange(const Edge& edge) {
1.146 - erase(edge);
1.147 - }
1.148 -
1.149 - virtual void commitChange(const Edge& edge) {
1.150 - add(edge);
1.151 - }
1.152 -
1.153 virtual void build() {
1.154 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1.155 deg[it] = countInEdges(graph, it);
1.156 @@ -1485,8 +1513,8 @@
1.157 ///
1.158 /// \warning Besides addNode() and addEdge(), a graph structure may provide
1.159 /// alternative ways to modify the graph. The correct behavior of OutDegMap
1.160 - /// is not guarantied if these additional featureas are used. For example
1.161 - /// the funstions \ref ListGraph::changeSource() "changeSource()",
1.162 + /// is not guarantied if these additional features are used. For example
1.163 + /// the functions \ref ListGraph::changeSource() "changeSource()",
1.164 /// \ref ListGraph::changeTarget() "changeTarget()" and
1.165 /// \ref ListGraph::reverseEdge() "reverseEdge()"
1.166 /// of \ref ListGraph will \e not update the degree values correctly.
1.167 @@ -1515,10 +1543,16 @@
1.168
1.169 AutoNodeMap(const Graph& graph) : Parent(graph, 0) {}
1.170
1.171 - void add(const Key& key) {
1.172 + virtual void add(const Key& key) {
1.173 Parent::add(key);
1.174 Parent::set(key, 0);
1.175 }
1.176 + virtual void add(const std::vector<Key>& keys) {
1.177 + Parent::add(keys);
1.178 + for (int i = 0; i < (int)keys.size(); ++i) {
1.179 + Parent::set(keys[i], 0);
1.180 + }
1.181 + }
1.182 };
1.183
1.184 public:
1.185 @@ -1557,15 +1591,6 @@
1.186 --deg[graph.source(edge)];
1.187 }
1.188
1.189 - virtual void signalChange(const Edge& edge) {
1.190 - erase(edge);
1.191 - }
1.192 -
1.193 - virtual void commitChange(const Edge& edge) {
1.194 - add(edge);
1.195 - }
1.196 -
1.197 -
1.198 virtual void build() {
1.199 for(typename _Graph::NodeIt it(graph); it != INVALID; ++it) {
1.200 deg[it] = countOutEdges(graph, it);