alpar@906: /* -*- C++ -*- ladanyi@1435: * lemon/smart_graph.h - Part of LEMON, a generic C++ optimization library alpar@906: * alpar@1875: * Copyright (C) 2006 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@1692: ///\brief SmartGraph and UndirSmartGraph classes. alpar@242: alpar@104: #include alpar@104: alpar@921: #include alpar@157: deba@1307: #include deba@1307: #include deba@1307: #include deba@1307: #include deba@1307: #include deba@1791: #include klao@1034: klao@977: #include deba@1820: #include deba@782: 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: alpar@973: 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: klao@1034: typedef ClearableUndirGraphExtender< klao@1034: ExtendableUndirGraphExtender< klao@1034: MappableUndirGraphExtender< klao@1034: IterableUndirGraphExtender< klao@1034: AlterableUndirGraphExtender< deba@1669: UndirGraphExtender > > > > > ExtendedUndirSmartGraphBase; klao@1034: alpar@1035: ///A smart undirected graph class. alpar@1035: alpar@1035: ///This is a simple and fast undirected graph implementation. alpar@1035: ///It is also quite memory efficient, but at the price alpar@1035: ///that it does support only limited (only stack-like) alpar@1035: ///node and edge deletions. alpar@1035: ///Except from this it conforms to alpar@1035: ///the \ref concept::UndirGraph "UndirGraph" concept. alpar@1035: ///\sa concept::UndirGraph. alpar@1035: /// alpar@1770: ///\todo Snapshot hasn't been implemented yet. alpar@1035: /// deba@1669: class UndirSmartGraph : public ExtendedUndirSmartGraphBase { klao@1034: }; klao@1034: deba@1820: deba@1820: class SmartUndirBipartiteGraphBase { deba@1820: public: deba@1820: deba@1820: class NodeSetError : public LogicError { deba@1820: virtual const char* exceptionName() const { deba@1820: return "lemon::FullUndirBipartiteGraph::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@1820: int upper, next_down; deba@1820: int lower, next_up; deba@1820: }; deba@1820: deba@1820: std::vector upperNodes; deba@1820: std::vector lowerNodes; deba@1820: deba@1820: std::vector edges; deba@1820: deba@1820: public: deba@1820: deba@1820: class Node { deba@1820: friend class SmartUndirBipartiteGraphBase; 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@1820: node.id = 2 * upperNodes.size() - 2; deba@1820: } else { deba@1820: node.id = 2 * lowerNodes.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@1820: node.id = 2 * lowerNodes.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@1820: void firstDown(Edge& edge, const Node& node) const { deba@1820: LEMON_ASSERT((node.id & 1) == 0, NodeSetError()); deba@1820: edge.id = upperNodes[node.id >> 1].first; deba@1820: } deba@1820: void nextDown(Edge& edge) const { deba@1820: edge.id = edges[edge.id].next_down; deba@1820: } deba@1820: deba@1820: void firstUp(Edge& edge, const Node& node) const { deba@1820: LEMON_ASSERT((node.id & 1) == 1, NodeSetError()); deba@1820: edge.id = lowerNodes[node.id >> 1].first; deba@1820: } deba@1820: void nextUp(Edge& edge) const { deba@1820: edge.id = edges[edge.id].next_up; 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@1820: return upperNodes.size() > lowerNodes.size() ? deba@1820: upperNodes.size() * 2 - 2 : lowerNodes.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@1820: static int upperId(const Node& node) { deba@1820: return node.id >> 1; deba@1820: } deba@1820: static Node fromUpperId(int id, Node) { deba@1820: return Node(id << 1); deba@1820: } deba@1820: int maxUpperId() const { deba@1820: return upperNodes.size(); deba@1820: } deba@1820: deba@1820: static int lowerId(const Node& node) { deba@1820: return node.id >> 1; deba@1820: } deba@1820: static Node fromLowerId(int id) { deba@1820: return Node((id << 1) + 1); deba@1820: } deba@1820: int maxLowerId() const { deba@1820: return lowerNodes.size(); deba@1820: } deba@1820: deba@1820: Node upperNode(const Edge& edge) const { deba@1820: return Node(edges[edge.id].upper); deba@1820: } deba@1820: Node lowerNode(const Edge& edge) const { deba@1820: return Node(edges[edge.id].lower); deba@1820: } deba@1820: deba@1820: static bool upper(const Node& node) { deba@1820: return (node.id & 1) == 0; deba@1820: } deba@1820: deba@1820: static bool lower(const Node& node) { deba@1820: return (node.id & 1) == 1; deba@1820: } deba@1820: deba@1820: Node addUpperNode() { deba@1820: NodeT nodeT; deba@1820: nodeT.first = -1; deba@1820: upperNodes.push_back(nodeT); deba@1820: return Node(upperNodes.size() * 2 - 2); deba@1820: } deba@1820: deba@1820: Node addLowerNode() { deba@1820: NodeT nodeT; deba@1820: nodeT.first = -1; deba@1820: lowerNodes.push_back(nodeT); deba@1820: return Node(lowerNodes.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@1820: edgeT.upper = source.id; deba@1820: edgeT.lower = target.id; deba@1820: } else { deba@1820: edgeT.upper = target.id; deba@1820: edgeT.lower = source.id; deba@1820: } deba@1820: edgeT.next_down = upperNodes[edgeT.upper >> 1].first; deba@1820: upperNodes[edgeT.upper >> 1].first = edges.size(); deba@1820: edgeT.next_up = lowerNodes[edgeT.lower >> 1].first; deba@1820: lowerNodes[edgeT.lower >> 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@1820: upperNodes.clear(); deba@1820: lowerNodes.clear(); deba@1820: edges.clear(); deba@1820: } deba@1820: deba@1820: }; deba@1820: deba@1820: deba@1820: typedef ClearableUndirBipartiteGraphExtender< deba@1820: ExtendableUndirBipartiteGraphExtender< deba@1820: MappableUndirBipartiteGraphExtender< deba@1820: IterableUndirBipartiteGraphExtender< deba@1820: AlterableUndirBipartiteGraphExtender< deba@1820: UndirBipartiteGraphExtender < deba@1820: SmartUndirBipartiteGraphBase> > > > > > deba@1820: ExtendedSmartUndirBipartiteGraphBase; deba@1820: deba@1820: deba@1820: class SmartUndirBipartiteGraph : deba@1820: public ExtendedSmartUndirBipartiteGraphBase { deba@1820: }; deba@1820: alpar@950: alpar@407: /// @} alpar@921: } //namespace lemon alpar@104: alpar@157: alpar@921: #endif //LEMON_SMART_GRAPH_H