RhodeCode

      }      

    }

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

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

    }

    void nextOut(Arc &e) const {

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

    }

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

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

    }

    void nextIn(Arc &e) const {

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

    }

    static int id(Node v) { return v.id; }

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

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

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

    Node addNode() {     

      int n;

      if(first_free_node==-1) {

	n = nodes.size();

	nodes.push_back(NodeT());

      } else {

	n = first_free_node;

	first_free_node = nodes[n].next;

      }

      nodes[n].next = first_node;

      if(first_node != -1) nodes[first_node].prev = n;

      first_node = n;

      nodes[n].prev = -1;

      nodes[n].first_in = nodes[n].first_out = -1;

      return Node(n);

    }

    Arc addArc(Node u, Node v) {

      int n;      

      }

      arcs[n].prev_in = arcs[n].prev_out = -1;

      nodes[u.id].first_out = nodes[v.id].first_in = n;

      return Arc(n);

    }

    void erase(const Node& node) {

      int n = node.id;

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

	nodes[nodes[n].next].prev = nodes[n].prev;

      }

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

	nodes[nodes[n].prev].next = nodes[n].next;

      } else {

	first_node = nodes[n].next;

      }

      nodes[n].next = first_free_node;

      first_free_node = n;

    }

    void erase(const Arc& arc) {

      int n = arc.id;

      if(arcs[n].next_in!=-1) {

	arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;

      }

      if(arcs[n].prev_in!=-1) {

	arcs[arcs[n].prev_in].next_in = arcs[n].next_in;

      } else {

	nodes[arcs[n].target].first_in = arcs[n].next_in;

      }

      if(arcs[n].next_out!=-1) {

	arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;

      } 

      if(arcs[n].prev_out!=-1) {

	arcs[arcs[n].prev_out].next_out = arcs[n].next_out;

      } else {

	nodes[arcs[n].source].first_out = arcs[n].next_out;

      }

      arcs[n].next_in = first_free_arc;

    }

    void clear() {

      arcs.clear();

      nodes.clear();

      first_node = first_free_node = first_free_arc = -1;

    }

  protected:

    void changeTarget(Arc e, Node n) 

    {

      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;

    }

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

    }

    /// Change the target of \c e to \c n

    /// Change the target of \c e to \c n

    ///

    ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing

    ///the changed arc remain valid. However <tt>InArcIt</tt>s are

    ///invalidated.

    ///

    ///\warning This functionality cannot be used together with the Snapshot

    ///feature.

    void changeTarget(Arc e, Node n) { 

      Parent::changeTarget(e,n); 

    }

    /// Change the source of \c e to \c n

    /// Change the source of \c e to \c n

    ///

    ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s referencing

    ///the changed arc remain valid. However <tt>OutArcIt</tt>s are

    ///invalidated.

    ///

    ///\warning This functionality cannot be used together with the Snapshot

    ///feature.

    void changeSource(Arc e, Node n) { 

      } else {

        e.id = -1;

        d = true;

      }

    }

    void nextInc(Edge &e, bool& d) const {

      int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);

      if (a != -1 ) {

        e.id = a / 2;

        d = ((a & 1) == 1);

      } else {

        e.id = -1;

        d = true;

      }

    }

    static int id(Node v) { return v.id; }

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

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

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

      int n;

      if(first_free_node==-1) {

	n = nodes.size();

	nodes.push_back(NodeT());

      } else {

	n = first_free_node;

	first_free_node = nodes[n].next;

      }

      nodes[n].next = first_node;

      if (first_node != -1) nodes[first_node].prev = n;

      first_node = n;

      nodes[n].prev = -1;

      nodes[n].first_out = -1;

      return Node(n);

    }

    Edge addEdge(Node u, Node v) {

      int n;      

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

	arcs[nodes[u.id].first_out].prev_out = (n | 1);

      }

      arcs[n | 1].prev_out = -1;      

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

      return Edge(n / 2);

    }

    void erase(const Node& node) {

      int n = node.id;

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

	nodes[nodes[n].next].prev = nodes[n].prev;

      }

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

	nodes[nodes[n].prev].next = nodes[n].next;

      } else {

	first_node = nodes[n].next;

      }

      nodes[n].next = first_free_node;

      first_free_node = n;

    }

    void erase(const Edge& edge) {

      int n = edge.id * 2;

      if (arcs[n].next_out != -1) {

	arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;

      } 

      if (arcs[n].prev_out != -1) {

	arcs[arcs[n].prev_out].next_out = arcs[n].next_out;

      } else {

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

      }

      if (arcs[n | 1].next_out != -1) {

	arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;

      } 

      if (arcs[n | 1].prev_out != -1) {

	arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;

      } else {

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

      }

      arcs[n].next_out = first_free_arc;

      first_free_arc = n;      

    }

    void clear() {

      arcs.clear();

      nodes.clear();

      first_node = first_free_node = first_free_arc = -1;

    }

  protected:

    void changeTarget(Edge e, Node n) {

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

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

      }

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

	arcs[arcs[2 * e.id].prev_out].next_out = 

          arcs[2 * e.id].next_out;

      } else {

        nodes[arcs[(2 * e.id) | 1].target].first_out = 

          arcs[2 * e.id].next_out;

      }

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

    /// 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 Change the source of \c e to \c n

    ///

    /// This function changes the source of \c e to \c n.

    ///

    ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s

    ///referencing the changed arc remain

    ///valid. However <tt>OutArcIt</tt>s are invalidated.

    ///

    ///\warning This functionality cannot be used together with the

    ///Snapshot feature.

    void changeSource(Edge e, Node n) { 

      Parent::changeSource(e,n); 

    }    

    /// \brief Change the target of \c e to \c n

    ///

    /// This function changes the target of \c e to \c n.

    ///

    /// \note The <tt>ArcIt</tt>s referencing the changed arc remain

    /// valid. However the other iterators may be invalidated.

    ///

    ///\warning This functionality cannot be used together with the

    ///Snapshot feature.

    void changeTarget(Edge e, Node n) { 

      Parent::changeTarget(e,n); 

      arcs.push_back(ArcT());

      arcs[n].source = u._id; 

      arcs[n].target = v._id;

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

      arcs[n].next_in = nodes[v._id].first_in;

      nodes[u._id].first_out = nodes[v._id].first_in = n;

      return Arc(n);

    }

    void clear() {

      arcs.clear();

      nodes.clear();

    }

    Node source(Arc a) const { return Node(arcs[a._id].source); }

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

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

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

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

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

    class Node {

      friend class SmartDigraphBase;

      friend class SmartDigraph;

    protected:

      int _id;

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

    public:

      Node() {}

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

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

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

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

    };

    class Arc {

      friend class SmartDigraphBase;

      friend class SmartDigraph;

    protected:

      int _id;

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

    public:

    }

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

    /// allocation.

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

    /// allocation: if you know that the digraph you want to build will

    /// be very large (e.g. it will contain millions of nodes and/or arcs)

    /// then it is worth reserving space for this amount before starting

    /// to build the digraph.

    /// \sa reserveArc

    void reserveNode(int n) { nodes.reserve(n); };

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

    /// allocation.

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

    /// allocation: if you know that the digraph you want to build will

    /// be very large (e.g. it will contain millions of nodes and/or arcs)

    /// then it is worth reserving space for this amount before starting

    /// to build the digraph.

    /// \sa reserveNode

    void reserveArc(int m) { arcs.reserve(m); };

    ///Clear the digraph.

    ///Erase all the nodes and arcs from the digraph.

    ///

    void clear() {

      Parent::clear();

    }

    ///Split a node.

    ///This function splits a node. First a new node is added to the digraph,

    ///then the source of each outgoing arc of \c n is moved to this new node.

    ///If \c connect is \c true (this is the default value), then a new arc

    ///from \c n to the newly created node is also added.

    ///\return The newly created node.

    ///

    ///\note The <tt>Arc</tt>s

    ///referencing a moved arc remain

    ///valid. However <tt>InArc</tt>'s and <tt>OutArc</tt>'s

    ///may be invalidated.

    ///\warning This functionality cannot be used together with the Snapshot

    ///feature.

    ///\todo It could be implemented in a bit faster way.

    Node split(Node n, bool connect = true)

      } else {

        arc._id = -1;

        d = true;

      }

    }

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

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

      if (de != -1) {

        arc._id = de / 2;

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

      } else {

        arc._id = -1;

        d = true;      

      }

    }

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

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

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

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

    }

    typedef ExtendedSmartGraphBase Parent;

    /// Constructor

    /// Constructor.

    ///

    SmartGraph() {}

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

    }

    ///Clear the graph.

    ///Erase all the nodes and edges from the graph.

    ///

    void clear() {

      Parent::clear();

    }

  public:

    class Snapshot;

  protected:

    void saveSnapshot(Snapshot &s)

    {

      s._graph = this;

      s.node_num = nodes.size();

      s.arc_num = arcs.size();

    }

    void restoreSnapshot(const Snapshot &s)

    {

      while(s.arc_num<arcs.size()) {

/* -*- C++ -*-

 *

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

 *

 */

#include <lemon/concepts/graph.h>

#include <lemon/list_graph.h>

#include <lemon/smart_graph.h>

// #include <lemon/full_graph.h>

// #include <lemon/grid_graph.h>

#include "test_tools.h"

using namespace lemon;

using namespace lemon::concepts;

void check_concepts() {

  { // checking digraph components

    checkConcept<BaseGraphComponent, BaseGraphComponent >();

    checkConcept<IDableGraphComponent<>, 

      IDableGraphComponent<> >();

    checkConcept<IterableGraphComponent<>, 

      IterableGraphComponent<> >();

    checkConcept<MappableGraphComponent<>, 

      MappableGraphComponent<> >();

  }

  {

    checkConcept<Graph, ListGraph>();    

    ++nn;

  }

  check(nn == n, "Wrong node number.");

  //  check(countNodes(g) == n, "Wrong node number.");

  int ee = 0;

  for (typename Graph::ArcIt it(g); it != INVALID; ++it) {

    ++ee;

  }

  check(ee == 2*e, "Wrong arc number.");

  //  check(countArcs(g) == 2*e, "Wrong arc number.");

  int uee = 0;

  for (typename Graph::EdgeIt it(g); it != INVALID; ++it) {

    ++uee;

  }

  check(uee == e, "Wrong edge number.");

  //  check(countEdges(g) == e, "Wrong edge number.");

}

template <typename Graph>

  Graph g;

  check_item_counts(g,0,0);

  Node

    n1 = g.addNode(),

    n2 = g.addNode(),

    n3 = g.addNode();

  Edge

    e1 = g.addEdge(n1, n2),

    e2 = g.addEdge(n2, n3);

  check_item_counts(g,3,2);

}

// void checkGridGraph(const GridGraph& g, int w, int h) {

//   check(g.width() == w, "Wrong width");

//   check(g.height() == h, "Wrong height");

//   for (int i = 0; i < w; ++i) {

//     for (int j = 0; j < h; ++j) {

//       check(g.col(g(i, j)) == i, "Wrong col");

//       check(g.row(g(i, j)) == j, "Wrong row");

//     }

//   }

//   for (int i = 0; i < w; ++i) {

//     for (int j = 0; j < h - 1; ++j) {

//       check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down");

//       check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down");

//     }

//     check(g.down(g(i, h - 1)) == INVALID, "Wrong down");

//   }

//   for (int i = 0; i < w; ++i) {

//     for (int j = 1; j < h; ++j) {

//       check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up");

//       check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up");

//     }

//     check(g.up(g(i, 0)) == INVALID, "Wrong up");

//   }

//   for (int j = 0; j < h; ++j) {

//     for (int i = 0; i < w - 1; ++i) {

//       check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right");

//       check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right");      

//     }

//     check(g.right(g(w - 1, j)) == INVALID, "Wrong right");    

//   }

//   for (int j = 0; j < h; ++j) {

//     for (int i = 1; i < w; ++i) {

//       check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left");

//       check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left");      

//     }

//     check(g.left(g(0, j)) == INVALID, "Wrong left");    

//   }

// }

int main() {

  check_concepts();

//   {

//     FullGraph g(5);

//     check_item_counts(g, 5, 10);

//   }

//   {

//     GridGraph g(5, 6);

//     check_item_counts(g, 30, 49);

//     checkGridGraph(g, 5, 6);

//   }

  std::cout << __FILE__ ": All tests passed.\n";

  return 0;

}