*

  *

  *

  *

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

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

  *

  *

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

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

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

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

 namespace lemon {

 namespace lemon {

   class StaticDigraphBase {

   class StaticDigraphBase {

   public:

   public:

         node_first_out(NULL), node_first_in(NULL),

         node_first_out(NULL), node_first_in(NULL),

         arc_next_in(NULL), arc_next_out(NULL) {}

         arc_next_in(NULL), arc_next_out(NULL) {}

     ~StaticDigraphBase() {

     ~StaticDigraphBase() {

       if (built) {

       if (built) {

         delete[] node_first_out;

         delete[] node_first_out;

         delete[] node_first_in;

         delete[] node_first_in;

         delete[] arc_source;

         delete[] arc_source;

       bool operator!=(const Node& node) const { return id != node.id; }

       bool operator!=(const Node& node) const { return id != node.id; }

       bool operator<(const Node& node) const { return id < node.id; }

       bool operator<(const Node& node) const { return id < node.id; }

     };

     };

     class Arc {

     class Arc {

     protected:

     protected:

       int id;

       int id;

       Arc(int _id) : id(_id) {}

       Arc(int _id) : id(_id) {}

     public:

     public:

       Arc() { }

       Arc() { }

     static void next(Node& n) { --n.id; }

     static void next(Node& n) { --n.id; }

     void first(Arc& e) const { e.id = arc_num - 1; }

     void first(Arc& e) const { e.id = arc_num - 1; }

     static void next(Arc& e) { --e.id; }

     static void next(Arc& e) { --e.id; }

         node_first_out[n.id] : -1;

         node_first_out[n.id] : -1;

     }

     }

     void nextOut(Arc& e) const { e.id = arc_next_out[e.id]; }

     void nextOut(Arc& e) const { e.id = arc_next_out[e.id]; }

     void firstIn(Arc& e, const Node& n) const { e.id = node_first_in[n.id]; }

     void firstIn(Arc& e, const Node& n) const { e.id = node_first_in[n.id]; }

     template <typename Digraph, typename NodeRefMap>

     template <typename Digraph, typename NodeRefMap>

     class ArcLess {

     class ArcLess {

     public:

     public:

       typedef typename Digraph::Arc Arc;

       typedef typename Digraph::Arc Arc;

         : digraph(_graph), nodeRef(_nodeRef) {}

         : digraph(_graph), nodeRef(_nodeRef) {}

       bool operator()(const Arc& left, const Arc& right) const {

       bool operator()(const Arc& left, const Arc& right) const {

       }

       }

     private:

     private:

       const Digraph& digraph;

       const Digraph& digraph;

       const NodeRefMap& nodeRef;

       const NodeRefMap& nodeRef;

     };

     };

   public:

   public:

     typedef True BuildTag;

     typedef True BuildTag;

     void clear() {

     void clear() {

       if (built) {

       if (built) {

         delete[] node_first_out;

         delete[] node_first_out;

         delete[] node_first_in;

         delete[] node_first_in;

         delete[] arc_source;

         delete[] arc_source;

       }

       }

       built = false;

       built = false;

       node_num = 0;

       node_num = 0;

       arc_num = 0;

       arc_num = 0;

     }

     }

     template <typename Digraph, typename NodeRefMap, typename ArcRefMap>

     template <typename Digraph, typename NodeRefMap, typename ArcRefMap>

     void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {

     void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {

       typedef typename Digraph::Node GNode;

       typedef typename Digraph::Node GNode;

       typedef typename Digraph::Arc GArc;

       typedef typename Digraph::Arc GArc;

           std::sort(arcs.begin(), arcs.end(), arcLess);

           std::sort(arcs.begin(), arcs.end(), arcLess);

           for (typename std::vector<GArc>::iterator it = arcs.begin();

           for (typename std::vector<GArc>::iterator it = arcs.begin();

                it != arcs.end(); ++it) {

                it != arcs.end(); ++it) {

             int target = nodeRef[digraph.target(*it)].id;

             int target = nodeRef[digraph.target(*it)].id;

             arcRef[*it] = Arc(arc_index);

             arcRef[*it] = Arc(arc_index);

             arc_target[arc_index] = target;

             arc_target[arc_index] = target;

             arc_next_in[arc_index] = node_first_in[target];

             arc_next_in[arc_index] = node_first_in[target];

             node_first_in[target] = arc_index;

             node_first_in[target] = arc_index;

             arc_next_out[arc_index] = arc_index + 1;

             arc_next_out[arc_index] = arc_index + 1;

             ++arc_index;

             ++arc_index;

           node_first_out[source] = arc_index;

           node_first_out[source] = arc_index;

         }

         }

       }

       }

       node_first_out[node_num] = arc_num;

       node_first_out[node_num] = arc_num;

     }

     }

     template <typename ArcListIterator>

     template <typename ArcListIterator>

     void build(int n, ArcListIterator first, ArcListIterator last) {

     void build(int n, ArcListIterator first, ArcListIterator last) {

       built = true;

       built = true;

       node_num = n;

       node_num = n;

       arc_source = new int[arc_num];

       arc_source = new int[arc_num];

       arc_target = new int[arc_num];

       arc_target = new int[arc_num];

       arc_next_out = new int[arc_num];

       arc_next_out = new int[arc_num];

       arc_next_in = new int[arc_num];

       arc_next_in = new int[arc_num];

       for (int i = 0; i != node_num; ++i) {

       for (int i = 0; i != node_num; ++i) {

         node_first_in[i] = -1;

         node_first_in[i] = -1;

       int arc_index = 0;

       int arc_index = 0;

       for (int i = 0; i != node_num; ++i) {

       for (int i = 0; i != node_num; ++i) {

         node_first_out[i] = arc_index;

         node_first_out[i] = arc_index;

         for ( ; first != last && (*first).first == i; ++first) {

         for ( ; first != last && (*first).first == i; ++first) {

           int j = (*first).second;

           int j = (*first).second;

   /// However it only provides build() and clear() functions and does not

   /// However it only provides build() and clear() functions and does not

   /// support any other modification of the digraph.

   /// support any other modification of the digraph.

   ///

   ///

   /// Since this digraph structure is completely static, its nodes and arcs

   /// Since this digraph structure is completely static, its nodes and arcs

   /// can be indexed with integers from the ranges <tt>[0..nodeNum()-1]</tt>

   /// can be indexed with integers from the ranges <tt>[0..nodeNum()-1]</tt>

   /// The index of an item is the same as its ID, it can be obtained

   /// The index of an item is the same as its ID, it can be obtained

   /// using the corresponding \ref index() or \ref concepts::Digraph::id()

   /// using the corresponding \ref index() or \ref concepts::Digraph::id()

   /// "id()" function. A node or arc with a certain index can be obtained

   /// "id()" function. A node or arc with a certain index can be obtained

   /// using node() or arc().

   /// using node() or arc().

   ///

   ///

   /// \sa concepts::Digraph

   /// \sa concepts::Digraph

   class StaticDigraph : public ExtendedStaticDigraphBase {

   class StaticDigraph : public ExtendedStaticDigraphBase {

   public:

   public:

     typedef ExtendedStaticDigraphBase Parent;

     typedef ExtendedStaticDigraphBase Parent;

   public:

   public:

     /// \brief Constructor

     /// \brief Constructor

     ///

     ///

     /// Default constructor.

     /// Default constructor.

     StaticDigraph() : Parent() {}

     StaticDigraph() : Parent() {}

     /// kind. It can be called more than once, but in such case, the whole

     /// kind. It can be called more than once, but in such case, the whole

     /// structure and all maps will be cleared and rebuilt.

     /// structure and all maps will be cleared and rebuilt.

     ///

     ///

     /// This method also makes possible to copy a digraph to a StaticDigraph

     /// This method also makes possible to copy a digraph to a StaticDigraph

     /// structure using \ref DigraphCopy.

     /// structure using \ref DigraphCopy.

     /// \param digraph An existing digraph to be copied.

     /// \param digraph An existing digraph to be copied.

     /// \param nodeRef The node references will be copied into this map.

     /// \param nodeRef The node references will be copied into this map.

     /// Its key type must be \c Digraph::Node and its value type must be

     /// Its key type must be \c Digraph::Node and its value type must be

     /// \c StaticDigraph::Node.

     /// \c StaticDigraph::Node.

     /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"

     /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"

     template <typename Digraph, typename NodeRefMap, typename ArcRefMap>

     template <typename Digraph, typename NodeRefMap, typename ArcRefMap>

     void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {

     void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {

       if (built) Parent::clear();

       if (built) Parent::clear();

       Parent::build(digraph, nodeRef, arcRef);

       Parent::build(digraph, nodeRef, arcRef);

     }

     }

     /// \brief Build the digraph from an arc list.

     /// \brief Build the digraph from an arc list.

     ///

     ///

     /// This function builds the digraph from the given arc list.

     /// This function builds the digraph from the given arc list.

     /// It can be called more than once, but in such case, the whole

     /// It can be called more than once, but in such case, the whole

     /// structure and all maps will be cleared and rebuilt.

     /// structure and all maps will be cleared and rebuilt.

   protected:

   protected:

     using Parent::fastFirstOut;

     using Parent::fastFirstOut;

     using Parent::fastNextOut;

     using Parent::fastNextOut;

     using Parent::fastLastOut;

     using Parent::fastLastOut;

   public:

   public:

     class OutArcIt : public Arc {

     class OutArcIt : public Arc {

     public:

     public:

       OutArcIt() { }

       OutArcIt() { }

       OutArcIt(Invalid i) : Arc(i) { }

       OutArcIt(Invalid i) : Arc(i) { }

       OutArcIt(const StaticDigraph& digraph, const Node& node) {

       OutArcIt(const StaticDigraph& digraph, const Node& node) {

         if (last == *this) *this = INVALID;

         if (last == *this) *this = INVALID;

       }

       }

       OutArcIt(const StaticDigraph& digraph, const Arc& arc) : Arc(arc) {

       OutArcIt(const StaticDigraph& digraph, const Arc& arc) : Arc(arc) {

         if (arc != INVALID) {

         if (arc != INVALID) {

           digraph.fastLastOut(last, digraph.source(arc));

           digraph.fastLastOut(last, digraph.source(arc));

         }

         }

       }

       }

         StaticDigraph::fastNextOut(*this);

         StaticDigraph::fastNextOut(*this);

         if (last == *this) *this = INVALID;

         if (last == *this) *this = INVALID;

       }

       }

     private:

     private:

       Arc last;

       Arc last;

     };

     };