1.1 --- a/doc/groups.dox Mon Dec 19 09:47:10 2005 +0000
1.2 +++ b/doc/groups.dox Mon Dec 19 14:58:09 2005 +0000
1.3 @@ -40,6 +40,16 @@
1.4 */
1.5
1.6 /**
1.7 +@defgroup semi_adaptors Semi-Adaptors Classes for Graphs
1.8 +@ingroup graphs
1.9 +\brief Graph types between real graphs and graph adaptors.
1.10 +
1.11 +Graph types between real graphs and graph adaptors. These classes
1.12 +wrap graphs to give new functionality as the adaptors do it. But the
1.13 +other way they are not light-weigth structures as the adaptors.
1.14 +*/
1.15 +
1.16 +/**
1.17 @defgroup maps Maps
1.18 @ingroup datas
1.19 \brief Some special purpose map to make life easier.
1.20 @@ -48,7 +58,6 @@
1.21 new maps from existing ones.
1.22 */
1.23
1.24 -
1.25 /**
1.26 @defgroup graph_maps Graph Maps
1.27 @ingroup maps
2.1 --- a/lemon/Makefile.am Mon Dec 19 09:47:10 2005 +0000
2.2 +++ b/lemon/Makefile.am Mon Dec 19 14:58:09 2005 +0000
2.3 @@ -62,6 +62,7 @@
2.4 radix_heap.h \
2.5 radix_sort.h \
2.6 smart_graph.h \
2.7 + sub_graph.h \
2.8 time_measure.h \
2.9 topology.h \
2.10 traits.h \
3.1 --- a/lemon/edge_set.h Mon Dec 19 09:47:10 2005 +0000
3.2 +++ b/lemon/edge_set.h Mon Dec 19 14:58:09 2005 +0000
3.3 @@ -192,7 +192,7 @@
3.4
3.5 };
3.6
3.7 - /// \ingroup graphs
3.8 + /// \ingroup semi_adaptors
3.9 ///
3.10 /// \brief Graph using a node set of another graph and an
3.11 /// own edge set.
3.12 @@ -291,7 +291,7 @@
3.13
3.14 };
3.15
3.16 - /// \ingroup graphs
3.17 + /// \ingroup semi_adaptors
3.18 ///
3.19 /// \brief Graph using a node set of another graph and an
3.20 /// own undir edge set.
3.21 @@ -363,6 +363,12 @@
3.22 _edgeset.eraseNode(node);
3.23 Parent::erase(node);
3.24 }
3.25 + virtual void erase(const std::vector<Node>& nodes) {
3.26 + for (int i = 0; i < nodes.size(); ++i) {
3.27 + _edgeset.eraseNode(nodes[i]);
3.28 + }
3.29 + Parent::erase(nodes);
3.30 + }
3.31 virtual void clear() {
3.32 _edgeset.clearNodes();
3.33 Parent::clear();
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/lemon/sub_graph.h Mon Dec 19 14:58:09 2005 +0000
4.3 @@ -0,0 +1,805 @@
4.4 +/* -*- C++ -*-
4.5 + * lemon/sub_graph.h - Part of LEMON, a generic C++ optimization library
4.6 + *
4.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
4.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
4.9 + *
4.10 + * Permission to use, modify and distribute this software is granted
4.11 + * provided that this copyright notice appears in all copies. For
4.12 + * precise terms see the accompanying LICENSE file.
4.13 + *
4.14 + * This software is provided "AS IS" with no warranty of any kind,
4.15 + * express or implied, and with no claim as to its suitability for any
4.16 + * purpose.
4.17 + *
4.18 + */
4.19 +
4.20 +#ifndef LEMON_SUB_GRAPH_H
4.21 +#define LEMON_SUB_GRAPH_H
4.22 +
4.23 +#include <lemon/graph_adaptor.h>
4.24 +
4.25 +namespace lemon {
4.26 +
4.27 + /// \brief Base for the SubGraph.
4.28 + ///
4.29 + /// Base for the SubGraph.
4.30 + template <typename _Graph>
4.31 + class SubGraphBase : public GraphAdaptorBase<const _Graph> {
4.32 + public:
4.33 + typedef _Graph Graph;
4.34 + typedef SubGraphBase<_Graph> SubGraph;
4.35 + typedef GraphAdaptorBase<const _Graph> Parent;
4.36 + typedef Parent Base;
4.37 +
4.38 + typedef typename Parent::Node Node;
4.39 + typedef typename Parent::Edge Edge;
4.40 +
4.41 +
4.42 + protected:
4.43 +
4.44 + class NodesImpl;
4.45 + class EdgesImpl;
4.46 +
4.47 + SubGraphBase() {}
4.48 +
4.49 + void construct(const Graph& _graph, NodesImpl& _nodes, EdgesImpl& _edges) {
4.50 + Parent::setGraph(_graph);
4.51 + nodes = &_nodes;
4.52 + edges = &_edges;
4.53 + firstNode = INVALID;
4.54 +
4.55 + Node node;
4.56 + Parent::first(node);
4.57 + while (node != INVALID) {
4.58 + (*nodes)[node].prev = node;
4.59 + (*nodes)[node].firstIn = INVALID;
4.60 + (*nodes)[node].firstOut = INVALID;
4.61 + Parent::next(node);
4.62 + }
4.63 +
4.64 + Edge edge;
4.65 + Parent::first(edge);
4.66 + while (edge != INVALID) {
4.67 + (*edges)[edge].prevOut = edge;
4.68 + Parent::next(edge);
4.69 + }
4.70 + }
4.71 +
4.72 + public:
4.73 +
4.74 + void first(Node& node) const {
4.75 + node = firstNode;
4.76 + }
4.77 + void next(Node& node) const {
4.78 + node = (*nodes)[node].next;
4.79 + }
4.80 +
4.81 + void first(Edge& edge) const {
4.82 + Node node = firstNode;
4.83 + while (node != INVALID && (*nodes)[node].firstOut == INVALID) {
4.84 + node = (*nodes)[node].next;
4.85 + }
4.86 + if (node == INVALID) {
4.87 + edge = INVALID;
4.88 + } else {
4.89 + edge = (*nodes)[node].firstOut;
4.90 + }
4.91 + }
4.92 + void next(Edge& edge) const {
4.93 + if ((*edges)[edge].nextOut != INVALID) {
4.94 + edge = (*edges)[edge].nextOut;
4.95 + } else {
4.96 + Node node = (*nodes)[source(edge)].next;
4.97 + while (node != INVALID && (*nodes)[node].firstOut == INVALID) {
4.98 + node = (*nodes)[node].next;
4.99 + }
4.100 + if (node == INVALID) {
4.101 + edge = INVALID;
4.102 + } else {
4.103 + edge = (*nodes)[node].firstOut;
4.104 + }
4.105 + }
4.106 + }
4.107 +
4.108 + void firstOut(Edge& edge, const Node& node) const {
4.109 + edge = (*nodes)[node].firstOut;
4.110 + }
4.111 + void nextOut(Edge& edge) const {
4.112 + edge = (*edges)[edge].nextOut;
4.113 + }
4.114 +
4.115 + void firstIn(Edge& edge, const Node& node) const {
4.116 + edge = (*nodes)[node].firstIn;
4.117 + }
4.118 + void nextIn(Edge& edge) const {
4.119 + edge = (*edges)[edge].nextIn;
4.120 + }
4.121 +
4.122 + /// \brief Returns true when the given node is hidden.
4.123 + ///
4.124 + /// Returns true when the given node is hidden.
4.125 + bool hidden(const Node& node) const {
4.126 + return (*nodes)[node].prev == node;
4.127 + }
4.128 +
4.129 + /// \brief Hide the given node in the sub-graph.
4.130 + ///
4.131 + /// Hide the given node in the sub graph. It just lace out from
4.132 + /// the linked lists the given node. If there are incoming or outgoing
4.133 + /// edges into or from this node then all of these will be hidden.
4.134 + void hide(const Node& node) {
4.135 + if (hidden(node)) return;
4.136 + Edge edge;
4.137 + firstOut(edge, node);
4.138 + while (edge != INVALID) {
4.139 + hide(edge);
4.140 + firstOut(edge, node);
4.141 + }
4.142 +
4.143 + firstOut(edge, node);
4.144 + while (edge != INVALID) {
4.145 + hide(edge);
4.146 + firstOut(edge, node);
4.147 + }
4.148 + if ((*nodes)[node].prev != INVALID) {
4.149 + (*nodes)[(*nodes)[node].prev].next = (*nodes)[node].next;
4.150 + } else {
4.151 + firstNode = (*nodes)[node].next;
4.152 + }
4.153 + if ((*nodes)[node].next != INVALID) {
4.154 + (*nodes)[(*nodes)[node].next].prev = (*nodes)[node].prev;
4.155 + }
4.156 + (*nodes)[node].prev = node;
4.157 + (*nodes)[node].firstIn = INVALID;
4.158 + (*nodes)[node].firstOut = INVALID;
4.159 + }
4.160 +
4.161 + /// \brief Unhide the given node in the sub-graph.
4.162 + ///
4.163 + /// Unhide the given node in the sub graph. It just lace in the given
4.164 + /// node into the linked lists.
4.165 + void unHide(const Node& node) {
4.166 + if (!hidden(node)) return;
4.167 + (*nodes)[node].next = firstNode;
4.168 + (*nodes)[node].prev = INVALID;
4.169 + if ((*nodes)[node].next != INVALID) {
4.170 + (*nodes)[(*nodes)[node].next].prev = node;
4.171 + }
4.172 + firstNode = node;
4.173 + }
4.174 +
4.175 + /// \brief Returns true when the given edge is hidden.
4.176 + ///
4.177 + /// Returns true when the given edge is hidden.
4.178 + bool hidden(const Edge& edge) const {
4.179 + return (*edges)[edge].prevOut == edge;
4.180 + }
4.181 +
4.182 + /// \brief Hide the given edge in the sub-graph.
4.183 + ///
4.184 + /// Hide the given edge in the sub graph. It just lace out from
4.185 + /// the linked lists the given edge.
4.186 + void hide(const Edge& edge) {
4.187 + if (hidden(edge)) return;
4.188 + if ((*edges)[edge].prevOut == edge) return;
4.189 + if ((*edges)[edge].prevOut != INVALID) {
4.190 + (*edges)[(*edges)[edge].prevOut].nextOut = (*edges)[edge].nextOut;
4.191 + } else {
4.192 + (*nodes)[source(edge)].firstOut = (*edges)[edge].nextOut;
4.193 + }
4.194 + if ((*edges)[edge].nextOut != INVALID) {
4.195 + (*edges)[(*edges)[edge].nextOut].prevOut = (*edges)[edge].prevOut;
4.196 + }
4.197 +
4.198 + if ((*edges)[edge].prevIn != INVALID) {
4.199 + (*edges)[(*edges)[edge].prevIn].nextIn = (*edges)[edge].nextIn;
4.200 + } else {
4.201 + (*nodes)[target(edge)].firstIn = (*edges)[edge].nextIn;
4.202 + }
4.203 + if ((*edges)[edge].nextIn != INVALID) {
4.204 + (*edges)[(*edges)[edge].nextIn].prevIn = (*edges)[edge].prevIn;
4.205 + }
4.206 + (*edges)[edge].next = edge;
4.207 + }
4.208 +
4.209 + /// \brief Unhide the given edge in the sub-graph.
4.210 + ///
4.211 + /// Unhide the given edge in the sub graph. It just lace in the given
4.212 + /// edge into the linked lists. If the source or the target of the
4.213 + /// node is hidden then it will unhide it.
4.214 + void unHide(const Edge& edge) {
4.215 + if (!hidden(edge)) return;
4.216 +
4.217 + Node node;
4.218 +
4.219 + node = Parent::source(edge);
4.220 + unHide(node);
4.221 + (*edges)[edge].nextOut = (*nodes)[node].firstOut;
4.222 + (*edges)[edge].prevOut = INVALID;
4.223 + if ((*edges)[edge].nextOut != INVALID) {
4.224 + (*edges)[(*edges)[edge].nextOut].prevOut = edge;
4.225 + }
4.226 + (*nodes)[node].firstOut = edge;
4.227 +
4.228 + node = Parent::target(edge);
4.229 + unHide(node);
4.230 + (*edges)[edge].nextIn = (*nodes)[node].firstIn;
4.231 + (*edges)[edge].prevIn = INVALID;
4.232 + if ((*edges)[edge].nextIn != INVALID) {
4.233 + (*edges)[(*edges)[edge].nextIn].prevIn = edge;
4.234 + }
4.235 + (*nodes)[node].firstIn = edge;
4.236 + }
4.237 +
4.238 + typedef False NodeNumTag;
4.239 + typedef False EdgeNumTag;
4.240 +
4.241 + protected:
4.242 + struct NodeT {
4.243 + Node prev, next;
4.244 + Edge firstIn, firstOut;
4.245 + };
4.246 + class NodesImpl : public Graph::template NodeMap<NodeT> {
4.247 + friend class SubGraphBase;
4.248 + public:
4.249 + typedef typename Graph::template NodeMap<NodeT> Parent;
4.250 +
4.251 + NodesImpl(SubGraph& _adaptor, const Graph& _graph)
4.252 + : Parent(_graph), adaptor(_adaptor) {}
4.253 +
4.254 + virtual ~NodesImpl() {}
4.255 +
4.256 + virtual void build() {
4.257 + Parent::build();
4.258 + Node node;
4.259 + adaptor.Base::first(node);
4.260 + while (node != INVALID) {
4.261 + Parent::operator[](node).prev = node;
4.262 + Parent::operator[](node).firstIn = INVALID;
4.263 + Parent::operator[](node).firstOut = INVALID;
4.264 + adaptor.Base::next(node);
4.265 + }
4.266 + }
4.267 +
4.268 + virtual void clear() {
4.269 + adaptor.firstNode = INVALID;
4.270 + Parent::clear();
4.271 + }
4.272 +
4.273 + virtual void add(const Node& node) {
4.274 + Parent::add(node);
4.275 + Parent::operator[](node).prev = node;
4.276 + Parent::operator[](node).firstIn = INVALID;
4.277 + Parent::operator[](node).firstOut = INVALID;
4.278 + }
4.279 + virtual void add(const std::vector<Node>& nodes) {
4.280 + Parent::add(nodes);
4.281 + for (int i = 0; i < (int)nodes.size(); ++i) {
4.282 + Parent::operator[](nodes[i]).prev = nodes[i];
4.283 + Parent::operator[](nodes[i]).firstIn = INVALID;
4.284 + Parent::operator[](nodes[i]).firstOut = INVALID;
4.285 + }
4.286 + }
4.287 +
4.288 + virtual void erase(const Node& node) {
4.289 + adaptor.hide(node);
4.290 + Parent::erase(node);
4.291 + }
4.292 +
4.293 + virtual void erase(const std::vector<Node>& nodes) {
4.294 + for (int i = 0; i < (int)nodes.size(); ++i) {
4.295 + adaptor.hide(nodes[i]);
4.296 + }
4.297 + Parent::erase(nodes);
4.298 + }
4.299 +
4.300 + private:
4.301 + SubGraph& adaptor;
4.302 + };
4.303 +
4.304 + struct EdgeT {
4.305 + Edge prevOut, nextOut;
4.306 + Edge prevIn, nextIn;
4.307 + };
4.308 + class EdgesImpl : public Graph::template EdgeMap<EdgeT> {
4.309 + friend class SubGraphBase;
4.310 + public:
4.311 + typedef typename Graph::template EdgeMap<EdgeT> Parent;
4.312 +
4.313 + EdgesImpl(SubGraph& _adaptor, const Graph& _graph)
4.314 + : Parent(_graph), adaptor(_adaptor) {}
4.315 +
4.316 + virtual ~EdgesImpl() {}
4.317 +
4.318 + virtual void build() {
4.319 + Parent::build();
4.320 + Edge edge;
4.321 + adaptor.Base::first(edge);
4.322 + while (edge != INVALID) {
4.323 + Parent::operator[](edge).prevOut = edge;
4.324 + adaptor.Base::next(edge);
4.325 + }
4.326 + }
4.327 +
4.328 + virtual void clear() {
4.329 + Node node;
4.330 + adaptor.first(node);
4.331 + while (node != INVALID) {
4.332 + (*adaptor.nodes).firstIn = INVALID;
4.333 + (*adaptor.nodes).firstOut = INVALID;
4.334 + adaptor.next(node);
4.335 + }
4.336 + Parent::clear();
4.337 + }
4.338 +
4.339 + virtual void add(const Edge& edge) {
4.340 + Parent::add(edge);
4.341 + Parent::operator[](edge).prevOut = edge;
4.342 + }
4.343 +
4.344 + virtual void add(const std::vector<Edge>& edges) {
4.345 + Parent::add(edges);
4.346 + for (int i = 0; i < (int)edges.size(); ++i) {
4.347 + Parent::operator[](edges[i]).prevOut = edges[i];
4.348 + }
4.349 + }
4.350 +
4.351 + virtual void erase(const Edge& edge) {
4.352 + adaptor.hide(edge);
4.353 + Parent::erase(edge);
4.354 + }
4.355 +
4.356 + virtual void erase(const std::vector<Edge>& edges) {
4.357 + for (int i = 0; i < (int)edges.size(); ++i) {
4.358 + adaptor.hide(edges[i]);
4.359 + }
4.360 + Parent::erase(edge);
4.361 + }
4.362 +
4.363 + private:
4.364 + SubGraph& adaptor;
4.365 + };
4.366 +
4.367 + NodesImpl* nodes;
4.368 + EdgesImpl* edges;
4.369 + Node firstNode;
4.370 + };
4.371 +
4.372 + /// \ingroup semi_adaptors
4.373 + ///
4.374 + /// \brief Graph which uses a subset of an other graph's nodes and edges.
4.375 + ///
4.376 + /// Graph which uses a subset of an other graph's nodes and edges. This class
4.377 + /// is an alternative to the SubGraphAdaptor which is created for the
4.378 + /// same reason. The main difference between the two class that it
4.379 + /// makes linked lists on the unhidden nodes and edges what cause that
4.380 + /// on sparse subgraphs the algorithms can be more efficient and some times
4.381 + /// provide better time complexity. On other way this implemetation is
4.382 + /// less efficient in most case when the subgraph filters out only
4.383 + /// a few nodes or edges.
4.384 + ///
4.385 + /// \see SubGraphAdaptor
4.386 + /// \see EdgeSubGraphBase
4.387 + template <typename Graph>
4.388 + class SubGraph
4.389 + : public IterableGraphExtender< SubGraphBase<Graph> > {
4.390 + public:
4.391 + typedef IterableGraphExtender< SubGraphBase<Graph> > Parent;
4.392 + public:
4.393 + /// \brief Constructor for sub-graph.
4.394 + ///
4.395 + /// Constructor for sub-graph. Initially all the edges and nodes
4.396 + /// are hidden in the graph.
4.397 + SubGraph(const Graph& _graph)
4.398 + : Parent(), nodes(*this, _graph), edges(*this, _graph) {
4.399 + Parent::construct(_graph, nodes, edges);
4.400 + }
4.401 + private:
4.402 + typename Parent::NodesImpl nodes;
4.403 + typename Parent::EdgesImpl edges;
4.404 + };
4.405 +
4.406 + /// \brief Base for the EdgeSubGraph.
4.407 + ///
4.408 + /// Base for the EdgeSubGraph.
4.409 + template <typename _Graph>
4.410 + class EdgeSubGraphBase : public GraphAdaptorBase<const _Graph> {
4.411 + public:
4.412 + typedef _Graph Graph;
4.413 + typedef EdgeSubGraphBase<_Graph> SubGraph;
4.414 + typedef GraphAdaptorBase<const _Graph> Parent;
4.415 + typedef Parent Base;
4.416 +
4.417 + typedef typename Parent::Node Node;
4.418 + typedef typename Parent::Edge Edge;
4.419 +
4.420 +
4.421 + protected:
4.422 +
4.423 + class NodesImpl;
4.424 + class EdgesImpl;
4.425 +
4.426 + EdgeSubGraphBase() {}
4.427 +
4.428 + void construct(const Graph& _graph, NodesImpl& _nodes, EdgesImpl& _edges) {
4.429 + Parent::setGraph(_graph);
4.430 + nodes = &_nodes;
4.431 + edges = &_edges;
4.432 +
4.433 + Node node;
4.434 + Parent::first(node);
4.435 + while (node != INVALID) {
4.436 + (*nodes)[node].firstIn = INVALID;
4.437 + (*nodes)[node].firstOut = INVALID;
4.438 + Parent::next(node);
4.439 + }
4.440 +
4.441 + Edge edge;
4.442 + Parent::first(edge);
4.443 + while (edge != INVALID) {
4.444 + (*edges)[edge].prevOut = edge;
4.445 + Parent::next(edge);
4.446 + }
4.447 + }
4.448 +
4.449 + public:
4.450 +
4.451 + void first(Node& node) const {
4.452 + Parent::first(node);
4.453 + }
4.454 + void next(Node& node) const {
4.455 + Parent::next(node);
4.456 + }
4.457 +
4.458 + void first(Edge& edge) const {
4.459 + Node node;
4.460 + Parent::first(node);
4.461 + while (node != INVALID && (*nodes)[node].firstOut == INVALID) {
4.462 + Parent::next(node);
4.463 + }
4.464 + if (node == INVALID) {
4.465 + edge = INVALID;
4.466 + } else {
4.467 + edge = (*nodes)[node].firstOut;
4.468 + }
4.469 + }
4.470 + void next(Edge& edge) const {
4.471 + if ((*edges)[edge].nextOut != INVALID) {
4.472 + edge = (*edges)[edge].nextOut;
4.473 + } else {
4.474 + Node node = source(edge);
4.475 + Parent::next(node);
4.476 + while (node != INVALID && (*nodes)[node].firstOut == INVALID) {
4.477 + Parent::next(node);
4.478 + }
4.479 + if (node == INVALID) {
4.480 + edge = INVALID;
4.481 + } else {
4.482 + edge = (*nodes)[node].firstOut;
4.483 + }
4.484 + }
4.485 + }
4.486 +
4.487 + void firstOut(Edge& edge, const Node& node) const {
4.488 + edge = (*nodes)[node].firstOut;
4.489 + }
4.490 + void nextOut(Edge& edge) const {
4.491 + edge = (*edges)[edge].nextOut;
4.492 + }
4.493 +
4.494 + void firstIn(Edge& edge, const Node& node) const {
4.495 + edge = (*nodes)[node].firstIn;
4.496 + }
4.497 + void nextIn(Edge& edge) const {
4.498 + edge = (*edges)[edge].nextIn;
4.499 + }
4.500 +
4.501 + /// \brief Returns true when the given edge is hidden.
4.502 + ///
4.503 + /// Returns true when the given edge is hidden.
4.504 + bool hidden(const Edge& edge) const {
4.505 + return (*edges)[edge].prevOut == edge;
4.506 + }
4.507 +
4.508 + /// \brief Hide the given edge in the sub-graph.
4.509 + ///
4.510 + /// Hide the given edge in the sub graph. It just lace out from
4.511 + /// the linked lists the given edge.
4.512 + void hide(const Edge& edge) {
4.513 + if (hidden(edge)) return;
4.514 + if ((*edges)[edge].prevOut != INVALID) {
4.515 + (*edges)[(*edges)[edge].prevOut].nextOut = (*edges)[edge].nextOut;
4.516 + } else {
4.517 + (*nodes)[source(edge)].firstOut = (*edges)[edge].nextOut;
4.518 + }
4.519 + if ((*edges)[edge].nextOut != INVALID) {
4.520 + (*edges)[(*edges)[edge].nextOut].prevOut = (*edges)[edge].prevOut;
4.521 + }
4.522 +
4.523 + if ((*edges)[edge].prevIn != INVALID) {
4.524 + (*edges)[(*edges)[edge].prevIn].nextIn = (*edges)[edge].nextIn;
4.525 + } else {
4.526 + (*nodes)[target(edge)].firstIn = (*edges)[edge].nextIn;
4.527 + }
4.528 + if ((*edges)[edge].nextIn != INVALID) {
4.529 + (*edges)[(*edges)[edge].nextIn].prevIn = (*edges)[edge].prevIn;
4.530 + }
4.531 + (*edges)[edge].prevOut = edge;
4.532 + }
4.533 +
4.534 + /// \brief Unhide the given edge in the sub-graph.
4.535 + ///
4.536 + /// Unhide the given edge in the sub graph. It just lace in the given
4.537 + /// edge into the linked lists.
4.538 + void unHide(const Edge& edge) {
4.539 + if (!hidden(edge)) return;
4.540 + Node node;
4.541 +
4.542 + node = Parent::source(edge);
4.543 + (*edges)[edge].nextOut = (*nodes)[node].firstOut;
4.544 + (*edges)[edge].prevOut = INVALID;
4.545 + if ((*edges)[edge].nextOut != INVALID) {
4.546 + (*edges)[(*edges)[edge].nextOut].prevOut = edge;
4.547 + }
4.548 + (*nodes)[node].firstOut = edge;
4.549 +
4.550 + node = Parent::target(edge);
4.551 + (*edges)[edge].nextIn = (*nodes)[node].firstIn;
4.552 + (*edges)[edge].prevIn = INVALID;
4.553 + if ((*edges)[edge].nextIn != INVALID) {
4.554 + (*edges)[(*edges)[edge].nextIn].prevIn = edge;
4.555 + }
4.556 + (*nodes)[node].firstIn = edge;
4.557 + }
4.558 +
4.559 + protected:
4.560 + struct NodeT {
4.561 + Edge firstIn, firstOut;
4.562 + };
4.563 + class NodesImpl : public Graph::template NodeMap<NodeT> {
4.564 + friend class EdgeSubGraphBase;
4.565 + public:
4.566 + typedef typename Graph::template NodeMap<NodeT> Parent;
4.567 +
4.568 + NodesImpl(SubGraph& _adaptor, const Graph& _graph)
4.569 + : Parent(_graph), adaptor(_adaptor) {}
4.570 +
4.571 + virtual ~NodesImpl() {}
4.572 +
4.573 + virtual void build() {
4.574 + Parent::build();
4.575 + Node node;
4.576 + adaptor.Base::first(node);
4.577 + while (node != INVALID) {
4.578 + Parent::operator[](node).firstIn = INVALID;
4.579 + Parent::operator[](node).firstOut = INVALID;
4.580 + adaptor.Base::next(node);
4.581 + }
4.582 + }
4.583 +
4.584 + virtual void add(const Node& node) {
4.585 + Parent::add(node);
4.586 + Parent::operator[](node).firstIn = INVALID;
4.587 + Parent::operator[](node).firstOut = INVALID;
4.588 + }
4.589 +
4.590 + private:
4.591 + SubGraph& adaptor;
4.592 + };
4.593 +
4.594 + struct EdgeT {
4.595 + Edge prevOut, nextOut;
4.596 + Edge prevIn, nextIn;
4.597 + };
4.598 + class EdgesImpl : public Graph::template EdgeMap<EdgeT> {
4.599 + friend class EdgeSubGraphBase;
4.600 + public:
4.601 + typedef typename Graph::template EdgeMap<EdgeT> Parent;
4.602 +
4.603 + EdgesImpl(SubGraph& _adaptor, const Graph& _graph)
4.604 + : Parent(_graph), adaptor(_adaptor) {}
4.605 +
4.606 + virtual ~EdgesImpl() {}
4.607 +
4.608 + virtual void build() {
4.609 + Parent::build();
4.610 + Edge edge;
4.611 + adaptor.Base::first(edge);
4.612 + while (edge != INVALID) {
4.613 + Parent::operator[](edge).prevOut = edge;
4.614 + adaptor.Base::next(edge);
4.615 + }
4.616 + }
4.617 +
4.618 + virtual void clear() {
4.619 + Node node;
4.620 + adaptor.Base::first(node);
4.621 + while (node != INVALID) {
4.622 + (*adaptor.nodes)[node].firstIn = INVALID;
4.623 + (*adaptor.nodes)[node].firstOut = INVALID;
4.624 + adaptor.Base::next(node);
4.625 + }
4.626 + Parent::clear();
4.627 + }
4.628 +
4.629 + virtual void add(const Edge& edge) {
4.630 + Parent::add(edge);
4.631 + Parent::operator[](edge).prevOut = edge;
4.632 + }
4.633 +
4.634 + virtual void add(const std::vector<Edge>& edges) {
4.635 + Parent::add(edges);
4.636 + for (int i = 0; i < (int)edges.size(); ++i) {
4.637 + Parent::operator[](edges[i]).prevOut = edges[i];
4.638 + }
4.639 + }
4.640 +
4.641 + virtual void erase(const Edge& edge) {
4.642 + adaptor.hide(edge);
4.643 + Parent::erase(edge);
4.644 + }
4.645 +
4.646 + virtual void erase(const std::vector<Edge>& edges) {
4.647 + for (int i = 0; i < (int)edges.size(); ++i) {
4.648 + adaptor.hide(edges[i]);
4.649 + }
4.650 + Parent::erase(edge);
4.651 + }
4.652 +
4.653 + private:
4.654 + SubGraph& adaptor;
4.655 + };
4.656 +
4.657 + NodesImpl* nodes;
4.658 + EdgesImpl* edges;
4.659 + };
4.660 +
4.661 + /// \ingroup semi_adaptors
4.662 + ///
4.663 + /// \brief Graph which uses a subset of an other graph's edges.
4.664 + ///
4.665 + /// Graph which uses a subset of an other graph's edges. This class
4.666 + /// is an alternative to the EdgeSubGraphAdaptor which is created for the
4.667 + /// same reason. The main difference between the two class that it
4.668 + /// makes linked lists on the unhidden edges what cause that
4.669 + /// on sparse subgraphs the algorithms can be more efficient and some times
4.670 + /// provide better time complexity. On other way this implemetation is
4.671 + /// less efficient in most case when the subgraph filters out only
4.672 + /// a few edges.
4.673 + ///
4.674 + /// \see EdgeSubGraphAdaptor
4.675 + /// \see EdgeSubGraphBase
4.676 + template <typename Graph>
4.677 + class EdgeSubGraph
4.678 + : public IterableGraphExtender< EdgeSubGraphBase<Graph> > {
4.679 + public:
4.680 + typedef IterableGraphExtender< EdgeSubGraphBase<Graph> > Parent;
4.681 + public:
4.682 + /// \brief Constructor for sub-graph.
4.683 + ///
4.684 + /// Constructor for sub-graph. Initially all the edges are hidden in the
4.685 + /// graph.
4.686 + EdgeSubGraph(const Graph& _graph)
4.687 + : Parent(), nodes(*this, _graph), edges(*this, _graph) {
4.688 + Parent::construct(_graph, nodes, edges);
4.689 + }
4.690 + private:
4.691 + typename Parent::NodesImpl nodes;
4.692 + typename Parent::EdgesImpl edges;
4.693 + };
4.694 +
4.695 +
4.696 +// template<typename Graph, typename Number,
4.697 +// typename CapacityMap, typename FlowMap>
4.698 +// class ResGraph
4.699 +// : public IterableGraphExtender<EdgeSubGraphBase<
4.700 +// UndirGraphAdaptor<Graph> > > {
4.701 +// public:
4.702 +// typedef IterableGraphExtender<EdgeSubGraphBase<
4.703 +// UndirGraphAdaptor<Graph> > > Parent;
4.704 +
4.705 +// protected:
4.706 +// UndirGraphAdaptor<Graph> undir;
4.707 +
4.708 +// const CapacityMap* capacity;
4.709 +// FlowMap* flow;
4.710 +
4.711 +// typename Parent::NodesImpl nodes;
4.712 +// typename Parent::EdgesImpl edges;
4.713 +
4.714 +// void setCapacityMap(const CapacityMap& _capacity) {
4.715 +// capacity=&_capacity;
4.716 +// }
4.717 +
4.718 +// void setFlowMap(FlowMap& _flow) {
4.719 +// flow=&_flow;
4.720 +// }
4.721 +
4.722 +// public:
4.723 +
4.724 +// typedef typename UndirGraphAdaptor<Graph>::Node Node;
4.725 +// typedef typename UndirGraphAdaptor<Graph>::Edge Edge;
4.726 +// typedef typename UndirGraphAdaptor<Graph>::UndirEdge UndirEdge;
4.727 +
4.728 +// ResGraphAdaptor(Graph& _graph,
4.729 +// const CapacityMap& _capacity, FlowMap& _flow)
4.730 +// : Parent(), undir(_graph), capacity(&_capacity), flow(&_flow),
4.731 +// nodes(*this, _graph), edges(*this, _graph) {
4.732 +// Parent::construct(undir, nodes, edges);
4.733 +// setFlowMap(_flow);
4.734 +// setCapacityMap(_capacity);
4.735 +// typename Graph::Edge edge;
4.736 +// for (_graph.first(edge); edge != INVALID; _graph.next(edge)) {
4.737 +// if ((*flow)[edge] != (*capacity)[edge]) {
4.738 +// Parent::unHide(direct(edge, true));
4.739 +// }
4.740 +// if ((*flow)[edge] != 0) {
4.741 +// Parent::unHide(direct(edge, false));
4.742 +// }
4.743 +// }
4.744 +// }
4.745 +
4.746 +// void augment(const Edge& e, Number a) {
4.747 +// if (direction(e)) {
4.748 +// flow->set(e, (*flow)[e]+a);
4.749 +// } else {
4.750 +// flow->set(e, (*flow)[e]-a);
4.751 +// }
4.752 +// if ((*flow)[e] == (*capacity)[e]) {
4.753 +// Parent::hide(e);
4.754 +// } else {
4.755 +// Parent::unHide(e);
4.756 +// }
4.757 +// if ((*flow)[e] == 0) {
4.758 +// Parent::hide(oppositeEdge(e));
4.759 +// } else {
4.760 +// Parent::unHide(oppositeEdge(e));
4.761 +// }
4.762 +// }
4.763 +
4.764 +// Number resCap(const Edge& e) {
4.765 +// if (direction(e)) {
4.766 +// return (*capacity)[e]-(*flow)[e];
4.767 +// } else {
4.768 +// return (*flow)[e];
4.769 +// }
4.770 +// }
4.771 +
4.772 +// bool direction(const Edge& edge) const {
4.773 +// return Parent::getGraph().direction(edge);
4.774 +// }
4.775 +
4.776 +// Edge direct(const UndirEdge& edge, bool direction) const {
4.777 +// return Parent::getGraph().direct(edge, direction);
4.778 +// }
4.779 +
4.780 +// Edge direct(const UndirEdge& edge, const Node& node) const {
4.781 +// return Parent::getGraph().direct(edge, node);
4.782 +// }
4.783 +
4.784 +// Edge oppositeEdge(const Edge& edge) const {
4.785 +// return Parent::getGraph().oppositeEdge(edge);
4.786 +// }
4.787 +
4.788 +// /// \brief Residual capacity map.
4.789 +// ///
4.790 +// /// In generic residual graphs the residual capacity can be obtained
4.791 +// /// as a map.
4.792 +// class ResCap {
4.793 +// protected:
4.794 +// const ResGraphAdaptor* res_graph;
4.795 +// public:
4.796 +// typedef Number Value;
4.797 +// typedef Edge Key;
4.798 +// ResCap(const ResGraphAdaptor& _res_graph)
4.799 +// : res_graph(&_res_graph) {}
4.800 +// Number operator[](const Edge& e) const {
4.801 +// return res_graph->resCap(e);
4.802 +// }
4.803 +// };
4.804 +// };
4.805 +
4.806 +}
4.807 +
4.808 +#endif