RhodeCode

    ///Use DigraphCopy() instead.

    ///Assignment of SmartDigraph to another one is \e not allowed.

    ///Use DigraphCopy() instead.

    void operator=(const SmartDigraph &) {}

  public:

    /// Constructor

    /// Constructor.

    ///

    SmartDigraph() {};

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

    }

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

    /// \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 arcs are added to the graph.

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

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

    Node split(Node n, bool connect = true)

    {

      Node b = addNode();

      nodes[b._id].first_out=nodes[n._id].first_out;

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

      if(connect) addArc(n,b);

      return b;

    }

  public:

    class Snapshot;

  protected:

    void restoreSnapshot(const Snapshot &s)

    {

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

        Arc arc = arcFromId(arcs.size()-1);

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

        nodes[arcs.back().source].first_out=arcs.back().next_out;

        nodes[arcs.back().target].first_in=arcs.back().next_in;

        arcs.pop_back();

      }

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

        Node node = nodeFromId(nodes.size()-1);

        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

    {

      SmartDigraph *_graph;

    protected:

      friend class SmartDigraph;

      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(SmartDigraph &graph) : _graph(&graph) {

        node_num=_graph->nodes.size();

        arc_num=_graph->arcs.size();

      }

      ///Make a snapshot.

      ///Make a snapshot of the digraph.

      ///

      ///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(SmartDigraph &graph)

      {

        _graph=&graph;

        node_num=_graph->nodes.size();

        arc_num=_graph->arcs.size();

      }

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

      }

    };

  };

  class SmartGraphBase {