RhodeCode

      node._id = _node_num - 1;

    }

    static void next(Node& node) {

      --node._id;

    }

    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.

  ///

  ///

  /// 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

    }

    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.

  ///

  ///

  /// 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.

  ///

  /// \sa FullDigraph

  class FullGraph : public ExtendedFullGraphBase {

  public:

    typedef ExtendedFullGraphBase Parent;

    /// \brief Constructor

    FullGraph() { construct(0); }

    /// \brief Constructor

    ///

    /// Constructor.

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

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

    /// \brief Resizes the graph

    ///

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

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

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

    void resize(int n) {

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

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

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

      construct(n);

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

      Parent::notifier(Edge()).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

    /// graph 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.

    ///

    Arc down(Node n) const {

      if (n._id >= _width) {

        return Arc((n._id - _width) << 1);

      } else {

        return INVALID;

      }

    }

  private:

    int _width, _height;

    int _node_num, _edge_num;

    int _edge_limit;

  };

  typedef GraphExtender<GridGraphBase> ExtendedGridGraphBase;

  /// \ingroup graphs

  ///

  /// \brief Grid graph class

  ///

  /// This class implements a special graph type. The nodes of the

  /// graph can be indexed by two integer \c (i,j) value where \c i is

  /// in the \c [0..width()-1] range and j is in the \c

  /// [0..height()-1] range.  Two nodes are connected in the graph if

  /// the indexes differ exactly on one position and exactly one is

  /// the difference. The nodes of the graph can be indexed by position

  /// with the \c operator()() function. The positions of the nodes can be

  /// get with \c pos(), \c col() and \c row() members. The outgoing

  /// arcs can be retrieved with the \c right(), \c up(), \c left()

  /// and \c down() functions, where the bottom-left corner is the

  /// origin.

  ///

  /// \image html grid_graph.png

  /// \image latex grid_graph.eps "Grid graph" width=\textwidth

  ///

  /// A short example about the basic usage:

  ///\code

  /// GridGraph graph(rows, cols);

  /// GridGraph::NodeMap<int> val(graph);

  /// for (int i = 0; i < graph.width(); ++i) {

  ///   for (int j = 0; j < graph.height(); ++j) {

  ///     val[graph(i, j)] = i + j;

  ///   }

  /// }

  ///\endcode

  ///

  /// This graph type fully conforms to the \ref concepts::Graph

  class GridGraph : public ExtendedGridGraphBase {

  public:

    typedef ExtendedGridGraphBase Parent;

    /// \brief Map to get the indices of the nodes as dim2::Point<int>.

    ///

    /// Map to get the indices of the nodes as dim2::Point<int>.

    class IndexMap {

    public:

      /// \brief The key type of the map

      typedef GridGraph::Node Key;

      /// \brief The value type of the map

      typedef dim2::Point<int> Value;

      /// \brief Constructor

      ///

      /// Constructor

      IndexMap(const GridGraph& graph) : _graph(graph) {}

      /// \brief The subscript operator

      ///

      /// The subscript operator.

      Value operator[](Key key) const {

        return _graph.pos(key);

      }

    private:

      const GridGraph& _graph;

    };

    /// \brief Map to get the column of the nodes.

    ///

    /// Map to get the column of the nodes.

    class ColMap {

    public:

      /// \brief The key type of the map

      typedef GridGraph::Node Key;

      /// \brief The value type of the map

      typedef int Value;

      /// \brief Constructor

      ///

      /// Constructor

      ColMap(const GridGraph& graph) : _graph(graph) {}

      /// \brief The subscript operator

      ///

    }

    int dimension() const {

      return _dim;

    }

    bool projection(Node node, int n) const {

      return static_cast<bool>(node._id & (1 << n));

    }

    int dimension(Edge edge) const {

      return edge._id >> (_dim-1);

    }

    int dimension(Arc arc) const {

      return arc._id >> _dim;

    }

    int index(Node node) const {

      return node._id;

    }

    Node operator()(int ix) const {

      return Node(ix);

    }

  private:

    int _dim;

    int _node_num, _edge_num;

  };

  typedef GraphExtender<HypercubeGraphBase> ExtendedHypercubeGraphBase;

  /// \ingroup graphs

  ///

  /// \brief Hypercube graph class

  ///

  /// This class implements a special graph type. The nodes of the graph

  /// are indiced with integers with at most \c dim binary digits.

  /// Two nodes are connected in the graph if and only if their indices

  /// differ only on one position in the binary form.

  ///

  /// \note The type of the indices is chosen to \c int for efficiency

  /// reasons. Thus the maximum dimension of this implementation is 26

  /// (assuming that the size of \c int is 32 bit).

  ///

  /// This graph type fully conforms to the \ref concepts::Graph

  class HypercubeGraph : public ExtendedHypercubeGraphBase {

  public:

    typedef ExtendedHypercubeGraphBase Parent;

    /// \brief Constructs a hypercube graph with \c dim dimensions.

    ///

    /// Constructs a hypercube graph with \c dim dimensions.

    HypercubeGraph(int dim) { construct(dim); }

    /// \brief The number of dimensions.

    ///

    /// Gives back the number of dimensions.

    int dimension() const {

      return Parent::dimension();

    }

    /// \brief Returns \c true if the n'th bit of the node is one.

    ///

    /// Returns \c true if the n'th bit of the node is one.

    bool projection(Node node, int n) const {

      return Parent::projection(node, n);

    }

    /// \brief The dimension id of an edge.

    ///

    /// Gives back the dimension id of the given edge.

    /// It is in the [0..dim-1] range.

    int dimension(Edge edge) const {

      return Parent::dimension(edge);

    }

    /// \brief The dimension id of an arc.

    ///

    /// Gives back the dimension id of the given arc.

    /// It is in the [0..dim-1] range.

    int dimension(Arc arc) const {

      return Parent::dimension(arc);

    }

    /// \brief The index of a node.

    ///

    /// Gives back the index of the given node.

    /// The lower bits of the integer describes the node.

    int index(Node node) const {

      return Parent::index(node);

    }

    {

      if(arcs[e.id].next_in != -1)

        arcs[arcs[e.id].next_in].prev_in = arcs[e.id].prev_in;

      if(arcs[e.id].prev_in != -1)

        arcs[arcs[e.id].prev_in].next_in = arcs[e.id].next_in;

      else nodes[arcs[e.id].target].first_in = arcs[e.id].next_in;

      if (nodes[n.id].first_in != -1) {

        arcs[nodes[n.id].first_in].prev_in = e.id;

      }

      arcs[e.id].target = n.id;

      arcs[e.id].prev_in = -1;

      arcs[e.id].next_in = nodes[n.id].first_in;

      nodes[n.id].first_in = e.id;

    }

    void changeSource(Arc e, Node n)

    {

      if(arcs[e.id].next_out != -1)

        arcs[arcs[e.id].next_out].prev_out = arcs[e.id].prev_out;

      if(arcs[e.id].prev_out != -1)

        arcs[arcs[e.id].prev_out].next_out = arcs[e.id].next_out;

      else nodes[arcs[e.id].source].first_out = arcs[e.id].next_out;

      if (nodes[n.id].first_out != -1) {

        arcs[nodes[n.id].first_out].prev_out = e.id;

      }

      arcs[e.id].source = n.id;

      arcs[e.id].prev_out = -1;

      arcs[e.id].next_out = nodes[n.id].first_out;

      nodes[n.id].first_out = e.id;

    }

  };

  typedef DigraphExtender<ListDigraphBase> ExtendedListDigraphBase;

  /// \addtogroup graphs

  /// @{

  ///A general directed graph structure.

  ///\ref ListDigraph is a simple and fast <em>directed graph</em>

  ///implementation based on static linked lists that are stored in

  ///\c std::vector structures.

  ///

  ///It conforms to the \ref concepts::Digraph "Digraph concept" and it

  ///also provides several useful additional functionalities.

  ///Most of the member functions and nested classes are documented

  ///only in the concept class.

  ///

  ///\sa concepts::Digraph

  class ListDigraph : public ExtendedListDigraphBase {

  private:

    ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.

    ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.

    ///

    ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};

    ///\brief Assignment of ListDigraph to another one is \e not allowed.

    ///Use copyDigraph() instead.

    ///Assignment of ListDigraph to another one is \e not allowed.

    ///Use copyDigraph() instead.

    void operator=(const ListDigraph &) {}

  public:

    typedef ExtendedListDigraphBase Parent;

    /// Constructor

    /// Constructor.

    ///

    ListDigraph() {}

    ///Add a new node to the digraph.

    ///Add a new node to the digraph.

    ///\return The new node.

    Node addNode() { return Parent::addNode(); }

    ///Add a new arc to the digraph.

    ///Add a new arc to the digraph with source node \c s

    ///and target node \c t.

    ///\return The new arc.

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

      return Parent::addArc(s, t);

    }

    ///\brief Erase a node from the digraph.

    ///

    ///Erase a node from the digraph.

    ///

    void erase(const Node& n) { Parent::erase(n); }

    ///\brief Erase an arc from the digraph.

    ///

      }

      arcs[(2 * e.id) | 1].target = n.id;

      arcs[2 * e.id].prev_out = -1;

      arcs[2 * e.id].next_out = nodes[n.id].first_out;

      nodes[n.id].first_out = 2 * e.id;

    }

    void changeU(Edge e, Node n) {

      if(arcs[(2 * e.id) | 1].next_out != -1) {

        arcs[arcs[(2 * e.id) | 1].next_out].prev_out =

          arcs[(2 * e.id) | 1].prev_out;

      }

      if(arcs[(2 * e.id) | 1].prev_out != -1) {

        arcs[arcs[(2 * e.id) | 1].prev_out].next_out =

          arcs[(2 * e.id) | 1].next_out;

      } else {

        nodes[arcs[2 * e.id].target].first_out =

          arcs[(2 * e.id) | 1].next_out;

      }

      if (nodes[n.id].first_out != -1) {

        arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);

      }

      arcs[2 * e.id].target = n.id;

      arcs[(2 * e.id) | 1].prev_out = -1;

      arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out;

      nodes[n.id].first_out = ((2 * e.id) | 1);

    }

  };

  typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;

  /// \addtogroup graphs

  /// @{

  ///A general undirected graph structure.

  ///\ref ListGraph is a simple and fast <em>undirected graph</em>

  ///implementation based on static linked lists that are stored in

  ///\c std::vector structures.

  ///

  ///It conforms to the \ref concepts::Graph "Graph concept" and it

  ///also provides several useful additional functionalities.

  ///Most of the member functions and nested classes are documented

  ///only in the concept class.

  ///

  ///\sa concepts::Graph

  class ListGraph : public ExtendedListGraphBase {

  private:

    ///ListGraph is \e not copy constructible. Use copyGraph() instead.

    ///ListGraph is \e not copy constructible. Use copyGraph() instead.

    ///

    ListGraph(const ListGraph &) :ExtendedListGraphBase()  {};

    ///\brief Assignment of ListGraph to another one is \e not allowed.

    ///Use copyGraph() instead.

    ///Assignment of ListGraph to another one is \e not allowed.

    ///Use copyGraph() instead.

    void operator=(const ListGraph &) {}

  public:

    /// Constructor

    /// Constructor.

    ///

    ListGraph() {}

    typedef ExtendedListGraphBase Parent;

    typedef Parent::OutArcIt IncEdgeIt;

    /// \brief Add a new node to the graph.

    ///

    /// Add a new node to the graph.

    /// \return The new node.

    Node addNode() { return Parent::addNode(); }

    /// \brief Add a new edge to the graph.

    ///

    /// Add a new edge to the graph with source node \c s

    /// and target node \c t.

    /// \return The new edge.

    Edge addEdge(const Node& s, const Node& t) {

      return Parent::addEdge(s, t);

    }

    /// \brief Erase a node from the graph.

    ///

    /// Erase a node from the graph.

    ///

    void erase(const Node& n) { Parent::erase(n); }

    /// \brief Erase an edge from the graph.

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

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

    };

    void first(Node& node) const {

      node._id = nodes.size() - 1;

    }

    static void next(Node& node) {

      --node._id;

    }

    void first(Arc& arc) const {

      arc._id = arcs.size() - 1;

    }

    static void next(Arc& arc) {

      --arc._id;

    }

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

      arc._id = nodes[node._id].first_out;

    }

    void nextOut(Arc& arc) const {

      arc._id = arcs[arc._id].next_out;

    }

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

      arc._id = nodes[node._id].first_in;

    }

    void nextIn(Arc& arc) const {

      arc._id = arcs[arc._id].next_in;

    }

  };

  typedef DigraphExtender<SmartDigraphBase> ExtendedSmartDigraphBase;

  ///\ingroup graphs

  ///

  ///\brief A smart directed graph class.

  ///

  ///This is a simple and fast digraph implementation.

  ///It is also quite memory efficient, but at the price

  ///that <b> it does support only limited (only stack-like)

  ///node and arc deletions</b>.

  ///

  ///\sa concepts::Digraph.

  class SmartDigraph : public ExtendedSmartDigraphBase {

  public:

    typedef ExtendedSmartDigraphBase Parent;

  private:

    ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead.

    ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead.

    ///

    SmartDigraph(const SmartDigraph &) : ExtendedSmartDigraphBase() {};

    ///\brief Assignment of SmartDigraph to another one is \e not allowed.

    ///Use DigraphCopy() instead.

    ///Assignment of SmartDigraph to another one is \e not allowed.

    ///Use DigraphCopy() instead.

    void operator=(const SmartDigraph &) {}

  public:

    /// Constructor

    /// Constructor.

    ///

    SmartDigraph() {};

    ///Add a new node to the digraph.

    /// Add a new node to the digraph.

    /// \return The new node.

    Node addNode() { return Parent::addNode(); }

    ///Add a new arc to the digraph.

    ///Add a new arc to the digraph with source node \c s

    ///and target node \c t.

    ///\return The new arc.

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

      return Parent::addArc(s, t);

    }

    /// \brief Using this it is possible to avoid the superfluous memory

    /// allocation.

    /// Using this it is possible to avoid the superfluous memory

      return a._id >= 0 && a._id < static_cast<int>(arcs.size());

    }

    bool valid(Edge e) const {

      return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size());

    }

    Node addNode() {

      int n = nodes.size();

      nodes.push_back(NodeT());

      nodes[n].first_out = -1;

      return Node(n);

    }

    Edge addEdge(Node u, Node v) {

      int n = arcs.size();

      arcs.push_back(ArcT());

      arcs.push_back(ArcT());

      arcs[n].target = u._id;

      arcs[n | 1].target = v._id;

      arcs[n].next_out = nodes[v._id].first_out;

      nodes[v._id].first_out = n;

      arcs[n | 1].next_out = nodes[u._id].first_out;

      nodes[u._id].first_out = (n | 1);

      return Edge(n / 2);

    }

    void clear() {

      arcs.clear();

      nodes.clear();

    }

  };

  typedef GraphExtender<SmartGraphBase> ExtendedSmartGraphBase;

  /// \ingroup graphs

  ///

  /// \brief A smart undirected graph class.

  ///

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

  /// It is also quite memory efficient, but at the price

  /// that <b> it does support only limited (only stack-like)

  /// node and arc deletions</b>.

  ///

  /// \sa concepts::Graph.

  class SmartGraph : public ExtendedSmartGraphBase {

  private:

    ///SmartGraph is \e not copy constructible. Use GraphCopy() instead.

    ///SmartGraph is \e not copy constructible. Use GraphCopy() instead.

    ///

    SmartGraph(const SmartGraph &) : ExtendedSmartGraphBase() {};

    ///\brief Assignment of SmartGraph to another one is \e not allowed.

    ///Use GraphCopy() instead.

    ///Assignment of SmartGraph to another one is \e not allowed.

    ///Use GraphCopy() instead.

    void operator=(const SmartGraph &) {}

  public:

    typedef ExtendedSmartGraphBase Parent;

    /// Constructor

    /// Constructor.

    ///

    SmartGraph() {}

    ///Add a new node to the graph.

    /// Add a new node to the graph.

    /// \return The new node.

    Node addNode() { return Parent::addNode(); }

    ///Add a new edge to the graph.

    ///Add a new edge to the graph with node \c s

    ///and \c t.

    ///\return The new edge.

    Edge addEdge(const Node& s, const Node& t) {

      return Parent::addEdge(s, t);

    }

    /// \brief Node validity check

    ///

    /// This function gives back true if the given node is valid,

    /// ie. it is a real node of the graph.

    ///

    /// \warning A removed node (using Snapshot) could become valid again

    /// when new nodes are added to the graph.