alpar@209: /* -*- mode: C++; indent-tabs-mode: nil; -*- deba@109: * alpar@209: * This file is a part of LEMON, a generic C++ optimization library. deba@109: * alpar@877: * Copyright (C) 2003-2010 deba@109: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@109: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@109: * deba@109: * Permission to use, modify and distribute this software is granted deba@109: * provided that this copyright notice appears in all copies. For deba@109: * precise terms see the accompanying LICENSE file. deba@109: * deba@109: * This software is provided "AS IS" with no warranty of any kind, deba@109: * express or implied, and with no claim as to its suitability for any deba@109: * purpose. deba@109: * deba@109: */ deba@109: deba@109: #ifndef LEMON_SMART_GRAPH_H deba@109: #define LEMON_SMART_GRAPH_H deba@109: deba@109: ///\ingroup graphs deba@109: ///\file deba@109: ///\brief SmartDigraph and SmartGraph classes. deba@109: deba@109: #include <vector> deba@109: deba@220: #include <lemon/core.h> deba@109: #include <lemon/error.h> deba@109: #include <lemon/bits/graph_extender.h> deba@109: deba@109: namespace lemon { deba@109: deba@109: class SmartDigraph; deba@109: deba@109: class SmartDigraphBase { deba@109: protected: deba@109: alpar@209: struct NodeT deba@109: { alpar@209: int first_in, first_out; deba@109: NodeT() {} deba@109: }; alpar@209: struct ArcT deba@109: { alpar@209: int target, source, next_in, next_out; alpar@209: ArcT() {} deba@109: }; deba@109: deba@109: std::vector<NodeT> nodes; deba@109: std::vector<ArcT> arcs; alpar@209: deba@109: public: deba@109: kpeter@617: typedef SmartDigraphBase Digraph; deba@109: deba@109: class Node; deba@109: class Arc; deba@109: deba@109: public: deba@109: deba@109: SmartDigraphBase() : nodes(), arcs() { } alpar@209: SmartDigraphBase(const SmartDigraphBase &_g) deba@109: : nodes(_g.nodes), arcs(_g.arcs) { } alpar@209: deba@109: typedef True NodeNumTag; kpeter@360: typedef True ArcNumTag; deba@109: deba@109: int nodeNum() const { return nodes.size(); } deba@109: int arcNum() const { return arcs.size(); } deba@109: deba@109: int maxNodeId() const { return nodes.size()-1; } deba@109: int maxArcId() const { return arcs.size()-1; } deba@109: deba@109: Node addNode() { alpar@209: int n = nodes.size(); deba@109: nodes.push_back(NodeT()); deba@109: nodes[n].first_in = -1; deba@109: nodes[n].first_out = -1; deba@109: return Node(n); deba@109: } alpar@209: deba@109: Arc addArc(Node u, Node v) { alpar@209: int n = arcs.size(); deba@109: arcs.push_back(ArcT()); alpar@209: arcs[n].source = u._id; deba@109: arcs[n].target = v._id; deba@109: arcs[n].next_out = nodes[u._id].first_out; deba@109: arcs[n].next_in = nodes[v._id].first_in; deba@109: nodes[u._id].first_out = nodes[v._id].first_in = n; deba@109: deba@109: return Arc(n); deba@109: } deba@109: deba@109: void clear() { deba@109: arcs.clear(); deba@109: nodes.clear(); deba@109: } deba@109: deba@109: Node source(Arc a) const { return Node(arcs[a._id].source); } deba@109: Node target(Arc a) const { return Node(arcs[a._id].target); } deba@109: deba@109: static int id(Node v) { return v._id; } deba@109: static int id(Arc a) { return a._id; } deba@109: deba@109: static Node nodeFromId(int id) { return Node(id);} deba@109: static Arc arcFromId(int id) { return Arc(id);} deba@109: alpar@209: bool valid(Node n) const { alpar@209: return n._id >= 0 && n._id < static_cast<int>(nodes.size()); deba@149: } alpar@209: bool valid(Arc a) const { alpar@209: return a._id >= 0 && a._id < static_cast<int>(arcs.size()); deba@149: } deba@149: deba@109: class Node { deba@109: friend class SmartDigraphBase; deba@109: friend class SmartDigraph; deba@109: deba@109: protected: deba@109: int _id; deba@109: explicit Node(int id) : _id(id) {} deba@109: public: deba@109: Node() {} deba@109: Node (Invalid) : _id(-1) {} deba@109: bool operator==(const Node i) const {return _id == i._id;} deba@109: bool operator!=(const Node i) const {return _id != i._id;} deba@109: bool operator<(const Node i) const {return _id < i._id;} deba@109: }; alpar@209: deba@109: deba@109: class Arc { deba@109: friend class SmartDigraphBase; deba@109: friend class SmartDigraph; deba@109: deba@109: protected: deba@109: int _id; deba@109: explicit Arc(int id) : _id(id) {} deba@109: public: deba@109: Arc() { } deba@109: Arc (Invalid) : _id(-1) {} deba@109: bool operator==(const Arc i) const {return _id == i._id;} deba@109: bool operator!=(const Arc i) const {return _id != i._id;} deba@109: bool operator<(const Arc i) const {return _id < i._id;} deba@109: }; deba@109: deba@109: void first(Node& node) const { deba@109: node._id = nodes.size() - 1; deba@109: } deba@109: deba@109: static void next(Node& node) { deba@109: --node._id; deba@109: } deba@109: deba@109: void first(Arc& arc) const { deba@109: arc._id = arcs.size() - 1; deba@109: } deba@109: deba@109: static void next(Arc& arc) { deba@109: --arc._id; deba@109: } deba@109: deba@109: void firstOut(Arc& arc, const Node& node) const { deba@109: arc._id = nodes[node._id].first_out; deba@109: } deba@109: deba@109: void nextOut(Arc& arc) const { deba@109: arc._id = arcs[arc._id].next_out; deba@109: } deba@109: deba@109: void firstIn(Arc& arc, const Node& node) const { deba@109: arc._id = nodes[node._id].first_in; deba@109: } alpar@209: deba@109: void nextIn(Arc& arc) const { deba@109: arc._id = arcs[arc._id].next_in; deba@109: } deba@109: deba@109: }; deba@109: deba@109: typedef DigraphExtender<SmartDigraphBase> ExtendedSmartDigraphBase; deba@109: deba@109: ///\ingroup graphs deba@109: /// deba@109: ///\brief A smart directed graph class. deba@109: /// kpeter@735: ///\ref SmartDigraph is a simple and fast digraph implementation. kpeter@735: ///It is also quite memory efficient but at the price alpar@877: ///that it does not support node and arc deletion kpeter@735: ///(except for the Snapshot feature). deba@109: /// kpeter@735: ///This type fully conforms to the \ref concepts::Digraph "Digraph concept" kpeter@735: ///and it also provides some additional functionalities. kpeter@735: ///Most of its member functions and nested classes are documented kpeter@735: ///only in the concept class. kpeter@735: /// kpeter@787: ///This class provides constant time counting for nodes and arcs. kpeter@787: /// kpeter@735: ///\sa concepts::Digraph kpeter@735: ///\sa SmartGraph deba@109: class SmartDigraph : public ExtendedSmartDigraphBase { deba@109: typedef ExtendedSmartDigraphBase Parent; deba@109: deba@109: private: kpeter@735: /// Digraphs are \e not copy constructible. Use DigraphCopy instead. deba@109: SmartDigraph(const SmartDigraph &) : ExtendedSmartDigraphBase() {}; kpeter@735: /// \brief Assignment of a digraph to another one is \e not allowed. kpeter@735: /// Use DigraphCopy instead. deba@109: void operator=(const SmartDigraph &) {} deba@109: deba@109: public: alpar@209: deba@109: /// Constructor alpar@209: deba@109: /// Constructor. deba@109: /// deba@109: SmartDigraph() {}; alpar@209: deba@109: ///Add a new node to the digraph. alpar@209: kpeter@735: ///This function adds a new node to the digraph. kpeter@735: ///\return The new node. deba@109: Node addNode() { return Parent::addNode(); } alpar@209: deba@109: ///Add a new arc to the digraph. alpar@209: kpeter@735: ///This function adds a new arc to the digraph with source node \c s deba@109: ///and target node \c t. kpeter@559: ///\return The new arc. kpeter@735: Arc addArc(Node s, Node t) { alpar@209: return Parent::addArc(s, t); deba@109: } deba@109: deba@149: /// \brief Node validity check deba@149: /// kpeter@735: /// This function gives back \c true if the given node is valid, kpeter@735: /// i.e. it is a real node of the digraph. deba@149: /// deba@149: /// \warning A removed node (using Snapshot) could become valid again kpeter@735: /// if new nodes are added to the digraph. deba@149: bool valid(Node n) const { return Parent::valid(n); } deba@149: deba@149: /// \brief Arc validity check deba@149: /// kpeter@735: /// This function gives back \c true if the given arc is valid, kpeter@735: /// i.e. it is a real arc of the digraph. deba@149: /// deba@149: /// \warning A removed arc (using Snapshot) could become valid again kpeter@735: /// if new arcs are added to the graph. deba@149: bool valid(Arc a) const { return Parent::valid(a); } deba@149: deba@109: ///Split a node. alpar@209: kpeter@735: ///This function splits the given node. First, a new node is added kpeter@735: ///to the digraph, then the source of each outgoing arc of node \c n kpeter@735: ///is moved to this new node. kpeter@735: ///If the second parameter \c connect is \c true (this is the default kpeter@735: ///value), then a new arc from node \c n to the newly created node kpeter@735: ///is also added. deba@109: ///\return The newly created node. deba@109: /// kpeter@735: ///\note All iterators remain valid. kpeter@735: /// deba@109: ///\warning This functionality cannot be used together with the Snapshot deba@109: ///feature. deba@109: Node split(Node n, bool connect = true) deba@109: { deba@109: Node b = addNode(); deba@109: nodes[b._id].first_out=nodes[n._id].first_out; deba@109: nodes[n._id].first_out=-1; kpeter@370: for(int i=nodes[b._id].first_out; i!=-1; i=arcs[i].next_out) { kpeter@370: arcs[i].source=b._id; kpeter@370: } deba@109: if(connect) addArc(n,b); deba@109: return b; deba@109: } deba@109: kpeter@735: ///Clear the digraph. kpeter@735: kpeter@735: ///This function erases all nodes and arcs from the digraph. kpeter@735: /// kpeter@735: void clear() { kpeter@735: Parent::clear(); kpeter@735: } kpeter@735: kpeter@735: /// Reserve memory for nodes. kpeter@735: kpeter@735: /// Using this function, it is possible to avoid superfluous memory kpeter@735: /// allocation: if you know that the digraph you want to build will kpeter@735: /// be large (e.g. it will contain millions of nodes and/or arcs), kpeter@735: /// then it is worth reserving space for this amount before starting kpeter@735: /// to build the digraph. kpeter@735: /// \sa reserveArc() kpeter@735: void reserveNode(int n) { nodes.reserve(n); }; kpeter@735: kpeter@735: /// Reserve memory for arcs. kpeter@735: kpeter@735: /// Using this function, it is possible to avoid superfluous memory kpeter@735: /// allocation: if you know that the digraph you want to build will kpeter@735: /// be large (e.g. it will contain millions of nodes and/or arcs), kpeter@735: /// then it is worth reserving space for this amount before starting kpeter@735: /// to build the digraph. kpeter@735: /// \sa reserveNode() kpeter@735: void reserveArc(int m) { arcs.reserve(m); }; kpeter@735: deba@109: public: alpar@209: deba@109: class Snapshot; deba@109: deba@109: protected: deba@109: deba@109: void restoreSnapshot(const Snapshot &s) deba@109: { deba@109: while(s.arc_num<arcs.size()) { deba@109: Arc arc = arcFromId(arcs.size()-1); alpar@209: Parent::notifier(Arc()).erase(arc); alpar@209: nodes[arcs.back().source].first_out=arcs.back().next_out; alpar@209: nodes[arcs.back().target].first_in=arcs.back().next_in; alpar@209: arcs.pop_back(); deba@109: } deba@109: while(s.node_num<nodes.size()) { deba@109: Node node = nodeFromId(nodes.size()-1); alpar@209: Parent::notifier(Node()).erase(node); alpar@209: nodes.pop_back(); deba@109: } alpar@209: } deba@109: deba@109: public: deba@109: kpeter@735: ///Class to make a snapshot of the digraph and to restore it later. deba@109: kpeter@735: ///Class to make a snapshot of the digraph and to restore it later. deba@109: /// deba@109: ///The newly added nodes and arcs can be removed using the kpeter@735: ///restore() function. This is the only way for deleting nodes and/or kpeter@735: ///arcs from a SmartDigraph structure. deba@109: /// alpar@877: ///\note After a state is restored, you cannot restore a later state, kpeter@735: ///i.e. you cannot add the removed nodes and arcs again using kpeter@735: ///another Snapshot instance. kpeter@735: /// kpeter@735: ///\warning Node splitting cannot be restored. kpeter@735: ///\warning The validity of the snapshot is not stored due to kpeter@735: ///performance reasons. If you do not use the snapshot correctly, kpeter@735: ///it can cause broken program, invalid or not restored state of kpeter@735: ///the digraph or no change. alpar@209: class Snapshot deba@109: { deba@109: SmartDigraph *_graph; deba@109: protected: deba@109: friend class SmartDigraph; deba@109: unsigned int node_num; deba@109: unsigned int arc_num; deba@109: public: deba@109: ///Default constructor. alpar@209: deba@109: ///Default constructor. kpeter@735: ///You have to call save() to actually make a snapshot. deba@109: Snapshot() : _graph(0) {} deba@109: ///Constructor that immediately makes a snapshot alpar@209: kpeter@735: ///This constructor immediately makes a snapshot of the given digraph. kpeter@735: /// kpeter@735: Snapshot(SmartDigraph &gr) : _graph(&gr) { alpar@209: node_num=_graph->nodes.size(); alpar@209: arc_num=_graph->arcs.size(); deba@109: } deba@109: deba@109: ///Make a snapshot. deba@109: kpeter@735: ///This function makes a snapshot of the given digraph. kpeter@735: ///It can be called more than once. In case of a repeated deba@109: ///call, the previous snapshot gets lost. kpeter@735: void save(SmartDigraph &gr) { kpeter@735: _graph=&gr; alpar@209: node_num=_graph->nodes.size(); alpar@209: arc_num=_graph->arcs.size(); deba@109: } deba@109: deba@109: ///Undo the changes until a snapshot. alpar@209: kpeter@735: ///This function undos the changes until the last snapshot kpeter@735: ///created by save() or Snapshot(SmartDigraph&). deba@109: void restore() deba@109: { alpar@209: _graph->restoreSnapshot(*this); deba@109: } deba@109: }; deba@109: }; deba@109: deba@109: deba@109: class SmartGraphBase { deba@109: deba@109: protected: deba@109: deba@109: struct NodeT { deba@109: int first_out; deba@109: }; alpar@209: deba@109: struct ArcT { deba@109: int target; deba@109: int next_out; deba@109: }; deba@109: deba@109: std::vector<NodeT> nodes; deba@109: std::vector<ArcT> arcs; deba@109: deba@109: int first_free_arc; alpar@209: deba@109: public: alpar@209: kpeter@617: typedef SmartGraphBase Graph; deba@109: deba@109: class Node; deba@109: class Arc; deba@109: class Edge; alpar@209: deba@109: class Node { deba@109: friend class SmartGraphBase; deba@109: protected: deba@109: deba@109: int _id; deba@109: explicit Node(int id) { _id = id;} deba@109: deba@109: public: deba@109: Node() {} deba@109: Node (Invalid) { _id = -1; } deba@109: bool operator==(const Node& node) const {return _id == node._id;} deba@109: bool operator!=(const Node& node) const {return _id != node._id;} deba@109: bool operator<(const Node& node) const {return _id < node._id;} deba@109: }; deba@109: deba@109: class Edge { deba@109: friend class SmartGraphBase; deba@109: protected: deba@109: deba@109: int _id; deba@109: explicit Edge(int id) { _id = id;} deba@109: deba@109: public: deba@109: Edge() {} deba@109: Edge (Invalid) { _id = -1; } deba@109: bool operator==(const Edge& arc) const {return _id == arc._id;} deba@109: bool operator!=(const Edge& arc) const {return _id != arc._id;} deba@109: bool operator<(const Edge& arc) const {return _id < arc._id;} deba@109: }; deba@109: deba@109: class Arc { deba@109: friend class SmartGraphBase; deba@109: protected: deba@109: deba@109: int _id; deba@109: explicit Arc(int id) { _id = id;} deba@109: deba@109: public: kpeter@329: operator Edge() const { kpeter@329: return _id != -1 ? edgeFromId(_id / 2) : INVALID; deba@238: } deba@109: deba@109: Arc() {} deba@109: Arc (Invalid) { _id = -1; } deba@109: bool operator==(const Arc& arc) const {return _id == arc._id;} deba@109: bool operator!=(const Arc& arc) const {return _id != arc._id;} deba@109: bool operator<(const Arc& arc) const {return _id < arc._id;} deba@109: }; deba@109: deba@109: deba@109: deba@109: SmartGraphBase() deba@109: : nodes(), arcs() {} deba@109: kpeter@368: typedef True NodeNumTag; kpeter@368: typedef True EdgeNumTag; kpeter@368: typedef True ArcNumTag; kpeter@368: kpeter@368: int nodeNum() const { return nodes.size(); } kpeter@368: int edgeNum() const { return arcs.size() / 2; } kpeter@368: int arcNum() const { return arcs.size(); } alpar@209: alpar@209: int maxNodeId() const { return nodes.size()-1; } deba@109: int maxEdgeId() const { return arcs.size() / 2 - 1; } deba@109: int maxArcId() const { return arcs.size()-1; } deba@109: deba@109: Node source(Arc e) const { return Node(arcs[e._id ^ 1].target); } deba@109: Node target(Arc e) const { return Node(arcs[e._id].target); } deba@109: deba@125: Node u(Edge e) const { return Node(arcs[2 * e._id].target); } deba@125: Node v(Edge e) const { return Node(arcs[2 * e._id + 1].target); } deba@109: deba@109: static bool direction(Arc e) { deba@109: return (e._id & 1) == 1; deba@109: } deba@109: deba@109: static Arc direct(Edge e, bool d) { deba@109: return Arc(e._id * 2 + (d ? 1 : 0)); deba@109: } deba@109: alpar@209: void first(Node& node) const { deba@109: node._id = nodes.size() - 1; deba@109: } deba@109: kpeter@778: static void next(Node& node) { deba@109: --node._id; deba@109: } deba@109: alpar@209: void first(Arc& arc) const { deba@109: arc._id = arcs.size() - 1; deba@109: } deba@109: kpeter@778: static void next(Arc& arc) { deba@109: --arc._id; deba@109: } deba@109: alpar@209: void first(Edge& arc) const { deba@109: arc._id = arcs.size() / 2 - 1; deba@109: } deba@109: kpeter@778: static void next(Edge& arc) { deba@109: --arc._id; deba@109: } deba@109: deba@109: void firstOut(Arc &arc, const Node& v) const { deba@109: arc._id = nodes[v._id].first_out; deba@109: } deba@109: void nextOut(Arc &arc) const { deba@109: arc._id = arcs[arc._id].next_out; deba@109: } deba@109: deba@109: void firstIn(Arc &arc, const Node& v) const { deba@109: arc._id = ((nodes[v._id].first_out) ^ 1); deba@109: if (arc._id == -2) arc._id = -1; deba@109: } deba@109: void nextIn(Arc &arc) const { deba@109: arc._id = ((arcs[arc._id ^ 1].next_out) ^ 1); deba@109: if (arc._id == -2) arc._id = -1; deba@109: } deba@109: deba@109: void firstInc(Edge &arc, bool& d, const Node& v) const { deba@109: int de = nodes[v._id].first_out; deba@109: if (de != -1) { deba@109: arc._id = de / 2; deba@109: d = ((de & 1) == 1); deba@109: } else { deba@109: arc._id = -1; deba@109: d = true; deba@109: } deba@109: } deba@109: void nextInc(Edge &arc, bool& d) const { deba@109: int de = (arcs[(arc._id * 2) | (d ? 1 : 0)].next_out); deba@109: if (de != -1) { deba@109: arc._id = de / 2; deba@109: d = ((de & 1) == 1); deba@109: } else { deba@109: arc._id = -1; alpar@209: d = true; deba@109: } deba@109: } alpar@209: deba@109: static int id(Node v) { return v._id; } deba@109: static int id(Arc e) { return e._id; } deba@109: static int id(Edge e) { return e._id; } deba@109: deba@109: static Node nodeFromId(int id) { return Node(id);} deba@109: static Arc arcFromId(int id) { return Arc(id);} deba@109: static Edge edgeFromId(int id) { return Edge(id);} deba@109: alpar@209: bool valid(Node n) const { alpar@209: return n._id >= 0 && n._id < static_cast<int>(nodes.size()); deba@149: } alpar@209: bool valid(Arc a) const { deba@149: return a._id >= 0 && a._id < static_cast<int>(arcs.size()); deba@149: } alpar@209: bool valid(Edge e) const { alpar@209: return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size()); deba@149: } deba@149: alpar@209: Node addNode() { deba@109: int n = nodes.size(); deba@109: nodes.push_back(NodeT()); deba@109: nodes[n].first_out = -1; alpar@209: deba@109: return Node(n); deba@109: } alpar@209: deba@138: Edge addEdge(Node u, Node v) { deba@109: int n = arcs.size(); deba@109: arcs.push_back(ArcT()); deba@109: arcs.push_back(ArcT()); alpar@209: deba@109: arcs[n].target = u._id; deba@109: arcs[n | 1].target = v._id; deba@109: deba@109: arcs[n].next_out = nodes[v._id].first_out; deba@109: nodes[v._id].first_out = n; deba@109: alpar@209: arcs[n | 1].next_out = nodes[u._id].first_out; deba@109: nodes[u._id].first_out = (n | 1); deba@109: deba@109: return Edge(n / 2); deba@109: } alpar@209: deba@109: void clear() { deba@109: arcs.clear(); deba@109: nodes.clear(); deba@109: } deba@109: deba@109: }; deba@109: deba@109: typedef GraphExtender<SmartGraphBase> ExtendedSmartGraphBase; deba@109: deba@109: /// \ingroup graphs deba@109: /// deba@109: /// \brief A smart undirected graph class. deba@109: /// kpeter@735: /// \ref SmartGraph is a simple and fast graph implementation. kpeter@735: /// It is also quite memory efficient but at the price alpar@877: /// that it does not support node and edge deletion kpeter@735: /// (except for the Snapshot feature). deba@109: /// kpeter@735: /// This type fully conforms to the \ref concepts::Graph "Graph concept" kpeter@735: /// and it also provides some additional functionalities. kpeter@735: /// Most of its member functions and nested classes are documented kpeter@735: /// only in the concept class. kpeter@735: /// kpeter@787: /// This class provides constant time counting for nodes, edges and arcs. kpeter@787: /// kpeter@735: /// \sa concepts::Graph kpeter@735: /// \sa SmartDigraph deba@109: class SmartGraph : public ExtendedSmartGraphBase { kpeter@617: typedef ExtendedSmartGraphBase Parent; kpeter@617: deba@109: private: kpeter@735: /// Graphs are \e not copy constructible. Use GraphCopy instead. deba@109: SmartGraph(const SmartGraph &) : ExtendedSmartGraphBase() {}; kpeter@735: /// \brief Assignment of a graph to another one is \e not allowed. kpeter@735: /// Use GraphCopy instead. deba@109: void operator=(const SmartGraph &) {} deba@109: deba@109: public: deba@109: deba@109: /// Constructor alpar@209: deba@109: /// Constructor. deba@109: /// deba@109: SmartGraph() {} deba@109: kpeter@735: /// \brief Add a new node to the graph. kpeter@735: /// kpeter@735: /// This function adds a new node to the graph. kpeter@559: /// \return The new node. deba@109: Node addNode() { return Parent::addNode(); } alpar@209: kpeter@735: /// \brief Add a new edge to the graph. kpeter@735: /// kpeter@735: /// This function adds a new edge to the graph between nodes kpeter@735: /// \c u and \c v with inherent orientation from node \c u to kpeter@735: /// node \c v. kpeter@735: /// \return The new edge. kpeter@735: Edge addEdge(Node u, Node v) { kpeter@735: return Parent::addEdge(u, v); deba@109: } deba@109: deba@149: /// \brief Node validity check deba@149: /// kpeter@735: /// This function gives back \c true if the given node is valid, kpeter@735: /// i.e. it is a real node of the graph. deba@149: /// deba@149: /// \warning A removed node (using Snapshot) could become valid again kpeter@735: /// if new nodes are added to the graph. deba@149: bool valid(Node n) const { return Parent::valid(n); } deba@149: kpeter@735: /// \brief Edge validity check kpeter@735: /// kpeter@735: /// This function gives back \c true if the given edge is valid, kpeter@735: /// i.e. it is a real edge of the graph. kpeter@735: /// kpeter@735: /// \warning A removed edge (using Snapshot) could become valid again kpeter@735: /// if new edges are added to the graph. kpeter@735: bool valid(Edge e) const { return Parent::valid(e); } kpeter@735: deba@149: /// \brief Arc validity check deba@149: /// kpeter@735: /// This function gives back \c true if the given arc is valid, kpeter@735: /// i.e. it is a real arc of the graph. deba@149: /// deba@149: /// \warning A removed arc (using Snapshot) could become valid again kpeter@735: /// if new edges are added to the graph. deba@149: bool valid(Arc a) const { return Parent::valid(a); } deba@149: deba@109: ///Clear the graph. alpar@209: kpeter@735: ///This function erases all nodes and arcs from the graph. deba@109: /// deba@109: void clear() { deba@109: Parent::clear(); deba@109: } deba@109: kpeter@736: /// Reserve memory for nodes. kpeter@736: kpeter@736: /// Using this function, it is possible to avoid superfluous memory kpeter@736: /// allocation: if you know that the graph you want to build will kpeter@736: /// be large (e.g. it will contain millions of nodes and/or edges), kpeter@736: /// then it is worth reserving space for this amount before starting kpeter@736: /// to build the graph. kpeter@736: /// \sa reserveEdge() kpeter@736: void reserveNode(int n) { nodes.reserve(n); }; kpeter@736: kpeter@736: /// Reserve memory for edges. kpeter@736: kpeter@736: /// Using this function, it is possible to avoid superfluous memory kpeter@736: /// allocation: if you know that the graph you want to build will kpeter@736: /// be large (e.g. it will contain millions of nodes and/or edges), kpeter@736: /// then it is worth reserving space for this amount before starting kpeter@736: /// to build the graph. kpeter@736: /// \sa reserveNode() kpeter@736: void reserveEdge(int m) { arcs.reserve(2 * m); }; kpeter@736: deba@109: public: alpar@209: deba@109: class Snapshot; deba@109: deba@109: protected: deba@109: deba@109: void saveSnapshot(Snapshot &s) deba@109: { deba@109: s._graph = this; deba@109: s.node_num = nodes.size(); deba@109: s.arc_num = arcs.size(); deba@109: } deba@109: deba@109: void restoreSnapshot(const Snapshot &s) deba@109: { deba@109: while(s.arc_num<arcs.size()) { deba@109: int n=arcs.size()-1; deba@109: Edge arc=edgeFromId(n/2); alpar@209: Parent::notifier(Edge()).erase(arc); deba@109: std::vector<Arc> dir; deba@109: dir.push_back(arcFromId(n)); deba@109: dir.push_back(arcFromId(n-1)); alpar@209: Parent::notifier(Arc()).erase(dir); kpeter@373: nodes[arcs[n-1].target].first_out=arcs[n].next_out; kpeter@373: nodes[arcs[n].target].first_out=arcs[n-1].next_out; alpar@209: arcs.pop_back(); alpar@209: arcs.pop_back(); deba@109: } deba@109: while(s.node_num<nodes.size()) { deba@109: int n=nodes.size()-1; deba@109: Node node = nodeFromId(n); alpar@209: Parent::notifier(Node()).erase(node); alpar@209: nodes.pop_back(); deba@109: } alpar@209: } deba@109: deba@109: public: deba@109: kpeter@735: ///Class to make a snapshot of the graph and to restore it later. deba@109: kpeter@735: ///Class to make a snapshot of the graph and to restore it later. deba@109: /// kpeter@735: ///The newly added nodes and edges can be removed using the kpeter@735: ///restore() function. This is the only way for deleting nodes and/or kpeter@735: ///edges from a SmartGraph structure. deba@109: /// alpar@877: ///\note After a state is restored, you cannot restore a later state, kpeter@735: ///i.e. you cannot add the removed nodes and edges again using kpeter@735: ///another Snapshot instance. deba@109: /// kpeter@735: ///\warning The validity of the snapshot is not stored due to kpeter@735: ///performance reasons. If you do not use the snapshot correctly, kpeter@735: ///it can cause broken program, invalid or not restored state of kpeter@735: ///the graph or no change. alpar@209: class Snapshot deba@109: { deba@109: SmartGraph *_graph; deba@109: protected: deba@109: friend class SmartGraph; deba@109: unsigned int node_num; deba@109: unsigned int arc_num; deba@109: public: deba@109: ///Default constructor. alpar@209: deba@109: ///Default constructor. kpeter@735: ///You have to call save() to actually make a snapshot. deba@109: Snapshot() : _graph(0) {} deba@109: ///Constructor that immediately makes a snapshot alpar@209: kpeter@735: /// This constructor immediately makes a snapshot of the given graph. kpeter@735: /// kpeter@735: Snapshot(SmartGraph &gr) { kpeter@735: gr.saveSnapshot(*this); deba@109: } deba@109: deba@109: ///Make a snapshot. deba@109: kpeter@735: ///This function makes a snapshot of the given graph. kpeter@735: ///It can be called more than once. In case of a repeated deba@109: ///call, the previous snapshot gets lost. kpeter@735: void save(SmartGraph &gr) deba@109: { kpeter@735: gr.saveSnapshot(*this); deba@109: } deba@109: kpeter@735: ///Undo the changes until the last snapshot. alpar@209: kpeter@735: ///This function undos the changes until the last snapshot kpeter@735: ///created by save() or Snapshot(SmartGraph&). deba@109: void restore() deba@109: { deba@109: _graph->restoreSnapshot(*this); deba@109: } deba@109: }; deba@109: }; alpar@209: deba@109: } //namespace lemon deba@109: deba@109: deba@109: #endif //LEMON_SMART_GRAPH_H