RhodeCode

  struct InvalidType {};

  template <typename _Graph, typename _Item>

  class ItemSetTraits {};

  template <typename Graph, typename Enable = void>

  struct NodeNotifierIndicator {

    typedef InvalidType Type;

  };

  template <typename Graph>

  struct NodeNotifierIndicator<

    Graph,

    typename enable_if<typename Graph::NodeNotifier::Notifier, void>::type

  > {

    typedef typename Graph::NodeNotifier Type;

  };

  template <typename _Graph>

  class ItemSetTraits<_Graph, typename _Graph::Node> {

  public:

    typedef _Graph Graph;

    typedef typename Graph::Node Item;

    typedef typename Graph::NodeIt ItemIt;

    typedef typename NodeNotifierIndicator<Graph>::Type ItemNotifier;

    template <typename _Value>

    class Map : public Graph::template NodeMap<_Value> {

    public:

      typedef typename Graph::template NodeMap<_Value> Parent;

      typedef typename Graph::template NodeMap<_Value> Type;

      typedef typename Parent::Value Value;

      Map(const Graph& _digraph) : Parent(_digraph) {}

      Map(const Graph& _digraph, const Value& _value)

        : Parent(_digraph, _value) {}

     };

  };

  template <typename Graph, typename Enable = void>

  struct ArcNotifierIndicator {

    typedef InvalidType Type;

  };

  template <typename Graph>

  struct ArcNotifierIndicator<

    Graph,

    typename enable_if<typename Graph::ArcNotifier::Notifier, void>::type

  > {

    typedef typename Graph::ArcNotifier Type;

  };

  template <typename _Graph>

  class ItemSetTraits<_Graph, typename _Graph::Arc> {

  public:

    typedef _Graph Graph;

    typedef typename Graph::Arc Item;

    typedef typename Graph::ArcIt ItemIt;

    typedef typename ArcNotifierIndicator<Graph>::Type ItemNotifier;

    template <typename _Value>

    class Map : public Graph::template ArcMap<_Value> {

    public:

      typedef typename Graph::template ArcMap<_Value> Parent;

      typedef typename Graph::template ArcMap<_Value> Type;

      typedef typename Parent::Value Value;

      Map(const Graph& _digraph) : Parent(_digraph) {}

      Map(const Graph& _digraph, const Value& _value)

        : Parent(_digraph, _value) {}

    };

  };

  template <typename Graph, typename Enable = void>

  struct EdgeNotifierIndicator {

    typedef InvalidType Type;

  };

  template <typename Graph>

  struct EdgeNotifierIndicator<

    Graph,

    typename enable_if<typename Graph::EdgeNotifier::Notifier, void>::type

  > {

    typedef typename Graph::EdgeNotifier Type;

  };

  template <typename _Graph>

  class ItemSetTraits<_Graph, typename _Graph::Edge> {

  public:

    typedef _Graph Graph;

    typedef typename Graph::Edge Item;

    typedef typename Graph::EdgeIt ItemIt;

    typedef typename EdgeNotifierIndicator<Graph>::Type ItemNotifier;

    template <typename _Value>

    class Map : public Graph::template EdgeMap<_Value> {

    public:

      typedef typename Graph::template EdgeMap<_Value> Parent;

      typedef typename Graph::template EdgeMap<_Value> Type;

      typedef typename Parent::Value Value;

      Map(const Graph& _digraph) : Parent(_digraph) {}

      Map(const Graph& _digraph, const Value& _value)

        : Parent(_digraph, _value) {}

    };

  };

  template <typename Map, typename Enable = void>

  struct MapTraits {

    typedef False ReferenceMapTag;

    typedef typename Map::Key Key;

    typedef typename Map::Value Value;

    typedef Value ConstReturnValue;

    typedef Value ReturnValue;

  };

  template <typename Map>

  struct MapTraits<

    Map, typename enable_if<typename Map::ReferenceMapTag, void>::type >

  {

    typedef True ReferenceMapTag;

    typedef typename Map::Key Key;

    typedef typename Map::Value Value;

    typedef typename Map::ConstReference ConstReturnValue;

    typedef typename Map::Reference ReturnValue;

    typedef typename Map::ConstReference ConstReference;

    typedef typename Map::Reference Reference;

 };

  template <typename MatrixMap, typename Enable = void>

  struct MatrixMapTraits {

    typedef False ReferenceMapTag;

    typedef typename MatrixMap::FirstKey FirstKey;

    typedef typename MatrixMap::SecondKey SecondKey;

    typedef typename MatrixMap::Value Value;

    typedef Value ConstReturnValue;

    typedef Value ReturnValue;

  };

  template <typename MatrixMap>

  struct MatrixMapTraits<

    MatrixMap, typename enable_if<typename MatrixMap::ReferenceMapTag,

                                  void>::type >

  {

    typedef True ReferenceMapTag;

    typedef typename MatrixMap::FirstKey FirstKey;

    typedef typename MatrixMap::SecondKey SecondKey;

    typedef typename MatrixMap::Value Value;

    typedef typename MatrixMap::ConstReference ConstReturnValue;

    typedef typename MatrixMap::Reference ReturnValue;

    typedef typename MatrixMap::ConstReference ConstReference;

    typedef typename MatrixMap::Reference Reference;

 };

  // Indicators for the tags

  template <typename Graph, typename Enable = void>

  struct NodeNumTagIndicator {

    static const bool value = false;

  };

  template <typename Graph>

  struct NodeNumTagIndicator<

    Graph,

    typename enable_if<typename Graph::NodeNumTag, void>::type

  > {

    static const bool value = true;

  };

  template <typename Graph, typename Enable = void>

  struct EdgeNumTagIndicator {

    static const bool value = false;

  };

  template <typename Graph>

  struct EdgeNumTagIndicator<

    Graph,

    typename enable_if<typename Graph::EdgeNumTag, void>::type

  > {

    static const bool value = true;

  };

  template <typename Graph, typename Enable = void>

  struct FindEdgeTagIndicator {

    static const bool value = false;

  };

  template <typename Graph>

  struct FindEdgeTagIndicator<

    Graph,

    typename enable_if<typename Graph::FindEdgeTag, void>::type

  > {

    static const bool value = true;

  };

  template <typename Graph, typename Enable = void>

  struct UndirectedTagIndicator {

    static const bool value = false;

  };

  template <typename Graph>

  struct UndirectedTagIndicator<

    Graph,

    typename enable_if<typename Graph::UndirectedTag, void>::type

  > {

    static const bool value = true;

  };

  template <typename Graph, typename Enable = void>

  struct BuildTagIndicator {

    static const bool value = false;

  };

  template <typename Graph>

  struct BuildTagIndicator<

    Graph,

    typename enable_if<typename Graph::BuildTag, void>::type

  > {

    static const bool value = true;

  };

}

#endif

    }

    void first(Arc& arc) const {

      arc._id = _arc_num - 1;

    }

    static void next(Arc& arc) {

      --arc._id;

    }

    void firstOut(Arc& arc, const Node& node) const {

      arc._id = (node._id + 1) * _node_num - 1;

    }

    void nextOut(Arc& arc) const {

      if (arc._id % _node_num == 0) arc._id = 0;

      --arc._id;

    }

    void firstIn(Arc& arc, const Node& node) const {

      arc._id = _arc_num + node._id - _node_num;

    }

    void nextIn(Arc& arc) const {

      arc._id -= _node_num;

      if (arc._id < 0) arc._id = -1;

    }

  };

  typedef DigraphExtender<FullDigraphBase> ExtendedFullDigraphBase;

  /// \ingroup graphs

  ///

  /// \brief A full digraph class.

  ///

  /// This is a simple and fast directed full graph implementation.

  /// From each node go arcs to each node (including the source node),

  /// therefore the number of the arcs in the digraph is the square of

  /// the node number. This digraph type is completely static, so you

  /// can neither add nor delete either arcs or nodes, and it needs

  /// constant space in memory.

  ///

  /// This class conforms to the \ref concepts::Digraph "Digraph" concept

  /// and it also has an important extra feature that its maps are

  /// real \ref concepts::ReferenceMap "reference map"s.

  ///

  /// The \c FullDigraph and \c FullGraph classes are very similar,

  /// but there are two differences. While this class conforms only

  /// to the \ref concepts::Digraph "Digraph" concept, the \c FullGraph

  /// class conforms to the \ref concepts::Graph "Graph" concept,

  /// moreover \c FullGraph does not contain a loop arc for each

  /// node as \c FullDigraph does.

  ///

  /// \sa FullGraph

  class FullDigraph : public ExtendedFullDigraphBase {

  public:

    typedef ExtendedFullDigraphBase Parent;

    /// \brief Constructor

    FullDigraph() { construct(0); }

    /// \brief Constructor

    ///

    /// Constructor.

    /// \param n The number of the nodes.

    FullDigraph(int n) { construct(n); }

    /// \brief Resizes the digraph

    ///

    /// Resizes the digraph. The function will fully destroy and

    /// rebuild the digraph. This cause that the maps of the digraph will

    /// reallocated automatically and the previous values will be lost.

    void resize(int n) {

      Parent::notifier(Arc()).clear();

      Parent::notifier(Node()).clear();

      construct(n);

      Parent::notifier(Node()).build();

      Parent::notifier(Arc()).build();

    }

    /// \brief Returns the node with the given index.

    ///

    /// Returns the node with the given index. Since it is a static

    /// digraph its nodes can be indexed with integers from the range

    /// <tt>[0..nodeNum()-1]</tt>.

    /// \sa index()

    Node operator()(int ix) const { return Parent::operator()(ix); }

    /// \brief Returns the index of the given node.

    ///

    /// Returns the index of the given node. Since it is a static

    /// digraph its nodes can be indexed with integers from the range

    /// <tt>[0..nodeNum()-1]</tt>.

    /// \sa operator()

    int index(const Node& node) const { return Parent::index(node); }

    /// \brief Returns the arc connecting the given nodes.

    ///

    /// Returns the arc connecting the given nodes.

    Arc arc(const Node& u, const Node& v) const {

      return Parent::arc(u, v);

    }

    /// \brief Number of nodes.

    int nodeNum() const { return Parent::nodeNum(); }

    /// \brief Number of arcs.

    int arcNum() const { return Parent::arcNum(); }

  };

  class FullGraphBase {

    int _node_num;

    int _edge_num;

  public:

    typedef FullGraphBase Graph;

    class Node;

    class Arc;

    class Edge;

  protected:

    FullGraphBase() {}

    void construct(int n) { _node_num = n; _edge_num = n * (n - 1) / 2; }

    int _uid(int e) const {

      int u = e / _node_num;

      int v = e % _node_num;

      return u < v ? u : _node_num - 2 - u;

    }

    int _vid(int e) const {

      int u = e / _node_num;

      int v = e % _node_num;

      return u < v ? v : _node_num - 1 - v;

    }

    void _uvid(int e, int& u, int& v) const {

      u = e / _node_num;

      v = e % _node_num;

      if  (u >= v) {

        u = _node_num - 2 - u;

        v = _node_num - 1 - v;

      }

    }

    void _stid(int a, int& s, int& t) const {

      if ((a & 1) == 1) {

        _uvid(a >> 1, s, t);

      } else {

        _uvid(a >> 1, t, s);

      }

    }

    int _eid(int u, int v) const {

      if (u < (_node_num - 1) / 2) {

        return u * _node_num + v;

      } else {

        return (_node_num - 1 - u) * _node_num - v - 1;

      }

    }

  public:

    Node operator()(int ix) const { return Node(ix); }

    int index(const Node& node) const { return node._id; }

    Edge edge(const Node& u, const Node& v) const {

      if (u._id < v._id) {

        return Edge(_eid(u._id, v._id));

      } else if (u._id != v._id) {

        return Edge(_eid(v._id, u._id));

      } else {

        return INVALID;

      }

    }

    Arc arc(const Node& s, const Node& t) const {

      if (s._id < t._id) {

        return Arc((_eid(s._id, t._id) << 1) | 1);

      } else if (s._id != t._id) {

        return Arc(_eid(t._id, s._id) << 1);

      } else {

        return INVALID;

      }

    }

    typedef True NodeNumTag;

    typedef True EdgeNumTag;

    int nodeNum() const { return _node_num; }

    int arcNum() const { return 2 * _edge_num; }

    int edgeNum() const { return _edge_num; }

    static int id(Node node) { return node._id; }

    static int id(Arc arc) { return arc._id; }

    static int id(Edge edge) { return edge._id; }

    int maxNodeId() const { return _node_num-1; }

    int maxArcId() const { return 2 * _edge_num-1; }

    int maxEdgeId() const { return _edge_num-1; }

    static Node nodeFromId(int id) { return Node(id);}

    static Arc arcFromId(int id) { return Arc(id);}

    static Edge edgeFromId(int id) { return Edge(id);}

    Node u(Edge edge) const {

      return Node(_uid(edge._id));

    }

    Node v(Edge edge) const {

      return Node(_vid(edge._id));

    }

    Node source(Arc arc) const {

      return Node((arc._id & 1) == 1 ?

                  _uid(arc._id >> 1) : _vid(arc._id >> 1));

    }

    Node target(Arc arc) const {

      return Node((arc._id & 1) == 1 ?

                  _vid(arc._id >> 1) : _uid(arc._id >> 1));

    }

    typedef True FindEdgeTag;

    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {

      return prev != INVALID ? INVALID : edge(u, v);

    }

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

      return prev != INVALID ? INVALID : arc(s, t);

    }

    class Node {

      friend class FullGraphBase;

    protected:

      int _id;

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

    public:

      Node() {}

      Node (Invalid) { _id = -1; }

      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 Edge {

      friend class FullGraphBase;

      friend class Arc;

    protected:

      int _id;

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

    public:

      Edge() { }

      Edge (Invalid) { _id = -1; }

      bool operator==(const Edge edge) const {return _id == edge._id;}

      bool operator!=(const Edge edge) const {return _id != edge._id;}

      bool operator<(const Edge edge) const {return _id < edge._id;}

    };

    class Arc {

      friend class FullGraphBase;

    protected:

      int _id;

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

    public:

      Arc() { }

      Arc (Invalid) { _id = -1; }

      operator Edge() const { return Edge(_id != -1 ? (_id >> 1) : -1); }

      bool operator==(const Arc arc) const {return _id == arc._id;}

      bool operator!=(const Arc arc) const {return _id != arc._id;}

      bool operator<(const Arc arc) const {return _id < arc._id;}

    };

    static bool direction(Arc arc) {

      return (arc._id & 1) == 1;

    }

    static Arc direct(Edge edge, bool dir) {

      return Arc((edge._id << 1) | (dir ? 1 : 0));

    }

    void first(Node& node) const {

      node._id = _node_num - 1;

    }

    static void next(Node& node) {

      --node._id;

    }

    void first(Arc& arc) const {

      arc._id = (_edge_num << 1) - 1;

    }

    static void next(Arc& arc) {

      --arc._id;

    }

    void first(Edge& edge) const {

      edge._id = _edge_num - 1;

    }

    static void next(Edge& edge) {

      --edge._id;

    }

    void firstOut(Arc& arc, const Node& node) const {

      int s = node._id, t = _node_num - 1;

      if (s < t) {

        arc._id = (_eid(s, t) << 1) | 1;

      } else {

        --t;

        arc._id = (t != -1 ? (_eid(t, s) << 1) : -1);

      }

    }

    void nextOut(Arc& arc) const {

      int s, t;

      _stid(arc._id, s, t);

      --t;

      if (s < t) {

        arc._id = (_eid(s, t) << 1) | 1;

      } else {

        if (s == t) --t;

        arc._id = (t != -1 ? (_eid(t, s) << 1) : -1);

      }

    }

    void firstIn(Arc& arc, const Node& node) const {

      int s = _node_num - 1, t = node._id;

      if (s > t) {

        arc._id = (_eid(t, s) << 1);

      } else {

        --s;

        arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1);

      }

    }

    void nextIn(Arc& arc) const {

      int s, t;

      _stid(arc._id, s, t);

      --s;

      if (s > t) {

        arc._id = (_eid(t, s) << 1);

      } else {

        if (s == t) --s;

        arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1);

      }

    }

    void firstInc(Edge& edge, bool& dir, const Node& node) const {

      int u = node._id, v = _node_num - 1;

      if (u < v) {

        edge._id = _eid(u, v);

        dir = true;

      } else {

        --v;

        edge._id = (v != -1 ? _eid(v, u) : -1);

        dir = false;

      }

    }

    void nextInc(Edge& edge, bool& dir) const {

      int u, v;

      if (dir) {

        _uvid(edge._id, u, v);

        --v;

        if (u < v) {

          edge._id = _eid(u, v);

        } else {

          --v;

          edge._id = (v != -1 ? _eid(v, u) : -1);

          dir = false;

        }

      } else {

        _uvid(edge._id, v, u);

        --v;

        edge._id = (v != -1 ? _eid(v, u) : -1);

      }

    }

  };

  typedef GraphExtender<FullGraphBase> ExtendedFullGraphBase;

  /// \ingroup graphs

  ///

  /// \brief An undirected full graph class.

  ///

  /// This is a simple and fast undirected full graph

  /// implementation. From each node go edge to each other node,

  /// therefore the number of edges in the graph is \f$n(n-1)/2\f$.

  /// This graph type is completely static, so you can neither

  /// add nor delete either edges or nodes, and it needs constant

  /// space in memory.

  ///

  /// This class conforms to the \ref concepts::Graph "Graph" concept

  /// and it also has an important extra feature that its maps are

  /// real \ref concepts::ReferenceMap "reference map"s.

  ///

  /// The \c FullGraph and \c FullDigraph classes are very similar,

  /// but there are two differences. While the \c FullDigraph class

  /// conforms only to the \ref concepts::Digraph "Digraph" concept,

  /// this class conforms to the \ref concepts::Graph "Graph" concept,

  /// moreover \c FullGraph does not contain a loop arc for each

  /// node as \c FullDigraph does.

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

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

 *

 * Copyright (C) 2003-2008

 * 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 GRID_GRAPH_H

#define GRID_GRAPH_H

#include <lemon/core.h>

#include <lemon/bits/graph_extender.h>

#include <lemon/dim2.h>

#include <lemon/assert.h>

///\ingroup graphs

///\file

///\brief GridGraph class.

namespace lemon {

  class GridGraphBase {

  public:

    typedef GridGraphBase Graph;

    class Node;

    class Edge;

    class Arc;

  public:

    GridGraphBase() {}

  protected:

    void construct(int width, int height) {

       _width = width; _height = height;

      _node_num = width * height;

      _edge_num = 2 * _node_num - width - height;

      _edge_limit = _node_num - _width;

    }

  public:

    Node operator()(int i, int j) const {

      LEMON_DEBUG(0 <= i && i < _width &&

                  0 <= j  && j < _height, "Index out of range");

      return Node(i + j * _width);

    }

    int col(Node n) const {

      return n._id % _width;

    }

    int row(Node n) const {

      return n._id / _width;

    }

    dim2::Point<int> pos(Node n) const {

      return dim2::Point<int>(col(n), row(n));

    }

    int width() const {

      return _width;

    }

    int height() const {

      return _height;

    }

    typedef True NodeNumTag;

    typedef True ArcNumTag;

    int nodeNum() const { return _node_num; }

    int edgeNum() const { return _edge_num; }

    int arcNum() const { return 2 * _edge_num; }

    Node u(Edge edge) const {

      if (edge._id < _edge_limit) {

        return edge._id;

      } else {

        return (edge._id - _edge_limit) % (_width - 1) +

          (edge._id - _edge_limit) / (_width - 1) * _width;

      }

    }

    Node v(Edge edge) const {

      if (edge._id < _edge_limit) {

        return edge._id + _width;

      } else {

        return (edge._id - _edge_limit) % (_width - 1) +

          (edge._id - _edge_limit) / (_width - 1) * _width + 1;

      }

    }

    Node source(Arc arc) const {

      return (arc._id & 1) == 1 ? u(arc) : v(arc);

    }

    Node target(Arc arc) const {

      return (arc._id & 1) == 1 ? v(arc) : u(arc);

    }

    static int id(Node node) { return node._id; }

    static int id(Edge edge) { return edge._id; }

    static int id(Arc arc) { return arc._id; }

    int maxNodeId() const { return _node_num - 1; }

    int maxEdgeId() const { return _edge_num - 1; }

    int maxArcId() const { return 2 * _edge_num - 1; }

    static Node nodeFromId(int id) { return Node(id);}

    static Edge edgeFromId(int id) { return Edge(id);}

    static Arc arcFromId(int id) { return Arc(id);}

    typedef True FindEdgeTag;

    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {

      if (prev != INVALID) return INVALID;

      if (v._id > u._id) {

        if (v._id - u._id == _width)

          return Edge(u._id);

        if (v._id - u._id == 1 && u._id % _width < _width - 1) {

          return Edge(u._id / _width * (_width - 1) +

                      u._id % _width + _edge_limit);

        }

      } else {

        if (u._id - v._id == _width)

          return Edge(v._id);

        if (u._id - v._id == 1 && v._id % _width < _width - 1) {

          return Edge(v._id / _width * (_width - 1) +

                      v._id % _width + _edge_limit);

        }

      }

      return INVALID;

    }

    Arc findArc(Node u, Node v, Arc prev = INVALID) const {

      if (prev != INVALID) return INVALID;

      if (v._id > u._id) {

        if (v._id - u._id == _width)

          return Arc((u._id << 1) | 1);

        if (v._id - u._id == 1 && u._id % _width < _width - 1) {

          return Arc(((u._id / _width * (_width - 1) +

                       u._id % _width + _edge_limit) << 1) | 1);

        }

      } else {

        if (u._id - v._id == _width)

          return Arc(v._id << 1);

        if (u._id - v._id == 1 && v._id % _width < _width - 1) {

          return Arc((v._id / _width * (_width - 1) +

                       v._id % _width + _edge_limit) << 1);

        }

      }

      return INVALID;

    }

    class Node {

      friend class GridGraphBase;

    protected:

      int _id;

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

    public:

      Node() {}

      Node (Invalid) : _id(-1) {}

      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 Edge {

      friend class GridGraphBase;

      friend class Arc;

    protected:

      int _id;

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

    public:

      Edge() {}

      Edge (Invalid) : _id(-1) {}

      bool operator==(const Edge edge) const {return _id == edge._id;}

      bool operator!=(const Edge edge) const {return _id != edge._id;}

      bool operator<(const Edge edge) const {return _id < edge._id;}

    };

    class Arc {

      friend class GridGraphBase;

    protected:

      int _id;

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

    public:

      Arc() {}

      Arc (Invalid) : _id(-1) {}

      operator Edge() const { return _id != -1 ? Edge(_id >> 1) : INVALID; }

      bool operator==(const Arc arc) const {return _id == arc._id;}

      bool operator!=(const Arc arc) const {return _id != arc._id;}

      bool operator<(const Arc arc) const {return _id < arc._id;}

    };

    static bool direction(Arc arc) {

      return (arc._id & 1) == 1;

    }

    static Arc direct(Edge edge, bool dir) {

      return Arc((edge._id << 1) | (dir ? 1 : 0));

    }

    void first(Node& node) const {

      node._id = _node_num - 1;

    }

    static void next(Node& node) {

      --node._id;

    }

    void first(Edge& edge) const {

      edge._id = _edge_num - 1;

    }

    static void next(Edge& edge) {

      --edge._id;

    }

    void first(Arc& arc) const {

      arc._id = 2 * _edge_num - 1;

    }

    static void next(Arc& arc) {

      --arc._id;

    }

    void firstOut(Arc& arc, const Node& node) const {

      if (node._id % _width < _width - 1) {

        arc._id = (_edge_limit + node._id % _width +

                   (node._id / _width) * (_width - 1)) << 1 | 1;

        return;

      }

      if (node._id < _node_num - _width) {

        arc._id = node._id << 1 | 1;

        return;

      }

      if (node._id % _width > 0) {

        arc._id = (_edge_limit + node._id % _width +

                   (node._id / _width) * (_width - 1) - 1) << 1;

        return;

      }

      if (node._id >= _width) {

        arc._id = (node._id - _width) << 1;

        return;

      }

      arc._id = -1;

    }

    void nextOut(Arc& arc) const {

      int nid = arc._id >> 1;

      if ((arc._id & 1) == 1) {

        if (nid >= _edge_limit) {

          nid = (nid - _edge_limit) % (_width - 1) +

            (nid - _edge_limit) / (_width - 1) * _width;

          if (nid < _node_num - _width) {

            arc._id = nid << 1 | 1;

            return;

          }

        }

        if (nid % _width > 0) {

          arc._id = (_edge_limit + nid % _width +

                     (nid / _width) * (_width - 1) - 1) << 1;

          return;

        }

        if (nid >= _width) {

          arc._id = (nid - _width) << 1;

          return;

        }

      } else {

        if (nid >= _edge_limit) {

          nid = (nid - _edge_limit) % (_width - 1) +

            (nid - _edge_limit) / (_width - 1) * _width + 1;

          if (nid >= _width) {

            arc._id = (nid - _width) << 1;

            return;

          }

        }

      }

      arc._id = -1;

    }

    void firstIn(Arc& arc, const Node& node) const {

      if (node._id % _width < _width - 1) {

        arc._id = (_edge_limit + node._id % _width +

                   (node._id / _width) * (_width - 1)) << 1;

        return;

      }

      if (node._id < _node_num - _width) {

        arc._id = node._id << 1;

        return;

      }

      if (node._id % _width > 0) {

        arc._id = (_edge_limit + node._id % _width +

                   (node._id / _width) * (_width - 1) - 1) << 1 | 1;

        return;

      }

      if (node._id >= _width) {

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

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

 *

 * Copyright (C) 2003-2008

 * 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_SMART_GRAPH_H

#define LEMON_SMART_GRAPH_H

///\ingroup graphs

///\file

///\brief SmartDigraph and SmartGraph classes.

#include <vector>

#include <lemon/core.h>

#include <lemon/error.h>

#include <lemon/bits/graph_extender.h>

namespace lemon {

  class SmartDigraph;

  ///Base of SmartDigraph

  ///Base of SmartDigraph

  ///

  class SmartDigraphBase {

  protected:

    struct NodeT

    {

      int first_in, first_out;

      NodeT() {}

    };

    struct ArcT

    {

      int target, source, next_in, next_out;

      ArcT() {}

    };

    std::vector<NodeT> nodes;

    std::vector<ArcT> arcs;

  public:

    typedef SmartDigraphBase Graph;

    class Node;

    class Arc;

  public:

    SmartDigraphBase() : nodes(), arcs() { }

    SmartDigraphBase(const SmartDigraphBase &_g)

      : nodes(_g.nodes), arcs(_g.arcs) { }

    typedef True NodeNumTag;

    int nodeNum() const { return nodes.size(); }

    int arcNum() const { return arcs.size(); }

    int maxNodeId() const { return nodes.size()-1; }

    int maxArcId() const { return arcs.size()-1; }

    Node addNode() {

      int n = nodes.size();

      nodes.push_back(NodeT());

      nodes[n].first_in = -1;

      nodes[n].first_out = -1;

      return Node(n);

    }