RhodeCode

LEMON code without an explicit copyright is covered by the following

copyright/license.

Kutatocsoport (Egervary Combinatorial Optimization Research Group,

EGRES).

Permission is hereby granted, free of charge, to any person or organization

obtaining a copy of the software and accompanying documentation covered by

this license (the "Software") to use, reproduce, display, distribute,

execute, and transmit the Software, and to prepare derivative works of the

Software, and to permit third-parties to whom the Software is furnished to

do so, all subject to the following:

The copyright notices in the Software and this entire statement, including

the above license grant, this restriction and the following disclaimer,

must be included in all copies of the Software, in whole or in part, and

all derivative works of the Software, unless such copies or derivative

works are solely in the form of machine-executable object code generated by

a source language processor.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT

SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE

FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,

ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER

DEALINGS IN THE SOFTWARE.

===========================================================================

This license is a verbatim copy of the Boost Software License, Version 1.0.

/* -*- C++ -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_BITS_ALTERATION_NOTIFIER_H

#define LEMON_BITS_ALTERATION_NOTIFIER_H

#include <vector>

#include <list>

#include <lemon/bits/utility.h>

///\ingroup graphbits

///\file

///\brief Observer notifier for graph alteration observers.

namespace lemon {

  /// \ingroup graphbits

  ///

  /// \brief Notifier class to notify observes about alterations in 

  /// a container.

  ///

  /// The simple graph's can be refered as two containers, one node container

  /// and one edge container. But they are not standard containers they

  /// does not store values directly they are just key continars for more

  /// value containers which are the node and edge maps.

  ///

  /// The graph's node and edge sets can be changed as we add or erase

  /// nodes and edges in the graph. Lemon would like to handle easily

  /// that the node and edge maps should contain values for all nodes or

  /// edges. If we want to check on every indicing if the map contains

  /// the current indicing key that cause a drawback in the performance

  /// in the library. We use another solution we notify all maps about

  /// an alteration in the graph, which cause only drawback on the

  /// alteration of the graph.

  ///

  /// This class provides an interface to the container. The \e first() and \e 

  /// next() member functions make possible to iterate on the keys of the

  /// container. The \e id() function returns an integer id for each key.

  /// The \e maxId() function gives back an upper bound of the ids.

  ///

  /// For the proper functonality of this class, we should notify it

  /// about each alteration in the container. The alterations have four type

  /// as \e add(), \e erase(), \e build() and \e clear(). The \e add() and

  /// \e erase() signals that only one or few items added or erased to or

  /// from the graph. If all items are erased from the graph or from an empty

  /// graph a new graph is builded then it can be signaled with the

  /// clear() and build() members. Important rule that if we erase items 

  /// from graph we should first signal the alteration and after that erase

  /// them from the container, on the other way on item addition we should

  /// first extend the container and just after that signal the alteration.

  ///

  /// The alteration can be observed with a class inherited from the

  /// \e ObserverBase nested class. The signals can be handled with

  /// overriding the virtual functions defined in the base class.  The

  /// observer base can be attached to the notifier with the 

  /// \e attach() member and can be detached with detach() function. The

  /// alteration handlers should not call any function which signals

  /// an other alteration in the same notifier and should not

  /// detach any observer from the notifier.

  ///

  /// Alteration observers try to be exception safe. If an \e add() or

  /// a \e clear() function throws an exception then the remaining

  /// observeres will not be notified and the fulfilled additions will

  /// be rolled back by calling the \e erase() or \e clear()

  /// functions. Thence the \e erase() and \e clear() should not throw

  /// exception. Actullay, it can be throw only 

  /// \ref AlterationObserver::ImmediateDetach ImmediateDetach

  /// exception which detach the observer from the notifier.

  ///

  /// There are some place when the alteration observing is not completly

  /// reliable. If we want to carry out the node degree in the graph

  /// as in the \ref InDegMap and we use the reverseEdge that cause 

  /// unreliable functionality. Because the alteration observing signals

  /// only erasing and adding but not the reversing it will stores bad

  /// degrees. The sub graph adaptors cannot signal the alterations because

  /// just a setting in the filter map can modify the graph and this cannot

  /// be watched in any way.

  ///

  /// \param _Container The container which is observed.

  /// \param _Item The item type which is obserbved.

  ///

  /// \author Balazs Dezso

  template <typename _Container, typename _Item>

  class AlterationNotifier {

  public:

    typedef True Notifier;

    typedef _Container Container;

    typedef _Item Item;

    /// \brief Exception which can be called from \e clear() and 

    /// \e erase().

    ///

    /// From the \e clear() and \e erase() function only this

    /// exception is allowed to throw. The exception immediatly

    /// detaches the current observer from the notifier. Because the

    /// \e clear() and \e erase() should not throw other exceptions

    /// it can be used to invalidate the observer.

    struct ImmediateDetach {};

    /// \brief ObserverBase is the base class for the observers.

    ///

    /// ObserverBase is the abstract base class for the observers.

    /// It will be notified about an item was inserted into or

    /// erased from the graph.

    ///

    /// The observer interface contains some pure virtual functions

    /// to override. The add() and erase() functions are

    /// to notify the oberver when one item is added or

    /// erased.

    ///

    /// The build() and clear() members are to notify the observer

    /// about the container is built from an empty container or

    /// is cleared to an empty container. 

    /// 

    /// \author Balazs Dezso

    class ObserverBase {

    protected:

      typedef AlterationNotifier Notifier;

      friend class AlterationNotifier;

      /// \brief Default constructor.

      ///

      /// Default constructor for ObserverBase.

      /// 

      ObserverBase() : _notifier(0) {}

      /// \brief Constructor which attach the observer into notifier.

      ///

      /// Constructor which attach the observer into notifier.

      ObserverBase(AlterationNotifier& nf) {

        attach(nf);

      }

      /// \brief Constructor which attach the obserever to the same notifier.

      ///

      /// Constructor which attach the obserever to the same notifier as

      /// the other observer is attached to. 

      ObserverBase(const ObserverBase& copy) {

	if (copy.attached()) {

          attach(*copy.notifier());

	}

      }

      /// \brief Destructor

      virtual ~ObserverBase() {

        if (attached()) {

          detach();

        }

      }

      /// \brief Attaches the observer into an AlterationNotifier.

      ///

      /// This member attaches the observer into an AlterationNotifier.

      ///

      void attach(AlterationNotifier& nf) {

	nf.attach(*this);

      }

      /// \brief Detaches the observer into an AlterationNotifier.

      ///

      /// This member detaches the observer from an AlterationNotifier.

      ///

      void detach() {

        _notifier->detach(*this);

      }

      /// \brief Gives back a pointer to the notifier which the map 

      /// attached into.

      ///

      /// This function gives back a pointer to the notifier which the map

      /// attached into.

      ///

      Notifier* notifier() const { return const_cast<Notifier*>(_notifier); }

      /// Gives back true when the observer is attached into a notifier.

      bool attached() const { return _notifier != 0; }

    private:

      ObserverBase& operator=(const ObserverBase& copy);

    protected:

      Notifier* _notifier;

      typename std::list<ObserverBase*>::iterator _index;

      /// \brief The member function to notificate the observer about an

      /// item is added to the container.

      ///

      /// The add() member function notificates the observer about an item

      /// is added to the container. It have to be overrided in the

      /// subclasses.

      virtual void add(const Item&) = 0;

      /// \brief The member function to notificate the observer about 

      /// more item is added to the container.

      ///

      /// The add() member function notificates the observer about more item

      /// is added to the container. It have to be overrided in the

      /// subclasses.

      virtual void add(const std::vector<Item>& items) = 0;

      /// \brief The member function to notificate the observer about an

      /// item is erased from the container.

      ///

      /// The erase() member function notificates the observer about an

      /// item is erased from the container. It have to be overrided in

      /// the subclasses.	

      virtual void erase(const Item&) = 0;

      /// \brief The member function to notificate the observer about 

      /// more item is erased from the container.

      ///

      /// The erase() member function notificates the observer about more item

      /// is erased from the container. It have to be overrided in the

      /// subclasses.

      virtual void erase(const std::vector<Item>& items) = 0;

      /// \brief The member function to notificate the observer about the

      /// container is built.

      ///

      /// The build() member function notificates the observer about the

      /// container is built from an empty container. It have to be

      /// overrided in the subclasses.

      virtual void build() = 0;

      /// \brief The member function to notificate the observer about all

      /// items are erased from the container.

      ///

      /// The clear() member function notificates the observer about all

      /// items are erased from the container. It have to be overrided in

      /// the subclasses.      

      virtual void clear() = 0;

    };

  protected:

    const Container* container;

    typedef std::list<ObserverBase*> Observers; 

    Observers _observers;

  public:

    /// \brief Default constructor.

    ///

    /// The default constructor of the AlterationNotifier. 

    /// It creates an empty notifier.

    AlterationNotifier() 

      : container(0) {}

    /// \brief Constructor.

    ///

    /// Constructor with the observed container parameter.

    AlterationNotifier(const Container& _container) 

      : container(&_container) {}

    /// \brief Copy Constructor of the AlterationNotifier. 

    ///

    /// Copy constructor of the AlterationNotifier. 

    /// It creates only an empty notifier because the copiable

    /// notifier's observers have to be registered still into that notifier.

    AlterationNotifier(const AlterationNotifier& _notifier) 

      : container(_notifier.container) {}

    /// \brief Destructor.

    ///		

    /// Destructor of the AlterationNotifier.

    ///

    ~AlterationNotifier() {

      typename Observers::iterator it;

      for (it = _observers.begin(); it != _observers.end(); ++it) {

	(*it)->_notifier = 0;

      }

    }

    /// \brief Sets the container.

    ///

    /// Sets the container.

    void setContainer(const Container& _container) {

      container = &_container;

    }

  protected:

    AlterationNotifier& operator=(const AlterationNotifier&);

  public:

    /// \brief First item in the container.

    ///

    /// Returns the first item in the container. It is

    /// for start the iteration on the container.

    void first(Item& item) const {

      container->first(item);

    }

    /// \brief Next item in the container.

    ///

    /// Returns the next item in the container. It is

    /// for iterate on the container.

    void next(Item& item) const {

      container->next(item);

    }

    /// \brief Returns the id of the item.

    ///

    /// Returns the id of the item provided by the container.

    int id(const Item& item) const {

      return container->id(item);

    }

    /// \brief Returns the maximum id of the container.

    ///

    /// Returns the maximum id of the container.

    int maxId() const {

      return container->maxId(Item());

    }

  protected:

    void attach(ObserverBase& observer) {

      observer._index = _observers.insert(_observers.begin(), &observer);

      observer._notifier = this;

    } 

    void detach(ObserverBase& observer) {

      _observers.erase(observer._index);

      observer._index = _observers.end();

      observer._notifier = 0;

    }

  public:

    /// \brief Notifies all the registed observers about an item added to 

    /// the container.

    ///

    /// It notifies all the registed observers about an item added to 

    /// the container.

    /// 

    void add(const Item& item) {

      typename Observers::reverse_iterator it;

      try {

        for (it = _observers.rbegin(); it != _observers.rend(); ++it) {

          (*it)->add(item);

        }

      } catch (...) {

        typename Observers::iterator jt;

        for (jt = it.base(); jt != _observers.end(); ++jt) {

          (*jt)->erase(item);

        }

        throw;

      }

    }	

    /// \brief Notifies all the registed observers about more item added to 

    /// the container.

    ///

    /// It notifies all the registed observers about more item added to 

    /// the container.

    /// 

    void add(const std::vector<Item>& items) {

      typename Observers::reverse_iterator it;

/* -*- C++ -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_BITS_ARRAY_MAP_H

#define LEMON_BITS_ARRAY_MAP_H

#include <memory>

#include <lemon/bits/traits.h>

#include <lemon/bits/alteration_notifier.h>

#include <lemon/concept_check.h>

#include <lemon/concepts/maps.h>

/// \ingroup graphbits

/// \file

/// \brief Graph map based on the array storage.

namespace lemon {

  /// \ingroup graphbits

  ///

  /// \brief Graph map based on the array storage.

  ///

  /// The ArrayMap template class is graph map structure what

  /// automatically updates the map when a key is added to or erased from

  /// the map. This map uses the allocators to implement 

  /// the container functionality.

  ///

  /// The template parameters are the Graph the current Item type and

  /// the Value type of the map.

  template <typename _Graph, typename _Item, typename _Value>

  class ArrayMap 

    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {

  public:

    /// The graph type of the maps. 

    typedef _Graph Graph;

    /// The item type of the map.

    typedef _Item Item;

    /// The reference map tag.

    typedef True ReferenceMapTag;

    /// The key type of the maps.

    typedef _Item Key;

    /// The value type of the map.

    typedef _Value Value;

    /// The const reference type of the map.

    typedef const _Value& ConstReference;

    /// The reference type of the map.

    typedef _Value& Reference;

    /// The notifier type.

    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;

    /// The MapBase of the Map which imlements the core regisitry function.

    typedef typename Notifier::ObserverBase Parent;

  private:

    typedef std::allocator<Value> Allocator;

  public:

    /// \brief Graph initialized map constructor.

    ///

    /// Graph initialized map constructor.

    explicit ArrayMap(const Graph& graph) {

      Parent::attach(graph.notifier(Item()));

      allocate_memory();

      Notifier* nf = Parent::notifier();

      Item it;

      for (nf->first(it); it != INVALID; nf->next(it)) {

	int id = nf->id(it);;

	allocator.construct(&(values[id]), Value());

      }								

    }

    /// \brief Constructor to use default value to initialize the map. 

    ///

    /// It constructs a map and initialize all of the the map. 

    ArrayMap(const Graph& graph, const Value& value) {

      Parent::attach(graph.notifier(Item()));

      allocate_memory();

      Notifier* nf = Parent::notifier();

      Item it;

      for (nf->first(it); it != INVALID; nf->next(it)) {

	int id = nf->id(it);;

	allocator.construct(&(values[id]), value);

      }								

    }

    /// \brief Constructor to copy a map of the same map type.

    ///

    /// Constructor to copy a map of the same map type.     

    ArrayMap(const ArrayMap& copy) : Parent() {

      if (copy.attached()) {

	attach(*copy.notifier());

      }

      capacity = copy.capacity;

      if (capacity == 0) return;

      values = allocator.allocate(capacity);

      Notifier* nf = Parent::notifier();

      Item it;

      for (nf->first(it); it != INVALID; nf->next(it)) {

	int id = nf->id(it);;

	allocator.construct(&(values[id]), copy.values[id]);

      }

    }

    /// \brief Assign operator.

    ///

    /// This operator assigns for each item in the map the

    /// value mapped to the same item in the copied map.  

    /// The parameter map should be indiced with the same

    /// itemset because this assign operator does not change

    /// the container of the map. 

    ArrayMap& operator=(const ArrayMap& cmap) {

      return operator=<ArrayMap>(cmap);

    }

    /// \brief Template assign operator.

    ///

    /// The given parameter should be conform to the ReadMap

    /// concecpt and could be indiced by the current item set of

    /// the NodeMap. In this case the value for each item

    /// is assigned by the value of the given ReadMap. 

    template <typename CMap>

    ArrayMap& operator=(const CMap& cmap) {

      checkConcept<concepts::ReadMap<Key, _Value>, CMap>();

      const typename Parent::Notifier* nf = Parent::notifier();

      Item it;

      for (nf->first(it); it != INVALID; nf->next(it)) {

        set(it, cmap[it]);

      }

      return *this;

    }

    /// \brief The destructor of the map.

    ///     

    /// The destructor of the map.

    virtual ~ArrayMap() {      

      if (attached()) {

	clear();

	detach();

      }

    }

  protected:

    using Parent::attach;

    using Parent::detach;

    using Parent::attached;

  public:

    /// \brief The subscript operator. 

    ///

    /// The subscript operator. The map can be subscripted by the

    /// actual keys of the graph. 

    Value& operator[](const Key& key) {

      int id = Parent::notifier()->id(key);

      return values[id];

    } 

    /// \brief The const subscript operator.

    ///

    /// The const subscript operator. The map can be subscripted by the

    /// actual keys of the graph. 

    const Value& operator[](const Key& key) const {

      int id = Parent::notifier()->id(key);

      return values[id];

    }

    /// \brief Setter function of the map.

    ///	

    /// Setter function of the map. Equivalent with map[key] = val.

    /// This is a compatibility feature with the not dereferable maps.

    void set(const Key& key, const Value& val) {

      (*this)[key] = val;

    }

  protected:

    /// \brief Adds a new key to the map.

    ///		

    /// It adds a new key to the map. It called by the observer notifier

    /// and it overrides the add() member function of the observer base.     

    virtual void add(const Key& key) {

      Notifier* nf = Parent::notifier();

      int id = nf->id(key);

      if (id >= capacity) {

	int new_capacity = (capacity == 0 ? 1 : capacity);

	while (new_capacity <= id) {

	  new_capacity <<= 1;

	}

	Value* new_values = allocator.allocate(new_capacity);

	Item it;

	for (nf->first(it); it != INVALID; nf->next(it)) {

	  int jd = nf->id(it);;

	  if (id != jd) {

	    allocator.construct(&(new_values[jd]), values[jd]);

	    allocator.destroy(&(values[jd]));

	  }

	}

	if (capacity != 0) allocator.deallocate(values, capacity);

	values = new_values;

	capacity = new_capacity;

      }

      allocator.construct(&(values[id]), Value());

    }

    /// \brief Adds more new keys to the map.

    ///		

    /// It adds more new keys to the map. It called by the observer notifier

    /// and it overrides the add() member function of the observer base.     

    virtual void add(const std::vector<Key>& keys) {

      Notifier* nf = Parent::notifier();

      int max_id = -1;

      for (int i = 0; i < int(keys.size()); ++i) {

	int id = nf->id(keys[i]);

	if (id > max_id) {

	  max_id = id;

	}

      }

      if (max_id >= capacity) {

	int new_capacity = (capacity == 0 ? 1 : capacity);

	while (new_capacity <= max_id) {

	  new_capacity <<= 1;

	}

	Value* new_values = allocator.allocate(new_capacity);

	Item it;

	for (nf->first(it); it != INVALID; nf->next(it)) {

	  int id = nf->id(it);

	  bool found = false;

	  for (int i = 0; i < int(keys.size()); ++i) {

	    int jd = nf->id(keys[i]);

	    if (id == jd) {

	      found = true;

	      break;

	    }

	  }

	  if (found) continue;

	  allocator.construct(&(new_values[id]), values[id]);

	  allocator.destroy(&(values[id]));

	}

	if (capacity != 0) allocator.deallocate(values, capacity);

	values = new_values;

	capacity = new_capacity;

      }

      for (int i = 0; i < int(keys.size()); ++i) {

	int id = nf->id(keys[i]);

	allocator.construct(&(values[id]), Value());

      }

    }

    /// \brief Erase a key from the map.

    ///

    /// Erase a key from the map. It called by the observer notifier

    /// and it overrides the erase() member function of the observer base.     

    virtual void erase(const Key& key) {

      int id = Parent::notifier()->id(key);

      allocator.destroy(&(values[id]));

    }

    /// \brief Erase more keys from the map.

    ///

    /// Erase more keys from the map. It called by the observer notifier

    /// and it overrides the erase() member function of the observer base.     

    virtual void erase(const std::vector<Key>& keys) {

      for (int i = 0; i < int(keys.size()); ++i) {

	int id = Parent::notifier()->id(keys[i]);

	allocator.destroy(&(values[id]));

      }

    }

    /// \brief Buildes the map.

    ///	

    /// It buildes the map. It called by the observer notifier

    /// and it overrides the build() member function of the observer base. 

    virtual void build() {

      Notifier* nf = Parent::notifier();

      allocate_memory();

      Item it;

      for (nf->first(it); it != INVALID; nf->next(it)) {

	int id = nf->id(it);;

	allocator.construct(&(values[id]), Value());

      }								

    }

    /// \brief Clear the map.

    ///

    /// It erase all items from the map. It called by the observer notifier

    /// and it overrides the clear() member function of the observer base.     

    virtual void clear() {	

      Notifier* nf = Parent::notifier();

      if (capacity != 0) {

	Item it;

	for (nf->first(it); it != INVALID; nf->next(it)) {

	  int id = nf->id(it);

	  allocator.destroy(&(values[id]));

	}								

	allocator.deallocate(values, capacity);

	capacity = 0;

      }

    }

  private:

    void allocate_memory() {

      int max_id = Parent::notifier()->maxId();

      if (max_id == -1) {

	capacity = 0;

	values = 0;

	return;

      }

      capacity = 1;

      while (capacity <= max_id) {

	capacity <<= 1;

      }

      values = allocator.allocate(capacity);	

    }      

    int capacity;

    Value* values;

    Allocator allocator;

  };		

}

#endif 

/* -*- C++ -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library

 *

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_BITS_BASE_EXTENDER_H

#define LEMON_BITS_BASE_EXTENDER_H

#include <lemon/bits/invalid.h>

#include <lemon/error.h>

#include <lemon/bits/map_extender.h>

#include <lemon/bits/default_map.h>

#include <lemon/concept_check.h>

#include <lemon/concepts/maps.h>

///\ingroup digraphbits

///\file

///\brief Extenders for the digraph types

namespace lemon {

  /// \ingroup digraphbits

  ///

  /// \brief BaseDigraph to BaseGraph extender

  template <typename Base>

  class UndirDigraphExtender : public Base {

  public:

    typedef Base Parent;

    typedef typename Parent::Arc Edge;

    typedef typename Parent::Node Node;

    typedef True UndirectedTag;

    class Arc : public Edge {

      friend class UndirDigraphExtender;

    protected:

      bool forward;

      Arc(const Edge &ue, bool _forward) :

        Edge(ue), forward(_forward) {}

    public:

      Arc() {}

      /// Invalid arc constructor

      Arc(Invalid i) : Edge(i), forward(true) {}

      bool operator==(const Arc &that) const {

	return forward==that.forward && Edge(*this)==Edge(that);

      }

      bool operator!=(const Arc &that) const {

	return forward!=that.forward || Edge(*this)!=Edge(that);

      }

      bool operator<(const Arc &that) const {

	return forward<that.forward ||

	  (!(that.forward<forward) && Edge(*this)<Edge(that));

      }

    };

    using Parent::source;

    /// Source of the given Arc.

    Node source(const Arc &e) const {

      return e.forward ? Parent::source(e) : Parent::target(e);

    }

    using Parent::target;

    /// Target of the given Arc.

    Node target(const Arc &e) const {

      return e.forward ? Parent::target(e) : Parent::source(e);

    }

    /// \brief Directed arc from an edge.

    ///

    /// Returns a directed arc corresponding to the specified Edge.

    /// If the given bool is true the given edge and the

    /// returned arc have the same source node.

    static Arc direct(const Edge &ue, bool d) {

      return Arc(ue, d);

    }

    /// Returns whether the given directed arc is same orientation as the

    /// corresponding edge.

    ///

    /// \todo reference to the corresponding point of the undirected digraph

    /// concept. "What does the direction of an edge mean?"

    static bool direction(const Arc &e) { return e.forward; }

    using Parent::first;

    using Parent::next;

    void first(Arc &e) const {

      Parent::first(e);

      e.forward=true;

    }

    void next(Arc &e) const {

      if( e.forward ) {

	e.forward = false;

      }

      else {

	Parent::next(e);

	e.forward = true;

      }

    }

    void firstOut(Arc &e, const Node &n) const {

      Parent::firstIn(e,n);

      if( Edge(e) != INVALID ) {

	e.forward = false;

      }

      else {

	Parent::firstOut(e,n);

	e.forward = true;

      }

    }

    void nextOut(Arc &e) const {

      if( ! e.forward ) {

	Node n = Parent::target(e);

	Parent::nextIn(e);

	if( Edge(e) == INVALID ) {

	  Parent::firstOut(e, n);

	  e.forward = true;

	}

      }

      else {

	Parent::nextOut(e);

      }

    }

    void firstIn(Arc &e, const Node &n) const {

      Parent::firstOut(e,n);

      if( Edge(e) != INVALID ) {

	e.forward = false;

      }

      else {

	Parent::firstIn(e,n);

	e.forward = true;

      }

    }

    void nextIn(Arc &e) const {

      if( ! e.forward ) {

	Node n = Parent::source(e);

	Parent::nextOut(e);

	if( Edge(e) == INVALID ) {

	  Parent::firstIn(e, n);

	  e.forward = true;

	}

      }

      else {

	Parent::nextIn(e);

      }

    }

    void firstInc(Edge &e, bool &d, const Node &n) const {

      d = true;

      Parent::firstOut(e, n);

      if (e != INVALID) return;

      d = false;

      Parent::firstIn(e, n);

    }

    void nextInc(Edge &e, bool &d) const {

      if (d) {

	Node s = Parent::source(e);

	Parent::nextOut(e);

	if (e != INVALID) return;

	d = false;

	Parent::firstIn(e, s);

      } else {

	Parent::nextIn(e);

      }

    }

    Node nodeFromId(int ix) const {

      return Parent::nodeFromId(ix);

    }

    Arc arcFromId(int ix) const {

      return direct(Parent::arcFromId(ix >> 1), bool(ix & 1));

    }

    Edge edgeFromId(int ix) const {

      return Parent::arcFromId(ix);

    }

    int id(const Node &n) const {

      return Parent::id(n);

    }

    int id(const Edge &e) const {

      return Parent::id(e);

    }

    int id(const Arc &e) const {

      return 2 * Parent::id(e) + int(e.forward);

    }

    int maxNodeId() const {

      return Parent::maxNodeId();

    }

    int maxArcId() const {

      return 2 * Parent::maxArcId() + 1;

    }

    int maxEdgeId() const {

      return Parent::maxArcId();

    }

    int arcNum() const {

      return 2 * Parent::arcNum();

    }

    int edgeNum() const {

      return Parent::arcNum();

    }

    Arc findArc(Node s, Node t, Arc p = INVALID) const {

      if (p == INVALID) {

	Edge arc = Parent::findArc(s, t);

	if (arc != INVALID) return direct(arc, true);

	arc = Parent::findArc(t, s);

	if (arc != INVALID) return direct(arc, false);

      } else if (direction(p)) {

	Edge arc = Parent::findArc(s, t, p);

	if (arc != INVALID) return direct(arc, true);

	arc = Parent::findArc(t, s);

	if (arc != INVALID) return direct(arc, false);	

      } else {

	Edge arc = Parent::findArc(t, s, p);

	if (arc != INVALID) return direct(arc, false);	      

      }

      return INVALID;

    }

    Edge findEdge(Node s, Node t, Edge p = INVALID) const {

      if (s != t) {

        if (p == INVALID) {

          Edge arc = Parent::findArc(s, t);

          if (arc != INVALID) return arc;

          arc = Parent::findArc(t, s);

          if (arc != INVALID) return arc;

        } else if (Parent::s(p) == s) {

          Edge arc = Parent::findArc(s, t, p);

          if (arc != INVALID) return arc;

          arc = Parent::findArc(t, s);

          if (arc != INVALID) return arc;	

        } else {

          Edge arc = Parent::findArc(t, s, p);

          if (arc != INVALID) return arc;	      

        }

      } else {

        return Parent::findArc(s, t, p);

      }

      return INVALID;

    }

  };

  template <typename Base>

  class BidirBpGraphExtender : public Base {

  public:

    typedef Base Parent;

    typedef BidirBpGraphExtender Digraph;

    typedef typename Parent::Node Node;

    typedef typename Parent::Edge Edge;

    using Parent::first;

    using Parent::next;

    using Parent::id;

    class Red : public Node {

      friend class BidirBpGraphExtender;

    public:

      Red() {}

      Red(const Node& node) : Node(node) {

	LEMON_ASSERT(Parent::red(node) || node == INVALID, 

		     typename Parent::NodeSetError());

      }

      Red& operator=(const Node& node) {

	LEMON_ASSERT(Parent::red(node) || node == INVALID, 

		     typename Parent::NodeSetError());

        Node::operator=(node);

        return *this;

      }

      Red(Invalid) : Node(INVALID) {}

      Red& operator=(Invalid) {

        Node::operator=(INVALID);

        return *this;

      }

    };

    void first(Red& node) const {

      Parent::firstRed(static_cast<Node&>(node));

    }

    void next(Red& node) const {