RhodeCode

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

 *

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

 *

 * Copyright (C) 2003-2009

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

#define LEMON_BITS_GRAPH_EXTENDER_H

#include <lemon/core.h>

#include <lemon/bits/map_extender.h>

#include <lemon/bits/default_map.h>

#include <lemon/concept_check.h>

#include <lemon/concepts/maps.h>

//\ingroup graphbits

//\file

//\brief Extenders for the graph types

namespace lemon {

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

    NodeNotifier& notifier(Node) const {

      return node_notifier;

    }

    ArcNotifier& notifier(Arc) const {

      return arc_notifier;

    }

    class NodeIt : public Node {

      const Digraph* _digraph;

    public:

      NodeIt() {}

      NodeIt(Invalid i) : Node(i) { }

      explicit NodeIt(const Digraph& digraph) : _digraph(&digraph) {

        _digraph->first(static_cast<Node&>(*this));

      }

      NodeIt(const Digraph& digraph, const Node& node)

        : Node(node), _digraph(&digraph) {}

      NodeIt& operator++() {

        _digraph->next(*this);

        return *this;

      }

    };

    class ArcIt : public Arc {

      const Digraph* _digraph;

    public:

      ArcIt() { }

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

      explicit ArcIt(const Digraph& digraph) : _digraph(&digraph) {

        _digraph->first(static_cast<Arc&>(*this));

      }

      ArcIt(const Digraph& digraph, const Arc& arc) :

        Arc(arc), _digraph(&digraph) { }

      ArcIt& operator++() {

        _digraph->next(*this);

        return *this;

      }

    };

    class OutArcIt : public Arc {

      const Digraph* _digraph;

    public:

      OutArcIt() { }

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

      OutArcIt(const Digraph& digraph, const Node& node)

        : _digraph(&digraph) {

        _digraph->firstOut(*this, node);

      }

      OutArcIt(const Digraph& digraph, const Arc& arc)

        : Arc(arc), _digraph(&digraph) {}

      OutArcIt& operator++() {

        return *this;

      }

    };

    Node addNode() {

      Node node = Parent::addNode();

      notifier(Node()).add(node);

      return node;

    }

    Arc addArc(const Node& from, const Node& to) {

      Arc arc = Parent::addArc(from, to);

      notifier(Arc()).add(arc);

      return arc;

    }

    void clear() {

      notifier(Arc()).clear();

      notifier(Node()).clear();

      Parent::clear();

    }

    template <typename Digraph, typename NodeRefMap, typename ArcRefMap>

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

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

      notifier(Node()).build();

      notifier(Arc()).build();

    }

    void erase(const Node& node) {

      Arc arc;

      Parent::firstOut(arc, node);

      while (arc != INVALID ) {

        erase(arc);

        Parent::firstOut(arc, node);

      }

      Parent::firstIn(arc, node);

      while (arc != INVALID ) {

        erase(arc);

        Parent::firstIn(arc, node);

      }

      notifier(Node()).erase(node);

      Parent::erase(node);

    }

    void erase(const Arc& arc) {

      notifier(Arc()).erase(arc);

      Parent::erase(arc);

    }

    DigraphExtender() {

      node_notifier.setContainer(*this);

      arc_notifier.setContainer(*this);

    }

    ~DigraphExtender() {

      arc_notifier.clear();

      node_notifier.clear();

    }

  };

  // \ingroup _graphbits

  //

  // \brief Extender for the Graphs

  template <typename Base>

  class GraphExtender : public Base {

    typedef Base Parent;

  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;

    typedef AlterationNotifier<GraphExtender, Arc> ArcNotifier;

    typedef AlterationNotifier<GraphExtender, Edge> EdgeNotifier;

  protected:

    mutable NodeNotifier node_notifier;

    mutable ArcNotifier arc_notifier;

    mutable EdgeNotifier edge_notifier;

  public:

    NodeNotifier& notifier(Node) const {

      return node_notifier;

    }

    ArcNotifier& notifier(Arc) const {

      return arc_notifier;

    }

    EdgeNotifier& notifier(Edge) const {

      return edge_notifier;

    }

    class NodeIt : public Node {

      const Graph* _graph;

    public:

      NodeIt() {}

      NodeIt(Invalid i) : Node(i) { }

      explicit NodeIt(const Graph& graph) : _graph(&graph) {

        _graph->first(static_cast<Node&>(*this));

      }

      NodeIt(const Graph& graph, const Node& node)

        : Node(node), _graph(&graph) {}

      NodeIt& operator++() {

        _graph->next(*this);

        return *this;

      }

    };

    class ArcIt : public Arc {

      const Graph* _graph;

    public:

      ArcIt() { }

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

      explicit ArcIt(const Graph& graph) : _graph(&graph) {

        _graph->first(static_cast<Arc&>(*this));

      }

      ArcIt(const Graph& graph, const Arc& arc) :

        Arc(arc), _graph(&graph) { }

      ArcIt& operator++() {

        _graph->next(*this);

        return *this;

      }

    };

    void erase(const Edge& e) {

      return Parent::erase(e);

    }

  };

  template <typename GR>

  class SmartArcSetBase {

  public:

    typedef typename GR::Node Node;

    typedef typename GR::NodeIt NodeIt;

  protected:

    struct NodeT {

      int first_out, first_in;

      NodeT() : first_out(-1), first_in(-1) {}

    };

    typedef typename ItemSetTraits<GR, Node>::

    template Map<NodeT>::Type NodesImplBase;

    NodesImplBase* _nodes;

    struct ArcT {

      Node source, target;

      int next_out, next_in;

      ArcT() {}

    };

    std::vector<ArcT> arcs;

    const GR* _graph;

    void initalize(const GR& graph, NodesImplBase& nodes) {

      _graph = &graph;

      _nodes = &nodes;

    }

  public:

    class Arc {

      friend class SmartArcSetBase<GR>;

    protected:

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

      int id;

    public:

      Arc() {}

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

    };

    SmartArcSetBase() {}

    Node addNode() {

      LEMON_ASSERT(false,

        "This graph structure does not support node insertion");

      return INVALID; // avoid warning

    }

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

      int n = arcs.size();

      arcs.push_back(ArcT());

      arcs[n].next_in = (*_nodes)[v].first_in;

      (*_nodes)[v].first_in = n;

      arcs[n].next_out = (*_nodes)[u].first_out;

      (*_nodes)[u].first_out = n;

      arcs[n].source = u;

      arcs[n].target = v;

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

    int maxNodeId() const { return _graph->maxNodeId(); };

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

    Node source(const Arc& arc) const { return arcs[arc.id].source;}

    Node target(const Arc& arc) const { return arcs[arc.id].target;}

    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;

    NodeNotifier& notifier(Node) const {

      return _graph->notifier(Node());

    }

    template <typename V>

    class NodeMap : public GR::template NodeMap<V> {

      typedef typename GR::template NodeMap<V> Parent;

    public:

      explicit NodeMap(const SmartArcSetBase<GR>& arcset)

        : Parent(*arcset._graph) { }

      NodeMap(const SmartArcSetBase<GR>& arcset, const V& value)

        : Parent(*arcset._graph, value) { }

      NodeMap& operator=(const NodeMap& cmap) {

        return operator=<NodeMap>(cmap);

      }

      template <typename CMap>

      NodeMap& operator=(const CMap& cmap) {

        Parent::operator=(cmap);

        return *this;

      }

    };

  };

  /// \ingroup graphs

  ///

  /// \brief Digraph using a node set of another digraph or graph and

  /// an own arc set.

  ///

  /// This structure can be used to establish another directed graph

  /// over a node set of an existing one. This class uses the same

  /// Node type as the underlying graph, and each valid node of the

  /// original graph is valid in this arc set, therefore the node

  /// objects of the original graph can be used directly with this

  /// class. The node handling functions (id handling, observing, and

  /// iterators) works equivalently as in the original graph.

  ///

  /// \param GR The type of the graph which shares its node set with

  /// this class. Its interface must conform to the

  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"

  /// concept.

  ///

  /// This implementation is slightly faster than the \c ListArcSet,

  /// because it uses continuous storage for arcs and it uses just

  /// single-linked lists for enumerate outgoing and incoming

  /// arcs. Therefore the arcs cannot be erased from the arc sets.

  ///

  /// \warning If a node is erased from the underlying graph and this

  /// node is the source or target of one arc in the arc set, then

  /// the arc set is invalidated, and it cannot be used anymore. The

  /// validity can be checked with the \c valid() member function.

  ///

  /// This class fully conforms to the \ref concepts::Digraph

  /// "Digraph" concept.

  template <typename GR>

  class SmartArcSet : public ArcSetExtender<SmartArcSetBase<GR> > {

    typedef ArcSetExtender<SmartArcSetBase<GR> > Parent;

    template Map<NodeT>::Type NodesImplBase;

    NodesImplBase* _nodes;

    struct ArcT {

      Node target;

      int next_out;

      ArcT() {}

    };

    std::vector<ArcT> arcs;

    const GR* _graph;

    void initalize(const GR& graph, NodesImplBase& nodes) {

      _graph = &graph;

      _nodes = &nodes;

    }

  public:

    class Edge {

      friend class SmartEdgeSetBase;

    protected:

      int id;

      explicit Edge(int _id) { id = _id;}

    public:

      Edge() {}

      Edge (Invalid) { id = -1; }

      bool operator==(const Edge& arc) const {return id == arc.id;}

      bool operator!=(const Edge& arc) const {return id != arc.id;}

      bool operator<(const Edge& arc) const {return id < arc.id;}

    };

    class Arc {

      friend class SmartEdgeSetBase;

    protected:

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

      int id;

    public:

      operator Edge() const { return edgeFromId(id / 2); }

      Arc() {}

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

    };

    SmartEdgeSetBase() {}

    Node addNode() {

      LEMON_ASSERT(false,

        "This graph structure does not support node insertion");

      return INVALID; // avoid warning

    }

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

      int n = arcs.size();

      arcs.push_back(ArcT());

      arcs.push_back(ArcT());

      arcs[n].target = u;

      arcs[n | 1].target = v;

      arcs[n].next_out = (*_nodes)[v].first_out;

      (*_nodes)[v].first_out = n;

      arcs[n | 1].next_out = (*_nodes)[u].first_out;

      (*_nodes)[u].first_out = (n | 1);

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

        arc.id = de / 2;

        dir = ((de & 1) == 1);

      } else {

        arc.id = -1;

        dir = true;

      }

    }

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

      int de = (arcs[(arc.id * 2) | (dir ? 1 : 0)].next_out);

      if (de != -1 ) {

        arc.id = de / 2;

        dir = ((de & 1) == 1);

      } else {

        arc.id = -1;

        dir = true;

      }

    }

    static bool direction(Arc arc) {

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

    }

    static Arc direct(Edge edge, bool dir) {

      return Arc(edge.id * 2 + (dir ? 1 : 0));

    }

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

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

    static int id(Edge arc) { return arc.id; }

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

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

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

    int maxNodeId() const { return _graph->maxNodeId(); };

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

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

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

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

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

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

    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;

    NodeNotifier& notifier(Node) const {

      return _graph->notifier(Node());

    }

    template <typename V>

    class NodeMap : public GR::template NodeMap<V> {

      typedef typename GR::template NodeMap<V> Parent;

    public:

      explicit NodeMap(const SmartEdgeSetBase<GR>& arcset)

        : Parent(*arcset._graph) { }

      NodeMap(const SmartEdgeSetBase<GR>& arcset, const V& value)

        : Parent(*arcset._graph, value) { }

      NodeMap& operator=(const NodeMap& cmap) {

        return operator=<NodeMap>(cmap);

      }

      template <typename CMap>

      NodeMap& operator=(const CMap& cmap) {

        Parent::operator=(cmap);

        return *this;

      }

    };

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

 *

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

 *

 * Copyright (C) 2003-2009

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

#define LEMON_FULL_GRAPH_H

#include <lemon/core.h>

#include <lemon/bits/graph_extender.h>

///\ingroup graphs

///\file

///\brief FullGraph and FullDigraph classes.

namespace lemon {

  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;

    }

    class Node {

      friend class FullDigraphBase;

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

      friend class FullDigraphBase;

    protected:

      int _id;  // _node_num * source + target;

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

    public:

      Arc() { }

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

    };

    void first(Node& node) const {

      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.

  ///

  /// This class fully conforms to the \ref concepts::Digraph

  /// "Digraph concept".

  ///

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

    typedef ExtendedFullDigraphBase Parent;

  public:

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

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

  protected:

    int _node_num;

    int _edge_num;

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

    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;

    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 {