1.1 --- a/lemon/graph_adaptor.h Wed Nov 30 17:49:01 2005 +0000
1.2 +++ b/lemon/graph_adaptor.h Thu Dec 01 15:08:46 2005 +0000
1.3 @@ -1673,394 +1673,6 @@
1.4
1.5 };
1.6
1.7 - template <typename _Graph>
1.8 - class NewEdgeSetAdaptorBase {
1.9 - public:
1.10 -
1.11 - typedef _Graph Graph;
1.12 - typedef typename Graph::Node Node;
1.13 - typedef typename Graph::NodeIt NodeIt;
1.14 -
1.15 - protected:
1.16 -
1.17 - struct NodeT {
1.18 - int first_out, first_in;
1.19 - NodeT() : first_out(-1), first_in(-1) {}
1.20 - };
1.21 -
1.22 - class NodesImpl : protected Graph::template NodeMap<NodeT> {
1.23 -
1.24 - typedef typename Graph::template NodeMap<NodeT> Parent;
1.25 - typedef NewEdgeSetAdaptorBase<Graph> Adaptor;
1.26 -
1.27 - Adaptor& adaptor;
1.28 -
1.29 - public:
1.30 -
1.31 - NodesImpl(Adaptor& _adaptor, const Graph& _graph)
1.32 - : Parent(_graph), adaptor(_adaptor) {}
1.33 -
1.34 - virtual ~NodesImpl() {}
1.35 -
1.36 - virtual void build() {
1.37 - Parent::build();
1.38 - }
1.39 -
1.40 - virtual void clear() {
1.41 - adaptor._clear();
1.42 - Parent::clear();
1.43 - }
1.44 -
1.45 - virtual void add(const Node& node) {
1.46 - Parent::add(node);
1.47 - adaptor._add(node);
1.48 - }
1.49 -
1.50 - virtual void erase(const Node& node) {
1.51 - adaptor._erase(node);
1.52 - Parent::erase(node);
1.53 - }
1.54 -
1.55 - NodeT& operator[](const Node& node) {
1.56 - return Parent::operator[](node);
1.57 - }
1.58 -
1.59 - const NodeT& operator[](const Node& node) const {
1.60 - return Parent::operator[](node);
1.61 - }
1.62 -
1.63 - };
1.64 -
1.65 - NodesImpl* nodes;
1.66 -
1.67 - struct EdgeT {
1.68 - Node source, target;
1.69 - int next_out, next_in;
1.70 - int prev_out, prev_in;
1.71 - EdgeT() : prev_out(-1), prev_in(-1) {}
1.72 - };
1.73 -
1.74 - std::vector<EdgeT> edges;
1.75 -
1.76 - int first_edge;
1.77 - int first_free_edge;
1.78 -
1.79 - virtual void _clear() = 0;
1.80 - virtual void _add(const Node& node) = 0;
1.81 - virtual void _erase(const Node& node) = 0;
1.82 -
1.83 - const Graph* graph;
1.84 -
1.85 - void initalize(const Graph& _graph, NodesImpl& _nodes) {
1.86 - graph = &_graph;
1.87 - nodes = &_nodes;
1.88 - }
1.89 -
1.90 - public:
1.91 -
1.92 - class Edge {
1.93 - friend class NewEdgeSetAdaptorBase<Graph>;
1.94 - protected:
1.95 - Edge(int _id) : id(_id) {}
1.96 - int id;
1.97 - public:
1.98 - Edge() {}
1.99 - Edge(Invalid) : id(-1) {}
1.100 - bool operator==(const Edge& edge) const { return id == edge.id; }
1.101 - bool operator!=(const Edge& edge) const { return id != edge.id; }
1.102 - bool operator<(const Edge& edge) const { return id < edge.id; }
1.103 - };
1.104 -
1.105 - NewEdgeSetAdaptorBase() : first_edge(-1), first_free_edge(-1) {}
1.106 - virtual ~NewEdgeSetAdaptorBase() {}
1.107 -
1.108 - Edge addEdge(const Node& source, const Node& target) {
1.109 - int n;
1.110 - if (first_free_edge == -1) {
1.111 - n = edges.size();
1.112 - edges.push_back(EdgeT());
1.113 - } else {
1.114 - n = first_free_edge;
1.115 - first_free_edge = edges[first_free_edge].next_in;
1.116 - }
1.117 - edges[n].next_in = (*nodes)[target].first_in;
1.118 - (*nodes)[target].first_in = n;
1.119 - edges[n].next_out = (*nodes)[source].first_out;
1.120 - (*nodes)[source].first_out = n;
1.121 - edges[n].source = source;
1.122 - edges[n].target = target;
1.123 - return Edge(n);
1.124 - }
1.125 -
1.126 - void erase(const Edge& edge) {
1.127 - int n = edge.id;
1.128 - if (edges[n].prev_in != -1) {
1.129 - edges[edges[n].prev_in].next_in = edges[n].next_in;
1.130 - } else {
1.131 - (*nodes)[edges[n].target].first_in = edges[n].next_in;
1.132 - }
1.133 - if (edges[n].next_in != -1) {
1.134 - edges[edges[n].next_in].prev_in = edges[n].prev_in;
1.135 - }
1.136 -
1.137 - if (edges[n].prev_out != -1) {
1.138 - edges[edges[n].prev_out].next_out = edges[n].next_out;
1.139 - } else {
1.140 - (*nodes)[edges[n].source].first_out = edges[n].next_out;
1.141 - }
1.142 - if (edges[n].next_out != -1) {
1.143 - edges[edges[n].next_out].prev_out = edges[n].prev_out;
1.144 - }
1.145 -
1.146 - }
1.147 -
1.148 - void first(Node& node) const {
1.149 - graph->first(node);
1.150 - }
1.151 -
1.152 - void next(Node& node) const {
1.153 - graph->next(node);
1.154 - }
1.155 -
1.156 - void first(Edge& edge) const {
1.157 - Node node;
1.158 - for (first(node); node != INVALID && (*nodes)[node].first_in == -1;
1.159 - next(node));
1.160 - edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
1.161 - }
1.162 -
1.163 - void next(Edge& edge) const {
1.164 - if (edges[edge.id].next_in != -1) {
1.165 - edge.id = edges[edge.id].next_in;
1.166 - } else {
1.167 - Node node = edges[edge.id].target;
1.168 - for (next(node); node != INVALID && (*nodes)[node].first_in == -1;
1.169 - next(node));
1.170 - edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
1.171 - }
1.172 - }
1.173 -
1.174 - void firstOut(Edge& edge, const Node& node) const {
1.175 - edge.id = (*nodes)[node].first_out;
1.176 - }
1.177 -
1.178 - void nextOut(Edge& edge) const {
1.179 - edge.id = edges[edge.id].next_out;
1.180 - }
1.181 -
1.182 - void firstIn(Edge& edge, const Node& node) const {
1.183 - edge.id = (*nodes)[node].first_in;
1.184 - }
1.185 -
1.186 - void nextIn(Edge& edge) const {
1.187 - edge.id = edges[edge.id].next_in;
1.188 - }
1.189 -
1.190 - int id(const Node& node) const { return graph->id(node); }
1.191 - int id(const Edge& edge) const { return edge.id; }
1.192 -
1.193 - Node nodeFromId(int id) const { return graph->fromId(id, Node()); }
1.194 - Edge edgeFromId(int id) const { return Edge(id); }
1.195 -
1.196 - int maxNodeId() const { return graph->maxId(Node()); };
1.197 - int maxEdgeId() const { return edges.size() - 1; }
1.198 -
1.199 - Node source(const Edge& edge) const { return edges[edge.id].source;}
1.200 - Node target(const Edge& edge) const { return edges[edge.id].target;}
1.201 -
1.202 - };
1.203 -
1.204 -
1.205 - /// \brief Graph adaptor using a node set of another graph and an
1.206 - /// own edge set.
1.207 - ///
1.208 - /// This structure can be used to establish another graph over a node set
1.209 - /// of an existing one. The node iterator will go through the nodes of the
1.210 - /// original graph.
1.211 - ///
1.212 - /// \param _Graph The type of the graph which shares its node set with
1.213 - /// this class. Its interface must conform to the \ref concept::StaticGraph
1.214 - /// "StaticGraph" concept.
1.215 - ///
1.216 - /// In the edge extension and removing it conforms to the
1.217 - /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
1.218 - template <typename _Graph>
1.219 - class NewEdgeSetAdaptor :
1.220 - public ErasableGraphExtender<
1.221 - ClearableGraphExtender<
1.222 - ExtendableGraphExtender<
1.223 - MappableGraphExtender<
1.224 - IterableGraphExtender<
1.225 - AlterableGraphExtender<
1.226 - GraphExtender<
1.227 - NewEdgeSetAdaptorBase<_Graph> > > > > > > > {
1.228 -
1.229 - public:
1.230 -
1.231 - typedef ErasableGraphExtender<
1.232 - ClearableGraphExtender<
1.233 - ExtendableGraphExtender<
1.234 - MappableGraphExtender<
1.235 - IterableGraphExtender<
1.236 - AlterableGraphExtender<
1.237 - GraphExtender<
1.238 - NewEdgeSetAdaptorBase<_Graph> > > > > > > > Parent;
1.239 -
1.240 -
1.241 - typedef typename Parent::Node Node;
1.242 - typedef typename Parent::Edge Edge;
1.243 -
1.244 - private:
1.245 -
1.246 - virtual void _clear() {
1.247 - Parent::edges.clear();
1.248 - Parent::first_edge = -1;
1.249 - Parent::first_free_edge = -1;
1.250 - Parent::getNotifier(Edge()).clear();
1.251 - Parent::getNotifier(Node()).clear();
1.252 - }
1.253 -
1.254 - virtual void _add(const Node& node) {
1.255 - Parent::getNotifier(Node()).add(node);
1.256 - }
1.257 -
1.258 - virtual void _erase(const Node& node) {
1.259 - Edge edge;
1.260 - Parent::firstOut(edge, node);
1.261 - while (edge != INVALID) {
1.262 - Parent::erase(edge);
1.263 - Parent::firstOut(edge, node);
1.264 - }
1.265 -
1.266 - Parent::firstIn(edge, node);
1.267 - while (edge != INVALID) {
1.268 - Parent::erase(edge);
1.269 - Parent::firstIn(edge, node);
1.270 - }
1.271 -
1.272 - Parent::getNotifier(Node()).erase(node);
1.273 - }
1.274 -
1.275 -
1.276 - typedef typename Parent::NodesImpl NodesImpl;
1.277 -
1.278 - NodesImpl nodes;
1.279 -
1.280 - public:
1.281 -
1.282 - /// \brief Constructor of the adaptor.
1.283 - ///
1.284 - /// Constructor of the adaptor.
1.285 - NewEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {
1.286 - Parent::initalize(_graph, nodes);
1.287 - }
1.288 -
1.289 - void clear() {
1.290 - Parent::getNotifier(Edge()).clear();
1.291 -
1.292 - Parent::edges.clear();
1.293 - Parent::first_edge = -1;
1.294 - Parent::first_free_edge = -1;
1.295 - }
1.296 -
1.297 - };
1.298 -
1.299 - /// \brief Graph adaptor using a node set of another graph and an
1.300 - /// own undir edge set.
1.301 - ///
1.302 - /// This structure can be used to establish another undirected graph over
1.303 - /// a node set of an existing one. The node iterator will go through the
1.304 - /// nodes of the original graph.
1.305 - ///
1.306 - /// \param _Graph The type of the graph which shares its node set with
1.307 - /// this class. Its interface must conform to the \ref concept::StaticGraph
1.308 - /// "StaticGraph" concept.
1.309 - ///
1.310 - /// In the edge extension and removing it conforms to the
1.311 - /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
1.312 - template <typename _Graph>
1.313 - class NewUndirEdgeSetAdaptor :
1.314 - public ErasableUndirGraphExtender<
1.315 - ClearableUndirGraphExtender<
1.316 - ExtendableUndirGraphExtender<
1.317 - MappableUndirGraphExtender<
1.318 - IterableUndirGraphExtender<
1.319 - AlterableUndirGraphExtender<
1.320 - UndirGraphExtender<
1.321 - NewEdgeSetAdaptorBase<_Graph> > > > > > > > {
1.322 -
1.323 - public:
1.324 -
1.325 - typedef ErasableUndirGraphExtender<
1.326 - ClearableUndirGraphExtender<
1.327 - ExtendableUndirGraphExtender<
1.328 - MappableUndirGraphExtender<
1.329 - IterableUndirGraphExtender<
1.330 - AlterableUndirGraphExtender<
1.331 - UndirGraphExtender<
1.332 - NewEdgeSetAdaptorBase<_Graph> > > > > > > > Parent;
1.333 -
1.334 -
1.335 - typedef typename Parent::Node Node;
1.336 - typedef typename Parent::Edge Edge;
1.337 - typedef typename Parent::UndirEdge UndirEdge;
1.338 -
1.339 - private:
1.340 -
1.341 - virtual void _clear() {
1.342 - Parent::edges.clear();
1.343 - Parent::first_edge = -1;
1.344 - Parent::first_free_edge = -1;
1.345 - Parent::getNotifier(Edge()).clear();
1.346 - Parent::getNotifier(Node()).clear();
1.347 - }
1.348 -
1.349 - virtual void _add(const Node& node) {
1.350 - Parent::getNotifier(Node()).add(node);
1.351 - }
1.352 -
1.353 - virtual void _erase(const Node& node) {
1.354 - Edge edge;
1.355 - Parent::firstOut(edge, node);
1.356 - while (edge != INVALID) {
1.357 - Parent::erase(edge);
1.358 - Parent::firstOut(edge, node);
1.359 - }
1.360 -
1.361 - Parent::firstIn(edge, node);
1.362 - while (edge != INVALID) {
1.363 - Parent::erase(edge);
1.364 - Parent::firstIn(edge, node);
1.365 - }
1.366 -
1.367 - Parent::getNotifier(Node()).erase(node);
1.368 - }
1.369 -
1.370 - typedef typename Parent::NodesImpl NodesImpl;
1.371 -
1.372 - NodesImpl nodes;
1.373 -
1.374 - public:
1.375 -
1.376 -
1.377 - /// \brief Constructor of the adaptor.
1.378 - ///
1.379 - /// Constructor of the adaptor.
1.380 - NewUndirEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {
1.381 - Parent::initalize(_graph, nodes);
1.382 - }
1.383 -
1.384 - void clear() {
1.385 - Parent::getNotifier(Edge()).clear();
1.386 - Parent::getNotifier(UndirEdge()).clear();
1.387 -
1.388 - Parent::edges.clear();
1.389 - Parent::first_edge = -1;
1.390 - Parent::first_free_edge = -1;
1.391 - }
1.392 -
1.393 - };
1.394 -
1.395 ///@}
1.396
1.397 } //namespace lemon