alpar@906: /* -*- C++ -*-
alpar@906: *
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@906: *
alpar@906: * Permission to use, modify and distribute this software is granted
alpar@906: * provided that this copyright notice appears in all copies. For
alpar@906: * precise terms see the accompanying LICENSE file.
alpar@906: *
alpar@906: * This software is provided "AS IS" with no warranty of any kind,
alpar@906: * express or implied, and with no claim as to its suitability for any
alpar@906: * purpose.
alpar@906: *
alpar@906: */
alpar@105:
alpar@921: #ifndef LEMON_SMART_GRAPH_H
alpar@921: #define LEMON_SMART_GRAPH_H
alpar@104:
klao@491: ///\ingroup graphs
alpar@242: ///\file
deba@2116: ///\brief SmartGraph and SmartUGraph classes.
alpar@242:
alpar@104: #include <vector>
alpar@104:
deba@1993: #include <lemon/bits/invalid.h>
alpar@157:
deba@2116: #include <lemon/bits/base_extender.h>
deba@1791: #include <lemon/bits/graph_extender.h>
klao@1034:
deba@1993: #include <lemon/bits/utility.h>
deba@2116: #include <lemon/error.h>
deba@782:
deba@1979: #include <lemon/bits/graph_extender.h>
deba@1979:
alpar@921: namespace lemon {
alpar@104:
alpar@973: class SmartGraph;
alpar@969: ///Base of SmartGraph
alpar@969:
alpar@969: ///Base of SmartGraph
alpar@969: ///
klao@946: class SmartGraphBase {
deba@2190: protected:
alpar@104:
alpar@104: struct NodeT
alpar@104: {
deba@2190: int first_in, first_out;
deba@2190: NodeT() {}
alpar@104: };
alpar@104: struct EdgeT
alpar@104: {
alpar@986: int target, source, next_in, next_out;
deba@2190: EdgeT() {}
alpar@104: };
alpar@104:
alpar@104: std::vector<NodeT> nodes;
alpar@129:
alpar@104: std::vector<EdgeT> edges;
alpar@104:
alpar@185:
alpar@104: public:
deba@782:
klao@946: typedef SmartGraphBase Graph;
alpar@104:
alpar@164: class Node;
alpar@164: class Edge;
alpar@108:
alpar@104:
alpar@104: public:
alpar@104:
klao@946: SmartGraphBase() : nodes(), edges() { }
deba@1718: SmartGraphBase(const SmartGraphBase &_g)
deba@1718: : nodes(_g.nodes), edges(_g.edges) { }
alpar@104:
klao@977: typedef True NodeNumTag;
klao@977: typedef True EdgeNumTag;
klao@977:
alpar@813: int nodeNum() const { return nodes.size(); }
alpar@813: int edgeNum() const { return edges.size(); }
alpar@104:
deba@1791: int maxNodeId() const { return nodes.size()-1; }
deba@1791: int maxEdgeId() const { return edges.size()-1; }
alpar@108:
alpar@2128: Node addNode() {
deba@2190: int n = nodes.size();
deba@2190: nodes.push_back(NodeT());
deba@2190: nodes[n].first_in = -1;
deba@2190: nodes[n].first_out = -1;
deba@2190: return Node(n);
alpar@2128: }
alpar@2128:
alpar@2128: Edge addEdge(Node u, Node v) {
deba@2190: int n = edges.size();
deba@2190: edges.push_back(EdgeT());
deba@2190: edges[n].source = u.id;
deba@2190: edges[n].target = v.id;
deba@2190: edges[n].next_out = nodes[u.id].first_out;
deba@2190: edges[n].next_in = nodes[v.id].first_in;
deba@2190: nodes[u.id].first_out = nodes[v.id].first_in = n;
alpar@2128:
deba@2190: return Edge(n);
alpar@2128: }
alpar@2128:
deba@2190: void clear() {
deba@2190: edges.clear();
deba@2190: nodes.clear();
deba@2190: }
alpar@2128:
deba@2190: Node source(Edge e) const { return Node(edges[e.id].source); }
deba@2190: Node target(Edge e) const { return Node(edges[e.id].target); }
alpar@104:
deba@2190: static int id(Node v) { return v.id; }
deba@2190: static int id(Edge e) { return e.id; }
alpar@104:
deba@1791: static Node nodeFromId(int id) { return Node(id);}
deba@1791: static Edge edgeFromId(int id) { return Edge(id);}
deba@1106:
alpar@164: class Node {
klao@946: friend class SmartGraphBase;
alpar@973: friend class SmartGraph;
alpar@104:
alpar@104: protected:
deba@2190: int id;
deba@2190: explicit Node(int _id) : id(_id) {}
alpar@104: public:
alpar@164: Node() {}
deba@2190: Node (Invalid) : id(-1) {}
deba@2190: bool operator==(const Node i) const {return id == i.id;}
deba@2190: bool operator!=(const Node i) const {return id != i.id;}
deba@2190: bool operator<(const Node i) const {return id < i.id;}
alpar@104: };
alpar@104:
alpar@104:
alpar@164: class Edge {
klao@946: friend class SmartGraphBase;
alpar@973: friend class SmartGraph;
alpar@185:
alpar@104: protected:
deba@2190: int id;
deba@2190: explicit Edge(int _id) : id(_id) {}
alpar@706: public:
alpar@164: Edge() { }
deba@2190: Edge (Invalid) : id(-1) {}
deba@2190: bool operator==(const Edge i) const {return id == i.id;}
deba@2190: bool operator!=(const Edge i) const {return id != i.id;}
deba@2190: bool operator<(const Edge i) const {return id < i.id;}
klao@946: };
alpar@905:
klao@946: void first(Node& node) const {
deba@2190: node.id = nodes.size() - 1;
klao@946: }
klao@946:
klao@946: static void next(Node& node) {
deba@2190: --node.id;
klao@946: }
klao@946:
klao@946: void first(Edge& edge) const {
deba@2190: edge.id = edges.size() - 1;
klao@946: }
klao@946:
klao@946: static void next(Edge& edge) {
deba@2190: --edge.id;
klao@946: }
klao@946:
klao@946: void firstOut(Edge& edge, const Node& node) const {
deba@2190: edge.id = nodes[node.id].first_out;
klao@946: }
klao@946:
klao@946: void nextOut(Edge& edge) const {
deba@2190: edge.id = edges[edge.id].next_out;
klao@946: }
klao@946:
klao@946: void firstIn(Edge& edge, const Node& node) const {
deba@2190: edge.id = nodes[node.id].first_in;
klao@946: }
alpar@104:
klao@946: void nextIn(Edge& edge) const {
deba@2190: edge.id = edges[edge.id].next_in;
klao@946: }
alpar@105:
alpar@104: };
alpar@185:
deba@1979: typedef GraphExtender<SmartGraphBase> ExtendedSmartGraphBase;
deba@937:
deba@1791: /// \ingroup graphs
alpar@1161:
alpar@950: ///A smart graph class.
deba@937:
alpar@950: ///This is a simple and fast graph implementation.
alpar@950: ///It is also quite memory efficient, but at the price
alpar@974: ///that <b> it does support only limited (only stack-like)
alpar@974: ///node and edge deletions</b>.
alpar@950: ///It conforms to
alpar@2260: ///the \ref concepts::Graph "Graph concept" with an
alpar@2256: ///important extra feature that
alpar@2260: ///its maps are real \ref concepts::ReferenceMap "reference map"s.
alpar@2256: ///
alpar@2260: ///\sa concepts::Graph.
alpar@950: ///
alpar@950: ///\author Alpar Juttner
deba@1669: class SmartGraph : public ExtendedSmartGraphBase {
alpar@969: public:
deba@1979:
deba@1979: typedef ExtendedSmartGraphBase Parent;
deba@1979:
deba@2190: private:
alpar@973:
alpar@2128: ///SmartGraph is \e not copy constructible. Use GraphCopy() instead.
alpar@2128:
alpar@2128: ///SmartGraph is \e not copy constructible. Use GraphCopy() instead.
alpar@2128: ///
deba@2190: SmartGraph(const SmartGraph &) : ExtendedSmartGraphBase() {};
alpar@2132: ///\brief Assignment of SmartGraph to another one is \e not allowed.
alpar@2128: ///Use GraphCopy() instead.
alpar@2128:
alpar@2132: ///Assignment of SmartGraph to another one is \e not allowed.
alpar@2128: ///Use GraphCopy() instead.
alpar@2128: void operator=(const SmartGraph &) {}
alpar@1011:
alpar@1011: public:
alpar@2128:
alpar@2128: /// Constructor
alpar@2128:
alpar@2128: /// Constructor.
alpar@2128: ///
alpar@2128: SmartGraph() {};
alpar@2128:
alpar@2128: ///Add a new node to the graph.
alpar@2128:
alpar@2128: /// \return the new node.
alpar@2128: ///
alpar@2128: Node addNode() { return Parent::addNode(); }
alpar@2128:
alpar@2128: ///Add a new edge to the graph.
alpar@2128:
alpar@2128: ///Add a new edge to the graph with source node \c s
alpar@2128: ///and target node \c t.
alpar@2128: ///\return the new edge.
alpar@2128: Edge addEdge(const Node& s, const Node& t) {
alpar@2128: return Parent::addEdge(s, t);
alpar@2128: }
alpar@2128:
deba@2190: ///Clear the graph.
alpar@2128:
deba@2190: ///Erase all the nodes and edges from the graph.
deba@2190: ///
alpar@2128: void clear() {
deba@2190: Parent::clear();
alpar@2128: }
alpar@1284:
alpar@1284: ///Split a node.
alpar@1284:
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@1284: ///If \c connect is \c true (this is the default value), then a new edge
alpar@1284: ///from \c n to the newly created node is also added.
alpar@1284: ///\return The newly created node.
alpar@1284: ///
alpar@1284: ///\note The <tt>Edge</tt>s
alpar@1284: ///referencing a moved edge remain
alpar@1284: ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s
alpar@1284: ///may be invalidated.
alpar@1770: ///\warning This functionality cannot be used together with the Snapshot
alpar@1284: ///feature.
alpar@1284: ///\todo It could be implemented in a bit faster way.
alpar@2128: Node split(Node n, bool connect = true)
alpar@1284: {
alpar@2128: Node b = addNode();
deba@2190: nodes[b.id].first_out=nodes[n.id].first_out;
deba@2190: nodes[n.id].first_out=-1;
deba@2190: for(int i=nodes[b.id].first_out;i!=-1;i++) edges[i].source=b.id;
alpar@2128: if(connect) addEdge(n,b);
deba@1718: return b;
alpar@1284: }
alpar@1284:
deba@2190: public:
deba@2190:
deba@2190: class Snapshot;
deba@2190:
deba@2190: protected:
deba@2190:
deba@2190: void restoreSnapshot(const Snapshot &s)
deba@2190: {
deba@2190: while(s.edge_num<edges.size()) {
deba@2190: Edge edge = edgeFromId(edges.size()-1);
deba@2190: Parent::getNotifier(Edge()).erase(edge);
deba@2190: nodes[edges.back().source].first_out=edges.back().next_out;
deba@2190: nodes[edges.back().target].first_in=edges.back().next_in;
deba@2190: edges.pop_back();
deba@2190: }
deba@2190: while(s.node_num<nodes.size()) {
deba@2190: Node node = nodeFromId(nodes.size()-1);
deba@2190: Parent::getNotifier(Node()).erase(node);
deba@2190: nodes.pop_back();
deba@2190: }
deba@2190: }
deba@2190:
deba@2190: public:
deba@2190:
alpar@1011: ///Class to make a snapshot of the graph and to restrore to it later.
alpar@1011:
alpar@1011: ///Class to make a snapshot of the graph and to restrore to it later.
alpar@1011: ///
alpar@1011: ///The newly added nodes and edges can be removed using the
alpar@1011: ///restore() function.
alpar@1011: ///\note After you restore a state, you cannot restore
alpar@1011: ///a later state, in other word you cannot add again the edges deleted
alpar@2132: ///by restore() using another one Snapshot instance.
alpar@1011: ///
deba@2190: ///\warning If you do not use correctly the snapshot that can cause
deba@2190: ///either broken program, invalid state of the graph, valid but
deba@2190: ///not the restored graph or no change. Because the runtime performance
deba@2190: ///the validity of the snapshot is not stored.
alpar@1770: class Snapshot
alpar@1011: {
alpar@1011: SmartGraph *g;
alpar@1011: protected:
alpar@1011: friend class SmartGraph;
alpar@1011: unsigned int node_num;
alpar@1011: unsigned int edge_num;
alpar@1011: public:
zsuzska@1274: ///Default constructor.
alpar@1011:
zsuzska@1274: ///Default constructor.
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(SmartGraph &_g) :g(&_g) {
alpar@1011: node_num=g->nodes.size();
alpar@1011: edge_num=g->edges.size();
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(SmartGraph &_g)
alpar@1011: {
alpar@1011: g=&_g;
alpar@1011: node_num=g->nodes.size();
alpar@1011: edge_num=g->edges.size();
alpar@1011: }
alpar@1011:
alpar@1011: ///Undo the changes until a snapshot.
alpar@1011:
alpar@1011: ///Undo the changes until a snapshot created by save().
alpar@1011: ///
alpar@1011: ///\note After you restored a state, you cannot restore
alpar@1011: ///a later state, in other word you cannot add again the edges deleted
alpar@1011: ///by restore().
alpar@1011: void restore()
alpar@1011: {
alpar@1770: g->restoreSnapshot(*this);
alpar@1011: }
alpar@1011: };
alpar@973: };
klao@1034:
klao@1034:
deba@2116: /**************** Undirected List Graph ****************/
deba@2116:
deba@2116: typedef UGraphExtender<UndirGraphExtender<SmartGraphBase> >
deba@2116: ExtendedSmartUGraphBase;
deba@2116:
deba@2116: /// \ingroup graphs
deba@2116: ///
deba@2116: /// \brief A smart undirected graph class.
deba@2116: ///
deba@2116: /// This is a simple and fast undirected graph implementation.
deba@2116: /// It is also quite memory efficient, but at the price
deba@2116: /// that <b> it does support only limited (only stack-like)
deba@2116: /// node and edge deletions</b>.
deba@2116: /// Except from this it conforms to
alpar@2260: /// the \ref concepts::UGraph "UGraph concept".
alpar@2256: ///
alpar@2256: ///It also has an
alpar@2256: ///important extra feature that
alpar@2260: ///its maps are real \ref concepts::ReferenceMap "reference map"s.
alpar@2256: ///
alpar@2260: /// \sa concepts::UGraph.
deba@2116: ///
deba@2116: class SmartUGraph : public ExtendedSmartUGraphBase {
alpar@2128: private:
deba@2190:
alpar@2128: ///SmartUGraph is \e not copy constructible. Use UGraphCopy() instead.
alpar@2128:
alpar@2128: ///SmartUGraph is \e not copy constructible. Use UGraphCopy() instead.
alpar@2128: ///
alpar@2128: SmartUGraph(const SmartUGraph &) : ExtendedSmartUGraphBase() {};
deba@2190:
alpar@2132: ///\brief Assignment of SmartUGraph to another one is \e not allowed.
alpar@2128: ///Use UGraphCopy() instead.
alpar@2128:
alpar@2132: ///Assignment of SmartUGraph to another one is \e not allowed.
alpar@2128: ///Use UGraphCopy() instead.
alpar@2128: void operator=(const SmartUGraph &) {}
deba@2190:
alpar@2128: public:
deba@2190:
deba@2190: typedef ExtendedSmartUGraphBase Parent;
deba@2190:
alpar@2128: /// Constructor
alpar@2128:
alpar@2128: /// Constructor.
alpar@2128: ///
alpar@2128: SmartUGraph() {}
deba@2190:
deba@2190: ///Add a new node to the graph.
deba@2190:
deba@2190: /// \return the new node.
deba@2190: ///
deba@2190: Node addNode() { return Parent::addNode(); }
deba@2190:
deba@2190: ///Add a new undirected edge to the graph.
deba@2190:
deba@2190: ///Add a new undirected edge to the graph with node \c s
deba@2190: ///and \c t.
deba@2190: ///\return the new undirected edge.
deba@2190: UEdge addEdge(const Node& s, const Node& t) {
deba@2190: return Parent::addEdge(s, t);
deba@2190: }
deba@2190:
deba@2190: ///Clear the graph.
deba@2190:
deba@2190: ///Erase all the nodes and edges from the graph.
deba@2190: ///
deba@2190: void clear() {
deba@2190: Parent::clear();
deba@2190: }
deba@2190:
deba@2190: public:
deba@2190:
deba@2190: class Snapshot;
deba@2190:
deba@2190: protected:
deba@2190:
deba@2190:
deba@2190: void restoreSnapshot(const Snapshot &s)
deba@2190: {
deba@2190: while(s.edge_num<edges.size()) {
deba@2190: UEdge edge = uEdgeFromId(edges.size()-1);
deba@2190: Parent::getNotifier(UEdge()).erase(edge);
deba@2190: std::vector<Edge> dir;
deba@2190: dir.push_back(Parent::direct(edge, true));
deba@2190: dir.push_back(Parent::direct(edge, false));
deba@2190: Parent::getNotifier(Edge()).erase(dir);
deba@2190: nodes[edges.back().source].first_out=edges.back().next_out;
deba@2190: nodes[edges.back().target].first_in=edges.back().next_in;
deba@2190: edges.pop_back();
deba@2190: }
deba@2190: while(s.node_num<nodes.size()) {
deba@2190: Node node = nodeFromId(nodes.size()-1);
deba@2190: Parent::getNotifier(Node()).erase(node);
deba@2190: nodes.pop_back();
deba@2190: }
deba@2190: }
deba@2190:
deba@2190: public:
deba@2190:
deba@2190: ///Class to make a snapshot of the graph and to restrore to it later.
deba@2190:
deba@2190: ///Class to make a snapshot of the graph and to restrore to it later.
deba@2190: ///
deba@2190: ///The newly added nodes and edges can be removed using the
deba@2190: ///restore() function.
deba@2190: ///
deba@2190: ///\note After you restore a state, you cannot restore
deba@2190: ///a later state, in other word you cannot add again the edges deleted
deba@2190: ///by restore() using another one Snapshot instance.
deba@2190: ///
deba@2190: ///\warning If you do not use correctly the snapshot that can cause
deba@2190: ///either broken program, invalid state of the graph, valid but
deba@2190: ///not the restored graph or no change. Because the runtime performance
deba@2190: ///the validity of the snapshot is not stored.
deba@2190: class Snapshot
deba@2190: {
deba@2190: SmartUGraph *g;
deba@2190: protected:
deba@2190: friend class SmartUGraph;
deba@2190: unsigned int node_num;
deba@2190: unsigned int edge_num;
deba@2190: public:
deba@2190: ///Default constructor.
deba@2190:
deba@2190: ///Default constructor.
deba@2190: ///To actually make a snapshot you must call save().
deba@2190: ///
deba@2190: Snapshot() : g(0) {}
deba@2190: ///Constructor that immediately makes a snapshot
deba@2190:
deba@2190: ///This constructor immediately makes a snapshot of the graph.
deba@2190: ///\param _g The graph we make a snapshot of.
deba@2190: Snapshot(SmartUGraph &_g) :g(&_g) {
deba@2190: node_num=g->nodes.size();
deba@2190: edge_num=g->edges.size();
deba@2190: }
deba@2190:
deba@2190: ///Make a snapshot.
deba@2190:
deba@2190: ///Make a snapshot of the graph.
deba@2190: ///
deba@2190: ///This function can be called more than once. In case of a repeated
deba@2190: ///call, the previous snapshot gets lost.
deba@2190: ///\param _g The graph we make the snapshot of.
deba@2190: void save(SmartUGraph &_g)
deba@2190: {
deba@2190: g=&_g;
deba@2190: node_num=g->nodes.size();
deba@2190: edge_num=g->edges.size();
deba@2190: }
deba@2190:
deba@2190: ///Undo the changes until a snapshot.
deba@2190:
deba@2190: ///Undo the changes until a snapshot created by save().
deba@2190: ///
deba@2190: ///\note After you restored a state, you cannot restore
deba@2190: ///a later state, in other word you cannot add again the edges deleted
deba@2190: ///by restore().
deba@2190: void restore()
deba@2190: {
deba@2190: g->restoreSnapshot(*this);
deba@2190: }
deba@2190: };
deba@2116: };
deba@2116:
deba@2116:
deba@2116: class SmartBpUGraphBase {
deba@2116: public:
deba@2116:
deba@2116: class NodeSetError : public LogicError {
deba@2162: public:
alpar@2151: virtual const char* what() const throw() {
deba@2116: return "lemon::SmartBpUGraph::NodeSetError";
deba@2116: }
deba@2116: };
deba@2116:
deba@2116: protected:
deba@2116:
deba@2116: struct NodeT {
deba@2116: int first;
deba@2116: NodeT() {}
deba@2116: NodeT(int _first) : first(_first) {}
deba@2116: };
deba@2116:
deba@2116: struct UEdgeT {
deba@2116: int aNode, next_out;
deba@2116: int bNode, 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: public:
deba@2116:
deba@2116: class Node {
deba@2116: friend class SmartBpUGraphBase;
deba@2116: protected:
deba@2116: int id;
deba@2116:
deba@2190: explicit Node(int _id) : id(_id) {}
deba@2116: public:
deba@2116: Node() {}
deba@2190: 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 SmartBpUGraphBase;
deba@2116: protected:
deba@2116: int id;
deba@2116:
deba@2190: UEdge(int _id) : id(_id) {}
deba@2116: public:
deba@2116: UEdge() {}
deba@2190: 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: void firstANode(Node& node) const {
deba@2116: node.id = 2 * aNodes.size() - 2;
deba@2116: if (node.id < 0) node.id = -1;
deba@2116: }
deba@2116: void nextANode(Node& node) const {
deba@2116: node.id -= 2;
deba@2116: if (node.id < 0) node.id = -1;
deba@2116: }
deba@2116:
deba@2116: void firstBNode(Node& node) const {
deba@2116: node.id = 2 * bNodes.size() - 1;
deba@2116: }
deba@2116: void nextBNode(Node& node) const {
deba@2116: node.id -= 2;
deba@2116: }
deba@2116:
deba@2116: void first(Node& node) const {
deba@2116: if (aNodes.size() > 0) {
deba@2116: node.id = 2 * aNodes.size() - 2;
deba@2116: } else {
deba@2116: node.id = 2 * bNodes.size() - 1;
deba@2116: }
deba@2116: }
deba@2116: void next(Node& node) const {
deba@2116: node.id -= 2;
deba@2116: if (node.id == -2) {
deba@2116: node.id = 2 * bNodes.size() - 1;
deba@2116: }
deba@2116: }
deba@2116:
deba@2116: void first(UEdge& edge) const {
deba@2116: edge.id = edges.size() - 1;
deba@2116: }
deba@2116: void next(UEdge& edge) const {
deba@2116: --edge.id;
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;
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;
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@2116: NodeT nodeT;
deba@2116: nodeT.first = -1;
deba@2116: aNodes.push_back(nodeT);
deba@2116: return Node(aNodes.size() * 2 - 2);
deba@2116: }
deba@2116:
deba@2116: Node addBNode() {
deba@2116: NodeT nodeT;
deba@2116: nodeT.first = -1;
deba@2116: bNodes.push_back(nodeT);
deba@2116: return Node(bNodes.size() * 2 - 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: UEdgeT edgeT;
deba@2116: if ((source.id & 1) == 0) {
deba@2116: edgeT.aNode = source.id;
deba@2116: edgeT.bNode = target.id;
deba@2116: } else {
deba@2116: edgeT.aNode = target.id;
deba@2116: edgeT.bNode = source.id;
deba@2116: }
deba@2116: edgeT.next_out = aNodes[edgeT.aNode >> 1].first;
deba@2116: aNodes[edgeT.aNode >> 1].first = edges.size();
deba@2116: edgeT.next_in = bNodes[edgeT.bNode >> 1].first;
deba@2116: bNodes[edgeT.bNode >> 1].first = edges.size();
deba@2116: edges.push_back(edgeT);
deba@2116: return UEdge(edges.size() - 1);
deba@2116: }
deba@2116:
deba@2116: void clear() {
deba@2116: aNodes.clear();
deba@2116: bNodes.clear();
deba@2116: edges.clear();
deba@2116: }
deba@2116:
deba@2116: typedef True NodeNumTag;
deba@2116: int nodeNum() const { return aNodes.size() + bNodes.size(); }
deba@2116: int aNodeNum() const { return aNodes.size(); }
deba@2116: int bNodeNum() const { return bNodes.size(); }
deba@2116:
deba@2116: typedef True EdgeNumTag;
deba@2116: int uEdgeNum() const { return edges.size(); }
deba@2116:
deba@2116: };
deba@2116:
deba@2116:
deba@2231: typedef BpUGraphExtender<BidirBpUGraphExtender<SmartBpUGraphBase> >
deba@2231: ExtendedSmartBpUGraphBase;
deba@2116:
deba@2116: /// \ingroup graphs
deba@2116: ///
deba@2116: /// \brief A smart bipartite undirected graph class.
deba@2116: ///
deba@2116: /// This is a simple and fast bipartite undirected graph implementation.
deba@2116: /// It is also quite memory efficient, but at the price
deba@2116: /// that <b> it does not support node and edge deletions</b>.
deba@2116: /// Except from this it conforms to
alpar@2260: /// the \ref concepts::BpUGraph "BpUGraph concept".
alpar@2256: ///
alpar@2256: ///It also has an
alpar@2256: ///important extra feature that
alpar@2260: ///its maps are real \ref concepts::ReferenceMap "reference map"s.
alpar@2256: ///
alpar@2260: /// \sa concepts::BpUGraph.
deba@2116: ///
deba@2190: class SmartBpUGraph : public ExtendedSmartBpUGraphBase {
deba@2190: private:
deba@2190:
deba@2190: /// \brief SmartBpUGraph is \e not copy constructible.
deba@2190: ///
deba@2190: ///SmartBpUGraph is \e not copy constructible.
deba@2190: SmartBpUGraph(const SmartBpUGraph &) : ExtendedSmartBpUGraphBase() {};
deba@2190:
deba@2190: /// \brief Assignment of SmartBpUGraph to another one is \e not
deba@2190: /// allowed.
deba@2190: ///
deba@2190: /// Assignment of SmartBpUGraph to another one is \e not allowed.
deba@2190: void operator=(const SmartBpUGraph &) {}
deba@2190:
deba@2190: public:
deba@2190:
deba@2190: typedef ExtendedSmartBpUGraphBase Parent;
deba@2190:
deba@2190: ///Constructor
deba@2190:
deba@2190: ///Constructor.
deba@2190: ///
deba@2190: SmartBpUGraph() : ExtendedSmartBpUGraphBase() {}
deba@2190:
deba@2190: ///Add a new ANode to the graph.
deba@2190:
deba@2190: /// \return the new node.
deba@2190: ///
deba@2190: Node addANode() { return Parent::addANode(); }
deba@2190:
deba@2190: ///Add a new BNode to the graph.
deba@2190:
deba@2190: /// \return the new node.
deba@2190: ///
deba@2190: Node addBNode() { return Parent::addBNode(); }
deba@2190:
deba@2190: ///Add a new undirected edge to the graph.
deba@2190:
deba@2190: ///Add a new undirected edge to the graph with node \c s
deba@2190: ///and \c t.
deba@2190: ///\return the new undirected edge.
deba@2190: UEdge addEdge(const Node& s, const Node& t) {
deba@2190: return Parent::addEdge(s, t);
deba@2190: }
deba@2190:
deba@2190: ///Clear the graph.
deba@2190:
deba@2190: ///Erase all the nodes and edges from the graph.
deba@2190: ///
deba@2190: void clear() {
deba@2190: Parent::clear();
deba@2190: }
deba@2190:
deba@2190: public:
deba@2190:
deba@2190: class Snapshot;
deba@2190:
deba@2190: protected:
deba@2190:
deba@2190: void restoreSnapshot(const Snapshot &s)
deba@2190: {
deba@2190: while(s.edge_num<edges.size()) {
deba@2190: UEdge edge = uEdgeFromId(edges.size()-1);
deba@2190: Parent::getNotifier(UEdge()).erase(edge);
deba@2190: std::vector<Edge> dir;
deba@2190: dir.push_back(Parent::direct(edge, true));
deba@2190: dir.push_back(Parent::direct(edge, false));
deba@2190: Parent::getNotifier(Edge()).erase(dir);
deba@2190: aNodes[edges.back().aNode >> 1].first=edges.back().next_out;
deba@2190: bNodes[edges.back().bNode >> 1].first=edges.back().next_in;
deba@2190: edges.pop_back();
deba@2190: }
deba@2190: while(s.anode_num<aNodes.size()) {
deba@2231: Node node = nodeFromANodeId(aNodes.size() - 1);
deba@2190: Parent::getNotifier(ANode()).erase(node);
deba@2190: Parent::getNotifier(Node()).erase(node);
deba@2190: aNodes.pop_back();
deba@2190: }
deba@2190: while(s.bnode_num<bNodes.size()) {
deba@2231: Node node = nodeFromBNodeId(bNodes.size() - 1);
deba@2190: Parent::getNotifier(BNode()).erase(node);
deba@2190: Parent::getNotifier(Node()).erase(node);
deba@2190: bNodes.pop_back();
deba@2190: }
deba@2190: }
deba@2190:
deba@2190: public:
deba@2190:
deba@2190: ///Class to make a snapshot of the graph and to restrore to it later.
deba@2190:
deba@2190: ///Class to make a snapshot of the graph and to restrore to it later.
deba@2190: ///
deba@2190: ///The newly added nodes and edges can be removed using the
deba@2190: ///restore() function.
deba@2190: ///
deba@2190: ///\note After you restore a state, you cannot restore
deba@2190: ///a later state, in other word you cannot add again the edges deleted
deba@2190: ///by restore() using another one Snapshot instance.
deba@2190: ///
deba@2190: ///\warning If you do not use correctly the snapshot that can cause
deba@2190: ///either broken program, invalid state of the graph, valid but
deba@2190: ///not the restored graph or no change. Because the runtime performance
deba@2190: ///the validity of the snapshot is not stored.
deba@2190: class Snapshot
deba@2190: {
deba@2190: SmartBpUGraph *g;
deba@2190: protected:
deba@2190: friend class SmartBpUGraph;
deba@2190: unsigned int anode_num;
deba@2190: unsigned int bnode_num;
deba@2190: unsigned int edge_num;
deba@2190: public:
deba@2190: ///Default constructor.
deba@2190:
deba@2190: ///Default constructor.
deba@2190: ///To actually make a snapshot you must call save().
deba@2190: ///
deba@2190: Snapshot() : g(0) {}
deba@2190:
deba@2190: ///Constructor that immediately makes a snapshot
deba@2190:
deba@2190: ///This constructor immediately makes a snapshot of the graph.
deba@2190: ///\param _g The graph we make a snapshot of.
deba@2190: Snapshot(SmartBpUGraph &_g) : g(&_g) {
deba@2190: anode_num=g->aNodes.size();
deba@2190: bnode_num=g->bNodes.size();
deba@2190: edge_num=g->edges.size();
deba@2190: }
deba@2190:
deba@2190: ///Make a snapshot.
deba@2190:
deba@2190: ///Make a snapshot of the graph.
deba@2190: ///
deba@2190: ///This function can be called more than once. In case of a repeated
deba@2190: ///call, the previous snapshot gets lost.
deba@2190: ///\param _g The graph we make the snapshot of.
deba@2190: void save(SmartBpUGraph &_g)
deba@2190: {
deba@2190: g=&_g;
deba@2190: anode_num=g->aNodes.size();
deba@2190: bnode_num=g->bNodes.size();
deba@2190: edge_num=g->edges.size();
deba@2190: }
deba@2190:
deba@2190: ///Undo the changes until a snapshot.
deba@2190:
deba@2190: ///Undo the changes until a snapshot created by save().
deba@2190: ///
deba@2190: ///\note After you restored a state, you cannot restore
deba@2190: ///a later state, in other word you cannot add again the edges deleted
deba@2190: ///by restore().
deba@2190: void restore()
deba@2190: {
deba@2190: g->restoreSnapshot(*this);
deba@2190: }
deba@2190: };
deba@2190: };
deba@2116:
deba@2116:
deba@2116: /// @}
alpar@921: } //namespace lemon
alpar@104:
alpar@157:
alpar@921: #endif //LEMON_SMART_GRAPH_H