Correcting the structure of the graph's and adaptor's map.
The template assign operators and map iterators can be used for adaptors also.
Some bugfix in the adaptors
New class SwapBpUGraphAdaptor which swaps the two nodeset of the graph.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_BITS_ALTERATION_NOTIFIER_H
20 #define LEMON_BITS_ALTERATION_NOTIFIER_H
24 #include <lemon/bits/utility.h>
28 ///\brief Observer notifier for graph alteration observers.
32 /// \ingroup graphbits
34 /// \brief Notifier class to notify observes about alterations in
37 /// The simple graph's can be refered as two containers, one node container
38 /// and one edge container. But they are not standard containers they
39 /// does not store values directly they are just key continars for more
40 /// value containers which are the node and edge maps.
42 /// The graph's node and edge sets can be changed as we add or erase
43 /// nodes and edges in the graph. Lemon would like to handle easily
44 /// that the node and edge maps should contain values for all nodes or
45 /// edges. If we want to check on every indicing if the map contains
46 /// the current indicing key that cause a drawback in the performance
47 /// in the library. We use another solution we notify all maps about
48 /// an alteration in the graph, which cause only drawback on the
49 /// alteration of the graph.
51 /// This class provides an interface to the container. The \e first() and \e
52 /// next() member functions make possible to iterate on the keys of the
53 /// container. The \e id() function returns an integer id for each key.
54 /// The \e maxId() function gives back an upper bound of the ids.
56 /// For the proper functonality of this class, we should notify it
57 /// about each alteration in the container. The alterations have four type
58 /// as \e add(), \e erase(), \e build() and \e clear(). The \e add() and
59 /// \e erase() signals that only one or few items added or erased to or
60 /// from the graph. If all items are erased from the graph or from an empty
61 /// graph a new graph is builded then it can be signaled with the
62 /// clear() and build() members. Important rule that if we erase items
63 /// from graph we should first signal the alteration and after that erase
64 /// them from the container, on the other way on item addition we should
65 /// first extend the container and just after that signal the alteration.
67 /// The alteration can be observed with a class inherited from the
68 /// \e ObserverBase nested class. The signals can be handled with
69 /// overriding the virtual functions defined in the base class.
70 /// The observer base can be attached to the notifier with the
71 /// \e attach() member and can be detached with detach() function.
73 /// Alteration observers try to be exception safe. This can be achived
74 /// when the observers does not throw exception on \e erase() and
75 /// \e clear(). Less strict condition is that the \e erase() should
76 /// not throw exception after an \e add() with the same parameter and
77 /// the \e clear() should not throw exception after a \e build().
79 /// There are some place when the alteration observing is not completly
80 /// reliable. If we want to carry out the node degree in the graph
81 /// as in the \ref InDegMap and we use the reverseEdge that cause
82 /// unreliable functionality. Because the alteration observing signals
83 /// only erasing and adding but not the reversing it will stores bad
84 /// degrees. The sub graph adaptors cannot signal the alterations because
85 /// just a setting in the filter map can modify the graph and this cannot
86 /// be watched in any way.
88 /// \param _Container The container which is observed.
89 /// \param _Item The item type which is obserbved.
91 /// \author Balazs Dezso
93 template <typename _Container, typename _Item>
94 class AlterationNotifier {
97 typedef True Notifier;
99 typedef _Container Container;
102 /// \brief ObserverBase is the base class for the observers.
104 /// ObserverBase is the abstract base class for the observers.
105 /// It will be notified about an item was inserted into or
106 /// erased from the graph.
108 /// The observer interface contains some pure virtual functions
109 /// to override. The add() and erase() functions are
110 /// to notify the oberver when one item is added or
113 /// The build() and clear() members are to notify the observer
114 /// about the container is built from an empty container or
115 /// is cleared to an empty container.
117 /// \author Balazs Dezso
121 typedef AlterationNotifier Notifier;
123 friend class AlterationNotifier;
125 /// \brief Default constructor.
127 /// Default constructor for ObserverBase.
129 ObserverBase() : notifier(0) {}
131 /// \brief Constructor which attach the observer into notifier.
133 /// Constructor which attach the observer into notifier.
134 ObserverBase(AlterationNotifier& _notifier) {
138 /// \brief Constructor which attach the obserever to the same notifier.
140 /// Constructor which attach the obserever to the same notifier as
141 /// the other observer is attached to.
142 ObserverBase(const ObserverBase& copy) {
143 if (copy.attached()) {
144 attach(*copy.getNotifier());
148 /// \brief Destructor
149 virtual ~ObserverBase() {
155 /// \brief Attaches the observer into an AlterationNotifier.
157 /// This member attaches the observer into an AlterationNotifier.
159 void attach(AlterationNotifier& _notifier) {
160 notifier = &_notifier;
161 notifier->attach(*this);
164 /// \brief Detaches the observer into an AlterationNotifier.
166 /// This member detaches the observer from an AlterationNotifier.
169 notifier->detach(*this);
173 /// \brief Gives back a pointer to the notifier which the map
176 /// This function gives back a pointer to the notifier which the map
179 Notifier* getNotifier() const { return const_cast<Notifier*>(notifier); }
181 /// Gives back true when the observer is attached into a notifier.
182 bool attached() const { return notifier != 0; }
186 ObserverBase& operator=(const ObserverBase& copy);
193 /// \brief The member function to notificate the observer about an
194 /// item is added to the container.
196 /// The add() member function notificates the observer about an item
197 /// is added to the container. It have to be overrided in the
200 virtual void add(const Item&) = 0;
202 /// \brief The member function to notificate the observer about
203 /// more item is added to the container.
205 /// The add() member function notificates the observer about more item
206 /// is added to the container. It have to be overrided in the
209 virtual void add(const std::vector<Item>& items) {
212 for (i = 0; i < (int)items.size(); ++i) {
216 for (int j = 0; j < i; ++j) {
223 /// \brief The member function to notificate the observer about an
224 /// item is erased from the container.
226 /// The erase() member function notificates the observer about an
227 /// item is erased from the container. It have to be overrided in
230 virtual void erase(const Item&) = 0;
232 /// \brief The member function to notificate the observer about
233 /// more item is erased from the container.
235 /// The erase() member function notificates the observer about more item
236 /// is erased from the container. It have to be overrided in the
238 virtual void erase(const std::vector<Item>& items) {
239 for (int i = 0; i < (int)items.size(); ++i) {
244 /// \brief The member function to notificate the observer about the
245 /// container is built.
247 /// The build() member function notificates the observer about the
248 /// container is built from an empty container. It have to be
249 /// overrided in the subclasses.
251 virtual void build() {
254 for (notifier->first(it); it != INVALID; notifier->next(it)) {
259 for (notifier->first(jt); jt != it; notifier->next(jt)) {
266 /// \brief The member function to notificate the observer about all
267 /// items are erased from the container.
269 /// The clear() member function notificates the observer about all
270 /// items are erased from the container. It have to be overrided in
272 virtual void clear() {
274 for (notifier->first(it); it != INVALID; notifier->next(it)) {
283 const Container* container;
285 typedef std::vector<ObserverBase*> Observers;
291 /// \brief Default constructor.
293 /// The default constructor of the AlterationNotifier.
294 /// It creates an empty notifier.
298 /// \brief Constructor.
300 /// Constructor with the observed container parameter.
301 AlterationNotifier(const Container& _container)
302 : container(&_container) {}
304 /// \brief Copy Constructor of the AlterationNotifier.
306 /// Copy constructor of the AlterationNotifier.
307 /// It creates only an empty notifier because the copiable
308 /// notifier's observers have to be registered still into that notifier.
309 AlterationNotifier(const AlterationNotifier& _notifier)
310 : container(_notifier.container) {}
312 /// \brief Destructor.
314 /// Destructor of the AlterationNotifier.
316 ~AlterationNotifier() {
317 typename Observers::iterator it;
318 for (it = observers.begin(); it != observers.end(); ++it) {
323 /// \brief Sets the container.
325 /// Sets the container.
326 void setContainer(const Container& _container) {
327 container = &_container;
332 AlterationNotifier& operator=(const AlterationNotifier&);
338 /// \brief First item in the container.
340 /// Returns the first item in the container. It is
341 /// for start the iteration on the container.
342 void first(Item& item) const {
343 container->first(item);
346 /// \brief Next item in the container.
348 /// Returns the next item in the container. It is
349 /// for iterate on the container.
350 void next(Item& item) const {
351 container->next(item);
354 /// \brief Returns the id of the item.
356 /// Returns the id of the item provided by the container.
357 int id(const Item& item) const {
358 return container->id(item);
361 /// \brief Returns the maximum id of the container.
363 /// Returns the maximum id of the container.
365 return container->maxId(Item());
370 void attach(ObserverBase& observer) {
371 observers.push_back(&observer);
372 observer.notifier = this;
373 observer.notifier_index = observers.size() - 1;
376 void detach(ObserverBase& observer) {
377 observers.back()->notifier_index = observer.notifier_index;
378 observers[observer.notifier_index] = observers.back();
379 observers.pop_back();
380 observer.notifier = 0;
385 /// \brief Notifies all the registed observers about an item added to
388 /// It notifies all the registed observers about an item added to
391 void add(const Item& item) {
392 typename Observers::iterator it;
394 for (it = observers.begin(); it != observers.end(); ++it) {
398 typename Observers::iterator jt;
399 for (jt = observers.begin(); jt != it; ++jt) {
406 /// \brief Notifies all the registed observers about more item added to
409 /// It notifies all the registed observers about more item added to
412 void add(const std::vector<Item>& items) {
413 typename Observers::iterator it;
415 for (it = observers.begin(); it != observers.end(); ++it) {
419 typename Observers::iterator jt;
420 for (jt = observers.begin(); jt != it; ++jt) {
427 /// \brief Notifies all the registed observers about an item erased from
430 /// It notifies all the registed observers about an item erased from
433 void erase(const Item& key) {
434 typename Observers::iterator it;
435 for (it = observers.begin(); it != observers.end(); ++it) {
440 /// \brief Notifies all the registed observers about more item erased
441 /// from the container.
443 /// It notifies all the registed observers about more item erased from
446 void erase(const std::vector<Item>& items) {
447 typename Observers::iterator it;
448 for (it = observers.begin(); it != observers.end(); ++it) {
453 /// \brief Notifies all the registed observers about the container is
456 /// Notifies all the registed observers about the container is built
457 /// from an empty container.
459 typename Observers::iterator it;
461 for (it = observers.begin(); it != observers.end(); ++it) {
465 typename Observers::iterator jt;
466 for (jt = observers.begin(); jt != it; ++jt) {
474 /// \brief Notifies all the registed observers about all items are
477 /// Notifies all the registed observers about all items are erased
478 /// from the container.
480 typename Observers::iterator it;
481 for (it = observers.begin(); it != observers.end(); ++it) {