RhodeCode

      struct Constraints {

	  checkConcept<ReadWriteMap<K, T>, _ReferenceMap >();

	typename _ReferenceMap::Reference own_ref;

	Reference ref;

    void first(Arc& arc) const { 

      arc.id = (n == -1) ? -1 : nodes[n].first_in;

  /// \addtogroup graphs

  ///A general directed graph structure. 

  ///\ref ListDigraph is a simple and fast <em>directed graph</em> 

  ///implementation based on static linked lists that are stored in 

  ///\c std::vector structures.   

  ///also provides several useful additional functionalities.

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

  ///only in the concept class.

  ///\sa concepts::Digraph

    ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.

    ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.

    ///Use copyDigraph() instead.

    ///Use copyDigraph() instead.

    ///Add a new node to the digraph.

    ///\return the new node.

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

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

    ///

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

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

    ///

    ///

    /// Reserve memory for nodes.

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

    /// Reserve memory for arcs.

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

    ///\note The <tt>ArcIt</tt>s referencing a moved arc remain

    ///

    ///Snapshot feature.

    ///

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

    ///

    ///\return The newly created node.

    ///

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

    ///Snapshot feature.

    /// it later.

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

    /// \warning Arc and node deletions and other modifications (e.g.

    /// contracting, splitting, reversing arcs or nodes) cannot be 

    /// restored. These events invalidate the snapshot. 

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

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

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

      int a = nodes[v.id].first_out;

      if (a != -1 ) {

        e.id = a / 2;

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

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

      if (a != -1 ) {

        e.id = a / 2;

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

    void erase(const Edge& edge) {

      int n = edge.id * 2;

  /// \addtogroup graphs

  ///A general undirected graph structure.

  ///\ref ListGraph is a simple and fast <em>undirected graph</em> 

  ///implementation based on static linked lists that are stored in 

  ///\c std::vector structures. 

  ///It conforms to the \ref concepts::Graph "Graph concept" and it

  ///also provides several useful additional functionalities.

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

  ///only in the concept class.

  ///

  ///An important extra feature of this graph implementation is that

  ///\sa concepts::Graph

    ///ListGraph is \e not copy constructible. Use copyGraph() instead.

    ///ListGraph is \e not copy constructible. Use copyGraph() instead.

    ///Use copyGraph() instead.

    ///Use copyGraph() instead.

    typedef Parent::OutArcIt IncEdgeIt;

    /// \brief Add a new node to the graph.

    /// Add a new node to the graph.

    /// \brief Add a new edge to the graph.

    /// Add a new edge to the graph with source node \c s

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

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

    ///

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

    ///Snapshot feature.

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

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

    ///

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

    ///Snapshot feature.

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

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

    /// It also changes the proper node of the represented edge.

    ///

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

    ///Snapshot feature.

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

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

    /// It also changes the proper node of the represented edge.

    ///

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

    ///Snapshot feature.

    ///

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

    ///Snapshot feature.

      for(IncEdgeIt e(*this, b); e!=INVALID;) {

	IncEdgeIt f = e; ++f;

    /// \brief Class to make a snapshot of the graph and restore

    /// it later.

    /// Class to make a snapshot of the graph and restore it later.

    /// \warning Edge and node deletions and other modifications

    /// (e.g. changing nodes of edges, contracting nodes) cannot be 

    /// restored. These events invalidate the snapshot.

        virtual void add(const Edge& edge) {

          snapshot.addEdge(edge);

        virtual void add(const std::vector<Edge>& edges) {

          for (int i = edges.size() - 1; i >= 0; ++i) {

            snapshot.addEdge(edges[i]);

        virtual void erase(const Edge& edge) {

          snapshot.eraseEdge(edge);

        virtual void erase(const std::vector<Edge>& edges) {

          for (int i = 0; i < int(edges.size()); ++i) {

            snapshot.eraseEdge(edges[i]);

          Edge edge;

          std::vector<Edge> edges;

          for (notifier()->first(edge); edge != INVALID; 

               notifier()->next(edge)) {

            edges.push_back(edge);

          for (int i = edges.size() - 1; i >= 0; --i) {

            snapshot.addEdge(edges[i]);

          Edge edge;

          for (notifier()->first(edge); edge != INVALID; 

               notifier()->next(edge)) {

            snapshot.eraseEdge(edge);

      ListGraph *graph;

      EdgeObserverProxy edge_observer_proxy;

      std::list<Edge> added_edges;

          edge_observer_proxy.detach();

      void addEdge(const Edge& edge) {

        added_edges.push_front(edge);        

      void eraseEdge(const Edge& edge) {

          std::find(added_edges.begin(), added_edges.end(), edge);

        if (it == added_edges.end()) {

          added_edges.erase(it);

        }

      void attach(ListGraph &_graph) {

	graph = &_graph;

	node_observer_proxy.attach(graph->notifier(Node()));

        edge_observer_proxy.attach(graph->notifier(Edge()));

	edge_observer_proxy.detach();

        added_edges.clear();        

        : graph(0), node_observer_proxy(*this), 

          edge_observer_proxy(*this) {}

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

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

      Snapshot(ListGraph &_graph) 

          edge_observer_proxy(*this) {

	attach(_graph);

      /// Make a snapshot of the graph.

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

      void save(ListGraph &_graph) {

        attach(_graph);

	for(std::list<Edge>::iterator it = added_edges.begin(); 

            it != added_edges.end(); ++it) {

	  graph->erase(*it);

	  graph->erase(*it);