1.1 --- a/lemon/smart_graph.h Thu Jan 11 21:05:00 2007 +0000
1.2 +++ b/lemon/smart_graph.h Thu Jan 11 21:06:47 2007 +0000
1.3 @@ -366,10 +366,191 @@
1.4 };
1.5
1.6
1.7 - /**************** Undirected List Graph ****************/
1.8 + class SmartUGraphBase {
1.9
1.10 - typedef UGraphExtender<UndirGraphExtender<SmartGraphBase> >
1.11 - ExtendedSmartUGraphBase;
1.12 + protected:
1.13 +
1.14 + struct NodeT {
1.15 + int first_out;
1.16 + };
1.17 +
1.18 + struct EdgeT {
1.19 + int target;
1.20 + int next_out;
1.21 + };
1.22 +
1.23 + std::vector<NodeT> nodes;
1.24 + std::vector<EdgeT> edges;
1.25 +
1.26 + int first_free_edge;
1.27 +
1.28 + public:
1.29 +
1.30 + typedef SmartUGraphBase Graph;
1.31 +
1.32 + class Node {
1.33 + friend class SmartUGraphBase;
1.34 + protected:
1.35 +
1.36 + int id;
1.37 + explicit Node(int pid) { id = pid;}
1.38 +
1.39 + public:
1.40 + Node() {}
1.41 + Node (Invalid) { id = -1; }
1.42 + bool operator==(const Node& node) const {return id == node.id;}
1.43 + bool operator!=(const Node& node) const {return id != node.id;}
1.44 + bool operator<(const Node& node) const {return id < node.id;}
1.45 + };
1.46 +
1.47 + class UEdge {
1.48 + friend class SmartUGraphBase;
1.49 + protected:
1.50 +
1.51 + int id;
1.52 + explicit UEdge(int pid) { id = pid;}
1.53 +
1.54 + public:
1.55 + UEdge() {}
1.56 + UEdge (Invalid) { id = -1; }
1.57 + bool operator==(const UEdge& edge) const {return id == edge.id;}
1.58 + bool operator!=(const UEdge& edge) const {return id != edge.id;}
1.59 + bool operator<(const UEdge& edge) const {return id < edge.id;}
1.60 + };
1.61 +
1.62 + class Edge {
1.63 + friend class SmartUGraphBase;
1.64 + protected:
1.65 +
1.66 + int id;
1.67 + explicit Edge(int pid) { id = pid;}
1.68 +
1.69 + public:
1.70 + operator UEdge() const { return UEdge(id / 2); }
1.71 +
1.72 + Edge() {}
1.73 + Edge (Invalid) { id = -1; }
1.74 + bool operator==(const Edge& edge) const {return id == edge.id;}
1.75 + bool operator!=(const Edge& edge) const {return id != edge.id;}
1.76 + bool operator<(const Edge& edge) const {return id < edge.id;}
1.77 + };
1.78 +
1.79 +
1.80 +
1.81 + SmartUGraphBase()
1.82 + : nodes(), edges() {}
1.83 +
1.84 +
1.85 + int maxNodeId() const { return nodes.size()-1; }
1.86 + int maxUEdgeId() const { return edges.size() / 2 - 1; }
1.87 + int maxEdgeId() const { return edges.size()-1; }
1.88 +
1.89 + Node source(Edge e) const { return Node(edges[e.id ^ 1].target); }
1.90 + Node target(Edge e) const { return Node(edges[e.id].target); }
1.91 +
1.92 + Node source(UEdge e) const { return Node(edges[2 * e.id].target); }
1.93 + Node target(UEdge e) const { return Node(edges[2 * e.id + 1].target); }
1.94 +
1.95 + static bool direction(Edge e) {
1.96 + return (e.id & 1) == 1;
1.97 + }
1.98 +
1.99 + static Edge direct(UEdge e, bool d) {
1.100 + return Edge(e.id * 2 + (d ? 1 : 0));
1.101 + }
1.102 +
1.103 + void first(Node& node) const {
1.104 + node.id = nodes.size() - 1;
1.105 + }
1.106 +
1.107 + void next(Node& node) const {
1.108 + --node.id;
1.109 + }
1.110 +
1.111 + void first(Edge& edge) const {
1.112 + edge.id = edges.size() - 1;
1.113 + }
1.114 +
1.115 + void next(Edge& edge) const {
1.116 + --edge.id;
1.117 + }
1.118 +
1.119 + void first(UEdge& edge) const {
1.120 + edge.id = edges.size() / 2 - 1;
1.121 + }
1.122 +
1.123 + void next(UEdge& edge) const {
1.124 + --edge.id;
1.125 + }
1.126 +
1.127 + void firstOut(Edge &edge, const Node& v) const {
1.128 + edge.id = nodes[v.id].first_out;
1.129 + }
1.130 + void nextOut(Edge &edge) const {
1.131 + edge.id = edges[edge.id].next_out;
1.132 + }
1.133 +
1.134 + void firstIn(Edge &edge, const Node& v) const {
1.135 + edge.id = ((nodes[v.id].first_out) ^ 1);
1.136 + if (e.id == -2) e.id = -1;
1.137 + }
1.138 + void nextIn(Edge &edge) const {
1.139 + edge.id = ((edges[edge.id ^ 1].next_out) ^ 1);
1.140 + if (e.id == -2) e.id = -1;
1.141 + }
1.142 +
1.143 + void firstInc(UEdge &edge, bool& d, const Node& v) const {
1.144 + int de = nodes[v.id].first_out;
1.145 + edge.id = de / 2;
1.146 + d = ((de & 1) == 1);
1.147 + }
1.148 + void nextInc(UEdge &edge, bool& d) const {
1.149 + int de = (edges[(edge.id * 2) | (d ? 1 : 0)].next_out);
1.150 + edge.id = de / 2;
1.151 + d = ((de & 1) == 1);
1.152 + }
1.153 +
1.154 + static int id(Node v) { return v.id; }
1.155 + static int id(Edge e) { return e.id; }
1.156 + static int id(UEdge e) { return e.id; }
1.157 +
1.158 + static Node nodeFromId(int id) { return Node(id);}
1.159 + static Edge edgeFromId(int id) { return Edge(id);}
1.160 + static UEdge uEdgeFromId(int id) { return UEdge(id);}
1.161 +
1.162 + Node addNode() {
1.163 + int n = nodes.size();
1.164 + nodes.push_back(NodeT());
1.165 + nodes[n].first_out = -1;
1.166 +
1.167 + return Node(n);
1.168 + }
1.169 +
1.170 + UEdge addEdge(Node u, Node v) {
1.171 + int n = edges.size();
1.172 + edges.push_back(EdgeT());
1.173 + edges.push_back(EdgeT());
1.174 +
1.175 + edges[n].target = u.id;
1.176 + edges[n | 1].target = v.id;
1.177 +
1.178 + edges[n].next_out = nodes[v.id].first_out;
1.179 + edges[n | 1].next_out = nodes[u.id].first_out;
1.180 +
1.181 + nodes[v.id].first_out = n;
1.182 + nodes[u.id].first_out = (n | 1);
1.183 +
1.184 + return UEdge(n / 2);
1.185 + }
1.186 +
1.187 + void clear() {
1.188 + edges.clear();
1.189 + nodes.clear();
1.190 + }
1.191 +
1.192 + };
1.193 +
1.194 + typedef UGraphExtender<SmartUGraphBase> ExtendedSmartUGraphBase;
1.195
1.196 /// \ingroup graphs
1.197 ///
1.198 @@ -407,6 +588,7 @@
1.199 public:
1.200
1.201 typedef ExtendedSmartUGraphBase Parent;
1.202 + typedef Parent::OutEdgeIt IncEdgeIt;
1.203
1.204 /// Constructor
1.205
1.206 @@ -443,22 +625,31 @@
1.207
1.208 protected:
1.209
1.210 + void saveSnapshot(Snapshot &s)
1.211 + {
1.212 + s.g = this;
1.213 + s.node_num = nodes.size();
1.214 + s.edge_num = edges.size();
1.215 + }
1.216
1.217 void restoreSnapshot(const Snapshot &s)
1.218 {
1.219 while(s.edge_num<edges.size()) {
1.220 - UEdge edge = uEdgeFromId(edges.size()-1);
1.221 + int n=edges.size()-1;
1.222 + UEdge edge=uEdgeFromId(n/2);
1.223 Parent::getNotifier(UEdge()).erase(edge);
1.224 std::vector<Edge> dir;
1.225 - dir.push_back(Parent::direct(edge, true));
1.226 - dir.push_back(Parent::direct(edge, false));
1.227 + dir.push_back(edgeFromId(n));
1.228 + dir.push_back(edgeFromId(n-1));
1.229 Parent::getNotifier(Edge()).erase(dir);
1.230 - nodes[edges.back().source].first_out=edges.back().next_out;
1.231 - nodes[edges.back().target].first_in=edges.back().next_in;
1.232 + nodes[edges[n].target].first_out=edges[n].next_out;
1.233 + nodes[edges[n-1].target].first_out=edges[n-1].next_out;
1.234 + edges.pop_back();
1.235 edges.pop_back();
1.236 }
1.237 while(s.node_num<nodes.size()) {
1.238 - Node node = nodeFromId(nodes.size()-1);
1.239 + int n=nodes.size()-1;
1.240 + Node node = nodeFromId(n);
1.241 Parent::getNotifier(Node()).erase(node);
1.242 nodes.pop_back();
1.243 }
1.244 @@ -499,9 +690,8 @@
1.245
1.246 ///This constructor immediately makes a snapshot of the graph.
1.247 ///\param _g The graph we make a snapshot of.
1.248 - Snapshot(SmartUGraph &_g) :g(&_g) {
1.249 - node_num=g->nodes.size();
1.250 - edge_num=g->edges.size();
1.251 + Snapshot(SmartUGraph &g) {
1.252 + g.saveSnapshot(*this);
1.253 }
1.254
1.255 ///Make a snapshot.
1.256 @@ -511,11 +701,9 @@
1.257 ///This function can be called more than once. In case of a repeated
1.258 ///call, the previous snapshot gets lost.
1.259 ///\param _g The graph we make the snapshot of.
1.260 - void save(SmartUGraph &_g)
1.261 + void save(SmartUGraph &g)
1.262 {
1.263 - g=&_g;
1.264 - node_num=g->nodes.size();
1.265 - edge_num=g->edges.size();
1.266 + g.saveSnapshot(*this);
1.267 }
1.268
1.269 ///Undo the changes until a snapshot.
1.270 @@ -527,7 +715,7 @@
1.271 ///by restore().
1.272 void restore()
1.273 {
1.274 - g->restoreSnapshot(*this);
1.275 + g->restoreSnapshot(*this);
1.276 }
1.277 };
1.278 };