alpar@948: /* -*- C++ -*- ladanyi@1435: * lemon/list_graph.h - Part of LEMON, a generic C++ optimization library alpar@948: * alpar@1164: * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@1359: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@948: * alpar@948: * Permission to use, modify and distribute this software is granted alpar@948: * provided that this copyright notice appears in all copies. For alpar@948: * precise terms see the accompanying LICENSE file. alpar@948: * alpar@948: * This software is provided "AS IS" with no warranty of any kind, alpar@948: * express or implied, and with no claim as to its suitability for any alpar@948: * purpose. alpar@948: * alpar@948: */ alpar@395: alpar@921: #ifndef LEMON_LIST_GRAPH_H alpar@921: #define LEMON_LIST_GRAPH_H alpar@395: alpar@948: ///\ingroup graphs alpar@948: ///\file deba@1692: ///\brief ListGraph, UndirListGraph classes. alpar@948: deba@1307: #include deba@1307: #include deba@1307: #include deba@1307: #include deba@1307: #include deba@1307: #include deba@1791: #include deba@782: deba@1774: #include deba@1774: alpar@1011: #include deba@782: alpar@921: namespace lemon { alpar@395: klao@946: class ListGraphBase { alpar@406: alpar@949: protected: klao@946: struct NodeT { deba@1470: int first_in, first_out; alpar@397: int prev, next; alpar@395: }; klao@946: klao@946: struct EdgeT { alpar@986: int target, source; alpar@397: int prev_in, prev_out; alpar@397: int next_in, next_out; alpar@395: }; alpar@395: alpar@395: std::vector nodes; klao@946: alpar@397: int first_node; klao@946: alpar@397: int first_free_node; klao@946: alpar@395: std::vector edges; klao@946: alpar@397: int first_free_edge; alpar@395: deba@782: public: alpar@395: klao@946: typedef ListGraphBase Graph; alpar@397: klao@946: class Node { marci@975: friend class ListGraphBase; klao@946: protected: alpar@395: klao@946: int id; klao@946: Node(int pid) { id = pid;} alpar@395: klao@946: public: klao@946: Node() {} klao@946: Node (Invalid) { id = -1; } klao@946: bool operator==(const Node& node) const {return id == node.id;} klao@946: bool operator!=(const Node& node) const {return id != node.id;} klao@946: bool operator<(const Node& node) const {return id < node.id;} klao@946: }; deba@782: klao@946: class Edge { marci@975: friend class ListGraphBase; klao@946: protected: deba@782: klao@946: int id; klao@946: Edge(int pid) { id = pid;} alpar@395: klao@946: public: klao@946: Edge() {} klao@946: Edge (Invalid) { id = -1; } klao@946: bool operator==(const Edge& edge) const {return id == edge.id;} klao@946: bool operator!=(const Edge& edge) const {return id != edge.id;} klao@946: bool operator<(const Edge& edge) const {return id < edge.id;} klao@946: }; klao@946: klao@946: klao@946: klao@946: ListGraphBase() deba@782: : nodes(), first_node(-1), deba@782: first_free_node(-1), edges(), first_free_edge(-1) {} deba@782: alpar@395: 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; } klao@946: 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@395: alpar@986: Node source(Edge e) const { return edges[e.id].source; } alpar@986: Node target(Edge e) const { return edges[e.id].target; } alpar@395: alpar@395: klao@946: void first(Node& node) const { klao@946: node.id = first_node; klao@946: } klao@946: klao@946: void next(Node& node) const { klao@946: node.id = nodes[node.id].next; klao@946: } klao@946: klao@946: klao@946: void first(Edge& e) const { klao@946: int n; klao@946: for(n = first_node; klao@946: n!=-1 && nodes[n].first_in == -1; klao@946: n = nodes[n].next); klao@946: e.id = (n == -1) ? -1 : nodes[n].first_in; klao@946: } klao@946: klao@946: void next(Edge& edge) const { klao@946: if (edges[edge.id].next_in != -1) { klao@946: edge.id = edges[edge.id].next_in; klao@946: } else { klao@946: int n; alpar@986: for(n = nodes[edges[edge.id].target].next; klao@946: n!=-1 && nodes[n].first_in == -1; klao@946: n = nodes[n].next); klao@946: edge.id = (n == -1) ? -1 : nodes[n].first_in; klao@946: } klao@946: } klao@946: klao@946: void firstOut(Edge &e, const Node& v) const { klao@946: e.id = nodes[v.id].first_out; klao@946: } klao@946: void nextOut(Edge &e) const { klao@946: e.id=edges[e.id].next_out; klao@946: } klao@946: klao@946: void firstIn(Edge &e, const Node& v) const { klao@946: e.id = nodes[v.id].first_in; klao@946: } klao@946: void nextIn(Edge &e) const { klao@946: e.id=edges[e.id].next_in; klao@946: } klao@946: alpar@813: klao@946: static int id(Node v) { return v.id; } klao@946: static int id(Edge e) { return e.id; } alpar@395: deba@1791: static Node nodeFromId(int id) { return Node(id);} deba@1791: static Edge edgeFromId(int id) { return Edge(id);} deba@1106: alpar@397: /// Adds a new node to the graph. alpar@397: alpar@813: /// \warning It adds the new node to the front of the list. alpar@397: /// (i.e. the lastly added node becomes the first.) klao@946: Node addNode() { alpar@397: int n; alpar@397: klao@946: if(first_free_node==-1) { klao@946: n = nodes.size(); klao@946: nodes.push_back(NodeT()); klao@946: } else { alpar@397: n = first_free_node; alpar@397: first_free_node = nodes[n].next; alpar@397: } alpar@397: alpar@397: nodes[n].next = first_node; alpar@397: if(first_node != -1) nodes[first_node].prev = n; alpar@397: first_node = n; alpar@397: nodes[n].prev = -1; alpar@397: alpar@397: nodes[n].first_in = nodes[n].first_out = -1; alpar@397: klao@946: return Node(n); alpar@395: } alpar@395: alpar@395: Edge addEdge(Node u, Node v) { klao@946: int n; klao@946: klao@946: if (first_free_edge == -1) { klao@946: n = edges.size(); klao@946: edges.push_back(EdgeT()); klao@946: } else { alpar@397: n = first_free_edge; alpar@397: first_free_edge = edges[n].next_in; alpar@397: } alpar@397: alpar@986: edges[n].source = u.id; alpar@986: edges[n].target = v.id; alpar@395: klao@946: edges[n].next_out = nodes[u.id].first_out; klao@946: if(nodes[u.id].first_out != -1) { klao@946: edges[nodes[u.id].first_out].prev_out = n; klao@946: } klao@946: klao@946: edges[n].next_in = nodes[v.id].first_in; klao@946: if(nodes[v.id].first_in != -1) { klao@946: edges[nodes[v.id].first_in].prev_in = n; klao@946: } klao@946: alpar@397: edges[n].prev_in = edges[n].prev_out = -1; alpar@397: klao@946: nodes[u.id].first_out = nodes[v.id].first_in = n; alpar@397: klao@946: return Edge(n); alpar@395: } alpar@774: klao@946: void erase(const Node& node) { klao@946: int n = node.id; klao@946: klao@946: if(nodes[n].next != -1) { klao@946: nodes[nodes[n].next].prev = nodes[n].prev; klao@946: } klao@946: klao@946: if(nodes[n].prev != -1) { klao@946: nodes[nodes[n].prev].next = nodes[n].next; klao@946: } else { klao@946: first_node = nodes[n].next; klao@946: } klao@946: klao@946: nodes[n].next = first_free_node; klao@946: first_free_node = n; alpar@395: alpar@774: } alpar@774: klao@946: void erase(const Edge& edge) { klao@946: int n = edge.id; alpar@397: klao@946: if(edges[n].next_in!=-1) { alpar@397: edges[edges[n].next_in].prev_in = edges[n].prev_in; klao@946: } klao@946: klao@946: if(edges[n].prev_in!=-1) { alpar@397: edges[edges[n].prev_in].next_in = edges[n].next_in; klao@946: } else { alpar@986: nodes[edges[n].target].first_in = edges[n].next_in; klao@946: } klao@946: alpar@397: klao@946: if(edges[n].next_out!=-1) { alpar@397: edges[edges[n].next_out].prev_out = edges[n].prev_out; klao@946: } klao@946: klao@946: if(edges[n].prev_out!=-1) { alpar@397: edges[edges[n].prev_out].next_out = edges[n].next_out; klao@946: } else { alpar@986: nodes[edges[n].source].first_out = edges[n].next_out; klao@946: } alpar@397: alpar@397: edges[n].next_in = first_free_edge; alpar@695: first_free_edge = n; alpar@397: alpar@397: } alpar@397: alpar@397: void clear() { deba@782: edges.clear(); deba@782: nodes.clear(); klao@946: first_node = first_free_node = first_free_edge = -1; deba@937: } deba@937: alpar@949: protected: alpar@1546: void _changeTarget(Edge e, Node n) alpar@949: { alpar@949: if(edges[e.id].next_in != -1) alpar@949: edges[edges[e.id].next_in].prev_in = edges[e.id].prev_in; alpar@949: if(edges[e.id].prev_in != -1) alpar@949: edges[edges[e.id].prev_in].next_in = edges[e.id].next_in; alpar@986: else nodes[edges[e.id].target].first_in = edges[e.id].next_in; deba@1702: if (nodes[n.id].first_in != -1) { deba@1702: edges[nodes[n.id].first_in].prev_in = e.id; deba@1702: } alpar@986: edges[e.id].target = n.id; alpar@949: edges[e.id].prev_in = -1; alpar@949: edges[e.id].next_in = nodes[n.id].first_in; alpar@949: nodes[n.id].first_in = e.id; alpar@949: } alpar@1546: void _changeSource(Edge e, Node n) alpar@949: { alpar@949: if(edges[e.id].next_out != -1) alpar@949: edges[edges[e.id].next_out].prev_out = edges[e.id].prev_out; alpar@949: if(edges[e.id].prev_out != -1) alpar@949: edges[edges[e.id].prev_out].next_out = edges[e.id].next_out; alpar@986: else nodes[edges[e.id].source].first_out = edges[e.id].next_out; deba@1702: if (nodes[n.id].first_out != -1) { deba@1702: edges[nodes[n.id].first_out].prev_out = e.id; deba@1702: } alpar@986: edges[e.id].source = n.id; alpar@949: edges[e.id].prev_out = -1; alpar@949: edges[e.id].next_out = nodes[n.id].first_out; alpar@949: nodes[n.id].first_out = e.id; alpar@949: } alpar@949: alpar@919: }; deba@909: deba@1669: typedef ErasableGraphExtender< deba@1669: ClearableGraphExtender< deba@1669: ExtendableGraphExtender< deba@1669: MappableGraphExtender< deba@1669: IterableGraphExtender< deba@1791: AlterableGraphExtender< deba@1791: GraphExtender > > > > > > ExtendedListGraphBase; alpar@400: deba@1718: /// \addtogroup graphs deba@1718: /// @{ alpar@400: alpar@948: ///A list graph class. alpar@400: alpar@948: ///This is a simple and fast erasable graph implementation. alpar@948: /// alpar@1010: ///It addition that it conforms to the alpar@1010: ///\ref concept::ErasableGraph "ErasableGraph" concept, alpar@1010: ///it also provides several additional useful extra functionalities. klao@959: ///\sa concept::ErasableGraph. deba@782: deba@1669: class ListGraph : public ExtendedListGraphBase alpar@948: { alpar@948: public: alpar@1546: /// Changes the target of \c e to \c n alpar@948: alpar@1546: /// Changes the target of \c e to \c n alpar@948: /// alpar@1010: ///\note The Edge's and OutEdge's alpar@1546: ///referencing the changed edge remain alpar@1010: ///valid. However InEdge's are invalidated. deba@1718: void changeTarget(Edge e, Node n) { deba@1718: _changeTarget(e,n); deba@1718: } alpar@1546: /// Changes the source of \c e to \c n alpar@948: alpar@1546: /// Changes the source of \c e to \c n alpar@948: /// alpar@1010: ///\note The Edge's and InEdge's alpar@1546: ///referencing the changed edge remain alpar@1010: ///valid. However OutEdge's are invalidated. deba@1718: void changeSource(Edge e, Node n) { deba@1718: _changeSource(e,n); deba@1718: } alpar@949: alpar@1010: /// Invert the direction of an edge. alpar@1010: alpar@1010: ///\note The Edge's alpar@1546: ///referencing the changed edge remain alpar@1010: ///valid. However OutEdge's and InEdge's are invalidated. alpar@1010: void reverseEdge(Edge e) { alpar@1010: Node t=target(e); alpar@1546: _changeTarget(e,source(e)); alpar@1546: _changeSource(e,t); alpar@1010: } alpar@1010: alpar@1010: ///Using this it possible to avoid the superfluous memory allocation. alpar@1010: alpar@949: ///Using this it possible to avoid the superfluous memory allocation. alpar@949: ///\todo more docs... alpar@949: void reserveEdge(int n) { edges.reserve(n); }; alpar@1010: alpar@1010: ///Contract two nodes. alpar@1010: alpar@1010: ///This function contracts two nodes. alpar@1010: /// alpar@1010: ///Node \p b will be removed but instead of deleting alpar@1010: ///its neighboring edges, they will be joined to \p a. alpar@1010: ///The last parameter \p r controls whether to remove loops. \c true alpar@1010: ///means that loops will be removed. alpar@1010: /// alpar@1010: ///\note The Edges alpar@1281: ///referencing a moved edge remain alpar@1010: ///valid. However InEdge's and OutEdge's alpar@1010: ///may be invalidated. deba@1718: void contract(Node a, Node b, bool r = true) alpar@1010: { alpar@1010: for(OutEdgeIt e(*this,b);e!=INVALID;) { alpar@1010: OutEdgeIt f=e; alpar@1010: ++f; alpar@1010: if(r && target(e)==a) erase(e); alpar@1546: else changeSource(e,a); alpar@1010: e=f; alpar@1010: } alpar@1010: for(InEdgeIt e(*this,b);e!=INVALID;) { alpar@1010: InEdgeIt f=e; alpar@1010: ++f; alpar@1010: if(r && source(e)==a) erase(e); alpar@1546: else changeTarget(e,a); alpar@1010: e=f; alpar@1010: } alpar@1010: erase(b); alpar@1010: } alpar@1011: alpar@1281: ///Split a node. alpar@1011: 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@1281: ///If \c connect is \c true (this is the default value), then a new edge alpar@1281: ///from \c n to the newly created node is also added. alpar@1281: ///\return The newly created node. alpar@1281: /// alpar@1281: ///\note The Edges alpar@1281: ///referencing a moved edge remain alpar@1281: ///valid. However InEdge's and OutEdge's alpar@1281: ///may be invalidated. alpar@1770: ///\warning This functionality cannot be used together with the Snapshot alpar@1284: ///feature. alpar@1281: ///\todo It could be implemented in a bit faster way. alpar@1281: Node split(Node n, bool connect = true) alpar@1281: { alpar@1281: Node b = addNode(); alpar@1281: for(OutEdgeIt e(*this,n);e!=INVALID;) { alpar@1281: OutEdgeIt f=e; alpar@1281: ++f; alpar@1546: changeSource(e,b); alpar@1281: e=f; alpar@1281: } alpar@1281: if(connect) addEdge(n,b); alpar@1281: return b; alpar@1281: } alpar@1281: alpar@1812: ///Split an edge. alpar@1812: alpar@1812: ///This function splits an edge. First a new node \c b is added to the graph, alpar@1812: ///then the original edge is re-targetes to \c b. Finally an edge alpar@1812: ///from \c b to the original target is added. alpar@1812: ///\return The newly created node. alpar@1812: ///\warning This functionality cannot be used together with the Snapshot alpar@1812: ///feature. alpar@1812: Node split(Edge e) alpar@1812: { alpar@1812: Node b = addNode(); alpar@1812: addEdge(b,target(e)); alpar@1812: changeTarget(e,b); alpar@1812: return b; alpar@1812: } alpar@1812: 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: /// alpar@1011: ///\warning Edge and node deletions cannot be restored. alpar@1770: ///\warning Snapshots cannot be nested. alpar@1770: class Snapshot : protected AlterationNotifier::ObserverBase, deba@1039: protected AlterationNotifier::ObserverBase alpar@1011: { deba@1774: public: deba@1774: deba@1774: class UnsupportedOperation : public LogicError { deba@1774: public: deba@1774: virtual const char* exceptionName() const { deba@1774: return "lemon::ListGraph::Snapshot::UnsupportedOperation"; deba@1774: } deba@1774: }; deba@1774: deba@1774: alpar@1011: protected: alpar@1011: alpar@1011: ListGraph *g; alpar@1011: std::list added_nodes; alpar@1011: std::list added_edges; alpar@1011: alpar@1011: bool active; alpar@1011: virtual void add(const Node& n) { alpar@1011: added_nodes.push_back(n); alpar@1011: }; alpar@1011: virtual void erase(const Node&) alpar@1011: { deba@1774: throw UnsupportedOperation(); alpar@1011: } alpar@1011: virtual void add(const Edge& n) { alpar@1011: added_edges.push_back(n); alpar@1011: }; alpar@1011: virtual void erase(const Edge&) alpar@1011: { deba@1774: throw UnsupportedOperation(); alpar@1011: } alpar@1011: alpar@1457: ///\bug What is this used for? alpar@1457: /// alpar@1457: virtual void build() {} alpar@1457: ///\bug What is this used for? alpar@1457: /// alpar@1457: virtual void clear() {} alpar@1457: alpar@1011: void regist(ListGraph &_g) { alpar@1011: g=&_g; deba@1039: AlterationNotifier::ObserverBase:: deba@1040: attach(g->getNotifier(Node())); deba@1039: AlterationNotifier::ObserverBase:: deba@1040: attach(g->getNotifier(Edge())); alpar@1011: } alpar@1011: alpar@1011: void deregist() { deba@1039: AlterationNotifier::ObserverBase:: alpar@1011: detach(); deba@1039: AlterationNotifier::ObserverBase:: alpar@1011: detach(); alpar@1011: g=0; alpar@1011: } deba@1774: alpar@1011: public: alpar@1011: ///Default constructur. alpar@1011: alpar@1011: ///Default constructur. 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(ListGraph &_g) { alpar@1011: regist(_g); alpar@1011: } alpar@1011: ///\bug Is it necessary? alpar@1011: /// alpar@1770: ~Snapshot() alpar@1011: { alpar@1011: if(g) deregist(); 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(ListGraph &_g) alpar@1011: { alpar@1011: if(g!=&_g) { alpar@1011: if(g) deregist(); alpar@1011: regist(_g); alpar@1011: } alpar@1011: added_nodes.clear(); alpar@1011: added_edges.clear(); alpar@1011: } alpar@1011: alpar@1011: ///Undo the changes until the last snapshot. alpar@1011: alpar@1011: ///Undo the changes until last snapshot created by save(). alpar@1011: /// alpar@1011: ///\todo This function might be called undo(). alpar@1011: void restore() { alpar@1457: ListGraph &old_g=*g; alpar@1011: deregist(); alpar@1011: while(!added_edges.empty()) { alpar@1457: old_g.erase(added_edges.front()); alpar@1011: added_edges.pop_front(); alpar@1011: } alpar@1011: while(!added_nodes.empty()) { alpar@1457: old_g.erase(added_nodes.front()); alpar@1011: added_nodes.pop_front(); alpar@1011: } alpar@1011: } alpar@1011: }; alpar@1011: alpar@949: }; klao@1034: alpar@1555: ///@} klao@1034: klao@1034: /**************** Undirected List Graph ****************/ klao@1034: klao@1034: typedef ErasableUndirGraphExtender< klao@1034: ClearableUndirGraphExtender< klao@1034: ExtendableUndirGraphExtender< klao@1034: MappableUndirGraphExtender< klao@1034: IterableUndirGraphExtender< klao@1034: AlterableUndirGraphExtender< deba@1669: UndirGraphExtender > > > > > > ExtendedUndirListGraphBase; klao@1034: deba@1718: /// \addtogroup graphs deba@1718: /// @{ alpar@1555: alpar@1035: ///An undirected list graph class. alpar@1035: alpar@1035: ///This is a simple and fast erasable undirected graph implementation. alpar@1035: /// alpar@1035: ///It conforms to the alpar@1035: ///\ref concept::UndirGraph "UndirGraph" concept. alpar@1035: /// alpar@1035: ///\sa concept::UndirGraph. alpar@1035: /// alpar@1770: ///\todo Snapshot, reverseEdge(), changeTarget(), changeSource(), contract() alpar@1161: ///haven't been implemented yet. alpar@1035: /// deba@1669: class UndirListGraph : public ExtendedUndirListGraphBase { deba@1718: public: deba@1718: typedef ExtendedUndirListGraphBase Parent; deba@1718: /// \brief Changes the target of \c e to \c n deba@1718: /// deba@1718: /// Changes the target of \c e to \c n deba@1718: /// deba@1718: /// \note The Edge's and OutEdge's deba@1718: /// referencing the changed edge remain deba@1718: /// valid. However InEdge's are invalidated. deba@1718: void changeTarget(UndirEdge e, Node n) { deba@1718: _changeTarget(e,n); deba@1718: } deba@1718: /// Changes the source of \c e to \c n deba@1718: /// deba@1718: /// Changes the source of \c e to \c n deba@1718: /// deba@1718: ///\note The Edge's and InEdge's deba@1718: ///referencing the changed edge remain deba@1718: ///valid. However OutEdge's are invalidated. deba@1718: void changeSource(UndirEdge e, Node n) { deba@1718: _changeSource(e,n); deba@1718: } deba@1718: /// \brief Contract two nodes. deba@1718: /// deba@1718: /// This function contracts two nodes. deba@1718: /// deba@1718: /// Node \p b will be removed but instead of deleting deba@1718: /// its neighboring edges, they will be joined to \p a. deba@1718: /// The last parameter \p r controls whether to remove loops. \c true deba@1718: /// means that loops will be removed. deba@1718: /// deba@1718: /// \note The Edges deba@1718: /// referencing a moved edge remain deba@1718: /// valid. deba@1718: void contract(Node a, Node b, bool r = true) { deba@1718: for(IncEdgeIt e(*this, b); e!=INVALID;) { deba@1718: IncEdgeIt f = e; ++f; deba@1718: if (r && runningNode(e) == a) { deba@1718: erase(e); deba@1718: } else if (source(e) == b) { deba@1718: changeSource(e, a); deba@1718: } else { deba@1718: changeTarget(e, a); deba@1718: } deba@1718: e = f; deba@1718: } deba@1718: erase(b); deba@1718: } klao@1034: }; klao@1034: alpar@949: alpar@948: /// @} alpar@948: } //namespace lemon klao@946: alpar@400: klao@946: #endif