RhodeCode

  // \ingroup graphbits

  //

  // \brief Extender for the digraph implementations

  template <typename Base>

  class DigraphExtender : public Base {

    typedef Base Parent;

  public:

    typedef DigraphExtender Digraph;

    // Base extensions

    typedef typename Parent::Node Node;

    typedef typename Parent::Arc Arc;

    int maxId(Node) const {

      return Parent::maxNodeId();

    }

    int maxId(Arc) const {

      return Parent::maxArcId();

    }

      return Parent::nodeFromId(id);

    }

      return Parent::arcFromId(id);

    }

    Node oppositeNode(const Node &node, const Arc &arc) const {

      if (node == Parent::source(arc))

        return Parent::target(arc);

      else if(node == Parent::target(arc))

        return Parent::source(arc);

      else

        return INVALID;

    }

    // Alterable extension

    typedef AlterationNotifier<DigraphExtender, Node> NodeNotifier;

    typedef AlterationNotifier<DigraphExtender, Arc> ArcNotifier;

  protected:

    mutable NodeNotifier node_notifier;

    mutable ArcNotifier arc_notifier;

  public:

  public:

    typedef GraphExtender Graph;

    typedef True UndirectedTag;

    typedef typename Parent::Node Node;

    typedef typename Parent::Arc Arc;

    typedef typename Parent::Edge Edge;

    // Graph extension

    int maxId(Node) const {

      return Parent::maxNodeId();

    }

    int maxId(Arc) const {

      return Parent::maxArcId();

    }

    int maxId(Edge) const {

      return Parent::maxEdgeId();

    }

      return Parent::nodeFromId(id);

    }

      return Parent::arcFromId(id);

    }

      return Parent::edgeFromId(id);

    }

    Node oppositeNode(const Node &n, const Edge &e) const {

      if( n == Parent::u(e))

        return Parent::v(e);

      else if( n == Parent::v(e))

        return Parent::u(e);

      else

        return INVALID;

    }

    Arc oppositeArc(const Arc &arc) const {

      return Parent::direct(arc, !Parent::direction(arc));

    }

    using Parent::direct;

    Arc direct(const Edge &edge, const Node &node) const {

      return Parent::direct(edge, Parent::u(edge) == node);

    }

    // Alterable extension

    typedef AlterationNotifier<GraphExtender, Node> NodeNotifier;

      return Arc(n);

    }

    void clear() {

      Node node;

      for (first(node); node != INVALID; next(node)) {

        (*_nodes)[node].first_in = -1;

        (*_nodes)[node].first_out = -1;

      }

      arcs.clear();

    }

    void first(Node& node) const {

      _graph->first(node);

    }

    void next(Node& node) const {

      _graph->next(node);

    }

    void first(Arc& arc) const {

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

    }

      --arc.id;

    }

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

      arc.id = (*_nodes)[node].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].first_in;

    }

    void nextIn(Arc& arc) const {

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

    }

    int id(const Node& node) const { return _graph->id(node); }

    int id(const Arc& arc) const { return arc.id; }

    Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }

    Arc arcFromId(int ix) const { return Arc(ix); }

      return Edge(n / 2);

    }

    void clear() {

      Node node;

      for (first(node); node != INVALID; next(node)) {

        (*_nodes)[node].first_out = -1;

      }

      arcs.clear();

    }

    void first(Node& node) const {

      _graph->first(node);

    }

    void next(Node& node) const {

      _graph->next(node);

    }

    void first(Arc& arc) const {

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

    }

      --arc.id;

    }

    void first(Edge& arc) const {

      arc.id = arcs.size() / 2 - 1;

    }

      --arc.id;

    }

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

      arc.id = (*_nodes)[node].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].first_out) ^ 1);

      if (arc.id == -2) arc.id = -1;

    }

    void nextIn(Arc& arc) const {

      arc.id = ((arcs[arc.id ^ 1].next_out) ^ 1);

      if (arc.id == -2) arc.id = -1;

    }

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

      int de = (*_nodes)[node].first_out;

      if (de != -1 ) {

  class FullDigraphBase {

  public:

    typedef FullDigraphBase Digraph;

    class Node;

    class Arc;

  protected:

    int _node_num;

    int _arc_num;

    FullDigraphBase() {}

    void construct(int n) { _node_num = n; _arc_num = n * n; }

  public:

    typedef True NodeNumTag;

    typedef True ArcNumTag;

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

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

      return Arc(s._id * _node_num + t._id);

    }

    int nodeNum() const { return _node_num; }

    int arcNum() const { return _arc_num; }

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

    int maxArcId() const { return _arc_num - 1; }

    Node source(Arc arc) const { return arc._id / _node_num; }

    Node target(Arc arc) const { return arc._id % _node_num; }

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

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

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

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

    typedef True FindArcTag;

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

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

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

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

  public:

    typedef FullGraphBase Graph;

    class Node;

    class Arc;

    class Edge;

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

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

    typedef True EdgeNumTag;

    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.

    ///

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

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

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

    /// \sa operator()

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

    ///

    /// Returns the arc connecting the given nodes.

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

      return Parent::arc(s, t);

    }

    /// \brief Returns the edge connects the given nodes.

    ///

    /// Returns the edge connects the given nodes.

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

      return Parent::edge(u, v);

    }

    /// \brief Number of nodes.

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

    /// \brief Number of arcs.

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

    /// \brief Number of edges.

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

  };

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

    }

    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;

    }

      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.

  ///

    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.

      return Parent::index(node);

    }

    /// \brief Gives back a node by its index.

    ///

    /// Gives back a node by its index.

    Node operator()(int ix) const {

      return Parent::operator()(ix);

    }

    /// \brief Number of nodes.

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

    /// \brief Number of edges.

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

    /// \brief Number of arcs.

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

    /// \brief Linear combination map.

    ///

    /// This map makes possible to give back a linear combination

    /// for each node. It works like the \c std::accumulate function,

    /// so it accumulates the \c bf binary function with the \c fv first

    /// value. The map accumulates only on that positions (dimensions)

    /// where the index of the node is one. The values that have to be

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

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

    int maxEdgeId() const { return arcs.size() / 2 - 1; }

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

    Node source(Arc e) const { return Node(arcs[e._id ^ 1].target); }

    Node target(Arc e) const { return Node(arcs[e._id].target); }

    Node u(Edge e) const { return Node(arcs[2 * e._id].target); }

    Node v(Edge e) const { return Node(arcs[2 * e._id + 1].target); }

    static bool direction(Arc e) {

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

    }

    static Arc direct(Edge e, bool d) {

      return Arc(e._id * 2 + (d ? 1 : 0));

    }

    void first(Node& node) const {

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

    }

      --node._id;

    }

    void first(Arc& arc) const {

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

    }

      --arc._id;

    }

    void first(Edge& arc) const {

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

    }

      --arc._id;

    }

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

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

    }

    void nextOut(Arc &arc) const {

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

    }

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

      arc._id = ((nodes[v._id].first_out) ^ 1);

      if (arc._id == -2) arc._id = -1;

    }

    void nextIn(Arc &arc) const {

      arc._id = ((arcs[arc._id ^ 1].next_out) ^ 1);

      if (arc._id == -2) arc._id = -1;

    }

    void firstInc(Edge &arc, bool& d, const Node& v) const {

      int de = nodes[v._id].first_out;

      if (de != -1) {

        arc._id = de / 2;

        d = ((de & 1) == 1);

      Arc (Invalid) : id(-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; }

    };

    Node source(const Arc& e) const { return Node(arc_source[e.id]); }

    Node target(const Arc& e) const { return Node(arc_target[e.id]); }

    void first(Node& n) const { n.id = node_num - 1; }

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

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

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

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

      e.id = node_first_out[n.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 firstIn(Arc& e, const Node& n) const { e.id = node_first_in[n.id]; }

    void nextIn(Arc& e) const { e.id = arc_next_in[e.id]; }

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

    int maxArcId() const { return arc_num - 1; }

    typedef True NodeNumTag;

    typedef True ArcNumTag;

    int nodeNum() const { return node_num; }

    int arcNum() const { return arc_num; }

  private:

    template <typename Digraph, typename NodeRefMap>

    class ArcLess {

    public:

      typedef typename Digraph::Arc Arc;

      ArcLess(const Digraph &_graph, const NodeRefMap& _nodeRef) 

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

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

	return nodeRef[digraph.target(left)] < nodeRef[digraph.target(right)];

      }

    private:

      const Digraph& digraph;

      const NodeRefMap& nodeRef;

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

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

  ///

  /// This type fully conforms to the \ref concepts::Digraph "Digraph concept".

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

  /// only in the concept class.

  ///

  /// \sa concepts::Digraph

  class StaticDigraph : public ExtendedStaticDigraphBase {

  public:

    typedef ExtendedStaticDigraphBase Parent;

  public:

    /// \brief Constructor

    ///

    /// Default constructor.

    StaticDigraph() : Parent() {}

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

    ///

    /// This function returns the node with the given index.

    /// \sa index()

    /// \brief The arc with the given index.

    ///

    /// This function returns the arc with the given index.

    /// \sa index()

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

    ///

    /// This function returns the index of the the given node.

    /// \sa node()

    /// \brief The index of the given arc.

    ///

    /// This function returns the index of the the given arc.

    /// \sa arc()

    /// \brief Number of nodes.

    ///

    /// This function returns the number of nodes.

    int nodeNum() const { return node_num; }

    /// \brief Number of arcs.

    ///

    /// This function returns the number of arcs.

    int arcNum() const { return arc_num; }

    /// \brief Build the digraph copying another digraph.

    ///

    /// This function builds the digraph copying another digraph of any

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

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

    ///

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

    /// structure using \ref DigraphCopy.

    /// 

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

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

    /// \c StaticDigraph::Node.