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 klao@1909: ///\brief SmartGraph and SmartUGraph classes. alpar@242: alpar@104: #include alpar@104: deba@1993: #include alpar@157: deba@1999: #include deba@1791: #include klao@1034: deba@1993: #include deba@1820: #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@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@1791: static Node nodeFromId(int id) { return Node(id);} deba@1106: deba@1791: static Edge edgeFromId(int id) { return Edge(id);} deba@1106: alpar@164: Node addNode() { alpar@164: Node n; n.n=nodes.size(); alpar@104: nodes.push_back(NodeT()); //FIXME: Hmmm... alpar@104: return n; alpar@104: } alpar@108: alpar@164: Edge addEdge(Node u, Node v) { alpar@164: Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm... alpar@986: edges[e.n].source=u.n; edges[e.n].target=v.n; alpar@104: edges[e.n].next_out=nodes[u.n].first_out; alpar@104: edges[e.n].next_in=nodes[v.n].first_in; alpar@104: nodes[u.n].first_out=nodes[v.n].first_in=e.n; alpar@108: alpar@104: return e; alpar@104: } alpar@104: deba@782: void clear() { deba@782: edges.clear(); deba@782: nodes.clear(); deba@782: } alpar@104: klao@946: 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 klao@959: ///the \ref concept::ExtendableGraph "ExtendableGraph" concept. klao@959: ///\sa concept::ExtendableGraph. 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@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@1284: Node split(Node n, bool connect = true) alpar@1284: { deba@1718: Node b = _split(n,connect); deba@1718: return b; alpar@1284: } 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@1770: ///by restore() using another 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: klao@1034: /**************** Undirected List Graph ****************/ klao@1034: deba@1979: typedef UGraphExtender > deba@1979: ExtendedSmartUGraphBase; klao@1034: klao@1909: /// \ingroup graphs alpar@1035: /// klao@1909: /// \brief A smart undirected graph class. alpar@1035: /// klao@1909: /// This is a simple and fast undirected graph implementation. klao@1909: /// It is also quite memory efficient, but at the price klao@1909: /// that it does support only limited (only stack-like) klao@1909: /// node and edge deletions. klao@1909: /// Except from this it conforms to klao@1909: /// the \ref concept::UGraph "UGraph" concept. klao@1909: /// \sa concept::UGraph. klao@1909: /// klao@1909: /// \todo Snapshot hasn't been implemented yet. klao@1909: /// klao@1909: class SmartUGraph : public ExtendedSmartUGraphBase { klao@1034: }; klao@1034: deba@1820: deba@1910: class SmartBpUGraphBase { deba@1820: public: deba@1820: deba@1820: class NodeSetError : public LogicError { deba@1820: virtual const char* exceptionName() const { deba@1910: return "lemon::SmartBpUGraph::NodeSetError"; deba@1820: } deba@1820: }; deba@1820: deba@1820: protected: deba@1820: deba@1820: struct NodeT { deba@1820: int first; deba@1820: NodeT() {} deba@1820: NodeT(int _first) : first(_first) {} deba@1820: }; deba@1820: deba@1820: struct EdgeT { deba@1910: int aNode, next_out; deba@1910: int bNode, next_in; deba@1820: }; deba@1820: deba@1910: std::vector aNodes; deba@1910: std::vector bNodes; deba@1820: deba@1820: std::vector edges; deba@1820: deba@1820: public: deba@1820: deba@1820: class Node { deba@1910: friend class SmartBpUGraphBase; deba@1820: protected: deba@1820: int id; deba@1820: deba@1820: Node(int _id) : id(_id) {} deba@1820: public: deba@1820: Node() {} deba@1820: Node(Invalid) { id = -1; } deba@1820: bool operator==(const Node i) const {return id==i.id;} deba@1820: bool operator!=(const Node i) const {return id!=i.id;} deba@1820: bool operator<(const Node i) const {return id 0) { deba@1910: node.id = 2 * aNodes.size() - 2; deba@1820: } else { deba@1910: node.id = 2 * bNodes.size() - 1; deba@1820: } deba@1820: } deba@1820: void next(Node& node) const { deba@1820: node.id -= 2; deba@1820: if (node.id == -2) { deba@1910: node.id = 2 * bNodes.size() - 1; deba@1820: } deba@1820: } deba@1820: deba@1820: void first(Edge& edge) const { deba@1820: edge.id = edges.size() - 1; deba@1820: } deba@1820: void next(Edge& edge) const { deba@1820: --edge.id; deba@1820: } deba@1820: deba@1910: void firstOut(Edge& edge, const Node& node) const { deba@1820: LEMON_ASSERT((node.id & 1) == 0, NodeSetError()); deba@1910: edge.id = aNodes[node.id >> 1].first; deba@1820: } deba@1910: void nextOut(Edge& edge) const { deba@1910: edge.id = edges[edge.id].next_out; deba@1820: } deba@1820: deba@1910: void firstIn(Edge& edge, const Node& node) const { deba@1820: LEMON_ASSERT((node.id & 1) == 1, NodeSetError()); deba@1910: edge.id = bNodes[node.id >> 1].first; deba@1820: } deba@1910: void nextIn(Edge& edge) const { deba@1910: edge.id = edges[edge.id].next_in; deba@1820: } deba@1820: deba@1820: static int id(const Node& node) { deba@1820: return node.id; deba@1820: } deba@1820: static Node nodeFromId(int id) { deba@1820: return Node(id); deba@1820: } deba@1820: int maxNodeId() const { deba@1910: return aNodes.size() > bNodes.size() ? deba@1910: aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1; deba@1820: } deba@1820: deba@1820: static int id(const Edge& edge) { deba@1820: return edge.id; deba@1820: } deba@1820: static Edge edgeFromId(int id) { deba@1820: return Edge(id); deba@1820: } deba@1820: int maxEdgeId() const { deba@1820: return edges.size(); deba@1820: } deba@1820: deba@1910: static int aNodeId(const Node& node) { deba@1820: return node.id >> 1; deba@1820: } deba@1995: static Node fromANodeId(int id) { deba@1820: return Node(id << 1); deba@1820: } deba@1910: int maxANodeId() const { deba@1910: return aNodes.size(); deba@1820: } deba@1820: deba@1910: static int bNodeId(const Node& node) { deba@1820: return node.id >> 1; deba@1820: } deba@1910: static Node fromBNodeId(int id) { deba@1820: return Node((id << 1) + 1); deba@1820: } deba@1910: int maxBNodeId() const { deba@1910: return bNodes.size(); deba@1820: } deba@1820: deba@1910: Node aNode(const Edge& edge) const { deba@1910: return Node(edges[edge.id].aNode); deba@1820: } deba@1910: Node bNode(const Edge& edge) const { deba@1910: return Node(edges[edge.id].bNode); deba@1820: } deba@1820: deba@1910: static bool aNode(const Node& node) { deba@1820: return (node.id & 1) == 0; deba@1820: } deba@1820: deba@1910: static bool bNode(const Node& node) { deba@1820: return (node.id & 1) == 1; deba@1820: } deba@1820: deba@1910: Node addANode() { deba@1820: NodeT nodeT; deba@1820: nodeT.first = -1; deba@1910: aNodes.push_back(nodeT); deba@1910: return Node(aNodes.size() * 2 - 2); deba@1820: } deba@1820: deba@1910: Node addBNode() { deba@1820: NodeT nodeT; deba@1820: nodeT.first = -1; deba@1910: bNodes.push_back(nodeT); deba@1910: return Node(bNodes.size() * 2 - 1); deba@1820: } deba@1820: deba@1820: Edge addEdge(const Node& source, const Node& target) { deba@1820: LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError()); deba@1820: EdgeT edgeT; deba@1820: if ((source.id & 1) == 0) { deba@1910: edgeT.aNode = source.id; deba@1910: edgeT.bNode = target.id; deba@1820: } else { deba@1910: edgeT.aNode = target.id; deba@1910: edgeT.bNode = source.id; deba@1820: } deba@1910: edgeT.next_out = aNodes[edgeT.aNode >> 1].first; deba@1910: aNodes[edgeT.aNode >> 1].first = edges.size(); deba@1910: edgeT.next_in = bNodes[edgeT.bNode >> 1].first; deba@1910: bNodes[edgeT.bNode >> 1].first = edges.size(); deba@1820: edges.push_back(edgeT); deba@1820: return Edge(edges.size() - 1); deba@1820: } deba@1820: deba@1820: void clear() { deba@1910: aNodes.clear(); deba@1910: bNodes.clear(); deba@1820: edges.clear(); deba@1820: } deba@1820: deba@1820: }; deba@1820: deba@1820: deba@1979: typedef BpUGraphExtender< BpUGraphBaseExtender< deba@1979: SmartBpUGraphBase> > ExtendedSmartBpUGraphBase; deba@1820: deba@1910: /// \ingroup graphs deba@1910: /// deba@1910: /// \brief A smart bipartite undirected graph class. deba@1910: /// deba@1910: /// This is a simple and fast bipartite undirected graph implementation. deba@1910: /// It is also quite memory efficient, but at the price deba@1910: /// that it does not support node and edge deletions. deba@1910: /// Except from this it conforms to deba@1910: /// the \ref concept::BpUGraph "BpUGraph" concept. deba@1910: /// \sa concept::BpUGraph. deba@1910: /// deba@1910: class SmartBpUGraph : public ExtendedSmartBpUGraphBase {}; deba@1820: alpar@950: alpar@407: /// @} alpar@921: } //namespace lemon alpar@104: alpar@157: alpar@921: #endif //LEMON_SMART_GRAPH_H