1.1 --- a/lemon/edge_set.h Mon Feb 06 15:52:32 2006 +0000
1.2 +++ b/lemon/edge_set.h Mon Feb 06 16:58:39 2006 +0000
1.3 @@ -19,6 +19,14 @@
1.4 #ifndef LEMON_EDGE_SET_H
1.5 #define LEMON_EDGE_SET_H
1.6
1.7 +#include <lemon/bits/erasable_graph_extender.h>
1.8 +#include <lemon/bits/clearable_graph_extender.h>
1.9 +#include <lemon/bits/extendable_graph_extender.h>
1.10 +#include <lemon/bits/iterable_graph_extender.h>
1.11 +#include <lemon/bits/alteration_notifier.h>
1.12 +#include <lemon/bits/default_map.h>
1.13 +#include <lemon/bits/graph_extender.h>
1.14 +
1.15 /// \ingroup graphs
1.16 /// \file
1.17 /// \brief EdgeSet classes.
1.18 @@ -92,8 +100,14 @@
1.19 first_free_edge = edges[first_free_edge].next_in;
1.20 }
1.21 edges[n].next_in = (*nodes)[target].first_in;
1.22 + if ((*nodes)[target].first_in != -1) {
1.23 + edges[(*nodes)[target].first_in].prev_in = n;
1.24 + }
1.25 (*nodes)[target].first_in = n;
1.26 edges[n].next_out = (*nodes)[source].first_out;
1.27 + if ((*nodes)[source].first_out != -1) {
1.28 + edges[(*nodes)[source].first_out].prev_out = n;
1.29 + }
1.30 (*nodes)[source].first_out = n;
1.31 edges[n].source = source;
1.32 edges[n].target = target;
1.33 @@ -123,6 +137,11 @@
1.34 }
1.35
1.36 void clear() {
1.37 + Node node;
1.38 + for (first(node); node != INVALID; next(node)) {
1.39 + (*nodes)[node].first_in = -1;
1.40 + (*nodes)[node].first_out = -1;
1.41 + }
1.42 edges.clear();
1.43 first_edge = -1;
1.44 first_free_edge = -1;
1.45 @@ -173,10 +192,10 @@
1.46 int id(const Node& node) const { return graph->id(node); }
1.47 int id(const Edge& edge) const { return edge.id; }
1.48
1.49 - Node nodeFromId(int id) const { return graph->fromId(id, Node()); }
1.50 + Node nodeFromId(int id) const { return graph->nodeFromId(id); }
1.51 Edge edgeFromId(int id) const { return Edge(id); }
1.52
1.53 - int maxNodeId() const { return graph->maxId(Node()); };
1.54 + int maxNodeId() const { return graph->maxNodeId(); };
1.55 int maxEdgeId() const { return edges.size() - 1; }
1.56
1.57 Node source(const Edge& edge) const { return edges[edge.id].source;}
1.58 @@ -208,7 +227,7 @@
1.59 /// "StaticGraph" concept.
1.60 ///
1.61 /// In the edge extension and removing it conforms to the
1.62 - /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
1.63 + /// \ref concept::ErasableGraph "ErasableGraph" concept.
1.64 template <typename _Graph>
1.65 class ListEdgeSet :
1.66 public ErasableEdgeSetExtender<
1.67 @@ -264,6 +283,8 @@
1.68
1.69 NodesImpl(const Graph& graph, ListEdgeSet& edgeset)
1.70 : Parent(graph), _edgeset(edgeset) {}
1.71 +
1.72 + virtual ~NodesImpl() {}
1.73
1.74 protected:
1.75
1.76 @@ -271,6 +292,12 @@
1.77 _edgeset.eraseNode(node);
1.78 Parent::erase(node);
1.79 }
1.80 + virtual void erase(const std::vector<Node>& nodes) {
1.81 + for (int i = 0; i < (int)nodes.size(); ++i) {
1.82 + _edgeset.eraseNode(nodes[i]);
1.83 + }
1.84 + Parent::erase(nodes);
1.85 + }
1.86 virtual void clear() {
1.87 _edgeset.clearNodes();
1.88 Parent::clear();
1.89 @@ -307,7 +334,7 @@
1.90 /// "StaticGraph" concept.
1.91 ///
1.92 /// In the edge extension and removing it conforms to the
1.93 - /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
1.94 + /// \ref concept::ErasableUGraph "ErasableUGraph" concept.
1.95 template <typename _Graph>
1.96 class ListUEdgeSet :
1.97 public ErasableUEdgeSetExtender<
1.98 @@ -358,6 +385,8 @@
1.99
1.100 NodesImpl(const Graph& graph, ListUEdgeSet& edgeset)
1.101 : Parent(graph), _edgeset(edgeset) {}
1.102 +
1.103 + virtual ~NodesImpl() {}
1.104
1.105 protected:
1.106
1.107 @@ -366,7 +395,7 @@
1.108 Parent::erase(node);
1.109 }
1.110 virtual void erase(const std::vector<Node>& nodes) {
1.111 - for (int i = 0; i < nodes.size(); ++i) {
1.112 + for (int i = 0; i < (int)nodes.size(); ++i) {
1.113 _edgeset.eraseNode(nodes[i]);
1.114 }
1.115 Parent::erase(nodes);
1.116 @@ -393,6 +422,341 @@
1.117
1.118 };
1.119
1.120 + template <typename _Graph>
1.121 + class SmartEdgeSetBase {
1.122 + public:
1.123 +
1.124 + typedef _Graph Graph;
1.125 + typedef typename Graph::Node Node;
1.126 + typedef typename Graph::NodeIt NodeIt;
1.127 +
1.128 + protected:
1.129 +
1.130 + struct NodeT {
1.131 + int first_out, first_in;
1.132 + NodeT() : first_out(-1), first_in(-1) {}
1.133 + };
1.134 +
1.135 + typedef typename Graph::template NodeMap<NodeT> NodesImplBase;
1.136 +
1.137 + NodesImplBase* nodes;
1.138 +
1.139 + struct EdgeT {
1.140 + Node source, target;
1.141 + int next_out, next_in;
1.142 + EdgeT() {}
1.143 + };
1.144 +
1.145 + std::vector<EdgeT> edges;
1.146 +
1.147 + const Graph* graph;
1.148 +
1.149 + void initalize(const Graph& _graph, NodesImplBase& _nodes) {
1.150 + graph = &_graph;
1.151 + nodes = &_nodes;
1.152 + }
1.153 +
1.154 + public:
1.155 +
1.156 + class Edge {
1.157 + friend class SmartEdgeSetBase<Graph>;
1.158 + protected:
1.159 + Edge(int _id) : id(_id) {}
1.160 + int id;
1.161 + public:
1.162 + Edge() {}
1.163 + Edge(Invalid) : id(-1) {}
1.164 + bool operator==(const Edge& edge) const { return id == edge.id; }
1.165 + bool operator!=(const Edge& edge) const { return id != edge.id; }
1.166 + bool operator<(const Edge& edge) const { return id < edge.id; }
1.167 + };
1.168 +
1.169 + SmartEdgeSetBase() {}
1.170 +
1.171 + Edge addEdge(const Node& source, const Node& target) {
1.172 + int n = edges.size();
1.173 + edges.push_back(EdgeT());
1.174 + edges[n].next_in = (*nodes)[target].first_in;
1.175 + (*nodes)[target].first_in = n;
1.176 + edges[n].next_out = (*nodes)[source].first_out;
1.177 + (*nodes)[source].first_out = n;
1.178 + edges[n].source = source;
1.179 + edges[n].target = target;
1.180 + return Edge(n);
1.181 + }
1.182 +
1.183 + void clear() {
1.184 + Node node;
1.185 + for (first(node); node != INVALID; next(node)) {
1.186 + (*nodes)[node].first_in = -1;
1.187 + (*nodes)[node].first_out = -1;
1.188 + }
1.189 + edges.clear();
1.190 + }
1.191 +
1.192 + void first(Node& node) const {
1.193 + graph->first(node);
1.194 + }
1.195 +
1.196 + void next(Node& node) const {
1.197 + graph->next(node);
1.198 + }
1.199 +
1.200 + void first(Edge& edge) const {
1.201 + edge.id = edges.size() - 1;
1.202 + }
1.203 +
1.204 + void next(Edge& edge) const {
1.205 + --edge.id;
1.206 + }
1.207 +
1.208 + void firstOut(Edge& edge, const Node& node) const {
1.209 + edge.id = (*nodes)[node].first_out;
1.210 + }
1.211 +
1.212 + void nextOut(Edge& edge) const {
1.213 + edge.id = edges[edge.id].next_out;
1.214 + }
1.215 +
1.216 + void firstIn(Edge& edge, const Node& node) const {
1.217 + edge.id = (*nodes)[node].first_in;
1.218 + }
1.219 +
1.220 + void nextIn(Edge& edge) const {
1.221 + edge.id = edges[edge.id].next_in;
1.222 + }
1.223 +
1.224 + int id(const Node& node) const { return graph->id(node); }
1.225 + int id(const Edge& edge) const { return edge.id; }
1.226 +
1.227 + Node nodeFromId(int id) const { return graph->nodeFromId(id); }
1.228 + Edge edgeFromId(int id) const { return Edge(id); }
1.229 +
1.230 + int maxNodeId() const { return graph->maxNodeId(); };
1.231 + int maxEdgeId() const { return edges.size() - 1; }
1.232 +
1.233 + Node source(const Edge& edge) const { return edges[edge.id].source;}
1.234 + Node target(const Edge& edge) const { return edges[edge.id].target;}
1.235 +
1.236 + template <typename _Value>
1.237 + class NodeMap : public Graph::template NodeMap<_Value> {
1.238 + public:
1.239 + typedef typename _Graph::template NodeMap<_Value> Parent;
1.240 + explicit NodeMap(const SmartEdgeSetBase<Graph>& edgeset)
1.241 + : Parent(*edgeset.graph) { }
1.242 + NodeMap(const SmartEdgeSetBase<Graph>& edgeset, const _Value& value)
1.243 + : Parent(*edgeset.graph, value) { }
1.244 + };
1.245 +
1.246 + };
1.247 +
1.248 +
1.249 + /// \ingroup semi_adaptors
1.250 + ///
1.251 + /// \brief Graph using a node set of another graph and an
1.252 + /// own edge set.
1.253 + ///
1.254 + /// This structure can be used to establish another graph over a node set
1.255 + /// of an existing one. The node iterator will go through the nodes of the
1.256 + /// original graph.
1.257 + ///
1.258 + /// \param _Graph The type of the graph which shares its node set with
1.259 + /// this class. Its interface must conform to the \ref concept::StaticGraph
1.260 + /// "StaticGraph" concept.
1.261 + ///
1.262 + /// In the edge extension and removing it conforms to the
1.263 + /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
1.264 + template <typename _Graph>
1.265 + class SmartEdgeSet :
1.266 + public ClearableEdgeSetExtender<
1.267 + ExtendableEdgeSetExtender<
1.268 + MappableEdgeSetExtender<
1.269 + IterableGraphExtender<
1.270 + AlterableEdgeSetExtender<
1.271 + GraphExtender<
1.272 + SmartEdgeSetBase<_Graph> > > > > > > {
1.273 +
1.274 + public:
1.275 +
1.276 + typedef ClearableEdgeSetExtender<
1.277 + ExtendableEdgeSetExtender<
1.278 + MappableEdgeSetExtender<
1.279 + IterableGraphExtender<
1.280 + AlterableEdgeSetExtender<
1.281 + GraphExtender<
1.282 + SmartEdgeSetBase<_Graph> > > > > > > Parent;
1.283 +
1.284 + typedef typename Parent::Node Node;
1.285 + typedef typename Parent::Edge Edge;
1.286 +
1.287 + typedef _Graph Graph;
1.288 +
1.289 + class UnsupportedOperation : public LogicError {
1.290 + public:
1.291 + virtual const char* exceptionName() const {
1.292 + return "lemon::SmartEdgeSet::UnsupportedOperation";
1.293 + }
1.294 + };
1.295 +
1.296 +
1.297 +
1.298 + protected:
1.299 +
1.300 + typedef typename Parent::NodesImplBase NodesImplBase;
1.301 +
1.302 + void eraseNode(const Node&) {
1.303 + throw UnsupportedOperation();
1.304 + }
1.305 +
1.306 + void clearNodes() {
1.307 + Parent::clear();
1.308 + }
1.309 +
1.310 + class NodesImpl : public NodesImplBase {
1.311 + public:
1.312 + typedef NodesImplBase Parent;
1.313 +
1.314 + NodesImpl(const Graph& graph, SmartEdgeSet& edgeset)
1.315 + : Parent(graph), _edgeset(edgeset) {}
1.316 +
1.317 + virtual ~NodesImpl() {}
1.318 +
1.319 + protected:
1.320 +
1.321 + virtual void erase(const Node& node) {
1.322 + _edgeset.eraseNode(node);
1.323 + Parent::erase(node);
1.324 + }
1.325 + virtual void erase(const std::vector<Node>& nodes) {
1.326 + for (int i = 0; i < (int)nodes.size(); ++i) {
1.327 + _edgeset.eraseNode(nodes[i]);
1.328 + }
1.329 + Parent::erase(nodes);
1.330 + }
1.331 + virtual void clear() {
1.332 + _edgeset.clearNodes();
1.333 + Parent::clear();
1.334 + }
1.335 +
1.336 + private:
1.337 + SmartEdgeSet& _edgeset;
1.338 + };
1.339 +
1.340 + NodesImpl nodes;
1.341 +
1.342 + public:
1.343 +
1.344 + /// \brief Constructor of the adaptor.
1.345 + ///
1.346 + /// Constructor of the adaptor.
1.347 + SmartEdgeSet(const Graph& graph) : nodes(graph, *this) {
1.348 + Parent::initalize(graph, nodes);
1.349 + }
1.350 +
1.351 + };
1.352 +
1.353 + /// \ingroup semi_adaptors
1.354 + ///
1.355 + /// \brief Graph using a node set of another graph and an
1.356 + /// own uedge set.
1.357 + ///
1.358 + /// This structure can be used to establish another graph over a node set
1.359 + /// of an existing one. The node iterator will go through the nodes of the
1.360 + /// original graph.
1.361 + ///
1.362 + /// \param _Graph The type of the graph which shares its node set with
1.363 + /// this class. Its interface must conform to the \ref concept::StaticGraph
1.364 + /// "StaticGraph" concept.
1.365 + ///
1.366 + /// In the edge extension and removing it conforms to the
1.367 + /// \ref concept::ExtendableUGraph "ExtendableUGraph" concept.
1.368 + template <typename _Graph>
1.369 + class SmartUEdgeSet :
1.370 + public ClearableUEdgeSetExtender<
1.371 + ExtendableUEdgeSetExtender<
1.372 + MappableUEdgeSetExtender<
1.373 + IterableUGraphExtender<
1.374 + AlterableUEdgeSetExtender<
1.375 + UGraphExtender<
1.376 + SmartEdgeSetBase<_Graph> > > > > > > {
1.377 +
1.378 + public:
1.379 +
1.380 + typedef ClearableUEdgeSetExtender<
1.381 + ExtendableUEdgeSetExtender<
1.382 + MappableUEdgeSetExtender<
1.383 + IterableUGraphExtender<
1.384 + AlterableUEdgeSetExtender<
1.385 + UGraphExtender<
1.386 + SmartEdgeSetBase<_Graph> > > > > > > Parent;
1.387 +
1.388 + typedef typename Parent::Node Node;
1.389 + typedef typename Parent::Edge Edge;
1.390 +
1.391 + typedef _Graph Graph;
1.392 +
1.393 + class UnsupportedOperation : public LogicError {
1.394 + public:
1.395 + virtual const char* exceptionName() const {
1.396 + return "lemon::SmartUEdgeSet::UnsupportedOperation";
1.397 + }
1.398 + };
1.399 +
1.400 + protected:
1.401 +
1.402 + typedef typename Parent::NodesImplBase NodesImplBase;
1.403 +
1.404 + void eraseNode(const Node&) {
1.405 + throw UnsupportedOperation();
1.406 + }
1.407 +
1.408 + void clearNodes() {
1.409 + Parent::clear();
1.410 + }
1.411 +
1.412 + class NodesImpl : public NodesImplBase {
1.413 + public:
1.414 + typedef NodesImplBase Parent;
1.415 +
1.416 + NodesImpl(const Graph& graph, SmartUEdgeSet& edgeset)
1.417 + : Parent(graph), _edgeset(edgeset) {}
1.418 +
1.419 + virtual ~NodesImpl() {}
1.420 +
1.421 + protected:
1.422 +
1.423 + virtual void erase(const Node& node) {
1.424 + _edgeset.eraseNode(node);
1.425 + Parent::erase(node);
1.426 + }
1.427 + virtual void erase(const std::vector<Node>& nodes) {
1.428 + for (int i = 0; i < (int)nodes.size(); ++i) {
1.429 + _edgeset.eraseNode(nodes[i]);
1.430 + }
1.431 + Parent::erase(nodes);
1.432 + }
1.433 + virtual void clear() {
1.434 + _edgeset.clearNodes();
1.435 + Parent::clear();
1.436 + }
1.437 +
1.438 + private:
1.439 + SmartUEdgeSet& _edgeset;
1.440 + };
1.441 +
1.442 + NodesImpl nodes;
1.443 +
1.444 + public:
1.445 +
1.446 + /// \brief Constructor of the adaptor.
1.447 + ///
1.448 + /// Constructor of the adaptor.
1.449 + SmartUEdgeSet(const Graph& graph) : nodes(graph, *this) {
1.450 + Parent::initalize(graph, nodes);
1.451 + }
1.452 +
1.453 + };
1.454 +
1.455 }
1.456
1.457 #endif
2.1 --- a/test/Makefile.am Mon Feb 06 15:52:32 2006 +0000
2.2 +++ b/test/Makefile.am Mon Feb 06 16:58:39 2006 +0000
2.3 @@ -17,6 +17,7 @@
2.4 counter_test \
2.5 dfs_test \
2.6 dijkstra_test \
2.7 + edge_set_test \
2.8 graph_test \
2.9 graph_adaptor_test \
2.10 graph_utils_test \
2.11 @@ -54,6 +55,7 @@
2.12 counter_test_SOURCES = counter_test.cc
2.13 dfs_test_SOURCES = dfs_test.cc
2.14 dijkstra_test_SOURCES = dijkstra_test.cc
2.15 +edge_set_test_SOURCES = edge_set_test.cc
2.16 graph_test_SOURCES = graph_test.cc
2.17 graph_utils_test_SOURCES = graph_utils_test.cc
2.18 graph_adaptor_test_SOURCES = graph_adaptor_test.cc
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/test/edge_set_test.cc Mon Feb 06 16:58:39 2006 +0000
3.3 @@ -0,0 +1,33 @@
3.4 +// -*- c++ -*-
3.5 +
3.6 +#include <iostream>
3.7 +#include <vector>
3.8 +
3.9 +#include <lemon/concept/graph.h>
3.10 +#include <lemon/concept/ugraph.h>
3.11 +#include <lemon/smart_graph.h>
3.12 +
3.13 +#include <lemon/edge_set.h>
3.14 +
3.15 +#include "test_tools.h"
3.16 +#include "graph_test.h"
3.17 +#include "map_test.h"
3.18 +
3.19 +
3.20 +using namespace lemon;
3.21 +using namespace lemon::concept;
3.22 +
3.23 +typedef StaticGraph Graph;
3.24 +
3.25 +int main() {
3.26 + { // checking edge_sets
3.27 + checkConcept<StaticGraph, ListEdgeSet<Graph> >();
3.28 + checkConcept<UGraph, ListUEdgeSet<Graph> >();
3.29 + checkConcept<StaticGraph, SmartEdgeSet<Graph> >();
3.30 + checkConcept<UGraph, SmartUEdgeSet<Graph> >();
3.31 + }
3.32 +
3.33 + std::cout << __FILE__ ": All tests passed.\n";
3.34 +
3.35 + return 0;
3.36 +}