Changes in / [359:0eec1736ff1d:362:51597950d0fe] in lemon-1.2
- Location:
- lemon
- Files:
-
- 9 edited
-
bits/alteration_notifier.h (modified) (3 diffs)
-
bits/array_map.h (modified) (8 diffs)
-
bits/base_extender.h (modified) (1 diff)
-
bits/graph_extender.h (modified) (1 diff)
-
bits/traits.h (modified) (2 diffs)
-
bits/vector_map.h (modified) (7 diffs)
-
full_graph.h (modified) (2 diffs)
-
grid_graph.h (modified) (2 diffs)
-
smart_graph.h (modified) (1 diff)
Legend:
- Unmodified
- Added
- Removed
-
lemon/bits/alteration_notifier.h
r314 r361 36 36 // a container. 37 37 // 38 // The simple graph 's can be refered as two containers, onenode container39 // and one edge container. But they are not standard containersthey40 // does not store values directly they are just key continars for more41 // value containers which are thenode and edge maps.42 // 43 // The graph's node and edge sets can be changed as we add or erase38 // The simple graphs can be refered as two containers: a node container 39 // and an edge container. But they do not store values directly, they 40 // are just key continars for more value containers, which are the 41 // node and edge maps. 42 // 43 // The node and edge sets of the graphs can be changed as we add or erase 44 44 // nodes and edges in the graph. LEMON would like to handle easily 45 45 // that the node and edge maps should contain values for all nodes or 46 46 // edges. If we want to check on every indicing if the map contains 47 47 // the current indicing key that cause a drawback in the performance 48 // in the library. We use another solution we notify all maps about48 // in the library. We use another solution: we notify all maps about 49 49 // an alteration in the graph, which cause only drawback on the 50 50 // alteration of the graph. 51 51 // 52 // This class provides an interface to the container. The \e first() and \e 53 // next() member functions make possible to iterate on the keys of the 54 // container. The \e id() function returns an integer id for each key. 55 // The \e maxId() function gives back an upper bound of the ids. 52 // This class provides an interface to a node or edge container. 53 // The first() and next() member functions make possible 54 // to iterate on the keys of the container. 55 // The id() function returns an integer id for each key. 56 // The maxId() function gives back an upper bound of the ids. 56 57 // 57 58 // For the proper functonality of this class, we should notify it 58 // about each alteration in the container. The alterations have four type 59 // a s \e add(), \e erase(), \e build() and \e clear(). The \e add() and60 // \e erase() signalsthat only one or few items added or erased to or61 // from the graph. If all items are erased from the graph or from an empty62 // graph a new graph is buildedthen it can be signaled with the59 // about each alteration in the container. The alterations have four type: 60 // add(), erase(), build() and clear(). The add() and 61 // erase() signal that only one or few items added or erased to or 62 // from the graph. If all items are erased from the graph or if a new graph 63 // is built from an empty graph, then it can be signaled with the 63 64 // clear() and build() members. Important rule that if we erase items 64 // from graph we should first signal the alteration and after that erase65 // from graphs we should first signal the alteration and after that erase 65 66 // them from the container, on the other way on item addition we should 66 67 // first extend the container and just after that signal the alteration. 67 68 // 68 69 // The alteration can be observed with a class inherited from the 69 // \eObserverBase nested class. The signals can be handled with70 // ObserverBase nested class. The signals can be handled with 70 71 // overriding the virtual functions defined in the base class. The 71 72 // observer base can be attached to the notifier with the 72 // \eattach() member and can be detached with detach() function. The73 // attach() member and can be detached with detach() function. The 73 74 // alteration handlers should not call any function which signals 74 75 // an other alteration in the same notifier and should not 75 76 // detach any observer from the notifier. 76 77 // 77 // Alteration observers try to be exception safe. If an \eadd() or78 // a \eclear() function throws an exception then the remaining78 // Alteration observers try to be exception safe. If an add() or 79 // a clear() function throws an exception then the remaining 79 80 // observeres will not be notified and the fulfilled additions will 80 // be rolled back by calling the \e erase() or \e clear()81 // functions. Thence the \e erase() and \e clear() should not throw82 // exception. Actullay, it can be throw only \ref ImmediateDetach83 // exceptionwhich detach the observer from the notifier.84 // 85 // There are some placewhen the alteration observing is not completly81 // be rolled back by calling the erase() or clear() functions. 82 // Hence erase() and clear() should not throw exception. 83 // Actullay, they can throw only \ref ImmediateDetach exception, 84 // which detach the observer from the notifier. 85 // 86 // There are some cases, when the alteration observing is not completly 86 87 // reliable. If we want to carry out the node degree in the graph 87 // as in the \ref InDegMap and we use the reverse Edge that cause88 // as in the \ref InDegMap and we use the reverseArc(), then it cause 88 89 // unreliable functionality. Because the alteration observing signals 89 // only erasing and adding but not the reversing it will stores bad90 // degrees. The sub graph adaptors cannot signal the alterations because91 // just a setting in the filter map can modify the graph and this cannot92 // be watched in any way.90 // only erasing and adding but not the reversing, it will stores bad 91 // degrees. Apart form that the subgraph adaptors cannot even signal 92 // the alterations because just a setting in the filter map can modify 93 // the graph and this cannot be watched in any way. 93 94 // 94 95 // \param _Container The container which is observed. … … 104 105 typedef _Item Item; 105 106 106 // \brief Exception which can be called from \eclear() and107 // \eerase().108 // 109 // From the \e clear() and \eerase() function only this107 // \brief Exception which can be called from clear() and 108 // erase(). 109 // 110 // From the clear() and erase() function only this 110 111 // exception is allowed to throw. The exception immediatly 111 112 // detaches the current observer from the notifier. Because the 112 // \e clear() and \eerase() should not throw other exceptions113 // clear() and erase() should not throw other exceptions 113 114 // it can be used to invalidate the observer. 114 115 struct ImmediateDetach {}; … … 122 123 // The observer interface contains some pure virtual functions 123 124 // to override. The add() and erase() functions are 124 // to notify the oberver when one item is added or 125 // erased. 125 // to notify the oberver when one item is added or erased. 126 126 // 127 127 // The build() and clear() members are to notify the observer -
lemon/bits/array_map.h
r314 r361 37 37 // \brief Graph map based on the array storage. 38 38 // 39 // The ArrayMap template class is graph map structure what 40 // automatically updates the map when a key is added to or erased from 41 // the map. This map uses the allocators to implement 42 // the container functionality. 39 // The ArrayMap template class is graph map structure that automatically 40 // updates the map when a key is added to or erased from the graph. 41 // This map uses the allocators to implement the container functionality. 43 42 // 44 // The template parameters are the Graph the current Item type and43 // The template parameters are the Graph, the current Item type and 45 44 // the Value type of the map. 46 45 template <typename _Graph, typename _Item, typename _Value> … … 48 47 : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase { 49 48 public: 50 // The graph type of the maps.49 // The graph type. 51 50 typedef _Graph Graph; 52 // The item type of the map.51 // The item type. 53 52 typedef _Item Item; 54 53 // The reference map tag. 55 54 typedef True ReferenceMapTag; 56 55 57 // The key type of the map s.56 // The key type of the map. 58 57 typedef _Item Key; 59 58 // The value type of the map. … … 201 200 // \brief Adds a new key to the map. 202 201 // 203 // It adds a new key to the map. It called by the observer notifier202 // It adds a new key to the map. It is called by the observer notifier 204 203 // and it overrides the add() member function of the observer base. 205 204 virtual void add(const Key& key) { … … 229 228 // \brief Adds more new keys to the map. 230 229 // 231 // It adds more new keys to the map. It called by the observer notifier230 // It adds more new keys to the map. It is called by the observer notifier 232 231 // and it overrides the add() member function of the observer base. 233 232 virtual void add(const std::vector<Key>& keys) { … … 273 272 // \brief Erase a key from the map. 274 273 // 275 // Erase a key from the map. It called by the observer notifier274 // Erase a key from the map. It is called by the observer notifier 276 275 // and it overrides the erase() member function of the observer base. 277 276 virtual void erase(const Key& key) { … … 282 281 // \brief Erase more keys from the map. 283 282 // 284 // Erase more keys from the map. It called by the observer notifier283 // Erase more keys from the map. It is called by the observer notifier 285 284 // and it overrides the erase() member function of the observer base. 286 285 virtual void erase(const std::vector<Key>& keys) { … … 291 290 } 292 291 293 // \brief Build es the map.294 // 295 // It build es the map. Itcalled by the observer notifier292 // \brief Builds the map. 293 // 294 // It builds the map. It is called by the observer notifier 296 295 // and it overrides the build() member function of the observer base. 297 296 virtual void build() { … … 307 306 // \brief Clear the map. 308 307 // 309 // It erase all items from the map. It called by the observer notifier308 // It erase all items from the map. It is called by the observer notifier 310 309 // and it overrides the clear() member function of the observer base. 311 310 virtual void clear() { -
lemon/bits/base_extender.h
r314 r361 31 31 //\ingroup digraphbits 32 32 //\file 33 //\brief Extenders for the digraph types33 //\brief Extenders for the graph types 34 34 namespace lemon { 35 35 -
lemon/bits/graph_extender.h
r314 r361 30 30 //\ingroup graphbits 31 31 //\file 32 //\brief Extenders for the digraph types32 //\brief Extenders for the graph types 33 33 namespace lemon { 34 34 35 35 // \ingroup graphbits 36 36 // 37 // \brief Extender for the Digraphs37 // \brief Extender for the digraph implementations 38 38 template <typename Base> 39 39 class DigraphExtender : public Base { -
lemon/bits/traits.h
r314 r360 219 219 220 220 template <typename Graph, typename Enable = void> 221 struct ArcNumTagIndicator { 222 static const bool value = false; 223 }; 224 225 template <typename Graph> 226 struct ArcNumTagIndicator< 227 Graph, 228 typename enable_if<typename Graph::ArcNumTag, void>::type 229 > { 230 static const bool value = true; 231 }; 232 233 template <typename Graph, typename Enable = void> 221 234 struct EdgeNumTagIndicator { 222 235 static const bool value = false; … … 232 245 233 246 template <typename Graph, typename Enable = void> 247 struct FindArcTagIndicator { 248 static const bool value = false; 249 }; 250 251 template <typename Graph> 252 struct FindArcTagIndicator< 253 Graph, 254 typename enable_if<typename Graph::FindArcTag, void>::type 255 > { 256 static const bool value = true; 257 }; 258 259 template <typename Graph, typename Enable = void> 234 260 struct FindEdgeTagIndicator { 235 261 static const bool value = false; -
lemon/bits/vector_map.h
r314 r361 39 39 // \brief Graph map based on the std::vector storage. 40 40 // 41 // The VectorMap template class is graph map structure what42 // automatically updates the map when a key is added to or erased from43 // the map. This map type uses thestd::vector to store the values.41 // The VectorMap template class is graph map structure that automatically 42 // updates the map when a key is added to or erased from the graph. 43 // This map type uses std::vector to store the values. 44 44 // 45 45 // \tparam _Graph The graph this map is attached to. … … 170 170 // \brief Adds a new key to the map. 171 171 // 172 // It adds a new key to the map. It called by the observer notifier172 // It adds a new key to the map. It is called by the observer notifier 173 173 // and it overrides the add() member function of the observer base. 174 174 virtual void add(const Key& key) { … … 181 181 // \brief Adds more new keys to the map. 182 182 // 183 // It adds more new keys to the map. It called by the observer notifier183 // It adds more new keys to the map. It is called by the observer notifier 184 184 // and it overrides the add() member function of the observer base. 185 185 virtual void add(const std::vector<Key>& keys) { … … 196 196 // \brief Erase a key from the map. 197 197 // 198 // Erase a key from the map. It called by the observer notifier198 // Erase a key from the map. It is called by the observer notifier 199 199 // and it overrides the erase() member function of the observer base. 200 200 virtual void erase(const Key& key) { … … 204 204 // \brief Erase more keys from the map. 205 205 // 206 // Erase more keys from the map. Itcalled by the observer notifier206 // It erases more keys from the map. It is called by the observer notifier 207 207 // and it overrides the erase() member function of the observer base. 208 208 virtual void erase(const std::vector<Key>& keys) { … … 212 212 } 213 213 214 // \brief Build esthe map.215 // 216 // It build es the map. Itcalled by the observer notifier214 // \brief Build the map. 215 // 216 // It builds the map. It is called by the observer notifier 217 217 // and it overrides the build() member function of the observer base. 218 218 virtual void build() { … … 224 224 // \brief Clear the map. 225 225 // 226 // It erase all items from the map. Itcalled by the observer notifier226 // It erases all items from the map. It is called by the observer notifier 227 227 // and it overrides the clear() member function of the observer base. 228 228 virtual void clear() { -
lemon/full_graph.h
r355 r360 307 307 308 308 typedef True NodeNumTag; 309 typedef True ArcNumTag; 309 310 typedef True EdgeNumTag; 310 311 … … 344 345 345 346 typedef True FindEdgeTag; 347 typedef True FindArcTag; 346 348 347 349 Edge findEdge(Node u, Node v, Edge prev = INVALID) const { -
lemon/grid_graph.h
r338 r360 83 83 84 84 typedef True NodeNumTag; 85 typedef True EdgeNumTag; 85 86 typedef True ArcNumTag; 86 87 … … 128 129 129 130 typedef True FindEdgeTag; 131 typedef True FindArcTag; 130 132 131 133 Edge findEdge(Node u, Node v, Edge prev = INVALID) const { -
lemon/smart_graph.h
r329 r360 68 68 69 69 typedef True NodeNumTag; 70 typedef True EdgeNumTag;70 typedef True ArcNumTag; 71 71 72 72 int nodeNum() const { return nodes.size(); }
Note: See TracChangeset
for help on using the changeset viewer.
