alpar@948: /* -*- C++ -*-
alpar@948: *
alpar@1956: * This file is a part of LEMON, a generic C++ optimization library
alpar@1956: *
alpar@2391: * Copyright (C) 2003-2007
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 <lemon/bits/base_extender.h>
deba@1791: #include <lemon/bits/graph_extender.h>
deba@782:
deba@2116: #include <lemon/error.h>
deba@2116:
deba@1979: #include <vector>
alpar@1011: #include <list>
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<NodeT> nodes;
klao@946:
alpar@397: int first_node;
klao@946:
alpar@397: int first_free_node;
klao@946:
alpar@395: std::vector<EdgeT> 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:
deba@1791: int maxNodeId() const { return nodes.size()-1; }
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:
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<ListGraphBase> 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@2260: ///It conforms to the \ref concepts::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.
alpar@2256: ///
alpar@2256: ///An important extra feature of this graph implementation is that
alpar@2260: ///its maps are real \ref concepts::ReferenceMap "reference map"s.
alpar@2256: ///
alpar@2260: ///\sa concepts::Graph.
deba@782:
deba@1999: class ListGraph : public ExtendedListGraphBase {
alpar@2128: private:
alpar@2128: ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
alpar@2128:
alpar@2128: ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
alpar@2128: ///
alpar@2128: ListGraph(const ListGraph &) :ExtendedListGraphBase() {};
alpar@2132: ///\brief Assignment of ListGraph to another one is \e not allowed.
alpar@2128: ///Use GraphCopy() instead.
alpar@2128:
alpar@2132: ///Assignment of ListGraph to another one is \e not allowed.
alpar@2128: ///Use GraphCopy() instead.
alpar@2128: void operator=(const ListGraph &) {}
alpar@948: public:
deba@1999:
deba@1999: typedef ExtendedListGraphBase Parent;
deba@1999:
alpar@2128: /// Constructor
alpar@2128:
alpar@2128: /// Constructor.
alpar@2128: ///
alpar@2128: ListGraph() {}
alpar@2128:
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@2160: ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s referencing
deba@2114: ///the changed edge remain valid. However <tt>InEdgeIt</tt>s are
deba@2114: ///invalidated.
alpar@2123: ///\warning This functionality cannot be used together with the Snapshot
alpar@2123: ///feature.
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@2160: ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
deba@2114: ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
deba@2114: ///invalidated.
alpar@2123: ///\warning This functionality cannot be used together with the Snapshot
alpar@2123: ///feature.
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@2160: ///\note The <tt>EdgeIt</tt>s referencing the changed edge remain
deba@2114: ///valid. However <tt>OutEdgeIt</tt>s and <tt>InEdgeIt</tt>s are
deba@2114: ///invalidated.
alpar@2123: ///\warning This functionality cannot be used together with the Snapshot
alpar@2123: ///feature.
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
alpar@2123: ///contain at least 10 million nodes then it is worth reserving
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: ///
deba@2160: ///\note The <tt>EdgeIt</tt>s
alpar@1281: ///referencing a moved edge remain
deba@2160: ///valid. However <tt>InEdgeIt</tt>s and <tt>OutEdgeIt</tt>s
alpar@1010: ///may be invalidated.
alpar@2123: ///\warning This functionality cannot be used together with the Snapshot
alpar@2123: ///feature.
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: ///
deba@2160: ///\note The <tt>EdgeIt</tt>s referencing a moved edge remain
deba@2160: ///valid. However <tt>InEdgeIt</tt>s and <tt>OutEdgeIt</tt>s may
deba@2160: ///be invalidated.
deba@2160: ///
deba@2160: ///\warning This functionality cannot be used together with the
deba@2160: ///Snapshot feature. \todo It could be implemented in a bit
deba@2160: ///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@2189: /// \warning Edge and node deletions cannot be restored. This
deba@2189: /// events invalidate the snapshot.
deba@2114: class Snapshot {
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<Node>& 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<Node>& nodes) {
deba@2386: for (int i = 0; i < int(nodes.size()); ++i) {
deba@2189: snapshot.eraseNode(nodes[i]);
deba@2114: }
deba@2114: }
deba@2114: virtual void build() {
deba@2114: Node node;
deba@2114: std::vector<Node> nodes;
deba@2386: for (notifier()->first(node); node != INVALID;
deba@2386: 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: Node node;
deba@2386: for (notifier()->first(node); node != INVALID;
deba@2386: notifier()->next(node)) {
deba@2189: snapshot.eraseNode(node);
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<Edge>& 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<Edge>& edges) {
deba@2386: for (int i = 0; i < int(edges.size()); ++i) {
deba@2189: snapshot.eraseEdge(edges[i]);
deba@2114: }
deba@2114: }
deba@2114: virtual void build() {
deba@2114: Edge edge;
deba@2114: std::vector<Edge> edges;
deba@2386: for (notifier()->first(edge); edge != INVALID;
deba@2386: 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: Edge edge;
deba@2386: for (notifier()->first(edge); edge != INVALID;
deba@2386: notifier()->next(edge)) {
deba@2189: snapshot.eraseEdge(edge);
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<Node> added_nodes;
alpar@1011: std::list<Edge> added_edges;
deba@2114:
deba@2114:
deba@2114: void addNode(const Node& node) {
deba@2114: added_nodes.push_front(node);
alpar@1011: }
deba@2189: void eraseNode(const Node& node) {
deba@2114: std::list<Node>::iterator it =
deba@2114: std::find(added_nodes.begin(), added_nodes.end(), node);
deba@2114: if (it == added_nodes.end()) {
deba@2114: clear();
deba@2189: edge_observer_proxy.detach();
deba@2189: throw NodeNotifier::ImmediateDetach();
deba@2114: } else {
deba@2114: added_nodes.erase(it);
deba@2114: }
alpar@1011: }
alpar@1011:
deba@2114: void addEdge(const Edge& edge) {
deba@2114: added_edges.push_front(edge);
deba@2114: }
deba@2189: void eraseEdge(const Edge& edge) {
deba@2114: std::list<Edge>::iterator it =
deba@2114: std::find(added_edges.begin(), added_edges.end(), edge);
deba@2114: if (it == added_edges.end()) {
deba@2114: clear();
deba@2189: node_observer_proxy.detach();
deba@2189: throw EdgeNotifier::ImmediateDetach();
deba@2114: } else {
deba@2114: added_edges.erase(it);
deba@2114: }
deba@2114: }
alpar@1457:
deba@2114: void attach(ListGraph &_graph) {
deba@2114: graph = &_graph;
deba@2381: node_observer_proxy.attach(graph->notifier(Node()));
deba@2381: edge_observer_proxy.attach(graph->notifier(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@2189: bool attached() const {
deba@2189: return node_observer_proxy.attached();
deba@2189: }
deba@2189:
deba@2114: void clear() {
deba@2114: added_nodes.clear();
deba@2114: added_edges.clear();
alpar@1011: }
deba@1774:
alpar@1011: public:
deba@2114:
deba@2160: /// \brief Default constructor.
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@2189: if (attached()) {
deba@2189: detach();
deba@2189: clear();
deba@2189: }
deba@2114: attach(_graph);
alpar@1011: }
alpar@1011:
deba@2114: /// \brief Undo the changes until the last snapshot.
deba@2114: //
alpar@2123: /// Undo the changes until the last snapshot created by save().
alpar@1011: void restore() {
deba@2114: detach();
deba@2189: for(std::list<Edge>::iterator it = added_edges.begin();
deba@2189: it != added_edges.end(); ++it) {
deba@2189: graph->erase(*it);
alpar@1011: }
deba@2189: for(std::list<Node>::iterator it = added_nodes.begin();
deba@2189: it != added_nodes.end(); ++it) {
deba@2189: graph->erase(*it);
alpar@1011: }
deba@2189: clear();
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@2189: return attached();
deba@2114: }
alpar@1011: };
alpar@1011:
alpar@949: };
klao@1034:
deba@2116: ///@}
deba@2116:
deba@2338: class ListUGraphBase {
deba@2116:
deba@2338: protected:
deba@2338:
deba@2338: struct NodeT {
deba@2338: int first_out;
deba@2338: int prev, next;
deba@2338: };
deba@2338:
deba@2338: struct EdgeT {
deba@2338: int target;
deba@2338: int prev_out, next_out;
deba@2338: };
deba@2338:
deba@2338: std::vector<NodeT> nodes;
deba@2338:
deba@2338: int first_node;
deba@2338:
deba@2338: int first_free_node;
deba@2338:
deba@2338: std::vector<EdgeT> edges;
deba@2338:
deba@2338: int first_free_edge;
deba@2338:
deba@2338: public:
deba@2338:
deba@2338: typedef ListUGraphBase Graph;
deba@2343:
deba@2343: class Node;
deba@2343: class Edge;
deba@2343: class UEdge;
deba@2338:
deba@2338: class Node {
deba@2338: friend class ListUGraphBase;
deba@2338: protected:
deba@2338:
deba@2338: int id;
deba@2338: explicit Node(int pid) { id = pid;}
deba@2338:
deba@2338: public:
deba@2338: Node() {}
deba@2338: Node (Invalid) { id = -1; }
deba@2338: bool operator==(const Node& node) const {return id == node.id;}
deba@2338: bool operator!=(const Node& node) const {return id != node.id;}
deba@2338: bool operator<(const Node& node) const {return id < node.id;}
deba@2338: };
deba@2338:
deba@2338: class UEdge {
deba@2338: friend class ListUGraphBase;
deba@2338: protected:
deba@2338:
deba@2338: int id;
deba@2338: explicit UEdge(int pid) { id = pid;}
deba@2338:
deba@2338: public:
deba@2338: UEdge() {}
deba@2338: UEdge (Invalid) { id = -1; }
deba@2338: bool operator==(const UEdge& edge) const {return id == edge.id;}
deba@2338: bool operator!=(const UEdge& edge) const {return id != edge.id;}
deba@2338: bool operator<(const UEdge& edge) const {return id < edge.id;}
deba@2338: };
deba@2338:
deba@2338: class Edge {
deba@2338: friend class ListUGraphBase;
deba@2338: protected:
deba@2338:
deba@2338: int id;
deba@2338: explicit Edge(int pid) { id = pid;}
deba@2338:
deba@2338: public:
deba@2343: operator UEdge() const { return uEdgeFromId(id / 2); }
deba@2338:
deba@2338: Edge() {}
deba@2338: Edge (Invalid) { id = -1; }
deba@2338: bool operator==(const Edge& edge) const {return id == edge.id;}
deba@2338: bool operator!=(const Edge& edge) const {return id != edge.id;}
deba@2338: bool operator<(const Edge& edge) const {return id < edge.id;}
deba@2338: };
deba@2338:
deba@2338:
deba@2338:
deba@2338: ListUGraphBase()
deba@2338: : nodes(), first_node(-1),
deba@2338: first_free_node(-1), edges(), first_free_edge(-1) {}
deba@2338:
deba@2338:
deba@2338: int maxNodeId() const { return nodes.size()-1; }
deba@2338: int maxUEdgeId() const { return edges.size() / 2 - 1; }
deba@2338: int maxEdgeId() const { return edges.size()-1; }
deba@2338:
deba@2338: Node source(Edge e) const { return Node(edges[e.id ^ 1].target); }
deba@2338: Node target(Edge e) const { return Node(edges[e.id].target); }
deba@2338:
deba@2338: Node source(UEdge e) const { return Node(edges[2 * e.id].target); }
deba@2338: Node target(UEdge e) const { return Node(edges[2 * e.id + 1].target); }
deba@2338:
deba@2338: static bool direction(Edge e) {
deba@2338: return (e.id & 1) == 1;
deba@2338: }
deba@2338:
deba@2338: static Edge direct(UEdge e, bool d) {
deba@2338: return Edge(e.id * 2 + (d ? 1 : 0));
deba@2338: }
deba@2338:
deba@2338: void first(Node& node) const {
deba@2338: node.id = first_node;
deba@2338: }
deba@2338:
deba@2338: void next(Node& node) const {
deba@2338: node.id = nodes[node.id].next;
deba@2338: }
deba@2338:
deba@2338: void first(Edge& e) const {
deba@2338: int n = first_node;
deba@2338: while (n != -1 && nodes[n].first_out == -1) {
deba@2338: n = nodes[n].next;
deba@2338: }
deba@2338: e.id = (n == -1) ? -1 : nodes[n].first_out;
deba@2338: }
deba@2338:
deba@2338: void next(Edge& e) const {
deba@2338: if (edges[e.id].next_out != -1) {
deba@2338: e.id = edges[e.id].next_out;
deba@2338: } else {
deba@2338: int n = nodes[edges[e.id ^ 1].target].next;
deba@2338: while(n != -1 && nodes[n].first_out == -1) {
deba@2338: n = nodes[n].next;
deba@2338: }
deba@2338: e.id = (n == -1) ? -1 : nodes[n].first_out;
deba@2338: }
deba@2338: }
deba@2338:
deba@2338: void first(UEdge& e) const {
deba@2338: int n = first_node;
deba@2338: while (n != -1) {
deba@2338: e.id = nodes[n].first_out;
deba@2338: while ((e.id & 1) != 1) {
deba@2338: e.id = edges[e.id].next_out;
deba@2338: }
deba@2338: if (e.id != -1) {
deba@2338: e.id /= 2;
deba@2338: return;
deba@2338: }
deba@2338: n = nodes[n].next;
deba@2338: }
deba@2338: e.id = -1;
deba@2338: }
deba@2338:
deba@2338: void next(UEdge& e) const {
deba@2338: int n = edges[e.id * 2].target;
deba@2338: e.id = edges[(e.id * 2) | 1].next_out;
deba@2338: while ((e.id & 1) != 1) {
deba@2338: e.id = edges[e.id].next_out;
deba@2338: }
deba@2338: if (e.id != -1) {
deba@2338: e.id /= 2;
deba@2338: return;
deba@2338: }
deba@2338: n = nodes[n].next;
deba@2338: while (n != -1) {
deba@2338: e.id = nodes[n].first_out;
deba@2338: while ((e.id & 1) != 1) {
deba@2338: e.id = edges[e.id].next_out;
deba@2338: }
deba@2338: if (e.id != -1) {
deba@2338: e.id /= 2;
deba@2338: return;
deba@2338: }
deba@2338: n = nodes[n].next;
deba@2338: }
deba@2338: e.id = -1;
deba@2338: }
deba@2338:
deba@2338: void firstOut(Edge &e, const Node& v) const {
deba@2338: e.id = nodes[v.id].first_out;
deba@2338: }
deba@2338: void nextOut(Edge &e) const {
deba@2338: e.id = edges[e.id].next_out;
deba@2338: }
deba@2338:
deba@2338: void firstIn(Edge &e, const Node& v) const {
deba@2338: e.id = ((nodes[v.id].first_out) ^ 1);
deba@2338: if (e.id == -2) e.id = -1;
deba@2338: }
deba@2338: void nextIn(Edge &e) const {
deba@2338: e.id = ((edges[e.id ^ 1].next_out) ^ 1);
deba@2338: if (e.id == -2) e.id = -1;
deba@2338: }
deba@2338:
deba@2338: void firstInc(UEdge &e, bool& d, const Node& v) const {
deba@2338: int de = nodes[v.id].first_out;
deba@2381: if (de != -1 ) {
deba@2381: e.id = de / 2;
deba@2381: d = ((de & 1) == 1);
deba@2381: } else {
deba@2381: e.id = -1;
deba@2381: d = true;
deba@2381: }
deba@2338: }
deba@2338: void nextInc(UEdge &e, bool& d) const {
deba@2338: int de = (edges[(e.id * 2) | (d ? 1 : 0)].next_out);
deba@2381: if (de != -1 ) {
deba@2381: e.id = de / 2;
deba@2381: d = ((de & 1) == 1);
deba@2381: } else {
deba@2381: e.id = -1;
deba@2381: d = true;
deba@2381: }
deba@2338: }
deba@2338:
deba@2338: static int id(Node v) { return v.id; }
deba@2338: static int id(Edge e) { return e.id; }
deba@2338: static int id(UEdge e) { return e.id; }
deba@2338:
deba@2338: static Node nodeFromId(int id) { return Node(id);}
deba@2338: static Edge edgeFromId(int id) { return Edge(id);}
deba@2338: static UEdge uEdgeFromId(int id) { return UEdge(id);}
deba@2338:
deba@2338: Node addNode() {
deba@2338: int n;
deba@2338:
deba@2338: if(first_free_node==-1) {
deba@2338: n = nodes.size();
deba@2338: nodes.push_back(NodeT());
deba@2338: } else {
deba@2338: n = first_free_node;
deba@2338: first_free_node = nodes[n].next;
deba@2338: }
deba@2338:
deba@2338: nodes[n].next = first_node;
deba@2338: if (first_node != -1) nodes[first_node].prev = n;
deba@2338: first_node = n;
deba@2338: nodes[n].prev = -1;
deba@2338:
deba@2338: nodes[n].first_out = -1;
deba@2338:
deba@2338: return Node(n);
deba@2338: }
deba@2338:
deba@2338: UEdge addEdge(Node u, Node v) {
deba@2338: int n;
deba@2338:
deba@2338: if (first_free_edge == -1) {
deba@2338: n = edges.size();
deba@2338: edges.push_back(EdgeT());
deba@2338: edges.push_back(EdgeT());
deba@2338: } else {
deba@2338: n = first_free_edge;
deba@2338: first_free_edge = edges[n].next_out;
deba@2338: }
deba@2338:
deba@2338: edges[n].target = u.id;
deba@2338: edges[n | 1].target = v.id;
deba@2338:
deba@2338: edges[n].next_out = nodes[v.id].first_out;
deba@2338: edges[n | 1].next_out = nodes[u.id].first_out;
deba@2338: if (nodes[v.id].first_out != -1) {
deba@2338: edges[nodes[v.id].first_out].prev_out = n;
deba@2338: }
deba@2338: if (nodes[u.id].first_out != -1) {
deba@2338: edges[nodes[u.id].first_out].prev_out = (n | 1);
deba@2338: }
deba@2338:
deba@2338: edges[n].prev_out = edges[n | 1].prev_out = -1;
deba@2338:
deba@2338: nodes[v.id].first_out = n;
deba@2338: nodes[u.id].first_out = (n | 1);
deba@2338:
deba@2338: return UEdge(n / 2);
deba@2338: }
deba@2338:
deba@2338: void erase(const Node& node) {
deba@2338: int n = node.id;
deba@2338:
deba@2338: if(nodes[n].next != -1) {
deba@2338: nodes[nodes[n].next].prev = nodes[n].prev;
deba@2338: }
deba@2338:
deba@2338: if(nodes[n].prev != -1) {
deba@2338: nodes[nodes[n].prev].next = nodes[n].next;
deba@2338: } else {
deba@2338: first_node = nodes[n].next;
deba@2338: }
deba@2338:
deba@2338: nodes[n].next = first_free_node;
deba@2338: first_free_node = n;
deba@2338:
deba@2338: }
deba@2338:
deba@2338: void erase(const UEdge& edge) {
deba@2338: int n = edge.id * 2;
deba@2338:
deba@2338: if (edges[n].next_out != -1) {
deba@2338: edges[edges[n].next_out].prev_out = edges[n].prev_out;
deba@2338: }
deba@2338:
deba@2338: if (edges[n].prev_out != -1) {
deba@2338: edges[edges[n].prev_out].next_out = edges[n].next_out;
deba@2338: } else {
deba@2338: nodes[edges[n | 1].target].first_out = edges[n].next_out;
deba@2338: }
deba@2338:
deba@2338: if (edges[n | 1].next_out != -1) {
deba@2338: edges[edges[n | 1].next_out].prev_out = edges[n | 1].prev_out;
deba@2338: }
deba@2338:
deba@2338: if (edges[n | 1].prev_out != -1) {
deba@2338: edges[edges[n | 1].prev_out].next_out = edges[n | 1].next_out;
deba@2338: } else {
deba@2338: nodes[edges[n].target].first_out = edges[n | 1].next_out;
deba@2338: }
deba@2338:
deba@2338: edges[n].next_out = first_free_edge;
deba@2338: first_free_edge = n;
deba@2338:
deba@2338: }
deba@2338:
deba@2338: void clear() {
deba@2338: edges.clear();
deba@2338: nodes.clear();
deba@2338: first_node = first_free_node = first_free_edge = -1;
deba@2338: }
deba@2338:
deba@2338: protected:
deba@2338:
deba@2338: void changeTarget(UEdge e, Node n) {
deba@2338: if(edges[2 * e.id].next_out != -1) {
deba@2338: edges[edges[2 * e.id].next_out].prev_out = edges[2 * e.id].prev_out;
deba@2338: }
deba@2338: if(edges[2 * e.id].prev_out != -1) {
deba@2338: edges[edges[2 * e.id].prev_out].next_out =
deba@2338: edges[2 * e.id].next_out;
deba@2338: } else {
deba@2338: nodes[edges[(2 * e.id) | 1].target].first_out =
deba@2338: edges[2 * e.id].next_out;
deba@2338: }
deba@2338:
deba@2338: if (nodes[n.id].first_out != -1) {
deba@2338: edges[nodes[n.id].first_out].prev_out = 2 * e.id;
deba@2338: }
deba@2338: edges[(2 * e.id) | 1].target = n.id;
deba@2338: edges[2 * e.id].prev_out = -1;
deba@2338: edges[2 * e.id].next_out = nodes[n.id].first_out;
deba@2338: nodes[n.id].first_out = 2 * e.id;
deba@2338: }
deba@2338:
deba@2338: void changeSource(UEdge e, Node n) {
deba@2338: if(edges[(2 * e.id) | 1].next_out != -1) {
deba@2338: edges[edges[(2 * e.id) | 1].next_out].prev_out =
deba@2338: edges[(2 * e.id) | 1].prev_out;
deba@2338: }
deba@2338: if(edges[(2 * e.id) | 1].prev_out != -1) {
deba@2338: edges[edges[(2 * e.id) | 1].prev_out].next_out =
deba@2338: edges[(2 * e.id) | 1].next_out;
deba@2338: } else {
deba@2338: nodes[edges[2 * e.id].target].first_out =
deba@2338: edges[(2 * e.id) | 1].next_out;
deba@2338: }
deba@2338:
deba@2338: if (nodes[n.id].first_out != -1) {
deba@2338: edges[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
deba@2338: }
deba@2338: edges[2 * e.id].target = n.id;
deba@2338: edges[(2 * e.id) | 1].prev_out = -1;
deba@2338: edges[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
deba@2338: nodes[n.id].first_out = ((2 * e.id) | 1);
deba@2338: }
deba@2338:
deba@2338: };
deba@2338:
deba@2338: // typedef UGraphExtender<UndirGraphExtender<ListGraphBase> >
deba@2338: // ExtendedListUGraphBase;
deba@2338:
deba@2338: typedef UGraphExtender<ListUGraphBase> ExtendedListUGraphBase;
deba@2338:
deba@2338:
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: ///
alpar@2256: ///An important extra feature of this graph implementation is that
alpar@2260: ///its maps are real \ref concepts::ReferenceMap "reference map"s.
alpar@2256: ///
deba@2116: ///It conforms to the
alpar@2260: ///\ref concepts::UGraph "UGraph concept".
deba@2116: ///
alpar@2260: ///\sa concepts::UGraph.
deba@2116: ///
deba@2116: class ListUGraph : public ExtendedListUGraphBase {
alpar@2128: private:
alpar@2128: ///ListUGraph is \e not copy constructible. Use UGraphCopy() instead.
alpar@2128:
alpar@2128: ///ListUGraph is \e not copy constructible. Use UGraphCopy() instead.
alpar@2128: ///
alpar@2128: ListUGraph(const ListUGraph &) :ExtendedListUGraphBase() {};
alpar@2132: ///\brief Assignment of ListUGraph to another one is \e not allowed.
alpar@2128: ///Use UGraphCopy() instead.
alpar@2128:
alpar@2132: ///Assignment of ListUGraph to another one is \e not allowed.
alpar@2128: ///Use UGraphCopy() instead.
alpar@2128: void operator=(const ListUGraph &) {}
deba@2116: public:
alpar@2128: /// Constructor
alpar@2128:
alpar@2128: /// Constructor.
alpar@2128: ///
alpar@2128: ListUGraph() {}
alpar@2128:
deba@2116: typedef ExtendedListUGraphBase Parent;
deba@2338:
deba@2338: typedef Parent::OutEdgeIt IncEdgeIt;
deba@2338:
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@2160: /// \brief Changes the source of \c e to \c n
deba@2160: ///
deba@2160: /// Changes the source of \c e to \c n
deba@2160: ///
deba@2160: ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
deba@2160: ///referencing the changed edge remain
deba@2160: ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
deba@2160: void changeSource(UEdge e, Node n) {
deba@2160: Parent::changeSource(e,n);
deba@2160: }
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@2160: /// \note The <tt>EdgeIt</tt>s referencing the changed edge remain
deba@2160: /// valid. However the other iterators may be invalidated.
deba@2116: void changeTarget(UEdge e, Node n) {
deba@2116: Parent::changeTarget(e,n);
deba@2116: }
deba@2160: /// \brief Changes the source of \c e to \c n
deba@2116: ///
deba@2160: /// Changes the source of \c e to \c n. It changes the proper
deba@2160: /// node of the represented undirected edge.
deba@2116: ///
deba@2160: ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
deba@2116: ///referencing the changed edge remain
deba@2160: ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
deba@2160: void changeSource(Edge e, Node n) {
deba@2160: if (Parent::direction(e)) {
deba@2160: Parent::changeSource(e,n);
deba@2160: } else {
deba@2160: Parent::changeTarget(e,n);
deba@2160: }
deba@2160: }
deba@2160: /// \brief Changes the target of \c e to \c n
deba@2160: ///
deba@2160: /// Changes the target of \c e to \c n. It changes the proper
deba@2160: /// node of the represented undirected edge.
deba@2160: ///
deba@2160: ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
deba@2160: ///referencing the changed edge remain
deba@2160: ///valid. However <tt>InEdgeIt</tt>s are invalidated.
deba@2160: void changeTarget(Edge e, Node n) {
deba@2160: if (Parent::direction(e)) {
deba@2160: Parent::changeTarget(e,n);
deba@2160: } else {
deba@2160: Parent::changeSource(e,n);
deba@2160: }
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@2160: /// \note The <tt>EdgeIt</tt>s 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@2189:
deba@2189:
deba@2189: /// \brief Class to make a snapshot of the graph and restore
deba@2189: /// to it later.
deba@2189: ///
deba@2189: /// Class to make a snapshot of the graph and to restore it
deba@2189: /// later.
deba@2189: ///
deba@2189: /// The newly added nodes and undirected edges can be removed
deba@2189: /// using the restore() function.
deba@2189: ///
deba@2189: /// \warning Edge and node deletions cannot be restored. This
deba@2189: /// events invalidate the snapshot.
deba@2189: class Snapshot {
deba@2189: protected:
deba@2189:
deba@2189: typedef Parent::NodeNotifier NodeNotifier;
deba@2189:
deba@2189: class NodeObserverProxy : public NodeNotifier::ObserverBase {
deba@2189: public:
deba@2189:
deba@2189: NodeObserverProxy(Snapshot& _snapshot)
deba@2189: : snapshot(_snapshot) {}
deba@2189:
deba@2189: using NodeNotifier::ObserverBase::attach;
deba@2189: using NodeNotifier::ObserverBase::detach;
deba@2189: using NodeNotifier::ObserverBase::attached;
deba@2189:
deba@2189: protected:
deba@2189:
deba@2189: virtual void add(const Node& node) {
deba@2189: snapshot.addNode(node);
deba@2189: }
deba@2189: virtual void add(const std::vector<Node>& nodes) {
deba@2189: for (int i = nodes.size() - 1; i >= 0; ++i) {
deba@2189: snapshot.addNode(nodes[i]);
deba@2189: }
deba@2189: }
deba@2189: virtual void erase(const Node& node) {
deba@2189: snapshot.eraseNode(node);
deba@2189: }
deba@2189: virtual void erase(const std::vector<Node>& nodes) {
deba@2386: for (int i = 0; i < int(nodes.size()); ++i) {
deba@2189: snapshot.eraseNode(nodes[i]);
deba@2189: }
deba@2189: }
deba@2189: virtual void build() {
deba@2189: Node node;
deba@2189: std::vector<Node> nodes;
deba@2386: for (notifier()->first(node); node != INVALID;
deba@2386: notifier()->next(node)) {
deba@2189: nodes.push_back(node);
deba@2189: }
deba@2189: for (int i = nodes.size() - 1; i >= 0; --i) {
deba@2189: snapshot.addNode(nodes[i]);
deba@2189: }
deba@2189: }
deba@2189: virtual void clear() {
deba@2189: Node node;
deba@2386: for (notifier()->first(node); node != INVALID;
deba@2386: notifier()->next(node)) {
deba@2189: snapshot.eraseNode(node);
deba@2189: }
deba@2189: }
deba@2189:
deba@2189: Snapshot& snapshot;
deba@2189: };
deba@2189:
deba@2189: class UEdgeObserverProxy : public UEdgeNotifier::ObserverBase {
deba@2189: public:
deba@2189:
deba@2189: UEdgeObserverProxy(Snapshot& _snapshot)
deba@2189: : snapshot(_snapshot) {}
deba@2189:
deba@2189: using UEdgeNotifier::ObserverBase::attach;
deba@2189: using UEdgeNotifier::ObserverBase::detach;
deba@2189: using UEdgeNotifier::ObserverBase::attached;
deba@2189:
deba@2189: protected:
deba@2189:
deba@2189: virtual void add(const UEdge& edge) {
deba@2189: snapshot.addUEdge(edge);
deba@2189: }
deba@2189: virtual void add(const std::vector<UEdge>& edges) {
deba@2189: for (int i = edges.size() - 1; i >= 0; ++i) {
deba@2189: snapshot.addUEdge(edges[i]);
deba@2189: }
deba@2189: }
deba@2189: virtual void erase(const UEdge& edge) {
deba@2189: snapshot.eraseUEdge(edge);
deba@2189: }
deba@2189: virtual void erase(const std::vector<UEdge>& edges) {
deba@2386: for (int i = 0; i < int(edges.size()); ++i) {
deba@2189: snapshot.eraseUEdge(edges[i]);
deba@2189: }
deba@2189: }
deba@2189: virtual void build() {
deba@2189: UEdge edge;
deba@2189: std::vector<UEdge> edges;
deba@2386: for (notifier()->first(edge); edge != INVALID;
deba@2386: notifier()->next(edge)) {
deba@2189: edges.push_back(edge);
deba@2189: }
deba@2189: for (int i = edges.size() - 1; i >= 0; --i) {
deba@2189: snapshot.addUEdge(edges[i]);
deba@2189: }
deba@2189: }
deba@2189: virtual void clear() {
deba@2189: UEdge edge;
deba@2386: for (notifier()->first(edge); edge != INVALID;
deba@2386: notifier()->next(edge)) {
deba@2189: snapshot.eraseUEdge(edge);
deba@2189: }
deba@2189: }
deba@2189:
deba@2189: Snapshot& snapshot;
deba@2189: };
deba@2189:
deba@2189: ListUGraph *graph;
deba@2189:
deba@2189: NodeObserverProxy node_observer_proxy;
deba@2189: UEdgeObserverProxy edge_observer_proxy;
deba@2189:
deba@2189: std::list<Node> added_nodes;
deba@2189: std::list<UEdge> added_edges;
deba@2189:
deba@2189:
deba@2189: void addNode(const Node& node) {
deba@2189: added_nodes.push_front(node);
deba@2189: }
deba@2189: void eraseNode(const Node& node) {
deba@2189: std::list<Node>::iterator it =
deba@2189: std::find(added_nodes.begin(), added_nodes.end(), node);
deba@2189: if (it == added_nodes.end()) {
deba@2189: clear();
deba@2189: edge_observer_proxy.detach();
deba@2189: throw NodeNotifier::ImmediateDetach();
deba@2189: } else {
deba@2189: added_nodes.erase(it);
deba@2189: }
deba@2189: }
deba@2189:
deba@2189: void addUEdge(const UEdge& edge) {
deba@2189: added_edges.push_front(edge);
deba@2189: }
deba@2189: void eraseUEdge(const UEdge& edge) {
deba@2189: std::list<UEdge>::iterator it =
deba@2189: std::find(added_edges.begin(), added_edges.end(), edge);
deba@2189: if (it == added_edges.end()) {
deba@2189: clear();
deba@2189: node_observer_proxy.detach();
deba@2189: throw UEdgeNotifier::ImmediateDetach();
deba@2189: } else {
deba@2189: added_edges.erase(it);
deba@2189: }
deba@2189: }
deba@2189:
deba@2189: void attach(ListUGraph &_graph) {
deba@2189: graph = &_graph;
deba@2381: node_observer_proxy.attach(graph->notifier(Node()));
deba@2381: edge_observer_proxy.attach(graph->notifier(UEdge()));
deba@2189: }
deba@2189:
deba@2189: void detach() {
deba@2189: node_observer_proxy.detach();
deba@2189: edge_observer_proxy.detach();
deba@2189: }
deba@2189:
deba@2189: bool attached() const {
deba@2189: return node_observer_proxy.attached();
deba@2189: }
deba@2189:
deba@2189: void clear() {
deba@2189: added_nodes.clear();
deba@2189: added_edges.clear();
deba@2189: }
deba@2189:
deba@2189: public:
deba@2189:
deba@2189: /// \brief Default constructor.
deba@2189: ///
deba@2189: /// Default constructor.
deba@2189: /// To actually make a snapshot you must call save().
deba@2189: Snapshot()
deba@2189: : graph(0), node_observer_proxy(*this),
deba@2189: edge_observer_proxy(*this) {}
deba@2189:
deba@2189: /// \brief Constructor that immediately makes a snapshot.
deba@2189: ///
deba@2189: /// This constructor immediately makes a snapshot of the graph.
deba@2189: /// \param _graph The graph we make a snapshot of.
deba@2189: Snapshot(ListUGraph &_graph)
deba@2189: : node_observer_proxy(*this),
deba@2189: edge_observer_proxy(*this) {
deba@2189: attach(_graph);
deba@2189: }
deba@2189:
deba@2189: /// \brief Make a snapshot.
deba@2189: ///
deba@2189: /// Make a snapshot of the graph.
deba@2189: ///
deba@2189: /// This function can be called more than once. In case of a repeated
deba@2189: /// call, the previous snapshot gets lost.
deba@2189: /// \param _graph The graph we make the snapshot of.
deba@2189: void save(ListUGraph &_graph) {
deba@2189: if (attached()) {
deba@2189: detach();
deba@2189: clear();
deba@2189: }
deba@2189: attach(_graph);
deba@2189: }
deba@2189:
deba@2189: /// \brief Undo the changes until the last snapshot.
deba@2189: //
deba@2189: /// Undo the changes until the last snapshot created by save().
deba@2189: void restore() {
deba@2189: detach();
deba@2189: for(std::list<UEdge>::iterator it = added_edges.begin();
deba@2189: it != added_edges.end(); ++it) {
deba@2189: graph->erase(*it);
deba@2189: }
deba@2189: for(std::list<Node>::iterator it = added_nodes.begin();
deba@2189: it != added_nodes.end(); ++it) {
deba@2189: graph->erase(*it);
deba@2189: }
deba@2189: clear();
deba@2189: }
deba@2189:
deba@2189: /// \brief Gives back true when the snapshot is valid.
deba@2189: ///
deba@2189: /// Gives back true when the snapshot is valid.
deba@2189: bool valid() const {
deba@2189: return attached();
deba@2189: }
deba@2189: };
deba@2116: };
deba@2116:
deba@2116:
deba@2116: class ListBpUGraphBase {
deba@2116: public:
deba@2116:
deba@2116: class NodeSetError : public LogicError {
deba@2160: public:
alpar@2151: virtual const char* what() const throw() {
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<NodeT> aNodes;
deba@2116: std::vector<NodeT> bNodes;
deba@2116:
deba@2116: std::vector<UEdgeT> 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<i.id;}
deba@2116: };
deba@2116:
deba@2116: class UEdge {
deba@2116: friend class ListBpUGraphBase;
deba@2116: protected:
deba@2116: int id;
deba@2116:
deba@2116: explicit UEdge(int _id) { id = _id;}
deba@2116: public:
deba@2116: UEdge() {}
deba@2116: UEdge (Invalid) { id = -1; }
deba@2116: bool operator==(const UEdge i) const {return id==i.id;}
deba@2116: bool operator!=(const UEdge i) const {return id!=i.id;}
deba@2116: bool operator<(const UEdge i) const {return id<i.id;}
deba@2116: };
deba@2116:
deba@2116: ListBpUGraphBase()
deba@2116: : first_anode(-1), first_free_anode(-1),
deba@2116: first_bnode(-1), first_free_bnode(-1),
deba@2116: first_free_edge(-1) {}
deba@2116:
deba@2116: void firstANode(Node& node) const {
deba@2116: node.id = first_anode != -1 ? (first_anode << 1) : -1;
deba@2116: }
deba@2116: void nextANode(Node& node) const {
deba@2116: node.id = aNodes[node.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@2386: int aid = first_anode;
deba@2386: while (aid != -1 && aNodes[aid].first_edge == -1) {
deba@2386: aid = aNodes[aid].next != -1 ?
deba@2386: aNodes[aid].next >> 1 : -1;
deba@2116: }
deba@2386: if (aid != -1) {
deba@2386: edge.id = aNodes[aid].first_edge;
deba@2116: } else {
deba@2116: edge.id = -1;
deba@2116: }
deba@2116: }
deba@2116: void next(UEdge& edge) const {
deba@2386: int aid = edges[edge.id].aNode >> 1;
deba@2116: edge.id = edges[edge.id].next_out;
deba@2116: if (edge.id == -1) {
deba@2386: aid = aNodes[aid].next != -1 ?
deba@2386: aNodes[aid].next >> 1 : -1;
deba@2386: while (aid != -1 && aNodes[aid].first_edge == -1) {
deba@2386: aid = aNodes[aid].next != -1 ?
deba@2386: aNodes[aid].next >> 1 : -1;
deba@2116: }
deba@2386: if (aid != -1) {
deba@2386: edge.id = aNodes[aid].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@2231: static Node nodeFromANodeId(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@2231: static Node nodeFromBNodeId(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@2386: int aid;
deba@2116: if (first_free_anode == -1) {
deba@2386: aid = aNodes.size();
deba@2116: aNodes.push_back(NodeT());
deba@2116: } else {
deba@2386: aid = first_free_anode;
deba@2116: first_free_anode = aNodes[first_free_anode].next;
deba@2116: }
deba@2116: if (first_anode != -1) {
deba@2386: aNodes[aid].next = first_anode << 1;
deba@2386: aNodes[first_anode].prev = aid << 1;
deba@2116: } else {
deba@2386: aNodes[aid].next = -1;
deba@2116: }
deba@2386: aNodes[aid].prev = -1;
deba@2386: first_anode = aid;
deba@2386: aNodes[aid].first_edge = -1;
deba@2386: return Node(aid << 1);
deba@2116: }
deba@2116:
deba@2116: Node addBNode() {
deba@2386: int bid;
deba@2116: if (first_free_bnode == -1) {
deba@2386: bid = bNodes.size();
deba@2116: bNodes.push_back(NodeT());
deba@2116: } else {
deba@2386: bid = first_free_bnode;
deba@2116: first_free_bnode = bNodes[first_free_bnode].next;
deba@2116: }
deba@2116: if (first_bnode != -1) {
deba@2386: bNodes[bid].next = (first_bnode << 1) + 1;
deba@2386: bNodes[first_bnode].prev = (bid << 1) + 1;
deba@2116: } else {
deba@2386: bNodes[bid].next = -1;
deba@2116: }
deba@2386: bNodes[bid].prev = -1;
deba@2386: first_bnode = bid;
deba@2386: bNodes[bid].first_edge = -1;
deba@2386: return Node((bid << 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@2386: int aid = node.id >> 1;
deba@2386: if (aNodes[aid].prev != -1) {
deba@2386: aNodes[aNodes[aid].prev >> 1].next = aNodes[aid].next;
deba@2116: } else {
deba@2189: first_anode =
deba@2386: aNodes[aid].next != -1 ? aNodes[aid].next >> 1 : -1;
deba@2116: }
deba@2386: if (aNodes[aid].next != -1) {
deba@2386: aNodes[aNodes[aid].next >> 1].prev = aNodes[aid].prev;
deba@2116: }
deba@2386: aNodes[aid].next = first_free_anode;
deba@2386: first_free_anode = aid;
deba@2116: } else {
deba@2386: int bid = node.id >> 1;
deba@2386: if (bNodes[bid].prev != -1) {
deba@2386: bNodes[bNodes[bid].prev >> 1].next = bNodes[bid].next;
deba@2116: } else {
deba@2189: first_bnode =
deba@2386: bNodes[bid].next != -1 ? bNodes[bid].next >> 1 : -1;
deba@2116: }
deba@2386: if (bNodes[bid].next != -1) {
deba@2386: bNodes[bNodes[bid].next >> 1].prev = bNodes[bid].prev;
deba@2116: }
deba@2386: bNodes[bid].next = first_free_bnode;
deba@2386: first_free_bnode = bid;
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: }
alpar@2128:
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@2160: void changeANode(const UEdge& edge, const Node& node) {
deba@2160: LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
deba@2160: if (edges[edge.id].prev_out != -1) {
deba@2160: edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
deba@2160: } else {
deba@2160: aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
deba@2160: }
deba@2160: if (edges[edge.id].next_out != -1) {
deba@2160: edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
deba@2160: }
deba@2160: if (aNodes[node.id >> 1].first_edge != -1) {
deba@2160: edges[aNodes[node.id >> 1].first_edge].prev_out = edge.id;
deba@2160: }
deba@2160: edges[edge.id].prev_out = -1;
deba@2160: edges[edge.id].next_out = aNodes[node.id >> 1].first_edge;
deba@2160: aNodes[node.id >> 1].first_edge = edge.id;
deba@2160: edges[edge.id].aNode = node.id;
deba@2160: }
deba@2160:
deba@2160: void changeBNode(const UEdge& edge, const Node& node) {
deba@2160: LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
deba@2160: if (edges[edge.id].prev_in != -1) {
deba@2160: edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
deba@2160: } else {
deba@2160: bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
deba@2160: }
deba@2160: if (edges[edge.id].next_in != -1) {
deba@2160: edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
deba@2160: }
deba@2160: if (bNodes[node.id >> 1].first_edge != -1) {
deba@2160: edges[bNodes[node.id >> 1].first_edge].prev_in = edge.id;
deba@2160: }
deba@2160: edges[edge.id].prev_in = -1;
deba@2160: edges[edge.id].next_in = bNodes[node.id >> 1].first_edge;
deba@2160: bNodes[node.id >> 1].first_edge = edge.id;
deba@2160: edges[edge.id].bNode = node.id;
deba@2160: }
deba@2160:
deba@2116: };
deba@2116:
deba@2116:
deba@2231: typedef BpUGraphExtender<BidirBpUGraphExtender<ListBpUGraphBase> >
deba@2231: 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@2260: /// It is conforms to the \ref concepts::BpUGraph "BpUGraph concept".
alpar@2256: ///
alpar@2256: ///An important extra feature of this graph implementation is that
alpar@2260: ///its maps are real \ref concepts::ReferenceMap "reference map"s.
alpar@2256: ///
alpar@2260: /// \sa concepts::BpUGraph.
deba@2116: ///
deba@2160: class ListBpUGraph : public ExtendedListBpUGraphBase {
deba@2160: /// \brief ListBpUGraph is \e not copy constructible.
deba@2160: ///
deba@2160: ///ListBpUGraph is \e not copy constructible.
deba@2160: ListBpUGraph(const ListBpUGraph &) :ExtendedListBpUGraphBase() {};
deba@2160: /// \brief Assignment of ListBpUGraph to another one is \e not
deba@2160: /// allowed.
deba@2160: ///
deba@2160: /// Assignment of ListBpUGraph to another one is \e not allowed.
deba@2160: void operator=(const ListBpUGraph &) {}
deba@2160: public:
deba@2160: /// \brief Constructor
deba@2160: ///
deba@2160: /// Constructor.
deba@2160: ///
deba@2160: ListBpUGraph() {}
deba@2160:
deba@2160: typedef ExtendedListBpUGraphBase Parent;
deba@2160: /// \brief Add a new ANode to the graph.
deba@2160: ///
deba@2160: /// \return the new node.
deba@2160: ///
deba@2160: Node addANode() { return Parent::addANode(); }
deba@2160:
deba@2160: /// \brief Add a new BNode to the graph.
deba@2160: ///
deba@2160: /// \return the new node.
deba@2160: ///
deba@2160: Node addBNode() { return Parent::addBNode(); }
deba@2160:
deba@2160: /// \brief Add a new edge to the graph.
deba@2160: ///
deba@2160: /// Add a new edge to the graph with an ANode and a BNode.
deba@2160: /// \return the new undirected edge.
deba@2160: UEdge addEdge(const Node& s, const Node& t) {
deba@2160: return Parent::addEdge(s, t);
deba@2160: }
deba@2160:
deba@2160: /// \brief Changes the ANode of \c e to \c n
deba@2160: ///
deba@2160: /// Changes the ANode of \c e to \c n
deba@2160: ///
deba@2160: ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
deba@2160: ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
deba@2160: ///invalidated.
deba@2160: void changeANode(UEdge e, Node n) {
deba@2160: Parent::changeANode(e,n);
deba@2160: }
deba@2160:
deba@2160: /// \brief Changes the BNode of \c e to \c n
deba@2160: ///
deba@2160: /// Changes the BNode of \c e to \c n
deba@2160: ///
deba@2160: /// \note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
deba@2160: /// referencing the changed edge remain
deba@2160: /// valid. However <tt>InEdgeIt</tt>s are invalidated.
deba@2160: void changeBNode(UEdge e, Node n) {
deba@2160: Parent::changeBNode(e,n);
deba@2160: }
deba@2160:
deba@2160: /// \brief Changes the source(ANode) of \c e to \c n
deba@2160: ///
deba@2160: /// Changes the source(ANode) of \c e to \c n
deba@2160: ///
deba@2160: ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
deba@2160: ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
deba@2160: ///invalidated.
deba@2160: void changeSource(UEdge e, Node n) {
deba@2160: Parent::changeANode(e,n);
deba@2160: }
deba@2160:
deba@2160: /// \brief Changes the target(BNode) of \c e to \c n
deba@2160: ///
deba@2160: /// Changes the target(BNode) of \c e to \c n
deba@2160: ///
deba@2160: /// \note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
deba@2160: /// referencing the changed edge remain
deba@2160: /// valid. However <tt>InEdgeIt</tt>s are invalidated.
deba@2160: void changeTarget(UEdge e, Node n) {
deba@2160: Parent::changeBNode(e,n);
deba@2160: }
deba@2160:
deba@2160: /// \brief Changes the source of \c e to \c n
deba@2160: ///
deba@2160: /// Changes the source of \c e to \c n. It changes the proper
deba@2160: /// node of the represented undirected edge.
deba@2160: ///
deba@2160: ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
deba@2160: ///referencing the changed edge remain
deba@2160: ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
deba@2160: void changeSource(Edge e, Node n) {
deba@2160: if (Parent::direction(e)) {
deba@2160: Parent::changeANode(e,n);
deba@2160: } else {
deba@2160: Parent::changeBNode(e,n);
deba@2160: }
deba@2160: }
deba@2160: /// \brief Changes the target of \c e to \c n
deba@2160: ///
deba@2160: /// Changes the target of \c e to \c n. It changes the proper
deba@2160: /// node of the represented undirected edge.
deba@2160: ///
deba@2160: ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
deba@2160: ///referencing the changed edge remain
deba@2160: ///valid. However <tt>InEdgeIt</tt>s are invalidated.
deba@2160: void changeTarget(Edge e, Node n) {
deba@2160: if (Parent::direction(e)) {
deba@2160: Parent::changeBNode(e,n);
deba@2160: } else {
deba@2160: Parent::changeANode(e,n);
deba@2160: }
deba@2160: }
deba@2160: /// \brief Contract two nodes.
deba@2160: ///
deba@2160: /// This function contracts two nodes.
deba@2160: ///
deba@2160: /// Node \p b will be removed but instead of deleting its
deba@2160: /// neighboring edges, they will be joined to \p a. The two nodes
deba@2160: /// should be from the same nodeset, of course.
deba@2160: ///
deba@2160: /// \note The <tt>EdgeIt</tt>s referencing a moved edge remain
deba@2160: /// valid.
deba@2160: void contract(const Node& a, const Node& b) {
deba@2160: LEMON_ASSERT(Parent::aNode(a) == Parent::aNode(b), NodeSetError());
deba@2160: if (Parent::aNode(a)) {
deba@2160: for (IncEdgeIt e(*this, b); e!=INVALID;) {
deba@2160: IncEdgeIt f = e; ++f;
deba@2160: changeSource(e, a);
deba@2160: e = f;
deba@2160: }
deba@2160: } else {
deba@2160: for (IncEdgeIt e(*this, b); e!=INVALID;) {
deba@2160: IncEdgeIt f = e; ++f;
deba@2160: changeTarget(e, a);
deba@2160: e = f;
deba@2160: }
deba@2160: }
deba@2160: erase(b);
deba@2160: }
deba@2160:
deba@2189: /// \brief Class to make a snapshot of the graph and restore
deba@2189: /// to it later.
deba@2189: ///
deba@2189: /// Class to make a snapshot of the graph and to restore it
deba@2189: /// later.
deba@2189: ///
deba@2189: /// The newly added nodes and undirected edges can be removed
deba@2189: /// using the restore() function.
deba@2189: ///
deba@2189: /// \warning Edge and node deletions cannot be restored. This
deba@2189: /// events invalidate the snapshot.
deba@2189: class Snapshot {
deba@2189: protected:
deba@2189:
deba@2189: typedef Parent::NodeNotifier NodeNotifier;
deba@2189:
deba@2189: class NodeObserverProxy : public NodeNotifier::ObserverBase {
deba@2189: public:
deba@2189:
deba@2189: NodeObserverProxy(Snapshot& _snapshot)
deba@2189: : snapshot(_snapshot) {}
deba@2189:
deba@2189: using NodeNotifier::ObserverBase::attach;
deba@2189: using NodeNotifier::ObserverBase::detach;
deba@2189: using NodeNotifier::ObserverBase::attached;
deba@2189:
deba@2189: protected:
deba@2189:
deba@2189: virtual void add(const Node& node) {
deba@2189: snapshot.addNode(node);
deba@2189: }
deba@2189: virtual void add(const std::vector<Node>& nodes) {
deba@2189: for (int i = nodes.size() - 1; i >= 0; ++i) {
deba@2189: snapshot.addNode(nodes[i]);
deba@2189: }
deba@2189: }
deba@2189: virtual void erase(const Node& node) {
deba@2189: snapshot.eraseNode(node);
deba@2189: }
deba@2189: virtual void erase(const std::vector<Node>& nodes) {
deba@2386: for (int i = 0; i < int(nodes.size()); ++i) {
deba@2189: snapshot.eraseNode(nodes[i]);
deba@2189: }
deba@2189: }
deba@2189: virtual void build() {
deba@2189: Node node;
deba@2189: std::vector<Node> nodes;
deba@2386: for (notifier()->first(node); node != INVALID;
deba@2386: notifier()->next(node)) {
deba@2189: nodes.push_back(node);
deba@2189: }
deba@2189: for (int i = nodes.size() - 1; i >= 0; --i) {
deba@2189: snapshot.addNode(nodes[i]);
deba@2189: }
deba@2189: }
deba@2189: virtual void clear() {
deba@2189: Node node;
deba@2386: for (notifier()->first(node); node != INVALID;
deba@2386: notifier()->next(node)) {
deba@2189: snapshot.eraseNode(node);
deba@2189: }
deba@2189: }
deba@2189:
deba@2189: Snapshot& snapshot;
deba@2189: };
deba@2189:
deba@2189: class UEdgeObserverProxy : public UEdgeNotifier::ObserverBase {
deba@2189: public:
deba@2189:
deba@2189: UEdgeObserverProxy(Snapshot& _snapshot)
deba@2189: : snapshot(_snapshot) {}
deba@2189:
deba@2189: using UEdgeNotifier::ObserverBase::attach;
deba@2189: using UEdgeNotifier::ObserverBase::detach;
deba@2189: using UEdgeNotifier::ObserverBase::attached;
deba@2189:
deba@2189: protected:
deba@2189:
deba@2189: virtual void add(const UEdge& edge) {
deba@2189: snapshot.addUEdge(edge);
deba@2189: }
deba@2189: virtual void add(const std::vector<UEdge>& edges) {
deba@2189: for (int i = edges.size() - 1; i >= 0; ++i) {
deba@2189: snapshot.addUEdge(edges[i]);
deba@2189: }
deba@2189: }
deba@2189: virtual void erase(const UEdge& edge) {
deba@2189: snapshot.eraseUEdge(edge);
deba@2189: }
deba@2189: virtual void erase(const std::vector<UEdge>& edges) {
deba@2386: for (int i = 0; i < int(edges.size()); ++i) {
deba@2189: snapshot.eraseUEdge(edges[i]);
deba@2189: }
deba@2189: }
deba@2189: virtual void build() {
deba@2189: UEdge edge;
deba@2189: std::vector<UEdge> edges;
deba@2386: for (notifier()->first(edge); edge != INVALID;
deba@2386: notifier()->next(edge)) {
deba@2189: edges.push_back(edge);
deba@2189: }
deba@2189: for (int i = edges.size() - 1; i >= 0; --i) {
deba@2189: snapshot.addUEdge(edges[i]);
deba@2189: }
deba@2189: }
deba@2189: virtual void clear() {
deba@2189: UEdge edge;
deba@2386: for (notifier()->first(edge); edge != INVALID;
deba@2386: notifier()->next(edge)) {
deba@2189: snapshot.eraseUEdge(edge);
deba@2189: }
deba@2189: }
deba@2189:
deba@2189: Snapshot& snapshot;
deba@2189: };
deba@2189:
deba@2189: ListBpUGraph *graph;
deba@2189:
deba@2189: NodeObserverProxy node_observer_proxy;
deba@2189: UEdgeObserverProxy edge_observer_proxy;
deba@2189:
deba@2189: std::list<Node> added_nodes;
deba@2189: std::list<UEdge> added_edges;
deba@2189:
deba@2189:
deba@2189: void addNode(const Node& node) {
deba@2189: added_nodes.push_front(node);
deba@2189: }
deba@2189: void eraseNode(const Node& node) {
deba@2189: std::list<Node>::iterator it =
deba@2189: std::find(added_nodes.begin(), added_nodes.end(), node);
deba@2189: if (it == added_nodes.end()) {
deba@2189: clear();
deba@2189: edge_observer_proxy.detach();
deba@2189: throw NodeNotifier::ImmediateDetach();
deba@2189: } else {
deba@2189: added_nodes.erase(it);
deba@2189: }
deba@2189: }
deba@2189:
deba@2189: void addUEdge(const UEdge& edge) {
deba@2189: added_edges.push_front(edge);
deba@2189: }
deba@2189: void eraseUEdge(const UEdge& edge) {
deba@2189: std::list<UEdge>::iterator it =
deba@2189: std::find(added_edges.begin(), added_edges.end(), edge);
deba@2189: if (it == added_edges.end()) {
deba@2189: clear();
deba@2189: node_observer_proxy.detach();
deba@2189: throw UEdgeNotifier::ImmediateDetach();
deba@2189: } else {
deba@2189: added_edges.erase(it);
deba@2189: }
deba@2189: }
deba@2189:
deba@2189: void attach(ListBpUGraph &_graph) {
deba@2189: graph = &_graph;
deba@2381: node_observer_proxy.attach(graph->notifier(Node()));
deba@2381: edge_observer_proxy.attach(graph->notifier(UEdge()));
deba@2189: }
deba@2189:
deba@2189: void detach() {
deba@2189: node_observer_proxy.detach();
deba@2189: edge_observer_proxy.detach();
deba@2189: }
deba@2189:
deba@2189: bool attached() const {
deba@2189: return node_observer_proxy.attached();
deba@2189: }
deba@2189:
deba@2189: void clear() {
deba@2189: added_nodes.clear();
deba@2189: added_edges.clear();
deba@2189: }
deba@2189:
deba@2189: public:
deba@2189:
deba@2189: /// \brief Default constructor.
deba@2189: ///
deba@2189: /// Default constructor.
deba@2189: /// To actually make a snapshot you must call save().
deba@2189: Snapshot()
deba@2189: : graph(0), node_observer_proxy(*this),
deba@2189: edge_observer_proxy(*this) {}
deba@2189:
deba@2189: /// \brief Constructor that immediately makes a snapshot.
deba@2189: ///
deba@2189: /// This constructor immediately makes a snapshot of the graph.
deba@2189: /// \param _graph The graph we make a snapshot of.
deba@2189: Snapshot(ListBpUGraph &_graph)
deba@2189: : node_observer_proxy(*this),
deba@2189: edge_observer_proxy(*this) {
deba@2189: attach(_graph);
deba@2189: }
deba@2189:
deba@2189: /// \brief Make a snapshot.
deba@2189: ///
deba@2189: /// Make a snapshot of the graph.
deba@2189: ///
deba@2189: /// This function can be called more than once. In case of a repeated
deba@2189: /// call, the previous snapshot gets lost.
deba@2189: /// \param _graph The graph we make the snapshot of.
deba@2189: void save(ListBpUGraph &_graph) {
deba@2189: if (attached()) {
deba@2189: detach();
deba@2189: clear();
deba@2189: }
deba@2189: attach(_graph);
deba@2189: }
deba@2189:
deba@2189: /// \brief Undo the changes until the last snapshot.
deba@2189: //
deba@2189: /// Undo the changes until the last snapshot created by save().
deba@2189: void restore() {
deba@2189: detach();
deba@2189: for(std::list<UEdge>::iterator it = added_edges.begin();
deba@2189: it != added_edges.end(); ++it) {
deba@2189: graph->erase(*it);
deba@2189: }
deba@2189: for(std::list<Node>::iterator it = added_nodes.begin();
deba@2189: it != added_nodes.end(); ++it) {
deba@2189: graph->erase(*it);
deba@2189: }
deba@2189: clear();
deba@2189: }
deba@2189:
deba@2189: /// \brief Gives back true when the snapshot is valid.
deba@2189: ///
deba@2189: /// Gives back true when the snapshot is valid.
deba@2189: bool valid() const {
deba@2189: return attached();
deba@2189: }
deba@2189: };
deba@2160: };
deba@2116:
deba@2116:
deba@2116: /// @}
alpar@948: } //namespace lemon
klao@946:
alpar@400:
klao@946: #endif