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@427: * Copyright (C) 2003-2011 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 deba@109: deba@220: #include deba@109: #include deba@109: #include deba@109: deba@109: namespace lemon { deba@109: deba@109: class SmartDigraph; deba@109: ///Base of SmartDigraph deba@109: deba@109: ///Base of 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 nodes; deba@109: std::vector arcs; alpar@209: deba@109: public: deba@109: deba@109: typedef SmartDigraphBase Graph; 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; deba@139: typedef True EdgeNumTag; 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(nodes.size()); deba@149: } alpar@209: bool valid(Arc a) const { alpar@209: return a._id >= 0 && a._id < static_cast(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 ExtendedSmartDigraphBase; deba@109: deba@109: ///\ingroup graphs deba@109: /// deba@109: ///\brief A smart directed graph class. deba@109: /// deba@109: ///This is a simple and fast digraph implementation. deba@109: ///It is also quite memory efficient, but at the price deba@109: ///that it does support only limited (only stack-like) deba@109: ///node and arc deletions. deba@109: ///It conforms to the \ref concepts::Digraph "Digraph concept" with deba@109: ///an important extra feature that its maps are real \ref deba@109: ///concepts::ReferenceMap "reference map"s. deba@109: /// deba@109: ///\sa concepts::Digraph. deba@109: class SmartDigraph : public ExtendedSmartDigraphBase { deba@109: public: deba@109: deba@109: typedef ExtendedSmartDigraphBase Parent; deba@109: deba@109: private: deba@109: deba@109: ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead. deba@109: deba@109: ///SmartDigraph is \e not copy constructible. Use DigraphCopy() instead. deba@109: /// deba@109: SmartDigraph(const SmartDigraph &) : ExtendedSmartDigraphBase() {}; deba@109: ///\brief Assignment of SmartDigraph to another one is \e not allowed. deba@109: ///Use DigraphCopy() instead. deba@109: deba@109: ///Assignment of SmartDigraph to another one is \e not allowed. deba@109: ///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: deba@109: /// \return the new node. deba@109: /// deba@109: Node addNode() { return Parent::addNode(); } alpar@209: deba@109: ///Add a new arc to the digraph. alpar@209: deba@109: ///Add a new arc to the digraph with source node \c s deba@109: ///and target node \c t. deba@109: ///\return the new arc. alpar@209: Arc addArc(const Node& s, const Node& t) { alpar@209: return Parent::addArc(s, t); deba@109: } deba@109: deba@109: /// \brief Using this it is possible to avoid the superfluous memory deba@109: /// allocation. deba@109: deba@109: /// Using this it is possible to avoid the superfluous memory deba@109: /// allocation: if you know that the digraph you want to build will deba@109: /// be very large (e.g. it will contain millions of nodes and/or arcs) deba@109: /// then it is worth reserving space for this amount before starting deba@109: /// to build the digraph. deba@109: /// \sa reserveArc deba@109: void reserveNode(int n) { nodes.reserve(n); }; deba@109: deba@109: /// \brief Using this it is possible to avoid the superfluous memory deba@109: /// allocation. deba@109: deba@109: /// Using this it is possible to avoid the superfluous memory deba@109: /// allocation: if you know that the digraph you want to build will deba@109: /// be very large (e.g. it will contain millions of nodes and/or arcs) deba@109: /// then it is worth reserving space for this amount before starting deba@109: /// to build the digraph. deba@109: /// \sa reserveNode deba@109: void reserveArc(int m) { arcs.reserve(m); }; deba@109: deba@149: /// \brief Node validity check deba@149: /// deba@149: /// This function gives back true if the given node is valid, alpar@209: /// ie. it is a real node of the graph. deba@149: /// deba@149: /// \warning A removed node (using Snapshot) could become valid again deba@149: /// when new nodes are added to the graph. deba@149: bool valid(Node n) const { return Parent::valid(n); } deba@149: deba@149: /// \brief Arc validity check deba@149: /// deba@149: /// This function gives back true if the given arc is valid, alpar@209: /// ie. it is a real arc of the graph. deba@149: /// deba@149: /// \warning A removed arc (using Snapshot) could become valid again deba@149: /// when new arcs are added to the graph. deba@149: bool valid(Arc a) const { return Parent::valid(a); } deba@149: deba@109: ///Clear the digraph. alpar@209: deba@109: ///Erase all the nodes and arcs from the digraph. deba@109: /// deba@109: void clear() { deba@109: Parent::clear(); deba@109: } deba@109: deba@109: ///Split a node. alpar@209: deba@109: ///This function splits a node. First a new node is added to the digraph, deba@109: ///then the source of each outgoing arc of \c n is moved to this new node. deba@109: ///If \c connect is \c true (this is the default value), then a new arc deba@109: ///from \c n to the newly created node is also added. deba@109: ///\return The newly created node. deba@109: /// deba@109: ///\note The Arcs deba@109: ///referencing a moved arc remain deba@109: ///valid. However InArc's and OutArc's deba@109: ///may be invalidated. 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@335: for(int i=nodes[b._id].first_out; i!=-1; i=arcs[i].next_out) { kpeter@335: arcs[i].source=b._id; kpeter@335: } deba@109: if(connect) addArc(n,b); deba@109: return b; deba@109: } deba@109: 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_numnodes.size(); alpar@209: arc_num=_graph->arcs.size(); deba@109: } deba@109: deba@109: ///Make a snapshot. deba@109: deba@109: ///Make a snapshot of the digraph. deba@109: /// deba@109: ///This function can be called more than once. In case of a repeated deba@109: ///call, the previous snapshot gets lost. kpeter@317: ///\param graph The digraph we make the snapshot of. alpar@209: void save(SmartDigraph &graph) deba@109: { alpar@209: _graph=&graph; 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: deba@109: ///Undo the changes until a snapshot created by save(). deba@109: /// deba@109: ///\note After you restored a state, you cannot restore deba@109: ///a later state, in other word you cannot add again the arcs deleted deba@109: ///by restore(). 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 nodes; deba@109: std::vector arcs; deba@109: deba@109: int first_free_arc; alpar@209: deba@109: public: alpar@209: deba@109: typedef SmartGraphBase Digraph; 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: alpar@427: operator Edge() const { alpar@427: 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: 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: deba@109: void next(Node& node) const { 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: deba@109: void next(Arc& arc) const { 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: deba@109: void next(Edge& arc) const { 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(nodes.size()); deba@149: } alpar@209: bool valid(Arc a) const { deba@149: return a._id >= 0 && a._id < static_cast(arcs.size()); deba@149: } alpar@209: bool valid(Edge e) const { alpar@209: return e._id >= 0 && 2 * e._id < static_cast(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 ExtendedSmartGraphBase; deba@109: deba@109: /// \ingroup graphs deba@109: /// deba@109: /// \brief A smart undirected graph class. deba@109: /// deba@109: /// This is a simple and fast graph implementation. deba@109: /// It is also quite memory efficient, but at the price deba@109: /// that it does support only limited (only stack-like) deba@109: /// node and arc deletions. alpar@209: /// Except from this it conforms to deba@109: /// the \ref concepts::Graph "Graph concept". deba@109: /// deba@109: /// It also has an deba@109: /// important extra feature that deba@109: /// its maps are real \ref concepts::ReferenceMap "reference map"s. deba@109: /// deba@109: /// \sa concepts::Graph. deba@109: /// deba@109: class SmartGraph : public ExtendedSmartGraphBase { deba@109: private: deba@109: deba@109: ///SmartGraph is \e not copy constructible. Use GraphCopy() instead. deba@109: deba@109: ///SmartGraph is \e not copy constructible. Use GraphCopy() instead. deba@109: /// deba@109: SmartGraph(const SmartGraph &) : ExtendedSmartGraphBase() {}; deba@109: deba@109: ///\brief Assignment of SmartGraph to another one is \e not allowed. deba@109: ///Use GraphCopy() instead. deba@109: deba@109: ///Assignment of SmartGraph to another one is \e not allowed. deba@109: ///Use GraphCopy() instead. deba@109: void operator=(const SmartGraph &) {} deba@109: deba@109: public: deba@109: deba@109: typedef ExtendedSmartGraphBase Parent; deba@109: deba@109: /// Constructor alpar@209: deba@109: /// Constructor. deba@109: /// deba@109: SmartGraph() {} deba@109: deba@109: ///Add a new node to the graph. alpar@209: deba@109: /// \return the new node. deba@109: /// deba@109: Node addNode() { return Parent::addNode(); } alpar@209: deba@109: ///Add a new edge to the graph. alpar@209: deba@109: ///Add a new edge to the graph with node \c s deba@109: ///and \c t. deba@109: ///\return the new edge. alpar@209: Edge addEdge(const Node& s, const Node& t) { alpar@209: return Parent::addEdge(s, t); deba@109: } deba@109: deba@149: /// \brief Node validity check deba@149: /// deba@149: /// This function gives back true if the given node is valid, alpar@209: /// ie. it is a real node of the graph. deba@149: /// deba@149: /// \warning A removed node (using Snapshot) could become valid again deba@149: /// when new nodes are added to the graph. deba@149: bool valid(Node n) const { return Parent::valid(n); } deba@149: deba@149: /// \brief Arc validity check deba@149: /// deba@149: /// This function gives back true if the given arc is valid, alpar@209: /// ie. it is a real arc of the graph. deba@149: /// deba@149: /// \warning A removed arc (using Snapshot) could become valid again deba@149: /// when new edges are added to the graph. deba@149: bool valid(Arc a) const { return Parent::valid(a); } deba@149: deba@149: /// \brief Edge validity check deba@149: /// deba@149: /// This function gives back true if the given edge is valid, alpar@209: /// ie. it is a real edge of the graph. deba@149: /// deba@149: /// \warning A removed edge (using Snapshot) could become valid again deba@149: /// when new edges are added to the graph. deba@149: bool valid(Edge e) const { return Parent::valid(e); } deba@149: deba@109: ///Clear the graph. alpar@209: deba@109: ///Erase all the nodes and edges from the graph. deba@109: /// deba@109: void clear() { deba@109: Parent::clear(); deba@109: } deba@109: 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 dir; deba@109: dir.push_back(arcFromId(n)); deba@109: dir.push_back(arcFromId(n-1)); alpar@209: Parent::notifier(Arc()).erase(dir); kpeter@337: nodes[arcs[n-1].target].first_out=arcs[n].next_out; kpeter@337: 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_numrestoreSnapshot(*this); deba@109: } deba@109: }; deba@109: }; alpar@209: deba@109: } //namespace lemon deba@109: deba@109: deba@109: #endif //LEMON_SMART_GRAPH_H