1.1 --- a/lemon/bits/ugraph_extender.h Fri Jun 30 12:14:36 2006 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,444 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - *
1.6 - * This file is a part of LEMON, a generic C++ optimization library
1.7 - *
1.8 - * Copyright (C) 2003-2006
1.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 - *
1.12 - * Permission to use, modify and distribute this software is granted
1.13 - * provided that this copyright notice appears in all copies. For
1.14 - * precise terms see the accompanying LICENSE file.
1.15 - *
1.16 - * This software is provided "AS IS" with no warranty of any kind,
1.17 - * express or implied, and with no claim as to its suitability for any
1.18 - * purpose.
1.19 - *
1.20 - */
1.21 -
1.22 -#ifndef LEMON_BITS_UGRAPH_EXTENDER_H
1.23 -#define LEMON_BITS_UGRAPH_EXTENDER_H
1.24 -
1.25 -#include <lemon/bits/invalid.h>
1.26 -#include <lemon/error.h>
1.27 -
1.28 -#include <lemon/bits/map_extender.h>
1.29 -#include <lemon/bits/default_map.h>
1.30 -
1.31 -#include <lemon/concept_check.h>
1.32 -#include <lemon/concept/maps.h>
1.33 -
1.34 -///\ingroup graphbits
1.35 -///\file
1.36 -///\brief Extenders for the graph types
1.37 -namespace lemon {
1.38 -
1.39 - /// \ingroup graphbits
1.40 - ///
1.41 - /// \brief Extender for the UGraphs
1.42 - template <typename Base>
1.43 - class UGraphExtender : public Base {
1.44 - public:
1.45 -
1.46 - typedef Base Parent;
1.47 - typedef UGraphExtender Graph;
1.48 -
1.49 - typedef typename Parent::Node Node;
1.50 - typedef typename Parent::Edge Edge;
1.51 - typedef typename Parent::UEdge UEdge;
1.52 -
1.53 - // UGraph extension
1.54 -
1.55 - int maxId(Node) const {
1.56 - return Parent::maxNodeId();
1.57 - }
1.58 -
1.59 - int maxId(Edge) const {
1.60 - return Parent::maxEdgeId();
1.61 - }
1.62 -
1.63 - int maxId(UEdge) const {
1.64 - return Parent::maxUEdgeId();
1.65 - }
1.66 -
1.67 - Node fromId(int id, Node) const {
1.68 - return Parent::nodeFromId(id);
1.69 - }
1.70 -
1.71 - Edge fromId(int id, Edge) const {
1.72 - return Parent::edgeFromId(id);
1.73 - }
1.74 -
1.75 - UEdge fromId(int id, UEdge) const {
1.76 - return Parent::uEdgeFromId(id);
1.77 - }
1.78 -
1.79 - Node oppositeNode(const Node &n, const UEdge &e) const {
1.80 - if( n == Parent::source(e))
1.81 - return Parent::target(e);
1.82 - else if( n == Parent::target(e))
1.83 - return Parent::source(e);
1.84 - else
1.85 - return INVALID;
1.86 - }
1.87 -
1.88 - Edge oppositeEdge(const Edge &e) const {
1.89 - return Parent::direct(e, !Parent::direction(e));
1.90 - }
1.91 -
1.92 - using Parent::direct;
1.93 - Edge direct(const UEdge &ue, const Node &s) const {
1.94 - return Parent::direct(ue, Parent::source(ue) == s);
1.95 - }
1.96 -
1.97 - // Alterable extension
1.98 -
1.99 - typedef AlterationNotifier<UGraphExtender, Node> NodeNotifier;
1.100 - typedef AlterationNotifier<UGraphExtender, Edge> EdgeNotifier;
1.101 - typedef AlterationNotifier<UGraphExtender, UEdge> UEdgeNotifier;
1.102 -
1.103 -
1.104 - protected:
1.105 -
1.106 - mutable NodeNotifier node_notifier;
1.107 - mutable EdgeNotifier edge_notifier;
1.108 - mutable UEdgeNotifier uedge_notifier;
1.109 -
1.110 - public:
1.111 -
1.112 - NodeNotifier& getNotifier(Node) const {
1.113 - return node_notifier;
1.114 - }
1.115 -
1.116 - EdgeNotifier& getNotifier(Edge) const {
1.117 - return edge_notifier;
1.118 - }
1.119 -
1.120 - UEdgeNotifier& getNotifier(UEdge) const {
1.121 - return uedge_notifier;
1.122 - }
1.123 -
1.124 -
1.125 -
1.126 - class NodeIt : public Node {
1.127 - const Graph* graph;
1.128 - public:
1.129 -
1.130 - NodeIt() {}
1.131 -
1.132 - NodeIt(Invalid i) : Node(i) { }
1.133 -
1.134 - explicit NodeIt(const Graph& _graph) : graph(&_graph) {
1.135 - _graph.first(static_cast<Node&>(*this));
1.136 - }
1.137 -
1.138 - NodeIt(const Graph& _graph, const Node& node)
1.139 - : Node(node), graph(&_graph) {}
1.140 -
1.141 - NodeIt& operator++() {
1.142 - graph->next(*this);
1.143 - return *this;
1.144 - }
1.145 -
1.146 - };
1.147 -
1.148 -
1.149 - class EdgeIt : public Edge {
1.150 - const Graph* graph;
1.151 - public:
1.152 -
1.153 - EdgeIt() { }
1.154 -
1.155 - EdgeIt(Invalid i) : Edge(i) { }
1.156 -
1.157 - explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
1.158 - _graph.first(static_cast<Edge&>(*this));
1.159 - }
1.160 -
1.161 - EdgeIt(const Graph& _graph, const Edge& e) :
1.162 - Edge(e), graph(&_graph) { }
1.163 -
1.164 - EdgeIt& operator++() {
1.165 - graph->next(*this);
1.166 - return *this;
1.167 - }
1.168 -
1.169 - };
1.170 -
1.171 -
1.172 - class OutEdgeIt : public Edge {
1.173 - const Graph* graph;
1.174 - public:
1.175 -
1.176 - OutEdgeIt() { }
1.177 -
1.178 - OutEdgeIt(Invalid i) : Edge(i) { }
1.179 -
1.180 - OutEdgeIt(const Graph& _graph, const Node& node)
1.181 - : graph(&_graph) {
1.182 - _graph.firstOut(*this, node);
1.183 - }
1.184 -
1.185 - OutEdgeIt(const Graph& _graph, const Edge& edge)
1.186 - : Edge(edge), graph(&_graph) {}
1.187 -
1.188 - OutEdgeIt& operator++() {
1.189 - graph->nextOut(*this);
1.190 - return *this;
1.191 - }
1.192 -
1.193 - };
1.194 -
1.195 -
1.196 - class InEdgeIt : public Edge {
1.197 - const Graph* graph;
1.198 - public:
1.199 -
1.200 - InEdgeIt() { }
1.201 -
1.202 - InEdgeIt(Invalid i) : Edge(i) { }
1.203 -
1.204 - InEdgeIt(const Graph& _graph, const Node& node)
1.205 - : graph(&_graph) {
1.206 - _graph.firstIn(*this, node);
1.207 - }
1.208 -
1.209 - InEdgeIt(const Graph& _graph, const Edge& edge) :
1.210 - Edge(edge), graph(&_graph) {}
1.211 -
1.212 - InEdgeIt& operator++() {
1.213 - graph->nextIn(*this);
1.214 - return *this;
1.215 - }
1.216 -
1.217 - };
1.218 -
1.219 -
1.220 - class UEdgeIt : public Parent::UEdge {
1.221 - const Graph* graph;
1.222 - public:
1.223 -
1.224 - UEdgeIt() { }
1.225 -
1.226 - UEdgeIt(Invalid i) : UEdge(i) { }
1.227 -
1.228 - explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
1.229 - _graph.first(static_cast<UEdge&>(*this));
1.230 - }
1.231 -
1.232 - UEdgeIt(const Graph& _graph, const UEdge& e) :
1.233 - UEdge(e), graph(&_graph) { }
1.234 -
1.235 - UEdgeIt& operator++() {
1.236 - graph->next(*this);
1.237 - return *this;
1.238 - }
1.239 -
1.240 - };
1.241 -
1.242 - class IncEdgeIt : public Parent::UEdge {
1.243 - friend class UGraphExtender;
1.244 - const Graph* graph;
1.245 - bool direction;
1.246 - public:
1.247 -
1.248 - IncEdgeIt() { }
1.249 -
1.250 - IncEdgeIt(Invalid i) : UEdge(i), direction(false) { }
1.251 -
1.252 - IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
1.253 - _graph.firstInc(*this, direction, n);
1.254 - }
1.255 -
1.256 - IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
1.257 - : graph(&_graph), UEdge(ue) {
1.258 - direction = (_graph.source(ue) == n);
1.259 - }
1.260 -
1.261 - IncEdgeIt& operator++() {
1.262 - graph->nextInc(*this, direction);
1.263 - return *this;
1.264 - }
1.265 - };
1.266 -
1.267 - /// \brief Base node of the iterator
1.268 - ///
1.269 - /// Returns the base node (ie. the source in this case) of the iterator
1.270 - Node baseNode(const OutEdgeIt &e) const {
1.271 - return Parent::source((Edge)e);
1.272 - }
1.273 - /// \brief Running node of the iterator
1.274 - ///
1.275 - /// Returns the running node (ie. the target in this case) of the
1.276 - /// iterator
1.277 - Node runningNode(const OutEdgeIt &e) const {
1.278 - return Parent::target((Edge)e);
1.279 - }
1.280 -
1.281 - /// \brief Base node of the iterator
1.282 - ///
1.283 - /// Returns the base node (ie. the target in this case) of the iterator
1.284 - Node baseNode(const InEdgeIt &e) const {
1.285 - return Parent::target((Edge)e);
1.286 - }
1.287 - /// \brief Running node of the iterator
1.288 - ///
1.289 - /// Returns the running node (ie. the source in this case) of the
1.290 - /// iterator
1.291 - Node runningNode(const InEdgeIt &e) const {
1.292 - return Parent::source((Edge)e);
1.293 - }
1.294 -
1.295 - /// Base node of the iterator
1.296 - ///
1.297 - /// Returns the base node of the iterator
1.298 - Node baseNode(const IncEdgeIt &e) const {
1.299 - return e.direction ? source(e) : target(e);
1.300 - }
1.301 - /// Running node of the iterator
1.302 - ///
1.303 - /// Returns the running node of the iterator
1.304 - Node runningNode(const IncEdgeIt &e) const {
1.305 - return e.direction ? target(e) : source(e);
1.306 - }
1.307 -
1.308 - // Mappable extension
1.309 -
1.310 - template <typename _Value>
1.311 - class NodeMap
1.312 - : public MapExtender<DefaultMap<Graph, Node, _Value> > {
1.313 - public:
1.314 - typedef UGraphExtender Graph;
1.315 - typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
1.316 -
1.317 - NodeMap(const Graph& graph)
1.318 - : Parent(graph) {}
1.319 - NodeMap(const Graph& graph, const _Value& value)
1.320 - : Parent(graph, value) {}
1.321 -
1.322 - NodeMap& operator=(const NodeMap& cmap) {
1.323 - return operator=<NodeMap>(cmap);
1.324 - }
1.325 -
1.326 - template <typename CMap>
1.327 - NodeMap& operator=(const CMap& cmap) {
1.328 - Parent::operator=(cmap);
1.329 - return *this;
1.330 - }
1.331 -
1.332 - };
1.333 -
1.334 - template <typename _Value>
1.335 - class EdgeMap
1.336 - : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
1.337 - public:
1.338 - typedef UGraphExtender Graph;
1.339 - typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
1.340 -
1.341 - EdgeMap(const Graph& graph)
1.342 - : Parent(graph) {}
1.343 - EdgeMap(const Graph& graph, const _Value& value)
1.344 - : Parent(graph, value) {}
1.345 -
1.346 - EdgeMap& operator=(const EdgeMap& cmap) {
1.347 - return operator=<EdgeMap>(cmap);
1.348 - }
1.349 -
1.350 - template <typename CMap>
1.351 - EdgeMap& operator=(const CMap& cmap) {
1.352 - Parent::operator=(cmap);
1.353 - return *this;
1.354 - }
1.355 - };
1.356 -
1.357 -
1.358 - template <typename _Value>
1.359 - class UEdgeMap
1.360 - : public MapExtender<DefaultMap<Graph, UEdge, _Value> > {
1.361 - public:
1.362 - typedef UGraphExtender Graph;
1.363 - typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
1.364 -
1.365 - UEdgeMap(const Graph& graph)
1.366 - : Parent(graph) {}
1.367 -
1.368 - UEdgeMap(const Graph& graph, const _Value& value)
1.369 - : Parent(graph, value) {}
1.370 -
1.371 - UEdgeMap& operator=(const UEdgeMap& cmap) {
1.372 - return operator=<UEdgeMap>(cmap);
1.373 - }
1.374 -
1.375 - template <typename CMap>
1.376 - UEdgeMap& operator=(const CMap& cmap) {
1.377 - Parent::operator=(cmap);
1.378 - return *this;
1.379 - }
1.380 -
1.381 - };
1.382 -
1.383 - // Alteration extension
1.384 -
1.385 - Node addNode() {
1.386 - Node node = Parent::addNode();
1.387 - getNotifier(Node()).add(node);
1.388 - return node;
1.389 - }
1.390 -
1.391 - UEdge addEdge(const Node& from, const Node& to) {
1.392 - UEdge uedge = Parent::addEdge(from, to);
1.393 - getNotifier(UEdge()).add(uedge);
1.394 - getNotifier(Edge()).add(Parent::direct(uedge, true));
1.395 - getNotifier(Edge()).add(Parent::direct(uedge, false));
1.396 - return uedge;
1.397 - }
1.398 -
1.399 - void clear() {
1.400 - getNotifier(Edge()).clear();
1.401 - getNotifier(UEdge()).clear();
1.402 - getNotifier(Node()).clear();
1.403 - Parent::clear();
1.404 - }
1.405 -
1.406 - void erase(const Node& node) {
1.407 - Edge edge;
1.408 - Parent::firstOut(edge, node);
1.409 - while (edge != INVALID ) {
1.410 - erase(edge);
1.411 - Parent::firstOut(edge, node);
1.412 - }
1.413 -
1.414 - Parent::firstIn(edge, node);
1.415 - while (edge != INVALID ) {
1.416 - erase(edge);
1.417 - Parent::firstIn(edge, node);
1.418 - }
1.419 -
1.420 - getNotifier(Node()).erase(node);
1.421 - Parent::erase(node);
1.422 - }
1.423 -
1.424 - void erase(const UEdge& uedge) {
1.425 - getNotifier(Edge()).erase(Parent::direct(uedge, true));
1.426 - getNotifier(Edge()).erase(Parent::direct(uedge, false));
1.427 - getNotifier(UEdge()).erase(uedge);
1.428 - Parent::erase(uedge);
1.429 - }
1.430 -
1.431 - UGraphExtender() {
1.432 - node_notifier.setContainer(*this);
1.433 - edge_notifier.setContainer(*this);
1.434 - uedge_notifier.setContainer(*this);
1.435 - }
1.436 -
1.437 - ~UGraphExtender() {
1.438 - uedge_notifier.clear();
1.439 - edge_notifier.clear();
1.440 - node_notifier.clear();
1.441 - }
1.442 -
1.443 - };
1.444 -
1.445 -}
1.446 -
1.447 -#endif