RhodeCode

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

      void restore() {

        detach();

        for(std::list<Arc>::iterator it = added_arcs.begin();

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

          digraph->erase(*it);

        }

        for(std::list<Node>::iterator it = added_nodes.begin();

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

          digraph->erase(*it);

        }

        clear();

      }

      /// \brief Gives back true when the snapshot is valid.

      ///

      /// Gives back true when the snapshot is valid.

      bool valid() const {

        return attached();

      }

    };

  };

  ///@}

  class ListGraphBase {

  protected:

    struct NodeT {

      int first_out;

      int prev, next;

    };

    struct ArcT {

      int target;

      int prev_out, next_out;

    };

    std::vector<NodeT> nodes;

    int first_node;

    int first_free_node;

    std::vector<ArcT> arcs;

    int first_free_arc;

  public:

    typedef ListGraphBase Digraph;

    class Node;

    class Arc;

    class Edge;

    class Node {

      friend class ListGraphBase;

    protected:

      int id;

      explicit Node(int pid) { id = pid;}

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

      friend class ListGraphBase;

    protected:

      int id;

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

    public:

      Edge() {}

      Edge (Invalid) { id = -1; }

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

    };

    class Arc {

      friend class ListGraphBase;

    protected:

      int id;

      explicit Arc(int pid) { id = pid;}

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

    };

    ListGraphBase()

      : nodes(), first_node(-1),

        first_free_node(-1), arcs(), first_free_arc(-1) {}

    int maxNodeId() const { return nodes.size()-1; }

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

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

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

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

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

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

    static bool direction(Arc e) {

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

    }

    static Arc direct(Edge e, bool d) {

      return Arc(e.id * 2 + (d ? 1 : 0));

    }

    void first(Node& node) const {

      node.id = first_node;

    }

    void next(Node& node) const {

      node.id = nodes[node.id].next;

    }

    void first(Arc& e) const {

      int n = first_node;

      while (n != -1 && nodes[n].first_out == -1) {

        n = nodes[n].next;

      }

      e.id = (n == -1) ? -1 : nodes[n].first_out;

    }

    void next(Arc& e) const {

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

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

      } else {

        int n = nodes[arcs[e.id ^ 1].target].next;

        while(n != -1 && nodes[n].first_out == -1) {

          n = nodes[n].next;

        }

        e.id = (n == -1) ? -1 : nodes[n].first_out;

      }

    }

    void first(Edge& e) const {

      int n = first_node;

      while (n != -1) {

        e.id = nodes[n].first_out;

        while ((e.id & 1) != 1) {

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

        }

        if (e.id != -1) {

          e.id /= 2;

          return;

        }

        n = nodes[n].next;

      }

      e.id = -1;

    }

    void next(Edge& e) const {

      int n = arcs[e.id * 2].target;

      e.id = arcs[(e.id * 2) | 1].next_out;

      while ((e.id & 1) != 1) {

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

      }

      if (e.id != -1) {

        e.id /= 2;

        return;

      }

      n = nodes[n].next;

      while (n != -1) {

        e.id = nodes[n].first_out;

        while ((e.id & 1) != 1) {

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

        }

        if (e.id != -1) {

          e.id /= 2;

          return;

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

  protected:

    struct NodeT {

      int first_out;

    };

    struct ArcT {

      int target;

      int next_out;

    };

    std::vector<NodeT> nodes;

    std::vector<ArcT> arcs;

    int first_free_arc;

  public:

    typedef SmartGraphBase Digraph;

    class Node;

    class Arc;

    class Edge;

    class Node {

      friend class SmartGraphBase;

    protected:

      int _id;

      explicit 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 Edge {

      friend class SmartGraphBase;

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

    protected:

      int _id;

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

    };

    SmartGraphBase()

      : nodes(), arcs() {}

    int maxNodeId() const { return nodes.size()-1; }

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

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

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

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

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

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

    static bool direction(Arc e) {

      return (e._id & 1) == 1;

    }

    static Arc direct(Edge e, bool d) {

      return Arc(e._id * 2 + (d ? 1 : 0));

    }

    void first(Node& node) const {

      node._id = nodes.size() - 1;

    }

    void next(Node& node) const {

      --node._id;

    }

    void first(Arc& arc) const {

      arc._id = arcs.size() - 1;

    }

    void next(Arc& arc) const {

      --arc._id;

    }

    void first(Edge& arc) const {

      arc._id = arcs.size() / 2 - 1;

    }

    void next(Edge& arc) const {

      --arc._id;

    }

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

      arc._id = nodes[v._id].first_out;

    }

    void nextOut(Arc &arc) const {

      arc._id = arcs[arc._id].next_out;

    }

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

      arc._id = ((nodes[v._id].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& 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; }