RhodeCode

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

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

    bool valid(Node n) const {

      return n._id >= 0 && n._id < static_cast<int>(nodes.size());

    }

    bool valid(Arc a) const {

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

  /// Except from this it conforms to

  /// the \ref concepts::Graph "Graph concept".

  ///

  /// It also has an

  /// important extra feature that

  /// its maps are real \ref concepts::ReferenceMap "reference map"s.

  ///

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

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

    bool valid(Node n) const { return Parent::valid(n); }

    /// \brief Arc validity check

    ///

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

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

    ///

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

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

    bool valid(Arc a) const { return Parent::valid(a); }

    /// \brief Edge validity check

    ///

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

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

    ///

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

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

    bool valid(Edge e) const { return Parent::valid(e); }

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

        int n=arcs.size()-1;

        Edge arc=edgeFromId(n/2);

        Parent::notifier(Edge()).erase(arc);

        std::vector<Arc> dir;

        dir.push_back(arcFromId(n));

        dir.push_back(arcFromId(n-1));

        Parent::notifier(Arc()).erase(dir);

        arcs.pop_back();

        arcs.pop_back();

      }

      while(s.node_num<nodes.size()) {

        int n=nodes.size()-1;

        Node node = nodeFromId(n);

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

        nodes.pop_back();

      }

    }

  public:

    ///Class to make a snapshot of the digraph and to restrore to it later.

    ///Class to make a snapshot of the digraph and to restrore to it later.

    ///

    ///The newly added nodes and arcs can be removed using the

    ///restore() function.

    ///

    ///\note After you restore a state, you cannot restore

    ///a later state, in other word you cannot add again the arcs deleted

    ///by restore() using another one Snapshot instance.

    ///

    ///\warning If you do not use correctly the snapshot that can cause

    ///either broken program, invalid state of the digraph, valid but

    ///not the restored digraph or no change. Because the runtime performance

    ///the validity of the snapshot is not stored.

    class Snapshot

    {

      SmartGraph *_graph;

    protected:

      friend class SmartGraph;

      unsigned int node_num;

      unsigned int arc_num;

    public:

      ///Default constructor.

      ///Default constructor.

      ///To actually make a snapshot you must call save().

      ///

      Snapshot() : _graph(0) {}

      ///Constructor that immediately makes a snapshot

      ///This constructor immediately makes a snapshot of the digraph.

      ///\param graph The digraph we make a snapshot of.

      Snapshot(SmartGraph &graph) {

        graph.saveSnapshot(*this);

      }

      ///Make a snapshot.

      ///Make a snapshot of the graph.

      ///

      ///This function can be called more than once. In case of a repeated

      ///call, the previous snapshot gets lost.

      ///\param graph The digraph we make the snapshot of.

      void save(SmartGraph &graph)

      {

        graph.saveSnapshot(*this);

      }

      ///Undo the changes until a snapshot.

      ///Undo the changes until a snapshot created by save().

      ///

      ///\note After you restored a state, you cannot restore

      ///a later state, in other word you cannot add again the arcs deleted

      ///by restore().

      void restore()

      {

        _graph->restoreSnapshot(*this);

      }

    };

  };

} //namespace lemon

#endif //LEMON_SMART_GRAPH_H

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

 *

 * 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/digraph.h>

#include <lemon/list_graph.h>

#include <lemon/smart_graph.h>

#include <lemon/full_graph.h>

#include "test_tools.h"

#include "graph_test.h"

using namespace lemon;

using namespace lemon::concepts;

template <class Digraph>

  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

  Digraph G;

  checkGraphNodeList(G, 0);

  checkGraphArcList(G, 0);

  Node

    n1 = G.addNode(),

    n2 = G.addNode(),

    n3 = G.addNode();

  checkGraphNodeList(G, 3);

  checkGraphArcList(G, 0);

  Arc a1 = G.addArc(n1, n2);

  check(G.source(a1) == n1 && G.target(a1) == n2, "Wrong arc");

  checkGraphNodeList(G, 3);

  checkGraphArcList(G, 1);

  checkGraphOutArcList(G, n1, 1);

  checkGraphOutArcList(G, n2, 0);

  checkGraphOutArcList(G, n3, 0);

  checkGraphInArcList(G, n1, 0);

  checkGraphInArcList(G, n2, 1);

  checkGraphInArcList(G, n3, 0);

  checkGraphConArcList(G, 1);

  checkGraphNodeList(G, 3);

  checkGraphArcList(G, 4);

  checkGraphOutArcList(G, n1, 1);

  checkGraphOutArcList(G, n2, 3);

  checkGraphOutArcList(G, n3, 0);

  checkGraphInArcList(G, n1, 1);

  checkGraphInArcList(G, n2, 1);

  checkGraphInArcList(G, n3, 2);

  checkGraphConArcList(G, 4);

  checkNodeIds(G);

  checkArcIds(G);

  checkGraphNodeMap(G);

  checkGraphArcMap(G);

}

void checkConcepts() {

  { // Checking digraph components

    checkConcept<BaseDigraphComponent, BaseDigraphComponent >();

    checkConcept<IDableDigraphComponent<>,

      IDableDigraphComponent<> >();

    checkConcept<IterableDigraphComponent<>,

      IterableDigraphComponent<> >();

    checkConcept<MappableDigraphComponent<>,

      MappableDigraphComponent<> >();

  }

  { // Checking skeleton digraph

    checkConcept<Digraph, Digraph>();

  }

  { // Checking ListDigraph

    checkConcept<Digraph, ListDigraph>();

    checkConcept<AlterableDigraphComponent<>, ListDigraph>();

    checkConcept<ExtendableDigraphComponent<>, ListDigraph>();

    checkConcept<ClearableDigraphComponent<>, ListDigraph>();

    checkConcept<ErasableDigraphComponent<>, ListDigraph>();

  }

  { // Checking SmartDigraph

    checkConcept<Digraph, SmartDigraph>();

    checkConcept<AlterableDigraphComponent<>, SmartDigraph>();

    checkConcept<ExtendableDigraphComponent<>, SmartDigraph>();

    checkConcept<ClearableDigraphComponent<>, SmartDigraph>();

  }

  { // Checking FullDigraph

    checkConcept<Digraph, FullDigraph>();

  }

}

template <typename Digraph>

void checkDigraphValidity() {

  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

  Digraph g;

  Node

    n1 = g.addNode(),

    n2 = g.addNode(),

    n3 = g.addNode();

  Arc

    e1 = g.addArc(n1, n2),

    e2 = g.addArc(n2, n3);

  check(g.valid(n1), "Wrong validity check");

  check(g.valid(e1), "Wrong validity check");

  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");

  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");

}

template <typename Digraph>

void checkDigraphValidityErase() {

  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

  Digraph g;

  Node

    n1 = g.addNode(),

    n2 = g.addNode(),

    n3 = g.addNode();

  Arc

    e1 = g.addArc(n1, n2),

    e2 = g.addArc(n2, n3);

  check(g.valid(n1), "Wrong validity check");

  check(g.valid(e1), "Wrong validity check");

  g.erase(n1);

  check(!g.valid(n1), "Wrong validity check");

  check(g.valid(n2), "Wrong validity check");

  check(g.valid(n3), "Wrong validity check");

  check(!g.valid(e1), "Wrong validity check");

  check(g.valid(e2), "Wrong validity check");

  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");

  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");

}

void checkDigraphs() {

  { // Checking ListDigraph

    checkDigraphValidityErase<ListDigraph>();

  }

  { // Checking SmartDigraph

    checkDigraphValidity<SmartDigraph>();

  }

  { // Checking FullDigraph

    checkFullDigraph(8);

  }

}

int main() {

  checkDigraphs();

  checkConcepts();

  return 0;

}

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

 *

 * 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 <lemon/hypercube_graph.h>

#include "test_tools.h"

#include "graph_test.h"

using namespace lemon;

using namespace lemon::concepts;

template <class Graph>

  TEMPLATE_GRAPH_TYPEDEFS(Graph);

  Graph G;

  checkGraphNodeList(G, 0);

  checkGraphEdgeList(G, 0);

  Node

    n1 = G.addNode(),

    n2 = G.addNode(),

    n3 = G.addNode();

  checkGraphNodeList(G, 3);

  checkGraphEdgeList(G, 0);

  Edge e1 = G.addEdge(n1, n2);

  check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1),

        "Wrong edge");

  checkGraphNodeList(G, 3);

  checkGraphArcList(G, 2);

  checkGraphConArcList(G, 6);

  checkArcDirections(G);

  checkNodeIds(G);

  checkArcIds(G);

  checkEdgeIds(G);

  checkGraphNodeMap(G);

  checkGraphArcMap(G);

  checkGraphEdgeMap(G);

}

void checkFullGraph(int num) {

  typedef FullGraph Graph;

  GRAPH_TYPEDEFS(Graph);

  Graph G(num);

  checkGraphNodeList(G, num);

  checkGraphEdgeList(G, num * (num - 1) / 2);

  for (NodeIt n(G); n != INVALID; ++n) {

    checkGraphOutArcList(G, n, num - 1);

    checkGraphInArcList(G, n, num - 1);

    checkGraphIncEdgeList(G, n, num - 1);

  }

  checkGraphConArcList(G, num * (num - 1));

  checkGraphConEdgeList(G, num * (num - 1) / 2);

  checkArcDirections(G);

  checkNodeIds(G);

  checkArcIds(G);

  checkEdgeIds(G);

  checkGraphNodeMap(G);

  checkGraphArcMap(G);

  checkGraphEdgeMap(G);

  for (int i = 0; i < G.nodeNum(); ++i) {

    check(G.index(G(i)) == i, "Wrong index");

  }

  for (NodeIt u(G); u != INVALID; ++u) {

    for (NodeIt v(G); v != INVALID; ++v) {

      Edge e = G.edge(u, v);

      Arc a = G.arc(u, v);

      if (u == v) {

        check(e == INVALID, "Wrong edge lookup");

        check(a == INVALID, "Wrong arc lookup");

      } else {

        check((G.u(e) == u && G.v(e) == v) ||

              (G.u(e) == v && G.v(e) == u), "Wrong edge lookup");

        check(G.source(a) == u && G.target(a) == v, "Wrong arc lookup");

      }

    }

  }

}

void checkConcepts() {

  { // Checking graph components

    checkConcept<BaseGraphComponent, BaseGraphComponent >();

    checkConcept<IDableGraphComponent<>,

      IDableGraphComponent<> >();

    checkConcept<IterableGraphComponent<>,

      IterableGraphComponent<> >();

    checkConcept<MappableGraphComponent<>,

      MappableGraphComponent<> >();

  }

  { // Checking skeleton graph

    checkConcept<Graph, Graph>();

  }

  { // Checking ListGraph

    checkConcept<Graph, ListGraph>();

    checkConcept<AlterableGraphComponent<>, ListGraph>();

    checkConcept<ExtendableGraphComponent<>, ListGraph>();

    checkConcept<ClearableGraphComponent<>, ListGraph>();

    checkConcept<ErasableGraphComponent<>, ListGraph>();