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@1334: ///\brief ListGraph, SymListGraph classes. alpar@948: deba@1307: #include deba@1307: #include deba@1307: #include deba@1307: #include deba@1307: #include deba@1307: #include alpar@395: deba@1307: #include deba@782: alpar@1011: #include deba@782: alpar@921: namespace lemon { alpar@395: klao@946: class ListGraphBase { alpar@406: alpar@949: protected: klao@946: struct NodeT { alpar@397: 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@980: int maxId(Node = INVALID) 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@980: int maxId(Edge = INVALID) 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@1106: static Node fromId(int id, Node) { return Node(id);} deba@1106: static Edge fromId(int id, Edge) { 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@986: void _moveTarget(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; 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@986: void _moveSource(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; 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: klao@946: typedef AlterableGraphExtender AlterableListGraphBase; klao@946: typedef IterableGraphExtender IterableListGraphBase; deba@980: typedef DefaultMappableGraphExtender MappableListGraphBase; klao@946: typedef ExtendableGraphExtender ExtendableListGraphBase; klao@946: typedef ClearableGraphExtender ClearableListGraphBase; klao@946: typedef ErasableGraphExtender ErasableListGraphBase; alpar@400: alpar@948: /// \addtogroup graphs alpar@948: /// @{ 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: alpar@948: class ListGraph : public ErasableListGraphBase alpar@948: { alpar@948: public: alpar@986: /// Moves the target of \c e to \c n alpar@948: alpar@986: /// Moves the target of \c e to \c n alpar@948: /// alpar@1010: ///\note The Edge's and OutEdge's alpar@1010: ///referencing the moved edge remain alpar@1010: ///valid. However InEdge's are invalidated. alpar@986: void moveTarget(Edge e, Node n) { _moveTarget(e,n); } alpar@986: /// Moves the source of \c e to \c n alpar@948: alpar@986: /// Moves the source of \c e to \c n alpar@948: /// alpar@1010: ///\note The Edge's and InEdge's alpar@1010: ///referencing the moved edge remain alpar@1010: ///valid. However OutEdge's are invalidated. alpar@986: void moveSource(Edge e, Node n) { _moveSource(e,n); } alpar@949: alpar@1010: /// Invert the direction of an edge. alpar@1010: alpar@1010: ///\note The Edge's alpar@1010: ///referencing the moved 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@1010: _moveTarget(e,source(e)); alpar@1010: _moveSource(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. alpar@1010: 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); athos@1184: else moveSource(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); athos@1184: else moveTarget(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@1284: ///\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@1281: moveSource(e,b); alpar@1281: e=f; alpar@1281: } alpar@1281: if(connect) addEdge(n,b); alpar@1281: return b; alpar@1281: } alpar@1281: 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@1011: ///\warning SnapShots cannot be nested. alpar@1035: ///\todo \c SnapShot or \c Snapshot? deba@1039: class SnapShot : protected AlterationNotifier::ObserverBase, deba@1039: protected AlterationNotifier::ObserverBase alpar@1011: { 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: ///\bug Exception... alpar@1011: /// alpar@1011: virtual void erase(const Node&) alpar@1011: { alpar@1011: exit(1); alpar@1011: } alpar@1011: virtual void add(const Edge& n) { alpar@1011: added_edges.push_back(n); alpar@1011: }; alpar@1011: ///\bug Exception... alpar@1011: /// alpar@1011: virtual void erase(const Edge&) alpar@1011: { alpar@1011: exit(1); alpar@1011: } alpar@1011: 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: } alpar@1011: 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@1011: 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@1011: SnapShot(ListGraph &_g) { alpar@1011: regist(_g); alpar@1011: } alpar@1011: ///\bug Is it necessary? alpar@1011: /// alpar@1011: ~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@1011: deregist(); alpar@1011: while(!added_edges.empty()) { alpar@1011: g->erase(added_edges.front()); alpar@1011: added_edges.pop_front(); alpar@1011: } alpar@1011: while(!added_nodes.empty()) { alpar@1011: g->erase(added_nodes.front()); alpar@1011: added_nodes.pop_front(); alpar@1011: } alpar@1011: } alpar@1011: }; alpar@1011: alpar@949: }; klao@1034: 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< klao@1034: UndirGraphExtender > > > > > > ErasableUndirListGraphBase; klao@1034: 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@1161: ///\todo SnapShot, reverseEdge(), moveTarget(), moveSource(), contract() alpar@1161: ///haven't been implemented yet. alpar@1035: /// klao@1034: class UndirListGraph : public ErasableUndirListGraphBase { klao@1034: }; klao@1034: alpar@949: alpar@948: /// @} alpar@948: } //namespace lemon klao@946: alpar@400: klao@946: #endif