1.1 --- a/lemon/bits/graph_extender.h Sun Nov 14 16:35:31 2010 +0100
1.2 +++ b/lemon/bits/graph_extender.h Sun Nov 14 20:06:23 2010 +0100
1.3 @@ -746,6 +746,610 @@
1.4
1.5 };
1.6
1.7 + // \ingroup _graphbits
1.8 + //
1.9 + // \brief Extender for the BpGraphs
1.10 + template <typename Base>
1.11 + class BpGraphExtender : public Base {
1.12 + typedef Base Parent;
1.13 +
1.14 + public:
1.15 +
1.16 + typedef BpGraphExtender BpGraph;
1.17 +
1.18 + typedef True UndirectedTag;
1.19 +
1.20 + typedef typename Parent::Node Node;
1.21 + typedef typename Parent::Arc Arc;
1.22 + typedef typename Parent::Edge Edge;
1.23 +
1.24 + // BpGraph extension
1.25 +
1.26 + class RedNode : public Node {
1.27 + public:
1.28 + RedNode() {}
1.29 + RedNode(const RedNode& node) : Node(node) {}
1.30 + RedNode(Invalid) : Node(INVALID){}
1.31 + RedNode(const Node& node) : Node(node) {}
1.32 + };
1.33 + class BlueNode : public Node {
1.34 + public:
1.35 + BlueNode() {}
1.36 + BlueNode(const BlueNode& node) : Node(node) {}
1.37 + BlueNode(Invalid) : Node(INVALID){}
1.38 + BlueNode(const Node& node) : Node(node) {}
1.39 + };
1.40 +
1.41 + using Parent::first;
1.42 + using Parent::next;
1.43 +
1.44 + void first(RedNode& node) const {
1.45 + Parent::firstRed(node);
1.46 + }
1.47 +
1.48 + void next(RedNode& node) const {
1.49 + Parent::nextRed(node);
1.50 + }
1.51 +
1.52 + void first(BlueNode& node) const {
1.53 + Parent::firstBlue(node);
1.54 + }
1.55 +
1.56 + void next(BlueNode& node) const {
1.57 + Parent::nextBlue(node);
1.58 + }
1.59 +
1.60 + using Parent::id;
1.61 +
1.62 + int id(const RedNode& node) const {
1.63 + return Parent::redId(node);
1.64 + }
1.65 +
1.66 + int id(const BlueNode& node) const {
1.67 + return Parent::blueId(node);
1.68 + }
1.69 +
1.70 + int maxId(Node) const {
1.71 + return Parent::maxNodeId();
1.72 + }
1.73 +
1.74 + int maxId(RedNode) const {
1.75 + return Parent::maxRedId();
1.76 + }
1.77 +
1.78 + int maxId(BlueNode) const {
1.79 + return Parent::maxBlueId();
1.80 + }
1.81 +
1.82 + int maxId(Arc) const {
1.83 + return Parent::maxArcId();
1.84 + }
1.85 +
1.86 + int maxId(Edge) const {
1.87 + return Parent::maxEdgeId();
1.88 + }
1.89 +
1.90 + static Node fromId(int id, Node) {
1.91 + return Parent::nodeFromId(id);
1.92 + }
1.93 +
1.94 + static Arc fromId(int id, Arc) {
1.95 + return Parent::arcFromId(id);
1.96 + }
1.97 +
1.98 + static Edge fromId(int id, Edge) {
1.99 + return Parent::edgeFromId(id);
1.100 + }
1.101 +
1.102 + Node oppositeNode(const Node &n, const Edge &e) const {
1.103 + if( n == Parent::u(e))
1.104 + return Parent::v(e);
1.105 + else if( n == Parent::v(e))
1.106 + return Parent::u(e);
1.107 + else
1.108 + return INVALID;
1.109 + }
1.110 +
1.111 + Arc oppositeArc(const Arc &arc) const {
1.112 + return Parent::direct(arc, !Parent::direction(arc));
1.113 + }
1.114 +
1.115 + using Parent::direct;
1.116 + Arc direct(const Edge &edge, const Node &node) const {
1.117 + return Parent::direct(edge, Parent::u(edge) == node);
1.118 + }
1.119 +
1.120 + // Alterable extension
1.121 +
1.122 + typedef AlterationNotifier<BpGraphExtender, Node> NodeNotifier;
1.123 + typedef AlterationNotifier<BpGraphExtender, RedNode> RedNodeNotifier;
1.124 + typedef AlterationNotifier<BpGraphExtender, BlueNode> BlueNodeNotifier;
1.125 + typedef AlterationNotifier<BpGraphExtender, Arc> ArcNotifier;
1.126 + typedef AlterationNotifier<BpGraphExtender, Edge> EdgeNotifier;
1.127 +
1.128 +
1.129 + protected:
1.130 +
1.131 + mutable NodeNotifier node_notifier;
1.132 + mutable RedNodeNotifier red_node_notifier;
1.133 + mutable BlueNodeNotifier blue_node_notifier;
1.134 + mutable ArcNotifier arc_notifier;
1.135 + mutable EdgeNotifier edge_notifier;
1.136 +
1.137 + public:
1.138 +
1.139 + NodeNotifier& notifier(Node) const {
1.140 + return node_notifier;
1.141 + }
1.142 +
1.143 + RedNodeNotifier& notifier(RedNode) const {
1.144 + return red_node_notifier;
1.145 + }
1.146 +
1.147 + BlueNodeNotifier& notifier(BlueNode) const {
1.148 + return blue_node_notifier;
1.149 + }
1.150 +
1.151 + ArcNotifier& notifier(Arc) const {
1.152 + return arc_notifier;
1.153 + }
1.154 +
1.155 + EdgeNotifier& notifier(Edge) const {
1.156 + return edge_notifier;
1.157 + }
1.158 +
1.159 +
1.160 +
1.161 + class NodeIt : public Node {
1.162 + const BpGraph* _graph;
1.163 + public:
1.164 +
1.165 + NodeIt() {}
1.166 +
1.167 + NodeIt(Invalid i) : Node(i) { }
1.168 +
1.169 + explicit NodeIt(const BpGraph& graph) : _graph(&graph) {
1.170 + _graph->first(static_cast<Node&>(*this));
1.171 + }
1.172 +
1.173 + NodeIt(const BpGraph& graph, const Node& node)
1.174 + : Node(node), _graph(&graph) {}
1.175 +
1.176 + NodeIt& operator++() {
1.177 + _graph->next(*this);
1.178 + return *this;
1.179 + }
1.180 +
1.181 + };
1.182 +
1.183 + class RedIt : public Node {
1.184 + const BpGraph* _graph;
1.185 + public:
1.186 +
1.187 + RedIt() {}
1.188 +
1.189 + RedIt(Invalid i) : Node(i) { }
1.190 +
1.191 + explicit RedIt(const BpGraph& graph) : _graph(&graph) {
1.192 + _graph->firstRed(static_cast<Node&>(*this));
1.193 + }
1.194 +
1.195 + RedIt(const BpGraph& graph, const Node& node)
1.196 + : Node(node), _graph(&graph) {
1.197 + LEMON_DEBUG(_graph->red(node), "Node has to be red.");
1.198 + }
1.199 +
1.200 + RedIt& operator++() {
1.201 + _graph->nextRed(*this);
1.202 + return *this;
1.203 + }
1.204 +
1.205 + };
1.206 +
1.207 + class BlueIt : public Node {
1.208 + const BpGraph* _graph;
1.209 + public:
1.210 +
1.211 + BlueIt() {}
1.212 +
1.213 + BlueIt(Invalid i) : Node(i) { }
1.214 +
1.215 + explicit BlueIt(const BpGraph& graph) : _graph(&graph) {
1.216 + _graph->firstBlue(static_cast<Node&>(*this));
1.217 + }
1.218 +
1.219 + BlueIt(const BpGraph& graph, const Node& node)
1.220 + : Node(node), _graph(&graph) {
1.221 + LEMON_DEBUG(_graph->blue(node), "Node has to be blue.");
1.222 + }
1.223 +
1.224 + BlueIt& operator++() {
1.225 + _graph->nextBlue(*this);
1.226 + return *this;
1.227 + }
1.228 +
1.229 + };
1.230 +
1.231 +
1.232 + class ArcIt : public Arc {
1.233 + const BpGraph* _graph;
1.234 + public:
1.235 +
1.236 + ArcIt() { }
1.237 +
1.238 + ArcIt(Invalid i) : Arc(i) { }
1.239 +
1.240 + explicit ArcIt(const BpGraph& graph) : _graph(&graph) {
1.241 + _graph->first(static_cast<Arc&>(*this));
1.242 + }
1.243 +
1.244 + ArcIt(const BpGraph& graph, const Arc& arc) :
1.245 + Arc(arc), _graph(&graph) { }
1.246 +
1.247 + ArcIt& operator++() {
1.248 + _graph->next(*this);
1.249 + return *this;
1.250 + }
1.251 +
1.252 + };
1.253 +
1.254 +
1.255 + class OutArcIt : public Arc {
1.256 + const BpGraph* _graph;
1.257 + public:
1.258 +
1.259 + OutArcIt() { }
1.260 +
1.261 + OutArcIt(Invalid i) : Arc(i) { }
1.262 +
1.263 + OutArcIt(const BpGraph& graph, const Node& node)
1.264 + : _graph(&graph) {
1.265 + _graph->firstOut(*this, node);
1.266 + }
1.267 +
1.268 + OutArcIt(const BpGraph& graph, const Arc& arc)
1.269 + : Arc(arc), _graph(&graph) {}
1.270 +
1.271 + OutArcIt& operator++() {
1.272 + _graph->nextOut(*this);
1.273 + return *this;
1.274 + }
1.275 +
1.276 + };
1.277 +
1.278 +
1.279 + class InArcIt : public Arc {
1.280 + const BpGraph* _graph;
1.281 + public:
1.282 +
1.283 + InArcIt() { }
1.284 +
1.285 + InArcIt(Invalid i) : Arc(i) { }
1.286 +
1.287 + InArcIt(const BpGraph& graph, const Node& node)
1.288 + : _graph(&graph) {
1.289 + _graph->firstIn(*this, node);
1.290 + }
1.291 +
1.292 + InArcIt(const BpGraph& graph, const Arc& arc) :
1.293 + Arc(arc), _graph(&graph) {}
1.294 +
1.295 + InArcIt& operator++() {
1.296 + _graph->nextIn(*this);
1.297 + return *this;
1.298 + }
1.299 +
1.300 + };
1.301 +
1.302 +
1.303 + class EdgeIt : public Parent::Edge {
1.304 + const BpGraph* _graph;
1.305 + public:
1.306 +
1.307 + EdgeIt() { }
1.308 +
1.309 + EdgeIt(Invalid i) : Edge(i) { }
1.310 +
1.311 + explicit EdgeIt(const BpGraph& graph) : _graph(&graph) {
1.312 + _graph->first(static_cast<Edge&>(*this));
1.313 + }
1.314 +
1.315 + EdgeIt(const BpGraph& graph, const Edge& edge) :
1.316 + Edge(edge), _graph(&graph) { }
1.317 +
1.318 + EdgeIt& operator++() {
1.319 + _graph->next(*this);
1.320 + return *this;
1.321 + }
1.322 +
1.323 + };
1.324 +
1.325 + class IncEdgeIt : public Parent::Edge {
1.326 + friend class BpGraphExtender;
1.327 + const BpGraph* _graph;
1.328 + bool _direction;
1.329 + public:
1.330 +
1.331 + IncEdgeIt() { }
1.332 +
1.333 + IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }
1.334 +
1.335 + IncEdgeIt(const BpGraph& graph, const Node &node) : _graph(&graph) {
1.336 + _graph->firstInc(*this, _direction, node);
1.337 + }
1.338 +
1.339 + IncEdgeIt(const BpGraph& graph, const Edge &edge, const Node &node)
1.340 + : _graph(&graph), Edge(edge) {
1.341 + _direction = (_graph->source(edge) == node);
1.342 + }
1.343 +
1.344 + IncEdgeIt& operator++() {
1.345 + _graph->nextInc(*this, _direction);
1.346 + return *this;
1.347 + }
1.348 + };
1.349 +
1.350 + // \brief Base node of the iterator
1.351 + //
1.352 + // Returns the base node (ie. the source in this case) of the iterator
1.353 + Node baseNode(const OutArcIt &arc) const {
1.354 + return Parent::source(static_cast<const Arc&>(arc));
1.355 + }
1.356 + // \brief Running node of the iterator
1.357 + //
1.358 + // Returns the running node (ie. the target in this case) of the
1.359 + // iterator
1.360 + Node runningNode(const OutArcIt &arc) const {
1.361 + return Parent::target(static_cast<const Arc&>(arc));
1.362 + }
1.363 +
1.364 + // \brief Base node of the iterator
1.365 + //
1.366 + // Returns the base node (ie. the target in this case) of the iterator
1.367 + Node baseNode(const InArcIt &arc) const {
1.368 + return Parent::target(static_cast<const Arc&>(arc));
1.369 + }
1.370 + // \brief Running node of the iterator
1.371 + //
1.372 + // Returns the running node (ie. the source in this case) of the
1.373 + // iterator
1.374 + Node runningNode(const InArcIt &arc) const {
1.375 + return Parent::source(static_cast<const Arc&>(arc));
1.376 + }
1.377 +
1.378 + // Base node of the iterator
1.379 + //
1.380 + // Returns the base node of the iterator
1.381 + Node baseNode(const IncEdgeIt &edge) const {
1.382 + return edge._direction ? this->u(edge) : this->v(edge);
1.383 + }
1.384 + // Running node of the iterator
1.385 + //
1.386 + // Returns the running node of the iterator
1.387 + Node runningNode(const IncEdgeIt &edge) const {
1.388 + return edge._direction ? this->v(edge) : this->u(edge);
1.389 + }
1.390 +
1.391 + // Mappable extension
1.392 +
1.393 + template <typename _Value>
1.394 + class NodeMap
1.395 + : public MapExtender<DefaultMap<BpGraph, Node, _Value> > {
1.396 + typedef MapExtender<DefaultMap<BpGraph, Node, _Value> > Parent;
1.397 +
1.398 + public:
1.399 + explicit NodeMap(const BpGraph& bpgraph)
1.400 + : Parent(bpgraph) {}
1.401 + NodeMap(const BpGraph& bpgraph, const _Value& value)
1.402 + : Parent(bpgraph, value) {}
1.403 +
1.404 + private:
1.405 + NodeMap& operator=(const NodeMap& cmap) {
1.406 + return operator=<NodeMap>(cmap);
1.407 + }
1.408 +
1.409 + template <typename CMap>
1.410 + NodeMap& operator=(const CMap& cmap) {
1.411 + Parent::operator=(cmap);
1.412 + return *this;
1.413 + }
1.414 +
1.415 + };
1.416 +
1.417 + template <typename _Value>
1.418 + class RedMap
1.419 + : public MapExtender<DefaultMap<BpGraph, RedNode, _Value> > {
1.420 + typedef MapExtender<DefaultMap<BpGraph, RedNode, _Value> > Parent;
1.421 +
1.422 + public:
1.423 + explicit RedMap(const BpGraph& bpgraph)
1.424 + : Parent(bpgraph) {}
1.425 + RedMap(const BpGraph& bpgraph, const _Value& value)
1.426 + : Parent(bpgraph, value) {}
1.427 +
1.428 + private:
1.429 + RedMap& operator=(const RedMap& cmap) {
1.430 + return operator=<RedMap>(cmap);
1.431 + }
1.432 +
1.433 + template <typename CMap>
1.434 + RedMap& operator=(const CMap& cmap) {
1.435 + Parent::operator=(cmap);
1.436 + return *this;
1.437 + }
1.438 +
1.439 + };
1.440 +
1.441 + template <typename _Value>
1.442 + class BlueMap
1.443 + : public MapExtender<DefaultMap<BpGraph, BlueNode, _Value> > {
1.444 + typedef MapExtender<DefaultMap<BpGraph, BlueNode, _Value> > Parent;
1.445 +
1.446 + public:
1.447 + explicit BlueMap(const BpGraph& bpgraph)
1.448 + : Parent(bpgraph) {}
1.449 + BlueMap(const BpGraph& bpgraph, const _Value& value)
1.450 + : Parent(bpgraph, value) {}
1.451 +
1.452 + private:
1.453 + BlueMap& operator=(const BlueMap& cmap) {
1.454 + return operator=<BlueMap>(cmap);
1.455 + }
1.456 +
1.457 + template <typename CMap>
1.458 + BlueMap& operator=(const CMap& cmap) {
1.459 + Parent::operator=(cmap);
1.460 + return *this;
1.461 + }
1.462 +
1.463 + };
1.464 +
1.465 + template <typename _Value>
1.466 + class ArcMap
1.467 + : public MapExtender<DefaultMap<BpGraph, Arc, _Value> > {
1.468 + typedef MapExtender<DefaultMap<BpGraph, Arc, _Value> > Parent;
1.469 +
1.470 + public:
1.471 + explicit ArcMap(const BpGraph& graph)
1.472 + : Parent(graph) {}
1.473 + ArcMap(const BpGraph& graph, const _Value& value)
1.474 + : Parent(graph, value) {}
1.475 +
1.476 + private:
1.477 + ArcMap& operator=(const ArcMap& cmap) {
1.478 + return operator=<ArcMap>(cmap);
1.479 + }
1.480 +
1.481 + template <typename CMap>
1.482 + ArcMap& operator=(const CMap& cmap) {
1.483 + Parent::operator=(cmap);
1.484 + return *this;
1.485 + }
1.486 + };
1.487 +
1.488 +
1.489 + template <typename _Value>
1.490 + class EdgeMap
1.491 + : public MapExtender<DefaultMap<BpGraph, Edge, _Value> > {
1.492 + typedef MapExtender<DefaultMap<BpGraph, Edge, _Value> > Parent;
1.493 +
1.494 + public:
1.495 + explicit EdgeMap(const BpGraph& graph)
1.496 + : Parent(graph) {}
1.497 +
1.498 + EdgeMap(const BpGraph& graph, const _Value& value)
1.499 + : Parent(graph, value) {}
1.500 +
1.501 + private:
1.502 + EdgeMap& operator=(const EdgeMap& cmap) {
1.503 + return operator=<EdgeMap>(cmap);
1.504 + }
1.505 +
1.506 + template <typename CMap>
1.507 + EdgeMap& operator=(const CMap& cmap) {
1.508 + Parent::operator=(cmap);
1.509 + return *this;
1.510 + }
1.511 +
1.512 + };
1.513 +
1.514 + // Alteration extension
1.515 +
1.516 + Node addRedNode() {
1.517 + Node node = Parent::addRedNode();
1.518 + notifier(RedNode()).add(node);
1.519 + notifier(Node()).add(node);
1.520 + return node;
1.521 + }
1.522 +
1.523 + Node addBlueNode() {
1.524 + Node node = Parent::addBlueNode();
1.525 + notifier(BlueNode()).add(node);
1.526 + notifier(Node()).add(node);
1.527 + return node;
1.528 + }
1.529 +
1.530 + Edge addEdge(const Node& from, const Node& to) {
1.531 + Edge edge = Parent::addEdge(from, to);
1.532 + notifier(Edge()).add(edge);
1.533 + std::vector<Arc> av;
1.534 + av.push_back(Parent::direct(edge, true));
1.535 + av.push_back(Parent::direct(edge, false));
1.536 + notifier(Arc()).add(av);
1.537 + return edge;
1.538 + }
1.539 +
1.540 + void clear() {
1.541 + notifier(Arc()).clear();
1.542 + notifier(Edge()).clear();
1.543 + notifier(Node()).clear();
1.544 + notifier(BlueNode()).clear();
1.545 + notifier(RedNode()).clear();
1.546 + Parent::clear();
1.547 + }
1.548 +
1.549 + template <typename BpGraph, typename NodeRefMap, typename EdgeRefMap>
1.550 + void build(const BpGraph& graph, NodeRefMap& nodeRef,
1.551 + EdgeRefMap& edgeRef) {
1.552 + Parent::build(graph, nodeRef, edgeRef);
1.553 + notifier(RedNode()).build();
1.554 + notifier(BlueNode()).build();
1.555 + notifier(Node()).build();
1.556 + notifier(Edge()).build();
1.557 + notifier(Arc()).build();
1.558 + }
1.559 +
1.560 + void erase(const Node& node) {
1.561 + Arc arc;
1.562 + Parent::firstOut(arc, node);
1.563 + while (arc != INVALID ) {
1.564 + erase(arc);
1.565 + Parent::firstOut(arc, node);
1.566 + }
1.567 +
1.568 + Parent::firstIn(arc, node);
1.569 + while (arc != INVALID ) {
1.570 + erase(arc);
1.571 + Parent::firstIn(arc, node);
1.572 + }
1.573 +
1.574 + if (Parent::red(node)) {
1.575 + notifier(RedNode()).erase(node);
1.576 + } else {
1.577 + notifier(BlueNode()).erase(node);
1.578 + }
1.579 +
1.580 + notifier(Node()).erase(node);
1.581 + Parent::erase(node);
1.582 + }
1.583 +
1.584 + void erase(const Edge& edge) {
1.585 + std::vector<Arc> av;
1.586 + av.push_back(Parent::direct(edge, true));
1.587 + av.push_back(Parent::direct(edge, false));
1.588 + notifier(Arc()).erase(av);
1.589 + notifier(Edge()).erase(edge);
1.590 + Parent::erase(edge);
1.591 + }
1.592 +
1.593 + BpGraphExtender() {
1.594 + red_node_notifier.setContainer(*this);
1.595 + blue_node_notifier.setContainer(*this);
1.596 + node_notifier.setContainer(*this);
1.597 + arc_notifier.setContainer(*this);
1.598 + edge_notifier.setContainer(*this);
1.599 + }
1.600 +
1.601 + ~BpGraphExtender() {
1.602 + edge_notifier.clear();
1.603 + arc_notifier.clear();
1.604 + node_notifier.clear();
1.605 + blue_node_notifier.clear();
1.606 + red_node_notifier.clear();
1.607 + }
1.608 +
1.609 + };
1.610 +
1.611 }
1.612
1.613 #endif