alpar@906: /* -*- C++ -*- alpar@906: * alpar@1956: * This file is a part of LEMON, a generic C++ optimization library alpar@1956: * alpar@2553: * Copyright (C) 2003-2008 alpar@1956: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@1359: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@906: * alpar@906: * Permission to use, modify and distribute this software is granted alpar@906: * provided that this copyright notice appears in all copies. For alpar@906: * precise terms see the accompanying LICENSE file. alpar@906: * alpar@906: * This software is provided "AS IS" with no warranty of any kind, alpar@906: * express or implied, and with no claim as to its suitability for any alpar@906: * purpose. alpar@906: * alpar@906: */ alpar@105: alpar@921: #ifndef LEMON_SMART_GRAPH_H alpar@921: #define LEMON_SMART_GRAPH_H alpar@104: klao@491: ///\ingroup graphs alpar@242: ///\file deba@2116: ///\brief SmartGraph and SmartUGraph classes. alpar@242: alpar@104: #include alpar@104: deba@1993: #include alpar@157: deba@2116: #include deba@1791: #include klao@1034: deba@1993: #include deba@2116: #include deba@782: deba@1979: #include deba@1979: alpar@921: namespace lemon { alpar@104: alpar@973: class SmartGraph; alpar@969: ///Base of SmartGraph alpar@969: alpar@969: ///Base of SmartGraph alpar@969: /// klao@946: class SmartGraphBase { deba@2190: protected: alpar@104: alpar@104: struct NodeT alpar@104: { deba@2190: int first_in, first_out; deba@2190: NodeT() {} alpar@104: }; alpar@104: struct EdgeT alpar@104: { alpar@986: int target, source, next_in, next_out; deba@2190: EdgeT() {} alpar@104: }; alpar@104: alpar@104: std::vector nodes; alpar@129: alpar@104: std::vector edges; alpar@104: alpar@185: alpar@104: public: deba@782: klao@946: typedef SmartGraphBase Graph; alpar@104: alpar@164: class Node; alpar@164: class Edge; alpar@108: alpar@104: alpar@104: public: alpar@104: klao@946: SmartGraphBase() : nodes(), edges() { } deba@1718: SmartGraphBase(const SmartGraphBase &_g) deba@1718: : nodes(_g.nodes), edges(_g.edges) { } alpar@104: klao@977: typedef True NodeNumTag; klao@977: typedef True EdgeNumTag; klao@977: alpar@813: int nodeNum() const { return nodes.size(); } alpar@813: int edgeNum() const { return edges.size(); } alpar@104: deba@1791: int maxNodeId() const { return nodes.size()-1; } deba@1791: int maxEdgeId() const { return edges.size()-1; } alpar@108: alpar@2128: Node addNode() { deba@2190: int n = nodes.size(); deba@2190: nodes.push_back(NodeT()); deba@2190: nodes[n].first_in = -1; deba@2190: nodes[n].first_out = -1; deba@2190: return Node(n); alpar@2128: } alpar@2128: alpar@2128: Edge addEdge(Node u, Node v) { deba@2190: int n = edges.size(); deba@2190: edges.push_back(EdgeT()); deba@2190: edges[n].source = u.id; deba@2190: edges[n].target = v.id; deba@2190: edges[n].next_out = nodes[u.id].first_out; deba@2190: edges[n].next_in = nodes[v.id].first_in; deba@2190: nodes[u.id].first_out = nodes[v.id].first_in = n; alpar@2128: deba@2190: return Edge(n); alpar@2128: } alpar@2128: deba@2190: void clear() { deba@2190: edges.clear(); deba@2190: nodes.clear(); deba@2190: } alpar@2128: deba@2190: Node source(Edge e) const { return Node(edges[e.id].source); } deba@2190: Node target(Edge e) const { return Node(edges[e.id].target); } alpar@104: deba@2190: static int id(Node v) { return v.id; } deba@2190: static int id(Edge e) { return e.id; } alpar@104: deba@1791: static Node nodeFromId(int id) { return Node(id);} deba@1791: static Edge edgeFromId(int id) { return Edge(id);} deba@1106: alpar@164: class Node { klao@946: friend class SmartGraphBase; alpar@973: friend class SmartGraph; alpar@104: alpar@104: protected: deba@2190: int id; deba@2190: explicit Node(int _id) : id(_id) {} alpar@104: public: alpar@164: Node() {} deba@2190: Node (Invalid) : id(-1) {} deba@2190: bool operator==(const Node i) const {return id == i.id;} deba@2190: bool operator!=(const Node i) const {return id != i.id;} deba@2190: bool operator<(const Node i) const {return id < i.id;} alpar@104: }; alpar@104: alpar@104: alpar@164: class Edge { klao@946: friend class SmartGraphBase; alpar@973: friend class SmartGraph; alpar@185: alpar@104: protected: deba@2190: int id; deba@2190: explicit Edge(int _id) : id(_id) {} alpar@706: public: alpar@164: Edge() { } deba@2190: Edge (Invalid) : id(-1) {} deba@2190: bool operator==(const Edge i) const {return id == i.id;} deba@2190: bool operator!=(const Edge i) const {return id != i.id;} deba@2190: bool operator<(const Edge i) const {return id < i.id;} klao@946: }; alpar@905: klao@946: void first(Node& node) const { deba@2190: node.id = nodes.size() - 1; klao@946: } klao@946: klao@946: static void next(Node& node) { deba@2190: --node.id; klao@946: } klao@946: klao@946: void first(Edge& edge) const { deba@2190: edge.id = edges.size() - 1; klao@946: } klao@946: klao@946: static void next(Edge& edge) { deba@2190: --edge.id; klao@946: } klao@946: klao@946: void firstOut(Edge& edge, const Node& node) const { deba@2190: edge.id = nodes[node.id].first_out; klao@946: } klao@946: klao@946: void nextOut(Edge& edge) const { deba@2190: edge.id = edges[edge.id].next_out; klao@946: } klao@946: klao@946: void firstIn(Edge& edge, const Node& node) const { deba@2190: edge.id = nodes[node.id].first_in; klao@946: } alpar@104: klao@946: void nextIn(Edge& edge) const { deba@2190: edge.id = edges[edge.id].next_in; klao@946: } alpar@105: alpar@104: }; alpar@185: deba@1979: typedef GraphExtender ExtendedSmartGraphBase; deba@937: deba@2498: ///\ingroup graphs deba@2498: /// deba@2498: ///\brief A smart graph class. deba@2498: /// alpar@950: ///This is a simple and fast graph implementation. alpar@950: ///It is also quite memory efficient, but at the price alpar@974: ///that it does support only limited (only stack-like) alpar@974: ///node and edge deletions. alpar@950: ///It conforms to alpar@2260: ///the \ref concepts::Graph "Graph concept" with an alpar@2256: ///important extra feature that alpar@2260: ///its maps are real \ref concepts::ReferenceMap "reference map"s. alpar@2256: /// alpar@2260: ///\sa concepts::Graph. alpar@950: /// alpar@950: ///\author Alpar Juttner deba@1669: class SmartGraph : public ExtendedSmartGraphBase { alpar@969: public: deba@1979: deba@1979: typedef ExtendedSmartGraphBase Parent; deba@1979: deba@2190: private: alpar@973: alpar@2128: ///SmartGraph is \e not copy constructible. Use GraphCopy() instead. alpar@2128: alpar@2128: ///SmartGraph is \e not copy constructible. Use GraphCopy() instead. alpar@2128: /// deba@2190: SmartGraph(const SmartGraph &) : ExtendedSmartGraphBase() {}; alpar@2132: ///\brief Assignment of SmartGraph to another one is \e not allowed. alpar@2128: ///Use GraphCopy() instead. alpar@2128: alpar@2132: ///Assignment of SmartGraph to another one is \e not allowed. alpar@2128: ///Use GraphCopy() instead. alpar@2128: void operator=(const SmartGraph &) {} alpar@1011: alpar@1011: public: alpar@2128: alpar@2128: /// Constructor alpar@2128: alpar@2128: /// Constructor. alpar@2128: /// alpar@2128: SmartGraph() {}; alpar@2128: alpar@2128: ///Add a new node to the graph. alpar@2128: alpar@2128: /// \return the new node. alpar@2128: /// alpar@2128: Node addNode() { return Parent::addNode(); } alpar@2128: alpar@2128: ///Add a new edge to the graph. alpar@2128: alpar@2128: ///Add a new edge to the graph with source node \c s alpar@2128: ///and target node \c t. alpar@2128: ///\return the new edge. alpar@2128: Edge addEdge(const Node& s, const Node& t) { alpar@2128: return Parent::addEdge(s, t); alpar@2128: } alpar@2128: deba@2456: /// \brief Using this it is possible to avoid the superfluous memory deba@2456: /// allocation. deba@2456: deba@2456: /// Using this it is possible to avoid the superfluous memory deba@2456: /// allocation: if you know that the graph you want to build will deba@2456: /// be very large (e.g. it will contain millions of nodes and/or edges) deba@2456: /// then it is worth reserving space for this amount before starting deba@2456: /// to build the graph. deba@2456: /// \sa reserveEdge deba@2456: void reserveNode(int n) { nodes.reserve(n); }; deba@2456: deba@2456: /// \brief Using this it is possible to avoid the superfluous memory deba@2456: /// allocation. deba@2456: deba@2456: /// Using this it is possible to avoid the superfluous memory deba@2456: /// allocation: if you know that the graph you want to build will deba@2456: /// be very large (e.g. it will contain millions of nodes and/or edges) deba@2456: /// then it is worth reserving space for this amount before starting deba@2456: /// to build the graph. deba@2456: /// \sa reserveNode deba@2456: void reserveEdge(int m) { edges.reserve(m); }; deba@2456: deba@2190: ///Clear the graph. alpar@2128: deba@2190: ///Erase all the nodes and edges from the graph. deba@2190: /// alpar@2128: void clear() { deba@2190: Parent::clear(); alpar@2128: } alpar@1284: alpar@1284: ///Split a node. alpar@1284: alpar@1284: ///This function splits a node. First a new node is added to the graph, alpar@1284: ///then the source of each outgoing edge of \c n is moved to this new node. alpar@1284: ///If \c connect is \c true (this is the default value), then a new edge alpar@1284: ///from \c n to the newly created node is also added. alpar@1284: ///\return The newly created node. alpar@1284: /// alpar@1284: ///\note The Edges alpar@1284: ///referencing a moved edge remain alpar@1284: ///valid. However InEdge's and OutEdge's alpar@1284: ///may be invalidated. alpar@1770: ///\warning This functionality cannot be used together with the Snapshot alpar@1284: ///feature. alpar@1284: ///\todo It could be implemented in a bit faster way. alpar@2128: Node split(Node n, bool connect = true) alpar@1284: { alpar@2128: Node b = addNode(); deba@2190: nodes[b.id].first_out=nodes[n.id].first_out; deba@2190: nodes[n.id].first_out=-1; deba@2190: for(int i=nodes[b.id].first_out;i!=-1;i++) edges[i].source=b.id; alpar@2128: if(connect) addEdge(n,b); deba@1718: return b; alpar@1284: } alpar@1284: deba@2190: public: deba@2190: deba@2190: class Snapshot; deba@2190: deba@2190: protected: deba@2190: deba@2190: void restoreSnapshot(const Snapshot &s) deba@2190: { deba@2190: while(s.edge_numnodes.size(); alpar@1011: edge_num=g->edges.size(); alpar@1011: } alpar@1011: alpar@1011: ///Make a snapshot. alpar@1011: alpar@1011: ///Make a snapshot of the graph. alpar@1011: /// alpar@1011: ///This function can be called more than once. In case of a repeated alpar@1011: ///call, the previous snapshot gets lost. alpar@1011: ///\param _g The graph we make the snapshot of. alpar@1011: void save(SmartGraph &_g) alpar@1011: { alpar@1011: g=&_g; alpar@1011: node_num=g->nodes.size(); alpar@1011: edge_num=g->edges.size(); alpar@1011: } alpar@1011: alpar@1011: ///Undo the changes until a snapshot. alpar@1011: alpar@1011: ///Undo the changes until a snapshot created by save(). alpar@1011: /// alpar@1011: ///\note After you restored a state, you cannot restore alpar@1011: ///a later state, in other word you cannot add again the edges deleted alpar@1011: ///by restore(). alpar@1011: void restore() alpar@1011: { alpar@1770: g->restoreSnapshot(*this); alpar@1011: } alpar@1011: }; alpar@973: }; klao@1034: klao@1034: deba@2338: class SmartUGraphBase { deba@2116: deba@2338: protected: deba@2338: deba@2338: struct NodeT { deba@2338: int first_out; deba@2338: }; deba@2338: deba@2338: struct EdgeT { deba@2338: int target; deba@2338: int next_out; deba@2338: }; deba@2338: deba@2338: std::vector nodes; deba@2338: std::vector edges; deba@2338: deba@2338: int first_free_edge; deba@2338: deba@2338: public: deba@2338: deba@2338: typedef SmartUGraphBase Graph; deba@2342: deba@2342: class Node; deba@2342: class Edge; deba@2342: class UEdge; deba@2338: deba@2338: class Node { deba@2338: friend class SmartUGraphBase; deba@2338: protected: deba@2338: deba@2338: int id; deba@2338: explicit Node(int pid) { id = pid;} deba@2338: deba@2338: public: deba@2338: Node() {} deba@2338: Node (Invalid) { id = -1; } deba@2338: bool operator==(const Node& node) const {return id == node.id;} deba@2338: bool operator!=(const Node& node) const {return id != node.id;} deba@2338: bool operator<(const Node& node) const {return id < node.id;} deba@2338: }; deba@2338: deba@2338: class UEdge { deba@2338: friend class SmartUGraphBase; deba@2338: protected: deba@2338: deba@2338: int id; deba@2338: explicit UEdge(int pid) { id = pid;} deba@2338: deba@2338: public: deba@2338: UEdge() {} deba@2338: UEdge (Invalid) { id = -1; } deba@2338: bool operator==(const UEdge& edge) const {return id == edge.id;} deba@2338: bool operator!=(const UEdge& edge) const {return id != edge.id;} deba@2338: bool operator<(const UEdge& edge) const {return id < edge.id;} deba@2338: }; deba@2338: deba@2338: class Edge { deba@2338: friend class SmartUGraphBase; deba@2338: protected: deba@2338: deba@2338: int id; deba@2338: explicit Edge(int pid) { id = pid;} deba@2338: deba@2338: public: deba@2343: operator UEdge() const { return uEdgeFromId(id / 2); } deba@2338: deba@2338: Edge() {} deba@2338: Edge (Invalid) { id = -1; } deba@2338: bool operator==(const Edge& edge) const {return id == edge.id;} deba@2338: bool operator!=(const Edge& edge) const {return id != edge.id;} deba@2338: bool operator<(const Edge& edge) const {return id < edge.id;} deba@2338: }; deba@2338: deba@2338: deba@2338: deba@2338: SmartUGraphBase() deba@2338: : nodes(), edges() {} deba@2338: deba@2338: deba@2338: int maxNodeId() const { return nodes.size()-1; } deba@2338: int maxUEdgeId() const { return edges.size() / 2 - 1; } deba@2338: int maxEdgeId() const { return edges.size()-1; } deba@2338: deba@2338: Node source(Edge e) const { return Node(edges[e.id ^ 1].target); } deba@2338: Node target(Edge e) const { return Node(edges[e.id].target); } deba@2338: deba@2338: Node source(UEdge e) const { return Node(edges[2 * e.id].target); } deba@2338: Node target(UEdge e) const { return Node(edges[2 * e.id + 1].target); } deba@2338: deba@2338: static bool direction(Edge e) { deba@2338: return (e.id & 1) == 1; deba@2338: } deba@2338: deba@2338: static Edge direct(UEdge e, bool d) { deba@2338: return Edge(e.id * 2 + (d ? 1 : 0)); deba@2338: } deba@2338: deba@2338: void first(Node& node) const { deba@2338: node.id = nodes.size() - 1; deba@2338: } deba@2338: deba@2338: void next(Node& node) const { deba@2338: --node.id; deba@2338: } deba@2338: deba@2338: void first(Edge& edge) const { deba@2338: edge.id = edges.size() - 1; deba@2338: } deba@2338: deba@2338: void next(Edge& edge) const { deba@2338: --edge.id; deba@2338: } deba@2338: deba@2338: void first(UEdge& edge) const { deba@2338: edge.id = edges.size() / 2 - 1; deba@2338: } deba@2338: deba@2338: void next(UEdge& edge) const { deba@2338: --edge.id; deba@2338: } deba@2338: deba@2338: void firstOut(Edge &edge, const Node& v) const { deba@2338: edge.id = nodes[v.id].first_out; deba@2338: } deba@2338: void nextOut(Edge &edge) const { deba@2338: edge.id = edges[edge.id].next_out; deba@2338: } deba@2338: deba@2338: void firstIn(Edge &edge, const Node& v) const { deba@2338: edge.id = ((nodes[v.id].first_out) ^ 1); deba@2339: if (edge.id == -2) edge.id = -1; deba@2338: } deba@2338: void nextIn(Edge &edge) const { deba@2338: edge.id = ((edges[edge.id ^ 1].next_out) ^ 1); deba@2339: if (edge.id == -2) edge.id = -1; deba@2338: } deba@2338: deba@2338: void firstInc(UEdge &edge, bool& d, const Node& v) const { deba@2338: int de = nodes[v.id].first_out; deba@2381: if (de != -1) { deba@2381: edge.id = de / 2; deba@2381: d = ((de & 1) == 1); deba@2381: } else { deba@2381: edge.id = -1; deba@2381: d = true; deba@2381: } deba@2338: } deba@2338: void nextInc(UEdge &edge, bool& d) const { deba@2338: int de = (edges[(edge.id * 2) | (d ? 1 : 0)].next_out); deba@2381: if (de != -1) { deba@2381: edge.id = de / 2; deba@2381: d = ((de & 1) == 1); deba@2381: } else { deba@2381: edge.id = -1; deba@2381: d = true; deba@2381: } deba@2338: } deba@2338: deba@2338: static int id(Node v) { return v.id; } deba@2338: static int id(Edge e) { return e.id; } deba@2338: static int id(UEdge e) { return e.id; } deba@2338: deba@2338: static Node nodeFromId(int id) { return Node(id);} deba@2338: static Edge edgeFromId(int id) { return Edge(id);} deba@2338: static UEdge uEdgeFromId(int id) { return UEdge(id);} deba@2338: deba@2338: Node addNode() { deba@2338: int n = nodes.size(); deba@2338: nodes.push_back(NodeT()); deba@2338: nodes[n].first_out = -1; deba@2338: deba@2338: return Node(n); deba@2338: } deba@2338: deba@2338: UEdge addEdge(Node u, Node v) { deba@2338: int n = edges.size(); deba@2338: edges.push_back(EdgeT()); deba@2338: edges.push_back(EdgeT()); deba@2338: deba@2338: edges[n].target = u.id; deba@2338: edges[n | 1].target = v.id; deba@2338: deba@2338: edges[n].next_out = nodes[v.id].first_out; deba@2338: nodes[v.id].first_out = n; deba@2498: deba@2498: edges[n | 1].next_out = nodes[u.id].first_out; deba@2338: nodes[u.id].first_out = (n | 1); deba@2338: deba@2338: return UEdge(n / 2); deba@2338: } deba@2338: deba@2338: void clear() { deba@2338: edges.clear(); deba@2338: nodes.clear(); deba@2338: } deba@2338: deba@2338: }; deba@2338: deba@2338: typedef UGraphExtender ExtendedSmartUGraphBase; deba@2116: deba@2116: /// \ingroup graphs deba@2116: /// deba@2116: /// \brief A smart undirected graph class. deba@2116: /// deba@2116: /// This is a simple and fast undirected graph implementation. deba@2116: /// It is also quite memory efficient, but at the price deba@2116: /// that it does support only limited (only stack-like) deba@2116: /// node and edge deletions. deba@2116: /// Except from this it conforms to alpar@2260: /// the \ref concepts::UGraph "UGraph concept". alpar@2256: /// alpar@2256: ///It also has an alpar@2256: ///important extra feature that alpar@2260: ///its maps are real \ref concepts::ReferenceMap "reference map"s. alpar@2256: /// alpar@2260: /// \sa concepts::UGraph. deba@2116: /// deba@2116: class SmartUGraph : public ExtendedSmartUGraphBase { alpar@2128: private: deba@2190: alpar@2128: ///SmartUGraph is \e not copy constructible. Use UGraphCopy() instead. alpar@2128: alpar@2128: ///SmartUGraph is \e not copy constructible. Use UGraphCopy() instead. alpar@2128: /// alpar@2128: SmartUGraph(const SmartUGraph &) : ExtendedSmartUGraphBase() {}; deba@2190: alpar@2132: ///\brief Assignment of SmartUGraph to another one is \e not allowed. alpar@2128: ///Use UGraphCopy() instead. alpar@2128: alpar@2132: ///Assignment of SmartUGraph to another one is \e not allowed. alpar@2128: ///Use UGraphCopy() instead. alpar@2128: void operator=(const SmartUGraph &) {} deba@2190: alpar@2128: public: deba@2190: deba@2190: typedef ExtendedSmartUGraphBase Parent; deba@2338: typedef Parent::OutEdgeIt IncEdgeIt; deba@2190: alpar@2128: /// Constructor alpar@2128: alpar@2128: /// Constructor. alpar@2128: /// alpar@2128: SmartUGraph() {} deba@2190: deba@2190: ///Add a new node to the graph. deba@2190: deba@2190: /// \return the new node. deba@2190: /// deba@2190: Node addNode() { return Parent::addNode(); } deba@2190: deba@2190: ///Add a new undirected edge to the graph. deba@2190: deba@2190: ///Add a new undirected edge to the graph with node \c s deba@2190: ///and \c t. deba@2190: ///\return the new undirected edge. deba@2190: UEdge addEdge(const Node& s, const Node& t) { deba@2190: return Parent::addEdge(s, t); deba@2190: } deba@2190: deba@2190: ///Clear the graph. deba@2190: deba@2190: ///Erase all the nodes and edges from the graph. deba@2190: /// deba@2190: void clear() { deba@2190: Parent::clear(); deba@2190: } deba@2190: deba@2190: public: deba@2190: deba@2190: class Snapshot; deba@2190: deba@2190: protected: deba@2190: deba@2338: void saveSnapshot(Snapshot &s) deba@2338: { deba@2386: s.graph = this; deba@2338: s.node_num = nodes.size(); deba@2338: s.edge_num = edges.size(); deba@2338: } deba@2190: deba@2190: void restoreSnapshot(const Snapshot &s) deba@2190: { deba@2190: while(s.edge_num dir; deba@2338: dir.push_back(edgeFromId(n)); deba@2338: dir.push_back(edgeFromId(n-1)); deba@2381: Parent::notifier(Edge()).erase(dir); deba@2338: nodes[edges[n].target].first_out=edges[n].next_out; deba@2338: nodes[edges[n-1].target].first_out=edges[n-1].next_out; deba@2338: edges.pop_back(); deba@2190: edges.pop_back(); deba@2190: } deba@2190: while(s.node_numrestoreSnapshot(*this); deba@2190: } deba@2190: }; deba@2116: }; deba@2116: deba@2116: deba@2116: class SmartBpUGraphBase { deba@2116: public: deba@2116: deba@2116: class NodeSetError : public LogicError { deba@2162: public: alpar@2151: virtual const char* what() const throw() { deba@2116: return "lemon::SmartBpUGraph::NodeSetError"; deba@2116: } deba@2116: }; deba@2116: deba@2116: protected: deba@2116: deba@2116: struct NodeT { deba@2116: int first; deba@2116: NodeT() {} deba@2116: NodeT(int _first) : first(_first) {} deba@2116: }; deba@2116: deba@2116: struct UEdgeT { deba@2116: int aNode, next_out; deba@2116: int bNode, next_in; deba@2116: }; deba@2116: deba@2116: std::vector aNodes; deba@2116: std::vector bNodes; deba@2116: deba@2116: std::vector edges; deba@2116: deba@2116: public: deba@2116: deba@2116: class Node { deba@2116: friend class SmartBpUGraphBase; deba@2116: protected: deba@2116: int id; deba@2116: deba@2190: explicit Node(int _id) : id(_id) {} deba@2116: public: deba@2116: Node() {} deba@2190: Node(Invalid) : id(-1) {} deba@2116: bool operator==(const Node i) const {return id==i.id;} deba@2116: bool operator!=(const Node i) const {return id!=i.id;} deba@2116: bool operator<(const Node i) const {return id 0) { deba@2116: node.id = 2 * aNodes.size() - 2; deba@2116: } else { deba@2116: node.id = 2 * bNodes.size() - 1; deba@2116: } deba@2116: } deba@2116: void next(Node& node) const { deba@2116: node.id -= 2; deba@2116: if (node.id == -2) { deba@2116: node.id = 2 * bNodes.size() - 1; deba@2116: } deba@2116: } deba@2116: deba@2116: void first(UEdge& edge) const { deba@2116: edge.id = edges.size() - 1; deba@2116: } deba@2116: void next(UEdge& edge) const { deba@2116: --edge.id; deba@2116: } deba@2116: deba@2116: void firstFromANode(UEdge& edge, const Node& node) const { deba@2116: LEMON_ASSERT((node.id & 1) == 0, NodeSetError()); deba@2116: edge.id = aNodes[node.id >> 1].first; deba@2116: } deba@2116: void nextFromANode(UEdge& edge) const { deba@2116: edge.id = edges[edge.id].next_out; deba@2116: } deba@2116: deba@2116: void firstFromBNode(UEdge& edge, const Node& node) const { deba@2116: LEMON_ASSERT((node.id & 1) == 1, NodeSetError()); deba@2116: edge.id = bNodes[node.id >> 1].first; deba@2116: } deba@2116: void nextFromBNode(UEdge& edge) const { deba@2116: edge.id = edges[edge.id].next_in; deba@2116: } deba@2116: deba@2116: static int id(const Node& node) { deba@2116: return node.id; deba@2116: } deba@2116: static Node nodeFromId(int id) { deba@2116: return Node(id); deba@2116: } deba@2116: int maxNodeId() const { deba@2116: return aNodes.size() > bNodes.size() ? deba@2116: aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1; deba@2116: } deba@2116: deba@2116: static int id(const UEdge& edge) { deba@2116: return edge.id; deba@2116: } deba@2116: static UEdge uEdgeFromId(int id) { deba@2116: return UEdge(id); deba@2116: } deba@2116: int maxUEdgeId() const { deba@2116: return edges.size(); deba@2116: } deba@2116: deba@2116: static int aNodeId(const Node& node) { deba@2116: return node.id >> 1; deba@2116: } deba@2231: static Node nodeFromANodeId(int id) { deba@2116: return Node(id << 1); deba@2116: } deba@2116: int maxANodeId() const { deba@2116: return aNodes.size(); deba@2116: } deba@2116: deba@2116: static int bNodeId(const Node& node) { deba@2116: return node.id >> 1; deba@2116: } deba@2231: static Node nodeFromBNodeId(int id) { deba@2116: return Node((id << 1) + 1); deba@2116: } deba@2116: int maxBNodeId() const { deba@2116: return bNodes.size(); deba@2116: } deba@2116: deba@2116: Node aNode(const UEdge& edge) const { deba@2116: return Node(edges[edge.id].aNode); deba@2116: } deba@2116: Node bNode(const UEdge& edge) const { deba@2116: return Node(edges[edge.id].bNode); deba@2116: } deba@2116: deba@2116: static bool aNode(const Node& node) { deba@2116: return (node.id & 1) == 0; deba@2116: } deba@2116: deba@2116: static bool bNode(const Node& node) { deba@2116: return (node.id & 1) == 1; deba@2116: } deba@2116: deba@2116: Node addANode() { deba@2116: NodeT nodeT; deba@2116: nodeT.first = -1; deba@2116: aNodes.push_back(nodeT); deba@2116: return Node(aNodes.size() * 2 - 2); deba@2116: } deba@2116: deba@2116: Node addBNode() { deba@2116: NodeT nodeT; deba@2116: nodeT.first = -1; deba@2116: bNodes.push_back(nodeT); deba@2116: return Node(bNodes.size() * 2 - 1); deba@2116: } deba@2116: deba@2116: UEdge addEdge(const Node& source, const Node& target) { deba@2116: LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError()); deba@2116: UEdgeT edgeT; deba@2116: if ((source.id & 1) == 0) { deba@2116: edgeT.aNode = source.id; deba@2116: edgeT.bNode = target.id; deba@2116: } else { deba@2116: edgeT.aNode = target.id; deba@2116: edgeT.bNode = source.id; deba@2116: } deba@2116: edgeT.next_out = aNodes[edgeT.aNode >> 1].first; deba@2116: aNodes[edgeT.aNode >> 1].first = edges.size(); deba@2116: edgeT.next_in = bNodes[edgeT.bNode >> 1].first; deba@2116: bNodes[edgeT.bNode >> 1].first = edges.size(); deba@2116: edges.push_back(edgeT); deba@2116: return UEdge(edges.size() - 1); deba@2116: } deba@2116: deba@2116: void clear() { deba@2116: aNodes.clear(); deba@2116: bNodes.clear(); deba@2116: edges.clear(); deba@2116: } deba@2116: deba@2116: typedef True NodeNumTag; deba@2116: int nodeNum() const { return aNodes.size() + bNodes.size(); } deba@2116: int aNodeNum() const { return aNodes.size(); } deba@2116: int bNodeNum() const { return bNodes.size(); } deba@2116: deba@2116: typedef True EdgeNumTag; deba@2116: int uEdgeNum() const { return edges.size(); } deba@2116: deba@2116: }; deba@2116: deba@2116: deba@2231: typedef BpUGraphExtender > deba@2231: ExtendedSmartBpUGraphBase; deba@2116: deba@2116: /// \ingroup graphs deba@2116: /// deba@2116: /// \brief A smart bipartite undirected graph class. deba@2116: /// deba@2116: /// This is a simple and fast bipartite undirected graph implementation. deba@2116: /// It is also quite memory efficient, but at the price deba@2116: /// that it does not support node and edge deletions. deba@2116: /// Except from this it conforms to alpar@2260: /// the \ref concepts::BpUGraph "BpUGraph concept". alpar@2256: /// alpar@2256: ///It also has an alpar@2256: ///important extra feature that alpar@2260: ///its maps are real \ref concepts::ReferenceMap "reference map"s. alpar@2256: /// alpar@2260: /// \sa concepts::BpUGraph. deba@2116: /// deba@2190: class SmartBpUGraph : public ExtendedSmartBpUGraphBase { deba@2190: private: deba@2190: deba@2190: /// \brief SmartBpUGraph is \e not copy constructible. deba@2190: /// deba@2190: ///SmartBpUGraph is \e not copy constructible. deba@2190: SmartBpUGraph(const SmartBpUGraph &) : ExtendedSmartBpUGraphBase() {}; deba@2190: deba@2190: /// \brief Assignment of SmartBpUGraph to another one is \e not deba@2190: /// allowed. deba@2190: /// deba@2190: /// Assignment of SmartBpUGraph to another one is \e not allowed. deba@2190: void operator=(const SmartBpUGraph &) {} deba@2190: deba@2190: public: deba@2190: deba@2190: typedef ExtendedSmartBpUGraphBase Parent; deba@2190: deba@2190: ///Constructor deba@2190: deba@2190: ///Constructor. deba@2190: /// deba@2190: SmartBpUGraph() : ExtendedSmartBpUGraphBase() {} deba@2190: deba@2190: ///Add a new ANode to the graph. deba@2190: deba@2190: /// \return the new node. deba@2190: /// deba@2190: Node addANode() { return Parent::addANode(); } deba@2190: deba@2190: ///Add a new BNode to the graph. deba@2190: deba@2190: /// \return the new node. deba@2190: /// deba@2190: Node addBNode() { return Parent::addBNode(); } deba@2190: deba@2190: ///Add a new undirected edge to the graph. deba@2190: deba@2190: ///Add a new undirected edge to the graph with node \c s deba@2190: ///and \c t. deba@2190: ///\return the new undirected edge. deba@2190: UEdge addEdge(const Node& s, const Node& t) { deba@2190: return Parent::addEdge(s, t); deba@2190: } deba@2190: deba@2190: ///Clear the graph. deba@2190: deba@2190: ///Erase all the nodes and edges from the graph. deba@2190: /// deba@2190: void clear() { deba@2190: Parent::clear(); deba@2190: } deba@2190: deba@2190: public: deba@2190: deba@2190: class Snapshot; deba@2190: deba@2190: protected: deba@2190: deba@2190: void restoreSnapshot(const Snapshot &s) deba@2190: { deba@2190: while(s.edge_num dir; deba@2190: dir.push_back(Parent::direct(edge, true)); deba@2190: dir.push_back(Parent::direct(edge, false)); deba@2381: Parent::notifier(Edge()).erase(dir); deba@2190: aNodes[edges.back().aNode >> 1].first=edges.back().next_out; deba@2190: bNodes[edges.back().bNode >> 1].first=edges.back().next_in; deba@2190: edges.pop_back(); deba@2190: } deba@2190: while(s.anode_numaNodes.size(); deba@2190: bnode_num=g->bNodes.size(); deba@2190: edge_num=g->edges.size(); deba@2190: } deba@2190: deba@2190: ///Make a snapshot. deba@2190: deba@2190: ///Make a snapshot of the graph. deba@2190: /// deba@2190: ///This function can be called more than once. In case of a repeated deba@2190: ///call, the previous snapshot gets lost. deba@2190: ///\param _g The graph we make the snapshot of. deba@2190: void save(SmartBpUGraph &_g) deba@2190: { deba@2190: g=&_g; deba@2190: anode_num=g->aNodes.size(); deba@2190: bnode_num=g->bNodes.size(); deba@2190: edge_num=g->edges.size(); deba@2190: } deba@2190: deba@2190: ///Undo the changes until a snapshot. deba@2190: deba@2190: ///Undo the changes until a snapshot created by save(). deba@2190: /// deba@2190: ///\note After you restored a state, you cannot restore deba@2190: ///a later state, in other word you cannot add again the edges deleted deba@2190: ///by restore(). deba@2190: void restore() deba@2190: { deba@2190: g->restoreSnapshot(*this); deba@2190: } deba@2190: }; deba@2190: }; deba@2116: deba@2116: deba@2116: /// @} alpar@921: } //namespace lemon alpar@104: alpar@157: alpar@921: #endif //LEMON_SMART_GRAPH_H