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 klao@1909: ///\brief ListGraph, ListUGraph classes. alpar@948: deba@1999: #include deba@1791: #include deba@782: deba@1774: #include deba@1774: 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: 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@1979: typedef 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: /// athos@2102: ///It conforms to the athos@2102: ///\ref concept::ErasableGraph "ErasableGraph" concept and alpar@1010: ///it also provides several additional useful extra functionalities. klao@959: ///\sa concept::ErasableGraph. deba@782: deba@1999: class ListGraph : public ExtendedListGraphBase { alpar@948: public: deba@1999: deba@1999: typedef ExtendedListGraphBase Parent; deba@1999: 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: /// athos@2102: ///\note The Edges and OutEdges alpar@1546: ///referencing the changed edge remain athos@2102: ///valid. However InEdges 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: /// athos@2102: ///\note The Edges and InEdges alpar@1546: ///referencing the changed edge remain athos@2102: ///valid. However OutEdges 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: athos@2102: ///\note The Edges alpar@1546: ///referencing the changed edge remain athos@2102: ///valid. However OutEdges and InEdges 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: athos@2102: ///Using this it is possible to avoid the superfluous memory allocation. alpar@1010: athos@2102: ///Using this it is 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 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. 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: 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. 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: athos@2102: ///Class to make a snapshot of the graph and to restore it later. alpar@1011: athos@2102: ///Class to make a snapshot of the graph and to restore 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. deba@1999: class Snapshot : protected Parent::NodeNotifier::ObserverBase, deba@1999: protected Parent::EdgeNotifier::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: deba@1999: 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@1999: Parent::NodeNotifier::ObserverBase::attach(g->getNotifier(Node())); deba@1999: Parent::EdgeNotifier::ObserverBase::attach(g->getNotifier(Edge())); alpar@1011: } alpar@1011: alpar@1011: void deregist() { deba@1999: Parent::NodeNotifier::ObserverBase::detach(); deba@1999: Parent::EdgeNotifier::ObserverBase::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: deba@2076: typedef UGraphExtender > deba@2076: ExtendedListUGraphBase; 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 klao@1909: ///\ref concept::UGraph "UGraph" concept. alpar@1035: /// klao@1909: ///\sa concept::UGraph. alpar@1035: /// alpar@1770: ///\todo Snapshot, reverseEdge(), changeTarget(), changeSource(), contract() alpar@1161: ///haven't been implemented yet. alpar@1035: /// klao@1909: class ListUGraph : public ExtendedListUGraphBase { deba@1718: public: klao@1909: typedef ExtendedListUGraphBase 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. klao@1909: void changeTarget(UEdge 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. klao@1909: void changeSource(UEdge 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: deba@1982: deba@1982: class ListBpUGraphBase { deba@1982: public: deba@1982: deba@1982: class NodeSetError : public LogicError { deba@1982: virtual const char* exceptionName() const { deba@1982: return "lemon::ListBpUGraph::NodeSetError"; deba@1982: } deba@1982: }; deba@1982: deba@1982: protected: deba@1982: deba@1982: struct NodeT { deba@2098: int first_edge, prev, next; deba@1982: }; deba@1982: deba@2076: struct UEdgeT { deba@1982: int aNode, prev_out, next_out; deba@1982: int bNode, prev_in, next_in; deba@1982: }; deba@1982: deba@1982: std::vector aNodes; deba@1982: std::vector bNodes; deba@1982: deba@2076: std::vector edges; deba@1982: deba@1982: int first_anode; deba@1982: int first_free_anode; deba@1982: deba@1982: int first_bnode; deba@1982: int first_free_bnode; deba@1982: deba@1982: int first_free_edge; deba@1982: deba@1982: public: deba@1982: deba@1982: class Node { deba@1982: friend class ListBpUGraphBase; deba@1982: protected: deba@1982: int id; deba@1982: deba@2031: explicit Node(int _id) : id(_id) {} deba@1982: public: deba@1982: Node() {} deba@1982: Node(Invalid) { id = -1; } deba@1982: bool operator==(const Node i) const {return id==i.id;} deba@1982: bool operator!=(const Node i) const {return id!=i.id;} deba@1982: bool operator<(const Node i) const {return id> 1].next; deba@1982: } deba@1982: deba@1982: void firstBNode(Node& node) const { deba@2098: node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1; deba@1982: } deba@1982: void nextBNode(Node& node) const { deba@2098: node.id = bNodes[node.id >> 1].next; deba@1982: } deba@1982: deba@1982: void first(Node& node) const { deba@1982: if (first_anode != -1) { deba@1982: node.id = (first_anode << 1); deba@1982: } else if (first_bnode != -1) { deba@1982: node.id = (first_bnode << 1) + 1; deba@1982: } else { deba@1982: node.id = -1; deba@1982: } deba@1982: } deba@1982: void next(Node& node) const { deba@1982: if (aNode(node)) { deba@2098: node.id = aNodes[node.id >> 1].next; deba@1982: if (node.id == -1) { deba@1982: if (first_bnode != -1) { deba@1982: node.id = (first_bnode << 1) + 1; deba@1982: } deba@1982: } deba@1982: } else { deba@2098: node.id = bNodes[node.id >> 1].next; deba@1982: } deba@1982: } deba@1982: deba@2076: void first(UEdge& edge) const { deba@1982: int aNodeId = first_anode; deba@1982: while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) { deba@2098: aNodeId = aNodes[aNodeId].next != -1 ? deba@2098: aNodes[aNodeId].next >> 1 : -1; deba@1982: } deba@1982: if (aNodeId != -1) { deba@1982: edge.id = aNodes[aNodeId].first_edge; deba@1982: } else { deba@1982: edge.id = -1; deba@1982: } deba@1982: } deba@2076: void next(UEdge& edge) const { deba@1982: int aNodeId = edges[edge.id].aNode >> 1; deba@1982: edge.id = edges[edge.id].next_out; deba@1982: if (edge.id == -1) { deba@2098: aNodeId = aNodes[aNodeId].next != -1 ? deba@2098: aNodes[aNodeId].next >> 1 : -1; deba@1982: while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) { deba@2098: aNodeId = aNodes[aNodeId].next != -1 ? deba@2098: aNodes[aNodeId].next >> 1 : -1; deba@1982: } deba@1982: if (aNodeId != -1) { deba@1982: edge.id = aNodes[aNodeId].first_edge; deba@1982: } else { deba@1982: edge.id = -1; deba@1982: } deba@1982: } deba@1982: } deba@1982: deba@2076: void firstFromANode(UEdge& edge, const Node& node) const { deba@1982: LEMON_ASSERT((node.id & 1) == 0, NodeSetError()); deba@1982: edge.id = aNodes[node.id >> 1].first_edge; deba@1982: } deba@2076: void nextFromANode(UEdge& edge) const { deba@1982: edge.id = edges[edge.id].next_out; deba@1982: } deba@1982: deba@2076: void firstFromBNode(UEdge& edge, const Node& node) const { deba@1982: LEMON_ASSERT((node.id & 1) == 1, NodeSetError()); deba@1982: edge.id = bNodes[node.id >> 1].first_edge; deba@1982: } deba@2076: void nextFromBNode(UEdge& edge) const { deba@1982: edge.id = edges[edge.id].next_in; deba@1982: } deba@1982: deba@1982: static int id(const Node& node) { deba@1982: return node.id; deba@1982: } deba@1982: static Node nodeFromId(int id) { deba@1982: return Node(id); deba@1982: } deba@1982: int maxNodeId() const { deba@1982: return aNodes.size() > bNodes.size() ? deba@1982: aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1; deba@1982: } deba@1982: deba@2076: static int id(const UEdge& edge) { deba@1982: return edge.id; deba@1982: } deba@2076: static UEdge uEdgeFromId(int id) { deba@2076: return UEdge(id); deba@1982: } deba@2076: int maxUEdgeId() const { deba@1982: return edges.size(); deba@1982: } deba@1982: deba@1982: static int aNodeId(const Node& node) { deba@1982: return node.id >> 1; deba@1982: } deba@1995: static Node fromANodeId(int id) { deba@1982: return Node(id << 1); deba@1982: } deba@1982: int maxANodeId() const { deba@1982: return aNodes.size(); deba@1982: } deba@1982: deba@1982: static int bNodeId(const Node& node) { deba@1982: return node.id >> 1; deba@1982: } deba@1982: static Node fromBNodeId(int id) { deba@1982: return Node((id << 1) + 1); deba@1982: } deba@1982: int maxBNodeId() const { deba@1982: return bNodes.size(); deba@1982: } deba@1982: deba@2076: Node aNode(const UEdge& edge) const { deba@1982: return Node(edges[edge.id].aNode); deba@1982: } deba@2076: Node bNode(const UEdge& edge) const { deba@1982: return Node(edges[edge.id].bNode); deba@1982: } deba@1982: deba@1982: static bool aNode(const Node& node) { deba@1982: return (node.id & 1) == 0; deba@1982: } deba@1982: deba@1982: static bool bNode(const Node& node) { deba@1982: return (node.id & 1) == 1; deba@1982: } deba@1982: deba@1982: Node addANode() { deba@1982: int aNodeId; deba@1982: if (first_free_anode == -1) { deba@1982: aNodeId = aNodes.size(); deba@1982: aNodes.push_back(NodeT()); deba@1982: } else { deba@1982: aNodeId = first_free_anode; deba@2098: first_free_anode = aNodes[first_free_anode].next; deba@1982: } deba@2098: if (first_anode != -1) { deba@2098: aNodes[aNodeId].next = first_anode << 1; deba@2098: aNodes[first_anode].prev = aNodeId << 1; deba@2098: } else { deba@2098: aNodes[aNodeId].next = -1; deba@2098: } deba@2098: aNodes[aNodeId].prev = -1; deba@1982: first_anode = aNodeId; deba@1982: aNodes[aNodeId].first_edge = -1; deba@1982: return Node(aNodeId << 1); deba@1982: } deba@1982: deba@1982: Node addBNode() { deba@1982: int bNodeId; deba@1984: if (first_free_bnode == -1) { deba@1982: bNodeId = bNodes.size(); deba@1982: bNodes.push_back(NodeT()); deba@1982: } else { deba@1982: bNodeId = first_free_bnode; deba@2098: first_free_bnode = bNodes[first_free_bnode].next; deba@1982: } deba@2098: if (first_bnode != -1) { deba@2098: bNodes[bNodeId].next = (first_bnode << 1) + 1; deba@2098: bNodes[first_bnode].prev = (bNodeId << 1) + 1; deba@2098: } else { deba@2098: bNodes[bNodeId].next = -1; deba@2098: } deba@1982: first_bnode = bNodeId; deba@1982: bNodes[bNodeId].first_edge = -1; deba@1982: return Node((bNodeId << 1) + 1); deba@1982: } deba@1982: deba@2076: UEdge addEdge(const Node& source, const Node& target) { deba@1982: LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError()); deba@1982: int edgeId; deba@1982: if (first_free_edge != -1) { deba@1982: edgeId = first_free_edge; deba@1982: first_free_edge = edges[edgeId].next_out; deba@1982: } else { deba@1982: edgeId = edges.size(); deba@2076: edges.push_back(UEdgeT()); deba@1982: } deba@1982: if ((source.id & 1) == 0) { deba@1982: edges[edgeId].aNode = source.id; deba@1982: edges[edgeId].bNode = target.id; deba@1982: } else { deba@1982: edges[edgeId].aNode = target.id; deba@1982: edges[edgeId].bNode = source.id; deba@1982: } deba@1982: edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge; deba@1982: edges[edgeId].prev_out = -1; deba@1982: if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) { deba@1982: edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId; deba@1982: } deba@1982: aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId; deba@1982: edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge; deba@1982: edges[edgeId].prev_in = -1; deba@1982: if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) { deba@1982: edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId; deba@1982: } deba@1982: bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId; deba@2076: return UEdge(edgeId); deba@1982: } deba@1982: deba@1982: void erase(const Node& node) { deba@1982: if (aNode(node)) { deba@1982: int aNodeId = node.id >> 1; deba@2098: if (aNodes[aNodeId].prev != -1) { deba@2098: aNodes[aNodes[aNodeId].prev >> 1].next = aNodes[aNodeId].next; deba@2098: } else { deba@2098: first_anode = aNodes[aNodeId].next >> 1; deba@2098: } deba@2098: if (aNodes[aNodeId].next != -1) { deba@2098: aNodes[aNodes[aNodeId].next >> 1].prev = aNodes[aNodeId].prev; deba@2098: } deba@2098: aNodes[aNodeId].next = first_free_anode; deba@1982: first_free_anode = aNodeId; deba@1982: } else { deba@1982: int bNodeId = node.id >> 1; deba@2098: if (bNodes[bNodeId].prev != -1) { deba@2098: bNodes[bNodes[bNodeId].prev >> 1].next = bNodes[bNodeId].next; deba@2098: } else { deba@2098: first_bnode = bNodes[bNodeId].next >> 1; deba@2098: } deba@2098: if (bNodes[bNodeId].next != -1) { deba@2098: bNodes[bNodes[bNodeId].next >> 1].prev = bNodes[bNodeId].prev; deba@2098: } deba@2098: bNodes[bNodeId].next = first_free_bnode; deba@1982: first_free_bnode = bNodeId; deba@1982: } deba@1982: } deba@1982: deba@2076: void erase(const UEdge& edge) { deba@2098: deba@1982: if (edges[edge.id].prev_out != -1) { deba@1982: edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out; deba@1982: } else { deba@2098: aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out; deba@1982: } deba@1982: if (edges[edge.id].next_out != -1) { deba@1982: edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out; deba@1982: } deba@2098: deba@1982: if (edges[edge.id].prev_in != -1) { deba@1982: edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in; deba@1982: } else { deba@2098: bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in; deba@1982: } deba@1982: if (edges[edge.id].next_in != -1) { deba@1982: edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in; deba@1982: } deba@2098: deba@1982: edges[edge.id].next_out = first_free_edge; deba@1982: first_free_edge = edge.id; deba@1982: } deba@1982: deba@1982: void clear() { deba@1982: aNodes.clear(); deba@1982: bNodes.clear(); deba@1982: edges.clear(); deba@1982: first_anode = -1; deba@1982: first_free_anode = -1; deba@1982: first_bnode = -1; deba@1982: first_free_bnode = -1; deba@1982: first_free_edge = -1; deba@1982: } deba@1982: deba@1982: }; deba@1982: deba@1982: deba@2076: typedef BpUGraphExtender< ListBpUGraphBase > ExtendedListBpUGraphBase; deba@1982: deba@1982: /// \ingroup graphs deba@1982: /// deba@1982: /// \brief A smart bipartite undirected graph class. deba@1982: /// deba@1982: /// This is a bipartite undirected graph implementation. deba@1991: /// It is conforms to the \ref concept::ErasableBpUGraph "ErasableBpUGraph" deba@1991: /// concept. deba@1982: /// \sa concept::BpUGraph. deba@1982: /// deba@1982: class ListBpUGraph : public ExtendedListBpUGraphBase {}; deba@1982: alpar@949: alpar@948: /// @} alpar@948: } //namespace lemon klao@946: alpar@400: klao@946: #endif