alpar@906: /* -*- C++ -*- alpar@906: * alpar@1956: * This file is a part of LEMON, a generic C++ optimization library alpar@1956: * alpar@1956: * Copyright (C) 2003-2006 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 { alpar@104: alpar@973: friend class SmatGraph; alpar@973: alpar@973: protected: alpar@104: struct NodeT alpar@104: { alpar@104: int first_in,first_out; alpar@157: NodeT() : first_in(-1), first_out(-1) {} alpar@104: }; alpar@104: struct EdgeT alpar@104: { alpar@986: int target, source, next_in, next_out; alpar@104: //FIXME: is this necessary? alpar@157: EdgeT() : next_in(-1), next_out(-1) {} 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: ///Number of nodes. alpar@813: int nodeNum() const { return nodes.size(); } alpar@813: ///Number of edges. alpar@813: int edgeNum() const { return edges.size(); } alpar@104: alpar@813: /// Maximum node ID. alpar@813: alpar@813: /// Maximum node ID. alpar@813: ///\sa id(Node) deba@1791: int maxNodeId() const { return nodes.size()-1; } alpar@813: /// Maximum edge ID. alpar@813: alpar@813: /// Maximum edge ID. alpar@813: ///\sa id(Edge) deba@1791: int maxEdgeId() const { return edges.size()-1; } alpar@108: alpar@2128: Node addNode() { alpar@2128: Node n; n.n=nodes.size(); alpar@2128: nodes.push_back(NodeT()); //FIXME: Hmmm... alpar@2128: return n; alpar@2128: } alpar@2128: alpar@2128: Edge addEdge(Node u, Node v) { alpar@2128: Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm... alpar@2128: edges[e.n].source=u.n; edges[e.n].target=v.n; alpar@2128: edges[e.n].next_out=nodes[u.n].first_out; alpar@2128: edges[e.n].next_in=nodes[v.n].first_in; alpar@2128: nodes[u.n].first_out=nodes[v.n].first_in=e.n; alpar@2128: alpar@2128: return e; alpar@2128: } alpar@2128: alpar@2128: alpar@986: Node source(Edge e) const { return edges[e.n].source; } alpar@986: Node target(Edge e) const { return edges[e.n].target; } alpar@104: alpar@813: /// Node ID. alpar@813: alpar@813: /// The ID of a valid Node is a nonnegative integer not greater than deba@1791: /// \ref maxNodeId(). The range of the ID's is not surely continuous deba@1791: /// and the greatest node ID can be actually less then \ref maxNodeId(). alpar@813: /// alpar@813: /// The ID of the \ref INVALID node is -1. alpar@813: ///\return The ID of the node \c v. alpar@713: static int id(Node v) { return v.n; } alpar@813: /// Edge ID. alpar@813: alpar@813: /// The ID of a valid Edge is a nonnegative integer not greater than deba@1791: /// \ref maxEdgeId(). The range of the ID's is not surely continuous deba@1791: /// and the greatest edge ID can be actually less then \ref maxEdgeId(). alpar@813: /// alpar@813: /// The ID of the \ref INVALID edge is -1. alpar@813: ///\return The ID of the edge \c e. alpar@713: static int id(Edge e) { return e.n; } alpar@104: deba@2076: /// \brief Returns the node from its \c id. deba@2076: /// deba@2076: /// Returns the node from its \c id. If there is not node deba@2076: /// with the given id the effect of the function is undefinied. deba@1791: static Node nodeFromId(int id) { return Node(id);} deba@1106: deba@2076: /// \brief Returns the edge from its \c id. deba@2076: /// deba@2076: /// Returns the edge from its \c id. If there is not edge deba@2076: /// with the given id the effect of the function is undefinied. 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: alpar@104: int n; alpar@164: Node(int nn) {n=nn;} alpar@104: public: alpar@164: Node() {} alpar@503: Node (Invalid) { n=-1; } alpar@164: bool operator==(const Node i) const {return n==i.n;} alpar@164: bool operator!=(const Node i) const {return n!=i.n;} alpar@164: bool operator<(const Node i) const {return n ExtendedSmartGraphBase; deba@937: deba@1791: /// \ingroup graphs alpar@1161: alpar@950: ///A smart graph class. deba@937: 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@2123: ///the \ref concept::Graph "Graph concept". deba@2111: ///\sa concept::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: alpar@1770: class Snapshot; alpar@1770: friend class Snapshot; alpar@973: alpar@2128: private: 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: /// alpar@2128: 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: protected: alpar@1770: void restoreSnapshot(const Snapshot &s) alpar@973: { alpar@1457: while(s.edge_numEdges 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(); alpar@2128: nodes[b.n].first_out=nodes[n.n].first_out; alpar@2128: nodes[n.n].first_out=-1; alpar@2128: for(int i=nodes[b.n].first_out;i!=-1;i++) edges[i].source=b.n; alpar@2128: if(connect) addEdge(n,b); deba@1718: return b; alpar@1284: } alpar@1284: alpar@1011: ///Class to make a snapshot of the graph and to restrore to it later. alpar@1011: alpar@1011: ///Class to make a snapshot of the graph and to restrore to it later. alpar@1011: /// alpar@1011: ///The newly added nodes and edges can be removed using the alpar@1011: ///restore() function. alpar@1011: ///\note After you restore a state, you cannot restore alpar@1011: ///a later state, in other word you cannot add again the edges deleted alpar@2132: ///by restore() using another one Snapshot instance. alpar@1011: /// alpar@1770: class Snapshot alpar@1011: { alpar@1011: SmartGraph *g; alpar@1011: protected: alpar@1011: friend class SmartGraph; alpar@1011: unsigned int node_num; alpar@1011: unsigned int edge_num; alpar@1011: public: zsuzska@1274: ///Default constructor. alpar@1011: zsuzska@1274: ///Default constructor. alpar@1011: ///To actually make a snapshot you must call save(). alpar@1011: /// alpar@1770: Snapshot() : g(0) {} alpar@1011: ///Constructor that immediately makes a snapshot alpar@1011: alpar@1011: ///This constructor immediately makes a snapshot of the graph. alpar@1011: ///\param _g The graph we make a snapshot of. alpar@1770: Snapshot(SmartGraph &_g) :g(&_g) { alpar@1011: node_num=g->nodes.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: /// alpar@1011: ///\todo This function might be called undo(). alpar@1011: alpar@1011: void restore() alpar@1011: { alpar@1770: g->restoreSnapshot(*this); alpar@1011: } alpar@1011: }; alpar@973: }; klao@1034: klao@1034: deba@2116: /**************** Undirected List Graph ****************/ deba@2116: deba@2116: typedef UGraphExtender > deba@2116: 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@2123: /// the \ref concept::UGraph "UGraph concept". deba@2116: /// \sa concept::UGraph. deba@2116: /// deba@2116: /// \todo Snapshot hasn't been implemented yet. deba@2116: /// deba@2116: class SmartUGraph : public ExtendedSmartUGraphBase { alpar@2128: private: 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() {}; 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 &) {} alpar@2128: public: alpar@2128: /// Constructor alpar@2128: alpar@2128: /// Constructor. alpar@2128: /// alpar@2128: SmartUGraph() {} 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@2116: Node(int _id) : id(_id) {} deba@2116: public: deba@2116: Node() {} deba@2116: 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@2116: static Node fromANodeId(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@2116: static Node fromBNodeId(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@2116: typedef BpUGraphExtender 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@2123: /// the \ref concept::BpUGraph "BpUGraph concept". deba@2116: /// \sa concept::BpUGraph. deba@2116: /// deba@2116: class SmartBpUGraph : public ExtendedSmartBpUGraphBase {}; deba@2116: deba@2116: deba@2116: /// @} alpar@921: } //namespace lemon alpar@104: alpar@157: alpar@921: #endif //LEMON_SMART_GRAPH_H