alpar@948: /* -*- C++ -*- alpar@948: * 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@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@2116: ///\brief ListGraph, ListUGraph classes. alpar@948: deba@2116: #include deba@1791: #include deba@782: deba@2116: #include deba@2116: deba@1979: #include 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; deba@2031: explicit 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; deba@2031: explicit 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: deba@2031: Node source(Edge e) const { return Node(edges[e.id].source); } deba@2031: Node target(Edge e) const { return Node(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: deba@2111: 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: } deba@2111: 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@1979: typedef GraphExtender ExtendedListGraphBase; alpar@400: deba@2116: /// \addtogroup graphs deba@2116: /// @{ alpar@400: alpar@948: ///A list graph class. alpar@400: alpar@2117: ///This is a simple and fast graph implementation. alpar@948: /// alpar@2117: ///It conforms to the \ref concept::Graph "Graph concept" and it deba@2111: ///also provides several additional useful extra functionalities. deba@2111: ///The most of the member functions and nested classes are deba@2111: ///documented only in the concept class. deba@2111: ///\sa concept::Graph. deba@782: deba@1999: class ListGraph : public ExtendedListGraphBase { alpar@948: public: deba@1999: deba@1999: typedef ExtendedListGraphBase Parent; deba@1999: deba@2111: ///Add a new node to the graph. deba@2111: deba@2111: /// \return the new node. deba@2111: /// deba@2111: Node addNode() { return Parent::addNode(); } deba@2111: deba@2111: ///Add a new edge to the graph. deba@2111: deba@2111: ///Add a new edge to the graph with source node \c s deba@2111: ///and target node \c t. deba@2111: ///\return the new edge. deba@2111: Edge addEdge(const Node& s, const Node& t) { deba@2111: return Parent::addEdge(s, t); deba@2111: } deba@2111: 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: /// deba@2114: ///\note The Edges and OutEdgeIts referencing deba@2114: ///the changed edge remain valid. However InEdgeIts are deba@2114: ///invalidated. deba@1718: void changeTarget(Edge e, Node n) { deba@2111: Parent::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: /// deba@2114: ///\note The Edges and InEdgeIts referencing deba@2114: ///the changed edge remain valid. However OutEdgeIts are deba@2114: ///invalidated. deba@1718: void changeSource(Edge e, Node n) { deba@2111: Parent::changeSource(e,n); deba@1718: } alpar@949: alpar@1010: /// Invert the direction of an edge. alpar@1010: deba@2114: ///\note The Edges referencing the changed edge remain deba@2114: ///valid. However OutEdgeIts and InEdgeIts are deba@2114: ///invalidated. alpar@1010: void reverseEdge(Edge e) { alpar@1010: Node t=target(e); deba@2111: changeTarget(e,source(e)); deba@2111: changeSource(e,t); alpar@1010: } alpar@1010: deba@2111: /// \brief Using this it is possible to avoid the superfluous memory deba@2111: /// allocation. alpar@1010: deba@2107: ///Using this it is possible to avoid the superfluous memory deba@2107: ///allocation: if you know that the graph you want to build will deba@2107: ///contain at least 10 million nodes then it is worth to reserve deba@2107: ///space for this amount before starting to build the graph. deba@2107: void reserveNode(int n) { nodes.reserve(n); }; deba@2107: deba@2111: /// \brief Using this it is possible to avoid the superfluous memory deba@2111: /// allocation. deba@2107: deba@2107: ///Using this it is possible to avoid the superfluous memory deba@2107: ///allocation: see the \ref reserveNode function. alpar@949: void reserveEdge(int n) { edges.reserve(n); }; alpar@1010: deba@2107: 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 athos@2102: ///incident 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 athos@2102: ///valid. However InEdges and OutEdges 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 athos@2102: ///valid. However InEdges and OutEdges 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. deba@2114: Node split(Node n, bool connect = true) { 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: } deba@2114: if (connect) addEdge(n,b); alpar@1281: return b; alpar@1281: } alpar@1281: alpar@1812: ///Split an edge. alpar@1812: athos@2102: ///This function splits an edge. First a new node \c b is added to athos@2102: ///the graph, then the original edge is re-targeted to \c athos@2102: ///b. Finally an edge from \c b to the original target is added. athos@2102: ///\return The newly created node. athos@2102: ///\warning This functionality athos@2102: ///cannot be used together with the Snapshot feature. deba@2114: Node split(Edge e) { alpar@1812: Node b = addNode(); alpar@1812: addEdge(b,target(e)); alpar@1812: changeTarget(e,b); alpar@1812: return b; alpar@1812: } alpar@1812: deba@2114: /// \brief Class to make a snapshot of the graph and restore deba@2114: /// to it later. alpar@1011: /// deba@2114: /// Class to make a snapshot of the graph and to restore it deba@2114: /// later. alpar@1011: /// deba@2114: /// The newly added nodes and edges can be removed using the deba@2114: /// restore() function. deba@2114: /// deba@2114: /// \warning Edge and node deletions cannot be restored. deba@2114: class Snapshot { 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: deba@1999: protected: deba@2114: deba@2114: typedef Parent::NodeNotifier NodeNotifier; deba@2114: deba@2114: class NodeObserverProxy : public NodeNotifier::ObserverBase { deba@2114: public: deba@2114: deba@2114: NodeObserverProxy(Snapshot& _snapshot) deba@2114: : snapshot(_snapshot) {} deba@2114: deba@2114: using NodeNotifier::ObserverBase::attach; deba@2114: using NodeNotifier::ObserverBase::detach; deba@2114: using NodeNotifier::ObserverBase::attached; deba@2114: deba@2114: protected: deba@2114: deba@2114: virtual void add(const Node& node) { deba@2114: snapshot.addNode(node); deba@2114: } deba@2114: virtual void add(const std::vector& nodes) { deba@2114: for (int i = nodes.size() - 1; i >= 0; ++i) { deba@2114: snapshot.addNode(nodes[i]); deba@2114: } deba@2114: } deba@2114: virtual void erase(const Node& node) { deba@2114: snapshot.eraseNode(node); deba@2114: } deba@2114: virtual void erase(const std::vector& nodes) { deba@2114: for (int i = 0; i < (int)nodes.size(); ++i) { deba@2114: if (!snapshot.eraseNode(nodes[i])) break; deba@2114: } deba@2114: } deba@2114: virtual void build() { deba@2114: NodeNotifier* notifier = getNotifier(); deba@2114: Node node; deba@2114: std::vector nodes; deba@2114: for (notifier->first(node); node != INVALID; notifier->next(node)) { deba@2114: nodes.push_back(node); deba@2114: } deba@2114: for (int i = nodes.size() - 1; i >= 0; --i) { deba@2114: snapshot.addNode(nodes[i]); deba@2114: } deba@2114: } deba@2114: virtual void clear() { deba@2114: NodeNotifier* notifier = getNotifier(); deba@2114: Node node; deba@2114: for (notifier->first(node); node != INVALID; notifier->next(node)) { deba@2114: if (!snapshot.eraseNode(node)) break; deba@2114: } deba@2114: } deba@2114: deba@2114: Snapshot& snapshot; deba@2114: }; deba@2114: deba@2114: class EdgeObserverProxy : public EdgeNotifier::ObserverBase { deba@2114: public: deba@2114: deba@2114: EdgeObserverProxy(Snapshot& _snapshot) deba@2114: : snapshot(_snapshot) {} deba@2114: deba@2114: using EdgeNotifier::ObserverBase::attach; deba@2114: using EdgeNotifier::ObserverBase::detach; deba@2114: using EdgeNotifier::ObserverBase::attached; deba@2114: deba@2114: protected: deba@2114: deba@2114: virtual void add(const Edge& edge) { deba@2114: snapshot.addEdge(edge); deba@2114: } deba@2114: virtual void add(const std::vector& edges) { deba@2114: for (int i = edges.size() - 1; i >= 0; ++i) { deba@2114: snapshot.addEdge(edges[i]); deba@2114: } deba@2114: } deba@2114: virtual void erase(const Edge& edge) { deba@2114: snapshot.eraseEdge(edge); deba@2114: } deba@2114: virtual void erase(const std::vector& edges) { deba@2114: for (int i = 0; i < (int)edges.size(); ++i) { deba@2114: if (!snapshot.eraseEdge(edges[i])) break; deba@2114: } deba@2114: } deba@2114: virtual void build() { deba@2114: EdgeNotifier* notifier = getNotifier(); deba@2114: Edge edge; deba@2114: std::vector edges; deba@2114: for (notifier->first(edge); edge != INVALID; notifier->next(edge)) { deba@2114: edges.push_back(edge); deba@2114: } deba@2114: for (int i = edges.size() - 1; i >= 0; --i) { deba@2114: snapshot.addEdge(edges[i]); deba@2114: } deba@2114: } deba@2114: virtual void clear() { deba@2114: EdgeNotifier* notifier = getNotifier(); deba@2114: Edge edge; deba@2114: for (notifier->first(edge); edge != INVALID; notifier->next(edge)) { deba@2114: if (!snapshot.eraseEdge(edge)) break; deba@2114: } deba@2114: } deba@2114: deba@2114: Snapshot& snapshot; deba@2114: }; alpar@1011: deba@2114: ListGraph *graph; deba@2114: deba@2114: NodeObserverProxy node_observer_proxy; deba@2114: EdgeObserverProxy edge_observer_proxy; deba@2114: alpar@1011: std::list added_nodes; alpar@1011: std::list added_edges; deba@2114: deba@2114: deba@2114: void addNode(const Node& node) { deba@2114: added_nodes.push_front(node); alpar@1011: } deba@2114: bool eraseNode(const Node& node) { deba@2114: std::list::iterator it = deba@2114: std::find(added_nodes.begin(), added_nodes.end(), node); deba@2114: if (it == added_nodes.end()) { deba@2114: clear(); deba@2114: return false; deba@2114: } else { deba@2114: added_nodes.erase(it); deba@2114: return true; deba@2114: } alpar@1011: } alpar@1011: deba@2114: void addEdge(const Edge& edge) { deba@2114: added_edges.push_front(edge); deba@2114: } deba@2114: bool eraseEdge(const Edge& edge) { deba@2114: std::list::iterator it = deba@2114: std::find(added_edges.begin(), added_edges.end(), edge); deba@2114: if (it == added_edges.end()) { deba@2114: clear(); deba@2114: return false; deba@2114: } else { deba@2114: added_edges.erase(it); deba@2114: return true; deba@2114: } deba@2114: } alpar@1457: deba@2114: void attach(ListGraph &_graph) { deba@2114: graph = &_graph; deba@2114: node_observer_proxy.attach(graph->getNotifier(Node())); deba@2114: edge_observer_proxy.attach(graph->getNotifier(Edge())); alpar@1011: } alpar@1011: deba@2114: void detach() { deba@2114: node_observer_proxy.detach(); deba@2114: edge_observer_proxy.detach(); deba@2114: } deba@2114: deba@2114: void clear() { deba@2114: detach(); deba@2114: added_nodes.clear(); deba@2114: added_edges.clear(); alpar@1011: } deba@1774: alpar@1011: public: deba@2114: deba@2114: /// \brief Default constructur. deba@2114: /// deba@2114: /// Default constructor. deba@2114: /// To actually make a snapshot you must call save(). deba@2114: Snapshot() deba@2114: : graph(0), node_observer_proxy(*this), deba@2114: edge_observer_proxy(*this) {} alpar@1011: deba@2114: /// \brief Constructor that immediately makes a snapshot. deba@2114: /// deba@2114: /// This constructor immediately makes a snapshot of the graph. deba@2114: /// \param _graph The graph we make a snapshot of. deba@2114: Snapshot(ListGraph &_graph) deba@2114: : node_observer_proxy(*this), deba@2114: edge_observer_proxy(*this) { deba@2114: attach(_graph); alpar@1011: } alpar@1011: deba@2114: /// \brief Make a snapshot. alpar@1011: /// deba@2114: /// Make a snapshot of the graph. deba@2114: /// deba@2114: /// This function can be called more than once. In case of a repeated deba@2114: /// call, the previous snapshot gets lost. deba@2114: /// \param _graph The graph we make the snapshot of. deba@2114: void save(ListGraph &_graph) { deba@2114: clear(); deba@2114: attach(_graph); alpar@1011: } alpar@1011: deba@2114: /// \brief Undo the changes until the last snapshot. deba@2114: // deba@2114: /// Undo the changes until last snapshot created by save(). deba@2114: /// deba@2114: /// \todo This function might be called undo(). alpar@1011: void restore() { deba@2114: detach(); alpar@1011: while(!added_edges.empty()) { deba@2114: graph->erase(added_edges.front()); alpar@1011: added_edges.pop_front(); alpar@1011: } alpar@1011: while(!added_nodes.empty()) { deba@2114: graph->erase(added_nodes.front()); alpar@1011: added_nodes.pop_front(); alpar@1011: } alpar@1011: } deba@2114: deba@2114: /// \brief Gives back true when the snapshot is valid. deba@2114: /// deba@2114: /// Gives back true when the snapshot is valid. deba@2114: bool valid() const { deba@2114: return node_observer_proxy.attached(); deba@2114: } alpar@1011: }; alpar@1011: alpar@949: }; klao@1034: deba@2116: ///@} deba@2116: deba@2116: /**************** Undirected List Graph ****************/ deba@2116: deba@2116: typedef UGraphExtender > deba@2116: ExtendedListUGraphBase; deba@2116: deba@2116: /// \addtogroup graphs deba@2116: /// @{ deba@2116: deba@2116: ///An undirected list graph class. deba@2116: alpar@2117: ///This is a simple and fast undirected graph implementation. deba@2116: /// deba@2116: ///It conforms to the alpar@2117: ///\ref concept::UGraph "UGraph concept". deba@2116: /// deba@2116: ///\sa concept::UGraph. deba@2116: /// deba@2116: ///\todo Snapshot, reverseEdge(), changeTarget(), changeSource(), contract() deba@2116: ///haven't been implemented yet. deba@2116: /// deba@2116: class ListUGraph : public ExtendedListUGraphBase { deba@2116: public: deba@2116: typedef ExtendedListUGraphBase Parent; deba@2116: /// \brief Add a new node to the graph. deba@2116: /// deba@2116: /// \return the new node. deba@2116: /// deba@2116: Node addNode() { return Parent::addNode(); } deba@2116: deba@2116: /// \brief Add a new edge to the graph. deba@2116: /// deba@2116: /// Add a new edge to the graph with source node \c s deba@2116: /// and target node \c t. deba@2116: /// \return the new undirected edge. deba@2116: UEdge addEdge(const Node& s, const Node& t) { deba@2116: return Parent::addEdge(s, t); deba@2116: } deba@2116: /// \brief Changes the target of \c e to \c n deba@2116: /// deba@2116: /// Changes the target of \c e to \c n deba@2116: /// deba@2116: /// \note The Edge's and OutEdge's deba@2116: /// referencing the changed edge remain deba@2116: /// valid. However InEdge's are invalidated. deba@2116: void changeTarget(UEdge e, Node n) { deba@2116: Parent::changeTarget(e,n); deba@2116: } deba@2116: /// Changes the source of \c e to \c n deba@2116: /// deba@2116: /// Changes the source of \c e to \c n deba@2116: /// deba@2116: ///\note The Edge's and InEdge's deba@2116: ///referencing the changed edge remain deba@2116: ///valid. However OutEdge's are invalidated. deba@2116: void changeSource(UEdge e, Node n) { deba@2116: Parent::changeSource(e,n); deba@2116: } deba@2116: /// \brief Contract two nodes. deba@2116: /// deba@2116: /// This function contracts two nodes. deba@2116: /// deba@2116: /// Node \p b will be removed but instead of deleting deba@2116: /// its neighboring edges, they will be joined to \p a. deba@2116: /// The last parameter \p r controls whether to remove loops. \c true deba@2116: /// means that loops will be removed. deba@2116: /// deba@2116: /// \note The Edges deba@2116: /// referencing a moved edge remain deba@2116: /// valid. deba@2116: void contract(Node a, Node b, bool r = true) { deba@2116: for(IncEdgeIt e(*this, b); e!=INVALID;) { deba@2116: IncEdgeIt f = e; ++f; deba@2116: if (r && runningNode(e) == a) { deba@2116: erase(e); deba@2116: } else if (source(e) == b) { deba@2116: changeSource(e, a); deba@2116: } else { deba@2116: changeTarget(e, a); deba@2116: } deba@2116: e = f; deba@2116: } deba@2116: erase(b); deba@2116: } deba@2116: }; deba@2116: deba@2116: deba@2116: class ListBpUGraphBase { deba@2116: public: deba@2116: deba@2116: class NodeSetError : public LogicError { deba@2116: virtual const char* exceptionName() const { deba@2116: return "lemon::ListBpUGraph::NodeSetError"; deba@2116: } deba@2116: }; deba@2116: deba@2116: protected: deba@2116: deba@2116: struct NodeT { deba@2116: int first_edge, prev, next; deba@2116: }; deba@2116: deba@2116: struct UEdgeT { deba@2116: int aNode, prev_out, next_out; deba@2116: int bNode, prev_in, 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: int first_anode; deba@2116: int first_free_anode; deba@2116: deba@2116: int first_bnode; deba@2116: int first_free_bnode; deba@2116: deba@2116: int first_free_edge; deba@2116: deba@2116: public: deba@2116: deba@2116: class Node { deba@2116: friend class ListBpUGraphBase; deba@2116: protected: deba@2116: int id; deba@2116: deba@2116: explicit 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> 1].next; deba@2116: } deba@2116: deba@2116: void firstBNode(Node& node) const { deba@2116: node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1; deba@2116: } deba@2116: void nextBNode(Node& node) const { deba@2116: node.id = bNodes[node.id >> 1].next; deba@2116: } deba@2116: deba@2116: void first(Node& node) const { deba@2116: if (first_anode != -1) { deba@2116: node.id = (first_anode << 1); deba@2116: } else if (first_bnode != -1) { deba@2116: node.id = (first_bnode << 1) + 1; deba@2116: } else { deba@2116: node.id = -1; deba@2116: } deba@2116: } deba@2116: void next(Node& node) const { deba@2116: if (aNode(node)) { deba@2116: node.id = aNodes[node.id >> 1].next; deba@2116: if (node.id == -1) { deba@2116: if (first_bnode != -1) { deba@2116: node.id = (first_bnode << 1) + 1; deba@2116: } deba@2116: } deba@2116: } else { deba@2116: node.id = bNodes[node.id >> 1].next; deba@2116: } deba@2116: } deba@2116: deba@2116: void first(UEdge& edge) const { deba@2116: int aNodeId = first_anode; deba@2116: while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) { deba@2116: aNodeId = aNodes[aNodeId].next != -1 ? deba@2116: aNodes[aNodeId].next >> 1 : -1; deba@2116: } deba@2116: if (aNodeId != -1) { deba@2116: edge.id = aNodes[aNodeId].first_edge; deba@2116: } else { deba@2116: edge.id = -1; deba@2116: } deba@2116: } deba@2116: void next(UEdge& edge) const { deba@2116: int aNodeId = edges[edge.id].aNode >> 1; deba@2116: edge.id = edges[edge.id].next_out; deba@2116: if (edge.id == -1) { deba@2116: aNodeId = aNodes[aNodeId].next != -1 ? deba@2116: aNodes[aNodeId].next >> 1 : -1; deba@2116: while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) { deba@2116: aNodeId = aNodes[aNodeId].next != -1 ? deba@2116: aNodes[aNodeId].next >> 1 : -1; deba@2116: } deba@2116: if (aNodeId != -1) { deba@2116: edge.id = aNodes[aNodeId].first_edge; deba@2116: } else { deba@2116: edge.id = -1; deba@2116: } deba@2116: } 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_edge; 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_edge; 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: int aNodeId; deba@2116: if (first_free_anode == -1) { deba@2116: aNodeId = aNodes.size(); deba@2116: aNodes.push_back(NodeT()); deba@2116: } else { deba@2116: aNodeId = first_free_anode; deba@2116: first_free_anode = aNodes[first_free_anode].next; deba@2116: } deba@2116: if (first_anode != -1) { deba@2116: aNodes[aNodeId].next = first_anode << 1; deba@2116: aNodes[first_anode].prev = aNodeId << 1; deba@2116: } else { deba@2116: aNodes[aNodeId].next = -1; deba@2116: } deba@2116: aNodes[aNodeId].prev = -1; deba@2116: first_anode = aNodeId; deba@2116: aNodes[aNodeId].first_edge = -1; deba@2116: return Node(aNodeId << 1); deba@2116: } deba@2116: deba@2116: Node addBNode() { deba@2116: int bNodeId; deba@2116: if (first_free_bnode == -1) { deba@2116: bNodeId = bNodes.size(); deba@2116: bNodes.push_back(NodeT()); deba@2116: } else { deba@2116: bNodeId = first_free_bnode; deba@2116: first_free_bnode = bNodes[first_free_bnode].next; deba@2116: } deba@2116: if (first_bnode != -1) { deba@2116: bNodes[bNodeId].next = (first_bnode << 1) + 1; deba@2116: bNodes[first_bnode].prev = (bNodeId << 1) + 1; deba@2116: } else { deba@2116: bNodes[bNodeId].next = -1; deba@2116: } deba@2116: first_bnode = bNodeId; deba@2116: bNodes[bNodeId].first_edge = -1; deba@2116: return Node((bNodeId << 1) + 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: int edgeId; deba@2116: if (first_free_edge != -1) { deba@2116: edgeId = first_free_edge; deba@2116: first_free_edge = edges[edgeId].next_out; deba@2116: } else { deba@2116: edgeId = edges.size(); deba@2116: edges.push_back(UEdgeT()); deba@2116: } deba@2116: if ((source.id & 1) == 0) { deba@2116: edges[edgeId].aNode = source.id; deba@2116: edges[edgeId].bNode = target.id; deba@2116: } else { deba@2116: edges[edgeId].aNode = target.id; deba@2116: edges[edgeId].bNode = source.id; deba@2116: } deba@2116: edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge; deba@2116: edges[edgeId].prev_out = -1; deba@2116: if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) { deba@2116: edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId; deba@2116: } deba@2116: aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId; deba@2116: edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge; deba@2116: edges[edgeId].prev_in = -1; deba@2116: if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) { deba@2116: edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId; deba@2116: } deba@2116: bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId; deba@2116: return UEdge(edgeId); deba@2116: } deba@2116: deba@2116: void erase(const Node& node) { deba@2116: if (aNode(node)) { deba@2116: int aNodeId = node.id >> 1; deba@2116: if (aNodes[aNodeId].prev != -1) { deba@2116: aNodes[aNodes[aNodeId].prev >> 1].next = aNodes[aNodeId].next; deba@2116: } else { deba@2116: first_anode = aNodes[aNodeId].next >> 1; deba@2116: } deba@2116: if (aNodes[aNodeId].next != -1) { deba@2116: aNodes[aNodes[aNodeId].next >> 1].prev = aNodes[aNodeId].prev; deba@2116: } deba@2116: aNodes[aNodeId].next = first_free_anode; deba@2116: first_free_anode = aNodeId; deba@2116: } else { deba@2116: int bNodeId = node.id >> 1; deba@2116: if (bNodes[bNodeId].prev != -1) { deba@2116: bNodes[bNodes[bNodeId].prev >> 1].next = bNodes[bNodeId].next; deba@2116: } else { deba@2116: first_bnode = bNodes[bNodeId].next >> 1; deba@2116: } deba@2116: if (bNodes[bNodeId].next != -1) { deba@2116: bNodes[bNodes[bNodeId].next >> 1].prev = bNodes[bNodeId].prev; deba@2116: } deba@2116: bNodes[bNodeId].next = first_free_bnode; deba@2116: first_free_bnode = bNodeId; deba@2116: } deba@2116: } deba@2116: deba@2116: void erase(const UEdge& edge) { deba@2116: deba@2116: if (edges[edge.id].prev_out != -1) { deba@2116: edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out; deba@2116: } else { deba@2116: aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out; deba@2116: } deba@2116: if (edges[edge.id].next_out != -1) { deba@2116: edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out; deba@2116: } deba@2116: deba@2116: if (edges[edge.id].prev_in != -1) { deba@2116: edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in; deba@2116: } else { deba@2116: bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in; deba@2116: } deba@2116: if (edges[edge.id].next_in != -1) { deba@2116: edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in; deba@2116: } deba@2116: deba@2116: edges[edge.id].next_out = first_free_edge; deba@2116: first_free_edge = edge.id; deba@2116: } deba@2116: deba@2116: void clear() { deba@2116: aNodes.clear(); deba@2116: bNodes.clear(); deba@2116: edges.clear(); deba@2116: first_anode = -1; deba@2116: first_free_anode = -1; deba@2116: first_bnode = -1; deba@2116: first_free_bnode = -1; deba@2116: first_free_edge = -1; deba@2116: } deba@2116: deba@2116: }; deba@2116: deba@2116: deba@2116: typedef BpUGraphExtender< ListBpUGraphBase > ExtendedListBpUGraphBase; deba@2116: deba@2116: /// \ingroup graphs deba@2116: /// deba@2116: /// \brief A smart bipartite undirected graph class. deba@2116: /// deba@2116: /// This is a bipartite undirected graph implementation. alpar@2117: /// It is conforms to the \ref concept::BpUGraph "BpUGraph concept". deba@2116: /// \sa concept::BpUGraph. deba@2116: /// deba@2116: class ListBpUGraph : public ExtendedListBpUGraphBase {}; deba@2116: deba@2116: deba@2116: /// @} alpar@948: } //namespace lemon klao@946: alpar@400: klao@946: #endif