RhodeCode

    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

          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

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

    }

  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);

    }

      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() {}

      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;

    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

      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.

    ///