1.1 --- a/lemon/graph_adaptor.h Fri May 12 09:54:58 2006 +0000
1.2 +++ b/lemon/graph_adaptor.h Fri May 12 09:56:14 2006 +0000
1.3 @@ -36,7 +36,7 @@
1.4
1.5 #include <lemon/tolerance.h>
1.6
1.7 -#include <iostream>
1.8 +#include <algorithm>
1.9
1.10 namespace lemon {
1.11
1.12 @@ -256,9 +256,8 @@
1.13 ///\code
1.14 /// RevGraphAdaptor<ListGraph> ga(g);
1.15 ///\endcode
1.16 - ///implements the graph obtained from \c g by
1.17 + /// implements the graph obtained from \c g by
1.18 /// reversing the orientation of its edges.
1.19 -
1.20 template<typename _Graph>
1.21 class RevGraphAdaptor :
1.22 public GraphAdaptorExtender<RevGraphAdaptorBase<_Graph> > {
1.23 @@ -983,13 +982,13 @@
1.24 return EdgeSubGraphAdaptor<const Graph, const EdgeFilterMap>(graph, efm);
1.25 }
1.26
1.27 - template <typename _Graph, typename Enable = void>
1.28 + template <typename _Graph>
1.29 class UndirGraphAdaptorBase :
1.30 - public UGraphBaseExtender<GraphAdaptorBase<_Graph> > {
1.31 + public UndirGraphExtender<GraphAdaptorBase<_Graph> > {
1.32 public:
1.33 typedef _Graph Graph;
1.34 typedef UndirGraphAdaptorBase Adaptor;
1.35 - typedef UGraphBaseExtender<GraphAdaptorBase<_Graph> > Parent;
1.36 + typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;
1.37
1.38 protected:
1.39
1.40 @@ -1103,38 +1102,50 @@
1.41
1.42 };
1.43
1.44 - template <typename _Graph>
1.45 - class UndirGraphAdaptorBase<
1.46 - _Graph, typename enable_if<
1.47 - typename _Graph::EdgeNotifier::Notifier>::type >
1.48 - : public UGraphBaseExtender<GraphAdaptorBase<_Graph> > {
1.49 + template <typename _Graph, typename Enable = void>
1.50 + class AlterableUndirGraphAdaptor
1.51 + : public UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > {
1.52 + public:
1.53 + typedef UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > Parent;
1.54 +
1.55 + protected:
1.56 +
1.57 + AlterableUndirGraphAdaptor() : Parent() {}
1.58 +
1.59 public:
1.60
1.61 + typedef typename Parent::EdgeNotifier UEdgeNotifier;
1.62 + typedef InvalidType EdgeNotifier;
1.63 +
1.64 + };
1.65 +
1.66 + template <typename _Graph>
1.67 + class AlterableUndirGraphAdaptor<
1.68 + _Graph,
1.69 + typename enable_if<typename _Graph::EdgeNotifier::Notifier>::type >
1.70 + : public UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > {
1.71 + public:
1.72 +
1.73 + typedef UGraphAdaptorExtender<UndirGraphAdaptorBase<_Graph> > Parent;
1.74 typedef _Graph Graph;
1.75 - typedef UndirGraphAdaptorBase Adaptor;
1.76 - typedef UGraphBaseExtender<GraphAdaptorBase<_Graph> > Parent;
1.77 -
1.78 + typedef typename _Graph::Edge GraphEdge;
1.79 +
1.80 protected:
1.81
1.82 - UndirGraphAdaptorBase()
1.83 - : edge_notifier(*this), edge_notifier_proxy(edge_notifier) {}
1.84 + AlterableUndirGraphAdaptor()
1.85 + : Parent(), edge_notifier(*this), edge_notifier_proxy(*this) {}
1.86
1.87 void setGraph(_Graph& graph) {
1.88 Parent::setGraph(graph);
1.89 - edge_notifier_proxy.setUEdgeNotifier(graph.getNotifier(UEdge()));
1.90 + edge_notifier_proxy.setNotifier(graph.getNotifier(GraphEdge()));
1.91 }
1.92
1.93 public:
1.94
1.95 - ~UndirGraphAdaptorBase() {
1.96 + ~AlterableUndirGraphAdaptor() {
1.97 edge_notifier.clear();
1.98 }
1.99
1.100 - int maxId(typename Parent::Edge) const {
1.101 - return Parent::maxEdgeId();
1.102 - }
1.103 -
1.104 -
1.105 typedef typename Parent::UEdge UEdge;
1.106 typedef typename Parent::Edge Edge;
1.107
1.108 @@ -1142,19 +1153,20 @@
1.109
1.110 using Parent::getNotifier;
1.111
1.112 - typedef AlterationNotifier<UndirGraphAdaptorBase, Edge> EdgeNotifier;
1.113 + typedef AlterationNotifier<AlterableUndirGraphAdaptor,
1.114 + Edge> EdgeNotifier;
1.115 EdgeNotifier& getNotifier(Edge) const { return edge_notifier; }
1.116
1.117 protected:
1.118
1.119 - class NotifierProxy : public UEdgeNotifier::ObserverBase {
1.120 + class NotifierProxy : public Graph::EdgeNotifier::ObserverBase {
1.121 public:
1.122
1.123 - typedef typename UEdgeNotifier::ObserverBase Parent;
1.124 - typedef UndirGraphAdaptorBase AdaptorBase;
1.125 + typedef typename Graph::EdgeNotifier::ObserverBase Parent;
1.126 + typedef AlterableUndirGraphAdaptor AdaptorBase;
1.127
1.128 - NotifierProxy(EdgeNotifier& _edge_notifier)
1.129 - : Parent(), edge_notifier(_edge_notifier) {
1.130 + NotifierProxy(const AdaptorBase& _adaptor)
1.131 + : Parent(), adaptor(&_adaptor) {
1.132 }
1.133
1.134 virtual ~NotifierProxy() {
1.135 @@ -1163,173 +1175,70 @@
1.136 }
1.137 }
1.138
1.139 - void setUEdgeNotifier(UEdgeNotifier& _uedge_notifier) {
1.140 - Parent::attach(_uedge_notifier);
1.141 + void setNotifier(typename Graph::EdgeNotifier& notifier) {
1.142 + Parent::attach(notifier);
1.143 }
1.144
1.145
1.146 protected:
1.147
1.148 - virtual void add(const UEdge& uedge) {
1.149 + virtual void add(const GraphEdge& ge) {
1.150 std::vector<Edge> edges;
1.151 - edges.push_back(AdaptorBase::Parent::direct(uedge, true));
1.152 - edges.push_back(AdaptorBase::Parent::direct(uedge, false));
1.153 - edge_notifier.add(edges);
1.154 + edges.push_back(AdaptorBase::Parent::direct(ge, true));
1.155 + edges.push_back(AdaptorBase::Parent::direct(ge, false));
1.156 + adaptor->getNotifier(Edge()).add(edges);
1.157 }
1.158 - virtual void add(const std::vector<UEdge>& uedges) {
1.159 + virtual void add(const std::vector<GraphEdge>& ge) {
1.160 std::vector<Edge> edges;
1.161 - for (int i = 0; i < (int)uedges.size(); ++i) {
1.162 - edges.push_back(AdaptorBase::Parent::direct(uedges[i], true));
1.163 - edges.push_back(AdaptorBase::Parent::direct(uedges[i], false));
1.164 + for (int i = 0; i < (int)ge.size(); ++i) {
1.165 + edges.push_back(AdaptorBase::Parent::direct(ge[i], true));
1.166 + edges.push_back(AdaptorBase::Parent::direct(ge[i], false));
1.167 }
1.168 - edge_notifier.add(edges);
1.169 + adaptor->getNotifier(Edge()).add(edges);
1.170 }
1.171 - virtual void erase(const UEdge& uedge) {
1.172 + virtual void erase(const GraphEdge& ge) {
1.173 std::vector<Edge> edges;
1.174 - edges.push_back(AdaptorBase::Parent::direct(uedge, true));
1.175 - edges.push_back(AdaptorBase::Parent::direct(uedge, false));
1.176 - edge_notifier.erase(edges);
1.177 + edges.push_back(AdaptorBase::Parent::direct(ge, true));
1.178 + edges.push_back(AdaptorBase::Parent::direct(ge, false));
1.179 + adaptor->getNotifier(Edge()).erase(edges);
1.180 }
1.181 - virtual void erase(const std::vector<UEdge>& uedges) {
1.182 + virtual void erase(const std::vector<GraphEdge>& ge) {
1.183 std::vector<Edge> edges;
1.184 - for (int i = 0; i < (int)uedges.size(); ++i) {
1.185 - edges.push_back(AdaptorBase::Parent::direct(uedges[i], true));
1.186 - edges.push_back(AdaptorBase::Parent::direct(uedges[i], false));
1.187 + for (int i = 0; i < (int)ge.size(); ++i) {
1.188 + edges.push_back(AdaptorBase::Parent::direct(ge[i], true));
1.189 + edges.push_back(AdaptorBase::Parent::direct(ge[i], false));
1.190 }
1.191 - edge_notifier.erase(edges);
1.192 + adaptor->getNotifier(Edge()).erase(edges);
1.193 }
1.194 virtual void build() {
1.195 - edge_notifier.build();
1.196 + adaptor->getNotifier(Edge()).build();
1.197 }
1.198 virtual void clear() {
1.199 - edge_notifier.clear();
1.200 + adaptor->getNotifier(Edge()).clear();
1.201 }
1.202
1.203 - EdgeNotifier& edge_notifier;
1.204 + const AdaptorBase* adaptor;
1.205 };
1.206
1.207
1.208 mutable EdgeNotifier edge_notifier;
1.209 NotifierProxy edge_notifier_proxy;
1.210
1.211 - private:
1.212 -
1.213 - template <typename _Value>
1.214 - class EdgeMapBase {
1.215 - private:
1.216 -
1.217 - typedef typename _Graph::template EdgeMap<_Value> MapImpl;
1.218 -
1.219 - public:
1.220 -
1.221 - typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
1.222 -
1.223 - typedef _Value Value;
1.224 - typedef Edge Key;
1.225 -
1.226 - EdgeMapBase(const Adaptor& adaptor) :
1.227 - forward_map(*adaptor.graph), backward_map(*adaptor.graph) {}
1.228 -
1.229 - EdgeMapBase(const Adaptor& adaptor, const Value& v)
1.230 - : forward_map(*adaptor.graph, v), backward_map(*adaptor.graph, v) {}
1.231 -
1.232 - void set(const Edge& e, const Value& a) {
1.233 - if (Parent::direction(e)) {
1.234 - forward_map.set(e, a);
1.235 - } else {
1.236 - backward_map.set(e, a);
1.237 - }
1.238 - }
1.239 -
1.240 - typename MapTraits<MapImpl>::ConstReturnValue operator[](Edge e) const {
1.241 - if (Parent::direction(e)) {
1.242 - return forward_map[e];
1.243 - } else {
1.244 - return backward_map[e];
1.245 - }
1.246 - }
1.247 -
1.248 - typename MapTraits<MapImpl>::ReturnValue operator[](Edge e) {
1.249 - if (Parent::direction(e)) {
1.250 - return forward_map[e];
1.251 - } else {
1.252 - return backward_map[e];
1.253 - }
1.254 - }
1.255 -
1.256 - protected:
1.257 -
1.258 - MapImpl forward_map, backward_map;
1.259 -
1.260 - };
1.261 -
1.262 - public:
1.263 -
1.264 - template <typename _Value>
1.265 - class EdgeMap
1.266 - : public SubMapExtender<Adaptor, EdgeMapBase<_Value> >
1.267 - {
1.268 - public:
1.269 - typedef Adaptor Graph;
1.270 - typedef SubMapExtender<Adaptor, EdgeMapBase<_Value> > Parent;
1.271 -
1.272 - EdgeMap(const Graph& graph)
1.273 - : Parent(graph) {}
1.274 - EdgeMap(const Graph& graph, const _Value& value)
1.275 - : Parent(graph, value) {}
1.276 -
1.277 - EdgeMap& operator=(const EdgeMap& cmap) {
1.278 - return operator=<EdgeMap>(cmap);
1.279 - }
1.280 -
1.281 - template <typename CMap>
1.282 - EdgeMap& operator=(const CMap& cmap) {
1.283 - Parent::operator=(cmap);
1.284 - return *this;
1.285 - }
1.286 - };
1.287 -
1.288 - template <typename _Value>
1.289 - class UEdgeMap : public Graph::template EdgeMap<_Value> {
1.290 - public:
1.291 -
1.292 - typedef typename Graph::template EdgeMap<_Value> Parent;
1.293 -
1.294 - explicit UEdgeMap(const Adaptor& ga)
1.295 - : Parent(*ga.graph) {}
1.296 -
1.297 - UEdgeMap(const Adaptor& ga, const _Value& value)
1.298 - : Parent(*ga.graph, value) {}
1.299 -
1.300 - UEdgeMap& operator=(const UEdgeMap& cmap) {
1.301 - return operator=<UEdgeMap>(cmap);
1.302 - }
1.303 -
1.304 - template <typename CMap>
1.305 - UEdgeMap& operator=(const CMap& cmap) {
1.306 - Parent::operator=(cmap);
1.307 - return *this;
1.308 - }
1.309 -
1.310 - };
1.311 -
1.312 };
1.313
1.314 - ///\brief An undirected graph is made from a directed graph by an adaptor
1.315 - ///\ingroup graph_adaptors
1.316 +
1.317 + /// \brief An undirected graph is made from a directed graph by an adaptor
1.318 + /// \ingroup graph_adaptors
1.319 ///
1.320 /// Undocumented, untested!!!
1.321 /// If somebody knows nice demo application, let's polulate it.
1.322 ///
1.323 /// \author Marton Makai
1.324 template<typename _Graph>
1.325 - class UndirGraphAdaptor :
1.326 - public UGraphAdaptorExtender<
1.327 - UndirGraphAdaptorBase<_Graph> > {
1.328 + class UndirGraphAdaptor : public AlterableUndirGraphAdaptor<_Graph> {
1.329 public:
1.330 typedef _Graph Graph;
1.331 - typedef UGraphAdaptorExtender<
1.332 - UndirGraphAdaptorBase<_Graph> > Parent;
1.333 + typedef AlterableUndirGraphAdaptor<_Graph> Parent;
1.334 protected:
1.335 UndirGraphAdaptor() { }
1.336 public:
1.337 @@ -1694,371 +1603,977 @@
1.338
1.339 };
1.340
1.341 -// template <typename _Graph>
1.342 -// class SplitGraphAdaptorBase
1.343 -// : public GraphAdaptorBase<_Graph> {
1.344 -// public:
1.345 -// typedef GraphAdaptorBase<_Graph> Parent;
1.346 + /// \brief Base class for split graph adaptor
1.347 + ///
1.348 + /// Base class of split graph adaptor. In most case you do not need to
1.349 + /// use it directly but the documented member functions of this class can
1.350 + /// be used with the SplitGraphAdaptor class.
1.351 + /// \sa SplitGraphAdaptor
1.352 + template <typename _Graph>
1.353 + class SplitGraphAdaptorBase
1.354 + : public GraphAdaptorBase<const _Graph> {
1.355 + public:
1.356
1.357 -// class Node;
1.358 -// class Edge;
1.359 -// template <typename T> class NodeMap;
1.360 -// template <typename T> class EdgeMap;
1.361 + typedef _Graph Graph;
1.362 +
1.363 + typedef GraphAdaptorBase<const _Graph> Parent;
1.364 +
1.365 + typedef typename Graph::Node GraphNode;
1.366 + typedef typename Graph::Edge GraphEdge;
1.367 +
1.368 + class Node;
1.369 + class Edge;
1.370 +
1.371 + template <typename T> class NodeMap;
1.372 + template <typename T> class EdgeMap;
1.373
1.374
1.375 -// class Node : public Parent::Node {
1.376 -// friend class SplitGraphAdaptorBase;
1.377 -// template <typename T> friend class NodeMap;
1.378 -// typedef typename Parent::Node NodeParent;
1.379 -// private:
1.380 + class Node : public GraphNode {
1.381 + friend class SplitGraphAdaptorBase;
1.382 + template <typename T> friend class NodeMap;
1.383 + private:
1.384
1.385 -// bool entry;
1.386 -// Node(typename Parent::Node _node, bool _entry)
1.387 -// : Parent::Node(_node), entry(_entry) {}
1.388 + bool in_node;
1.389 + Node(GraphNode _node, bool _in_node)
1.390 + : GraphNode(_node), in_node(_in_node) {}
1.391
1.392 -// public:
1.393 -// Node() {}
1.394 -// Node(Invalid) : NodeParent(INVALID), entry(true) {}
1.395 + public:
1.396
1.397 -// bool operator==(const Node& node) const {
1.398 -// return NodeParent::operator==(node) && entry == node.entry;
1.399 -// }
1.400 + Node() {}
1.401 + Node(Invalid) : GraphNode(INVALID), in_node(true) {}
1.402 +
1.403 + bool operator==(const Node& node) const {
1.404 + return GraphNode::operator==(node) && in_node == node.in_node;
1.405 + }
1.406
1.407 -// bool operator!=(const Node& node) const {
1.408 -// return !(*this == node);
1.409 -// }
1.410 + bool operator!=(const Node& node) const {
1.411 + return !(*this == node);
1.412 + }
1.413
1.414 -// bool operator<(const Node& node) const {
1.415 -// return NodeParent::operator<(node) ||
1.416 -// (NodeParent::operator==(node) && entry < node.entry);
1.417 -// }
1.418 -// };
1.419 + bool operator<(const Node& node) const {
1.420 + return GraphNode::operator<(node) ||
1.421 + (GraphNode::operator==(node) && in_node < node.in_node);
1.422 + }
1.423 + };
1.424
1.425 -// /// \todo May we want VARIANT/union type
1.426 -// class Edge : public Parent::Edge {
1.427 -// friend class SplitGraphAdaptorBase;
1.428 -// template <typename T> friend class EdgeMap;
1.429 -// private:
1.430 -// typedef typename Parent::Edge EdgeParent;
1.431 -// typedef typename Parent::Node NodeParent;
1.432 -// NodeParent bind;
1.433 + class Edge {
1.434 + friend class SplitGraphAdaptorBase;
1.435 + template <typename T> friend class EdgeMap;
1.436 + private:
1.437 + typedef BiVariant<GraphEdge, GraphNode> EdgeImpl;
1.438
1.439 -// Edge(const EdgeParent& edge, const NodeParent& node)
1.440 -// : EdgeParent(edge), bind(node) {}
1.441 -// public:
1.442 -// Edge() {}
1.443 -// Edge(Invalid) : EdgeParent(INVALID), bind(INVALID) {}
1.444 + explicit Edge(const GraphEdge& edge) : item(edge) {}
1.445 + explicit Edge(const GraphNode& node) : item(node) {}
1.446 +
1.447 + EdgeImpl item;
1.448
1.449 -// bool operator==(const Edge& edge) const {
1.450 -// return EdgeParent::operator==(edge) && bind == edge.bind;
1.451 -// }
1.452 + public:
1.453 + Edge() {}
1.454 + Edge(Invalid) : item(GraphEdge(INVALID)) {}
1.455 +
1.456 + bool operator==(const Edge& edge) const {
1.457 + if (item.firstState()) {
1.458 + if (edge.item.firstState()) {
1.459 + return item.first() == edge.item.first();
1.460 + }
1.461 + } else {
1.462 + if (edge.item.secondState()) {
1.463 + return item.second() == edge.item.second();
1.464 + }
1.465 + }
1.466 + return false;
1.467 + }
1.468
1.469 -// bool operator!=(const Edge& edge) const {
1.470 -// return !(*this == edge);
1.471 -// }
1.472 + bool operator!=(const Edge& edge) const {
1.473 + return !(*this == edge);
1.474 + }
1.475
1.476 -// bool operator<(const Edge& edge) const {
1.477 -// return EdgeParent::operator<(edge) ||
1.478 -// (EdgeParent::operator==(edge) && bind < edge.bind);
1.479 -// }
1.480 -// };
1.481 + bool operator<(const Edge& edge) const {
1.482 + if (item.firstState()) {
1.483 + if (edge.item.firstState()) {
1.484 + return item.first() < edge.item.first();
1.485 + }
1.486 + return false;
1.487 + } else {
1.488 + if (edge.item.secondState()) {
1.489 + return item.second() < edge.item.second();
1.490 + }
1.491 + return true;
1.492 + }
1.493 + }
1.494
1.495 -// void first(Node& node) const {
1.496 -// Parent::first(node);
1.497 -// node.entry = true;
1.498 -// }
1.499 + operator GraphEdge() const { return item.first(); }
1.500 + operator GraphNode() const { return item.second(); }
1.501
1.502 -// void next(Node& node) const {
1.503 -// if (node.entry) {
1.504 -// node.entry = false;
1.505 -// } else {
1.506 -// node.entry = true;
1.507 -// Parent::next(node);
1.508 -// }
1.509 -// }
1.510 + };
1.511
1.512 -// void first(Edge& edge) const {
1.513 -// Parent::first(edge);
1.514 -// if ((typename Parent::Edge&)edge == INVALID) {
1.515 -// Parent::first(edge.bind);
1.516 -// } else {
1.517 -// edge.bind = INVALID;
1.518 -// }
1.519 -// }
1.520 + void first(Node& node) const {
1.521 + Parent::first(node);
1.522 + node.in_node = true;
1.523 + }
1.524
1.525 -// void next(Edge& edge) const {
1.526 -// if ((typename Parent::Edge&)edge != INVALID) {
1.527 -// Parent::next(edge);
1.528 -// if ((typename Parent::Edge&)edge == INVALID) {
1.529 -// Parent::first(edge.bind);
1.530 -// }
1.531 -// } else {
1.532 -// Parent::next(edge.bind);
1.533 -// }
1.534 -// }
1.535 + void next(Node& node) const {
1.536 + if (node.in_node) {
1.537 + node.in_node = false;
1.538 + } else {
1.539 + node.in_node = true;
1.540 + Parent::next(node);
1.541 + }
1.542 + }
1.543
1.544 -// void firstIn(Edge& edge, const Node& node) const {
1.545 -// if (node.entry) {
1.546 -// Parent::firstIn(edge, node);
1.547 -// edge.bind = INVALID;
1.548 -// } else {
1.549 -// (typename Parent::Edge&)edge = INVALID;
1.550 -// edge.bind = node;
1.551 -// }
1.552 -// }
1.553 + void first(Edge& edge) const {
1.554 + edge.item.setSecond();
1.555 + Parent::first(edge.item.second());
1.556 + if (edge.item.second() == INVALID) {
1.557 + edge.item.setFirst();
1.558 + Parent::first(edge.item.first());
1.559 + }
1.560 + }
1.561
1.562 -// void nextIn(Edge& edge) const {
1.563 -// if ((typename Parent::Edge&)edge != INVALID) {
1.564 -// Parent::nextIn(edge);
1.565 -// } else {
1.566 -// edge.bind = INVALID;
1.567 -// }
1.568 -// }
1.569 + void next(Edge& edge) const {
1.570 + if (edge.item.secondState()) {
1.571 + Parent::next(edge.item.second());
1.572 + if (edge.item.second() == INVALID) {
1.573 + edge.item.setFirst();
1.574 + Parent::first(edge.item.first());
1.575 + }
1.576 + } else {
1.577 + Parent::next(edge.item.first());
1.578 + }
1.579 + }
1.580
1.581 -// void firstOut(Edge& edge, const Node& node) const {
1.582 -// if (!node.entry) {
1.583 -// Parent::firstOut(edge, node);
1.584 -// edge.bind = INVALID;
1.585 -// } else {
1.586 -// (typename Parent::Edge&)edge = INVALID;
1.587 -// edge.bind = node;
1.588 -// }
1.589 -// }
1.590 + void firstOut(Edge& edge, const Node& node) const {
1.591 + if (node.in_node) {
1.592 + edge.item.setSecond(node);
1.593 + } else {
1.594 + edge.item.setFirst();
1.595 + Parent::firstOut(edge.item.first(), node);
1.596 + }
1.597 + }
1.598
1.599 -// void nextOut(Edge& edge) const {
1.600 -// if ((typename Parent::Edge&)edge != INVALID) {
1.601 -// Parent::nextOut(edge);
1.602 -// } else {
1.603 -// edge.bind = INVALID;
1.604 -// }
1.605 -// }
1.606 + void nextOut(Edge& edge) const {
1.607 + if (!edge.item.firstState()) {
1.608 + edge.item.setFirst(INVALID);
1.609 + } else {
1.610 + Parent::nextOut(edge.item.first());
1.611 + }
1.612 + }
1.613
1.614 -// Node source(const Edge& edge) const {
1.615 -// if ((typename Parent::Edge&)edge != INVALID) {
1.616 -// return Node(Parent::source(edge), false);
1.617 -// } else {
1.618 -// return Node(edge.bind, true);
1.619 -// }
1.620 -// }
1.621 + void firstIn(Edge& edge, const Node& node) const {
1.622 + if (!node.in_node) {
1.623 + edge.item.setSecond(node);
1.624 + } else {
1.625 + edge.item.setFirst();
1.626 + Parent::firstIn(edge.item.first(), node);
1.627 + }
1.628 + }
1.629
1.630 -// Node target(const Edge& edge) const {
1.631 -// if ((typename Parent::Edge&)edge != INVALID) {
1.632 -// return Node(Parent::target(edge), true);
1.633 -// } else {
1.634 -// return Node(edge.bind, false);
1.635 -// }
1.636 -// }
1.637 + void nextIn(Edge& edge) const {
1.638 + if (!edge.item.firstState()) {
1.639 + edge.item.setFirst(INVALID);
1.640 + } else {
1.641 + Parent::nextIn(edge.item.first());
1.642 + }
1.643 + }
1.644
1.645 -// static bool entryNode(const Node& node) {
1.646 -// return node.entry;
1.647 -// }
1.648 + Node source(const Edge& edge) const {
1.649 + if (edge.item.firstState()) {
1.650 + return Node(Parent::source(edge.item.first()), false);
1.651 + } else {
1.652 + return Node(edge.item.second(), true);
1.653 + }
1.654 + }
1.655
1.656 -// static bool exitNode(const Node& node) {
1.657 -// return !node.entry;
1.658 -// }
1.659 + Node target(const Edge& edge) const {
1.660 + if (edge.item.firstState()) {
1.661 + return Node(Parent::target(edge.item.first()), true);
1.662 + } else {
1.663 + return Node(edge.item.second(), false);
1.664 + }
1.665 + }
1.666
1.667 -// static Node getEntry(const typename Parent::Node& node) {
1.668 -// return Node(node, true);
1.669 -// }
1.670 + int id(const Node& node) const {
1.671 + return (Parent::id(node) << 1) | (node.in_node ? 0 : 1);
1.672 + }
1.673 + Node nodeFromId(int id) const {
1.674 + return Node(Parent::nodeFromId(id >> 1), (id & 1) == 0);
1.675 + }
1.676 + int maxNodeId() const {
1.677 + return 2 * Parent::maxNodeId() + 1;
1.678 + }
1.679
1.680 -// static Node getExit(const typename Parent::Node& node) {
1.681 -// return Node(node, false);
1.682 -// }
1.683 + int id(const Edge& edge) const {
1.684 + if (edge.item.firstState()) {
1.685 + return Parent::id(edge.item.first()) << 1;
1.686 + } else {
1.687 + return (Parent::id(edge.item.second()) << 1) | 1;
1.688 + }
1.689 + }
1.690 + Edge edgeFromId(int id) const {
1.691 + if ((id & 1) == 0) {
1.692 + return Edge(Parent::edgeFromId(id >> 1));
1.693 + } else {
1.694 + return Edge(Parent::nodeFromId(id >> 1));
1.695 + }
1.696 + }
1.697 + int maxEdgeId() const {
1.698 + return std::max(Parent::maxNodeId() << 1,
1.699 + (Parent::maxEdgeId() << 1) | 1);
1.700 + }
1.701
1.702 -// static bool originalEdge(const Edge& edge) {
1.703 -// return (typename Parent::Edge&)edge != INVALID;
1.704 -// }
1.705 + /// \brief Returns true when the node is in-node.
1.706 + ///
1.707 + /// Returns true when the node is in-node.
1.708 + static bool inNode(const Node& node) {
1.709 + return node.in_node;
1.710 + }
1.711
1.712 -// static bool bindingEdge(const Edge& edge) {
1.713 -// return edge.bind != INVALID;
1.714 -// }
1.715 + /// \brief Returns true when the node is out-node.
1.716 + ///
1.717 + /// Returns true when the node is out-node.
1.718 + static bool outNode(const Node& node) {
1.719 + return !node.in_node;
1.720 + }
1.721
1.722 -// static Node getBindedNode(const Edge& edge) {
1.723 -// return edge.bind;
1.724 -// }
1.725 + /// \brief Returns true when the edge is edge in the original graph.
1.726 + ///
1.727 + /// Returns true when the edge is edge in the original graph.
1.728 + static bool origEdge(const Edge& edge) {
1.729 + return edge.item.firstState();
1.730 + }
1.731
1.732 -// int nodeNum() const {
1.733 -// return Parent::nodeNum() * 2;
1.734 -// }
1.735 + /// \brief Returns true when the edge binds an in-node and an out-node.
1.736 + ///
1.737 + /// Returns true when the edge binds an in-node and an out-node.
1.738 + static bool bindEdge(const Edge& edge) {
1.739 + return edge.item.secondState();
1.740 + }
1.741
1.742 -// typedef True EdgeNumTag;
1.743 + /// \brief Gives back the in-node created from the \c node.
1.744 + ///
1.745 + /// Gives back the in-node created from the \c node.
1.746 + static Node inNode(const GraphNode& node) {
1.747 + return Node(node, true);
1.748 + }
1.749 +
1.750 + /// \brief Gives back the out-node created from the \c node.
1.751 + ///
1.752 + /// Gives back the out-node created from the \c node.
1.753 + static Node outNode(const GraphNode& node) {
1.754 + return Node(node, false);
1.755 + }
1.756 +
1.757 + /// \brief Gives back the edge binds the two part of the node.
1.758 + ///
1.759 + /// Gives back the edge binds the two part of the node.
1.760 + static Edge edge(const GraphNode& node) {
1.761 + return Edge(node);
1.762 + }
1.763 +
1.764 + /// \brief Gives back the edge of the original edge.
1.765 + ///
1.766 + /// Gives back the edge of the original edge.
1.767 + static Edge edge(const GraphEdge& edge) {
1.768 + return Edge(edge);
1.769 + }
1.770 +
1.771 + typedef True NodeNumTag;
1.772 +
1.773 + int nodeNum() const {
1.774 + return 2 * countNodes(*Parent::graph);
1.775 + }
1.776 +
1.777 + typedef True EdgeNumTag;
1.778
1.779 -// int edgeNum() const {
1.780 -// return countEdges() + Parent::nodeNum();
1.781 -// }
1.782 + int edgeNum() const {
1.783 + return countEdges(*Parent::graph) + countNodes(*Parent::graph);
1.784 + }
1.785
1.786 -// Edge findEdge(const Node& source, const Node& target,
1.787 -// const Edge& prev = INVALID) const {
1.788 -// if (exitNode(source) && entryNode(target)) {
1.789 -// return Parent::findEdge(source, target, prev);
1.790 -// } else {
1.791 -// if (prev == INVALID && entryNode(source) && exitNode(target) &&
1.792 -// (typename Parent::Node&)source == (typename Parent::Node&)target) {
1.793 -// return Edge(INVALID, source);
1.794 -// } else {
1.795 -// return INVALID;
1.796 -// }
1.797 -// }
1.798 -// }
1.799 + typedef True FindEdgeTag;
1.800 +
1.801 + Edge findEdge(const Node& source, const Node& target,
1.802 + const Edge& prev = INVALID) const {
1.803 + if (inNode(source)) {
1.804 + if (outNode(target)) {
1.805 + if ((GraphNode&)source == (GraphNode&)target && prev == INVALID) {
1.806 + return Edge(source);
1.807 + }
1.808 + }
1.809 + } else {
1.810 + if (inNode(target)) {
1.811 + return Edge(findEdge(*Parent::graph, source, target, prev));
1.812 + }
1.813 + }
1.814 + return INVALID;
1.815 + }
1.816
1.817 -// template <typename T>
1.818 -// class NodeMap : public MapBase<Node, T> {
1.819 -// typedef typename Parent::template NodeMap<T> NodeImpl;
1.820 -// public:
1.821 -// NodeMap(const SplitGraphAdaptorBase& _graph)
1.822 -// : entry(_graph), exit(_graph) {}
1.823 -// NodeMap(const SplitGraphAdaptorBase& _graph, const T& t)
1.824 -// : entry(_graph, t), exit(_graph, t) {}
1.825 + template <typename T>
1.826 + class NodeMap : public MapBase<Node, T> {
1.827 + typedef typename Parent::template NodeMap<T> NodeImpl;
1.828 + public:
1.829 + NodeMap(const SplitGraphAdaptorBase& _graph)
1.830 + : inNodeMap(_graph), outNodeMap(_graph) {}
1.831 + NodeMap(const SplitGraphAdaptorBase& _graph, const T& t)
1.832 + : inNodeMap(_graph, t), outNodeMap(_graph, t) {}
1.833
1.834 -// void set(const Node& key, const T& val) {
1.835 -// if (key.entry) { entry.set(key, val); }
1.836 -// else {exit.set(key, val); }
1.837 -// }
1.838 + void set(const Node& key, const T& val) {
1.839 + if (SplitGraphAdaptorBase::inNode(key)) { inNodeMap.set(key, val); }
1.840 + else {outNodeMap.set(key, val); }
1.841 + }
1.842
1.843 -// typename MapTraits<NodeImpl>::ReturnValue
1.844 -// operator[](const Node& key) {
1.845 -// if (key.entry) { return entry[key]; }
1.846 -// else { return exit[key]; }
1.847 -// }
1.848 + typename MapTraits<NodeImpl>::ReturnValue
1.849 + operator[](const Node& key) {
1.850 + if (SplitGraphAdaptorBase::inNode(key)) { return inNodeMap[key]; }
1.851 + else { return outNodeMap[key]; }
1.852 + }
1.853
1.854 -// typename MapTraits<NodeImpl>::ConstReturnValue
1.855 -// operator[](const Node& key) const {
1.856 -// if (key.entry) { return entry[key]; }
1.857 -// else { return exit[key]; }
1.858 -// }
1.859 + typename MapTraits<NodeImpl>::ConstReturnValue
1.860 + operator[](const Node& key) const {
1.861 + if (SplitGraphAdaptorBase::inNode(key)) { return inNodeMap[key]; }
1.862 + else { return outNodeMap[key]; }
1.863 + }
1.864
1.865 -// private:
1.866 -// NodeImpl entry, exit;
1.867 -// };
1.868 + private:
1.869 + NodeImpl inNodeMap, outNodeMap;
1.870 + };
1.871
1.872 -// template <typename T>
1.873 -// class EdgeMap : public MapBase<Edge, T> {
1.874 -// typedef typename Parent::template NodeMap<T> NodeImpl;
1.875 -// typedef typename Parent::template EdgeMap<T> EdgeImpl;
1.876 -// public:
1.877 -// EdgeMap(const SplitGraphAdaptorBase& _graph)
1.878 -// : bind(_graph), orig(_graph) {}
1.879 -// EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t)
1.880 -// : bind(_graph, t), orig(_graph, t) {}
1.881 + template <typename T>
1.882 + class EdgeMap : public MapBase<Edge, T> {
1.883 + typedef typename Parent::template EdgeMap<T> EdgeMapImpl;
1.884 + typedef typename Parent::template NodeMap<T> NodeMapImpl;
1.885 + public:
1.886 +
1.887 + EdgeMap(const SplitGraphAdaptorBase& _graph)
1.888 + : edge_map(_graph), node_map(_graph) {}
1.889 + EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t)
1.890 + : edge_map(_graph, t), node_map(_graph, t) {}
1.891
1.892 -// void set(const Edge& key, const T& val) {
1.893 -// if ((typename Parent::Edge&)key != INVALID) { orig.set(key, val); }
1.894 -// else {bind.set(key.bind, val); }
1.895 -// }
1.896 + void set(const Edge& key, const T& val) {
1.897 + if (SplitGraphAdaptorBase::origEdge(key)) {
1.898 + edge_map.set(key.item.first(), val);
1.899 + } else {
1.900 + node_map.set(key.item.second(), val);
1.901 + }
1.902 + }
1.903
1.904 -// typename MapTraits<EdgeImpl>::ReturnValue
1.905 -// operator[](const Edge& key) {
1.906 -// if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
1.907 -// else {return bind[key.bind]; }
1.908 -// }
1.909 + typename MapTraits<EdgeMapImpl>::ReturnValue
1.910 + operator[](const Edge& key) {
1.911 + if (SplitGraphAdaptorBase::origEdge(key)) {
1.912 + return edge_map[key.item.first()];
1.913 + } else {
1.914 + return node_map[key.item.second()];
1.915 + }
1.916 + }
1.917
1.918 -// typename MapTraits<EdgeImpl>::ConstReturnValue
1.919 -// operator[](const Edge& key) const {
1.920 -// if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
1.921 -// else {return bind[key.bind]; }
1.922 -// }
1.923 + typename MapTraits<EdgeMapImpl>::ConstReturnValue
1.924 + operator[](const Edge& key) const {
1.925 + if (SplitGraphAdaptorBase::origEdge(key)) {
1.926 + return edge_map[key.item.first()];
1.927 + } else {
1.928 + return node_map[key.item.second()];
1.929 + }
1.930 + }
1.931
1.932 -// private:
1.933 -// typename Parent::template NodeMap<T> bind;
1.934 -// typename Parent::template EdgeMap<T> orig;
1.935 -// };
1.936 + private:
1.937 + typename Parent::template EdgeMap<T> edge_map;
1.938 + typename Parent::template NodeMap<T> node_map;
1.939 + };
1.940
1.941 -// template <typename EntryMap, typename ExitMap>
1.942 -// class CombinedNodeMap : public MapBase<Node, typename EntryMap::Value> {
1.943 -// public:
1.944 -// typedef MapBase<Node, typename EntryMap::Value> Parent;
1.945
1.946 -// typedef typename Parent::Key Key;
1.947 -// typedef typename Parent::Value Value;
1.948 + };
1.949
1.950 -// CombinedNodeMap(EntryMap& _entryMap, ExitMap& _exitMap)
1.951 -// : entryMap(_entryMap), exitMap(_exitMap) {}
1.952 + template <typename _Graph, typename NodeEnable = void,
1.953 + typename EdgeEnable = void>
1.954 + class AlterableSplitGraphAdaptor
1.955 + : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
1.956 + public:
1.957
1.958 -// Value& operator[](const Key& key) {
1.959 -// if (key.entry) {
1.960 -// return entryMap[key];
1.961 -// } else {
1.962 -// return exitMap[key];
1.963 -// }
1.964 -// }
1.965 + typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
1.966 + typedef _Graph Graph;
1.967
1.968 -// Value operator[](const Key& key) const {
1.969 -// if (key.entry) {
1.970 -// return entryMap[key];
1.971 -// } else {
1.972 -// return exitMap[key];
1.973 -// }
1.974 -// }
1.975 + typedef typename Graph::Node GraphNode;
1.976 + typedef typename Graph::Node GraphEdge;
1.977
1.978 -// void set(const Key& key, const Value& value) {
1.979 -// if (key.entry) {
1.980 -// entryMap.set(key, value);
1.981 -// } else {
1.982 -// exitMap.set(key, value);
1.983 -// }
1.984 -// }
1.985 + protected:
1.986 +
1.987 + AlterableSplitGraphAdaptor() : Parent() {}
1.988 +
1.989 + public:
1.990 +
1.991 + typedef InvalidType NodeNotifier;
1.992 + typedef InvalidType EdgeNotifier;
1.993 +
1.994 + };
1.995 +
1.996 + template <typename _Graph, typename EdgeEnable>
1.997 + class AlterableSplitGraphAdaptor<
1.998 + _Graph,
1.999 + typename enable_if<typename _Graph::NodeNotifier::Notifier>::type,
1.1000 + EdgeEnable>
1.1001 + : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
1.1002 + public:
1.1003 +
1.1004 + typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
1.1005 + typedef _Graph Graph;
1.1006 +
1.1007 + typedef typename Graph::Node GraphNode;
1.1008 + typedef typename Graph::Edge GraphEdge;
1.1009 +
1.1010 + typedef typename Parent::Node Node;
1.1011 + typedef typename Parent::Edge Edge;
1.1012 +
1.1013 + protected:
1.1014 +
1.1015 + AlterableSplitGraphAdaptor()
1.1016 + : Parent(), node_notifier(*this), node_notifier_proxy(*this) {}
1.1017 +
1.1018 + void setGraph(_Graph& graph) {
1.1019 + Parent::setGraph(graph);
1.1020 + node_notifier_proxy.setNotifier(graph.getNotifier(GraphNode()));
1.1021 + }
1.1022 +
1.1023 + public:
1.1024 +
1.1025 + ~AlterableSplitGraphAdaptor() {
1.1026 + node_notifier.clear();
1.1027 + }
1.1028 +
1.1029 + typedef AlterationNotifier<AlterableSplitGraphAdaptor, Node> NodeNotifier;
1.1030 + typedef InvalidType EdgeNotifier;
1.1031 +
1.1032 + NodeNotifier& getNotifier(Node) const { return node_notifier; }
1.1033 +
1.1034 + protected:
1.1035 +
1.1036 + class NodeNotifierProxy : public Graph::NodeNotifier::ObserverBase {
1.1037 + public:
1.1038 +
1.1039 + typedef typename Graph::NodeNotifier::ObserverBase Parent;
1.1040 + typedef AlterableSplitGraphAdaptor AdaptorBase;
1.1041
1.1042 -// private:
1.1043 + NodeNotifierProxy(const AdaptorBase& _adaptor)
1.1044 + : Parent(), adaptor(&_adaptor) {
1.1045 + }
1.1046 +
1.1047 + virtual ~NodeNotifierProxy() {
1.1048 + if (Parent::attached()) {
1.1049 + Parent::detach();
1.1050 + }
1.1051 + }
1.1052 +
1.1053 + void setNotifier(typename Graph::NodeNotifier& graph_notifier) {
1.1054 + Parent::attach(graph_notifier);
1.1055 + }
1.1056 +
1.1057
1.1058 -// EntryMap& entryMap;
1.1059 -// ExitMap& exitMap;
1.1060 + protected:
1.1061 +
1.1062 + virtual void add(const GraphNode& gn) {
1.1063 + std::vector<Node> nodes;
1.1064 + nodes.push_back(AdaptorBase::Parent::inNode(gn));
1.1065 + nodes.push_back(AdaptorBase::Parent::outNode(gn));
1.1066 + adaptor->getNotifier(Node()).add(nodes);
1.1067 + }
1.1068 +
1.1069 + virtual void add(const std::vector<GraphNode>& gn) {
1.1070 + std::vector<Node> nodes;
1.1071 + for (int i = 0; i < (int)gn.size(); ++i) {
1.1072 + nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
1.1073 + nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
1.1074 + }
1.1075 + adaptor->getNotifier(Node()).add(nodes);
1.1076 + }
1.1077 +
1.1078 + virtual void erase(const GraphNode& gn) {
1.1079 + std::vector<Node> nodes;
1.1080 + nodes.push_back(AdaptorBase::Parent::inNode(gn));
1.1081 + nodes.push_back(AdaptorBase::Parent::outNode(gn));
1.1082 + adaptor->getNotifier(Node()).erase(nodes);
1.1083 + }
1.1084 +
1.1085 + virtual void erase(const std::vector<GraphNode>& gn) {
1.1086 + std::vector<Node> nodes;
1.1087 + for (int i = 0; i < (int)gn.size(); ++i) {
1.1088 + nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
1.1089 + nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
1.1090 + }
1.1091 + adaptor->getNotifier(Node()).erase(nodes);
1.1092 + }
1.1093 + virtual void build() {
1.1094 + adaptor->getNotifier(Node()).build();
1.1095 + }
1.1096 + virtual void clear() {
1.1097 + adaptor->getNotifier(Node()).clear();
1.1098 + }
1.1099 +
1.1100 + const AdaptorBase* adaptor;
1.1101 + };
1.1102 +
1.1103 +
1.1104 + mutable NodeNotifier node_notifier;
1.1105 +
1.1106 + NodeNotifierProxy node_notifier_proxy;
1.1107 +
1.1108 + };
1.1109 +
1.1110 + template <typename _Graph>
1.1111 + class AlterableSplitGraphAdaptor<
1.1112 + _Graph,
1.1113 + typename enable_if<typename _Graph::NodeNotifier::Notifier>::type,
1.1114 + typename enable_if<typename _Graph::EdgeNotifier::Notifier>::type>
1.1115 + : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
1.1116 + public:
1.1117 +
1.1118 + typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
1.1119 + typedef _Graph Graph;
1.1120 +
1.1121 + typedef typename Graph::Node GraphNode;
1.1122 + typedef typename Graph::Edge GraphEdge;
1.1123 +
1.1124 + typedef typename Parent::Node Node;
1.1125 + typedef typename Parent::Edge Edge;
1.1126 +
1.1127 + protected:
1.1128 +
1.1129 + AlterableSplitGraphAdaptor()
1.1130 + : Parent(), node_notifier(*this), edge_notifier(*this),
1.1131 + node_notifier_proxy(*this), edge_notifier_proxy(*this) {}
1.1132 +
1.1133 + void setGraph(_Graph& graph) {
1.1134 + Parent::setGraph(graph);
1.1135 + node_notifier_proxy.setNotifier(graph.getNotifier(GraphNode()));
1.1136 + edge_notifier_proxy.setNotifier(graph.getNotifier(GraphEdge()));
1.1137 + }
1.1138 +
1.1139 + public:
1.1140 +
1.1141 + ~AlterableSplitGraphAdaptor() {
1.1142 + node_notifier.clear();
1.1143 + edge_notifier.clear();
1.1144 + }
1.1145 +
1.1146 + typedef AlterationNotifier<AlterableSplitGraphAdaptor, Node> NodeNotifier;
1.1147 + typedef AlterationNotifier<AlterableSplitGraphAdaptor, Edge> EdgeNotifier;
1.1148 +
1.1149 + NodeNotifier& getNotifier(Node) const { return node_notifier; }
1.1150 + EdgeNotifier& getNotifier(Edge) const { return edge_notifier; }
1.1151 +
1.1152 + protected:
1.1153 +
1.1154 + class NodeNotifierProxy : public Graph::NodeNotifier::ObserverBase {
1.1155 + public:
1.1156
1.1157 -// };
1.1158 + typedef typename Graph::NodeNotifier::ObserverBase Parent;
1.1159 + typedef AlterableSplitGraphAdaptor AdaptorBase;
1.1160 +
1.1161 + NodeNotifierProxy(const AdaptorBase& _adaptor)
1.1162 + : Parent(), adaptor(&_adaptor) {
1.1163 + }
1.1164
1.1165 -// template <typename EdgeMap, typename NodeMap>
1.1166 -// class CombinedEdgeMap : public MapBase<Edge, typename EdgeMap::Value> {
1.1167 -// public:
1.1168 -// typedef MapBase<Edge, typename EdgeMap::Value> Parent;
1.1169 + virtual ~NodeNotifierProxy() {
1.1170 + if (Parent::attached()) {
1.1171 + Parent::detach();
1.1172 + }
1.1173 + }
1.1174
1.1175 -// typedef typename Parent::Key Key;
1.1176 -// typedef typename Parent::Value Value;
1.1177 + void setNotifier(typename Graph::NodeNotifier& graph_notifier) {
1.1178 + Parent::attach(graph_notifier);
1.1179 + }
1.1180
1.1181 -// CombinedEdgeMap(EdgeMap& _edgeMap, NodeMap& _nodeMap)
1.1182 -// : edgeMap(_edgeMap), nodeMap(_nodeMap) {}
1.1183 +
1.1184 + protected:
1.1185
1.1186 -// void set(const Edge& edge, const Value& val) {
1.1187 -// if (SplitGraphAdaptorBase::originalEdge(edge)) {
1.1188 -// edgeMap.set(edge, val);
1.1189 -// } else {
1.1190 -// nodeMap.set(SplitGraphAdaptorBase::bindedNode(edge), val);
1.1191 -// }
1.1192 -// }
1.1193 + virtual void add(const GraphNode& gn) {
1.1194 + std::vector<Node> nodes;
1.1195 + nodes.push_back(AdaptorBase::Parent::inNode(gn));
1.1196 + nodes.push_back(AdaptorBase::Parent::outNode(gn));
1.1197 + adaptor->getNotifier(Node()).add(nodes);
1.1198 + adaptor->getNotifier(Edge()).add(AdaptorBase::Parent::edge(gn));
1.1199 + }
1.1200 + virtual void add(const std::vector<GraphNode>& gn) {
1.1201 + std::vector<Node> nodes;
1.1202 + std::vector<Edge> edges;
1.1203 + for (int i = 0; i < (int)gn.size(); ++i) {
1.1204 + edges.push_back(AdaptorBase::Parent::edge(gn[i]));
1.1205 + nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
1.1206 + nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
1.1207 + }
1.1208 + adaptor->getNotifier(Node()).add(nodes);
1.1209 + adaptor->getNotifier(Edge()).add(edges);
1.1210 + }
1.1211 + virtual void erase(const GraphNode& gn) {
1.1212 + adaptor->getNotifier(Edge()).erase(AdaptorBase::Parent::edge(gn));
1.1213 + std::vector<Node> nodes;
1.1214 + nodes.push_back(AdaptorBase::Parent::inNode(gn));
1.1215 + nodes.push_back(AdaptorBase::Parent::outNode(gn));
1.1216 + adaptor->getNotifier(Node()).erase(nodes);
1.1217 + }
1.1218 + virtual void erase(const std::vector<GraphNode>& gn) {
1.1219 + std::vector<Node> nodes;
1.1220 + std::vector<Edge> edges;
1.1221 + for (int i = 0; i < (int)gn.size(); ++i) {
1.1222 + edges.push_back(AdaptorBase::Parent::edge(gn[i]));
1.1223 + nodes.push_back(AdaptorBase::Parent::inNode(gn[i]));
1.1224 + nodes.push_back(AdaptorBase::Parent::outNode(gn[i]));
1.1225 + }
1.1226 + adaptor->getNotifier(Edge()).erase(edges);
1.1227 + adaptor->getNotifier(Node()).erase(nodes);
1.1228 + }
1.1229 + virtual void build() {
1.1230 + std::vector<Edge> edges;
1.1231 + const typename Parent::Notifier* notifier = Parent::getNotifier();
1.1232 + GraphNode it;
1.1233 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
1.1234 + edges.push_back(AdaptorBase::Parent::edge(it));
1.1235 + }
1.1236 + adaptor->getNotifier(Node()).build();
1.1237 + adaptor->getNotifier(Edge()).add(edges);
1.1238 + }
1.1239 + virtual void clear() {
1.1240 + std::vector<Edge> edges;
1.1241 + const typename Parent::Notifier* notifier = Parent::getNotifier();
1.1242 + GraphNode it;
1.1243 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
1.1244 + edges.push_back(AdaptorBase::Parent::edge(it));
1.1245 + }
1.1246 + adaptor->getNotifier(Edge()).erase(edges);
1.1247 + adaptor->getNotifier(Node()).clear();
1.1248 + }
1.1249
1.1250 -// Value operator[](const Key& edge) const {
1.1251 -// if (SplitGraphAdaptorBase::originalEdge(edge)) {
1.1252 -// return edgeMap[edge];
1.1253 -// } else {
1.1254 -// return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
1.1255 -// }
1.1256 -// }
1.1257 + const AdaptorBase* adaptor;
1.1258 + };
1.1259
1.1260 -// Value& operator[](const Key& edge) {
1.1261 -// if (SplitGraphAdaptorBase::originalEdge(edge)) {
1.1262 -// return edgeMap[edge];
1.1263 -// } else {
1.1264 -// return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
1.1265 -// }
1.1266 -// }
1.1267 + class EdgeNotifierProxy : public Graph::EdgeNotifier::ObserverBase {
1.1268 + public:
1.1269 +
1.1270 + typedef typename Graph::EdgeNotifier::ObserverBase Parent;
1.1271 + typedef AlterableSplitGraphAdaptor AdaptorBase;
1.1272
1.1273 -// private:
1.1274 -// EdgeMap& edgeMap;
1.1275 -// NodeMap& nodeMap;
1.1276 -// };
1.1277 + EdgeNotifierProxy(const AdaptorBase& _adaptor)
1.1278 + : Parent(), adaptor(&_adaptor) {
1.1279 + }
1.1280
1.1281 -// };
1.1282 + virtual ~EdgeNotifierProxy() {
1.1283 + if (Parent::attached()) {
1.1284 + Parent::detach();
1.1285 + }
1.1286 + }
1.1287
1.1288 -// template <typename _Graph>
1.1289 -// class SplitGraphAdaptor
1.1290 -// : public GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > {
1.1291 -// public:
1.1292 -// typedef GraphAdaptorExtender<SplitGraphAdaptorBase<_Graph> > Parent;
1.1293 + void setNotifier(typename Graph::EdgeNotifier& graph_notifier) {
1.1294 + Parent::attach(graph_notifier);
1.1295 + }
1.1296
1.1297 -// SplitGraphAdaptor(_Graph& graph) {
1.1298 -// Parent::setGraph(graph);
1.1299 -// }
1.1300 +
1.1301 + protected:
1.1302
1.1303 + virtual void add(const GraphEdge& ge) {
1.1304 + adaptor->getNotifier(Edge()).add(AdaptorBase::edge(ge));
1.1305 + }
1.1306 + virtual void add(const std::vector<GraphEdge>& ge) {
1.1307 + std::vector<Edge> edges;
1.1308 + for (int i = 0; i < (int)ge.size(); ++i) {
1.1309 + edges.push_back(AdaptorBase::edge(ge[i]));
1.1310 + }
1.1311 + adaptor->getNotifier(Edge()).add(edges);
1.1312 + }
1.1313 + virtual void erase(const GraphEdge& ge) {
1.1314 + adaptor->getNotifier(Edge()).erase(AdaptorBase::edge(ge));
1.1315 + }
1.1316 + virtual void erase(const std::vector<GraphEdge>& ge) {
1.1317 + std::vector<Edge> edges;
1.1318 + for (int i = 0; i < (int)ge.size(); ++i) {
1.1319 + edges.push_back(AdaptorBase::edge(ge[i]));
1.1320 + }
1.1321 + adaptor->getNotifier(Edge()).erase(edges);
1.1322 + }
1.1323 + virtual void build() {
1.1324 + std::vector<Edge> edges;
1.1325 + const typename Parent::Notifier* notifier = Parent::getNotifier();
1.1326 + GraphEdge it;
1.1327 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
1.1328 + edges.push_back(AdaptorBase::Parent::edge(it));
1.1329 + }
1.1330 + adaptor->getNotifier(Edge()).add(edges);
1.1331 + }
1.1332 + virtual void clear() {
1.1333 + std::vector<Edge> edges;
1.1334 + const typename Parent::Notifier* notifier = Parent::getNotifier();
1.1335 + GraphEdge it;
1.1336 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
1.1337 + edges.push_back(AdaptorBase::Parent::edge(it));
1.1338 + }
1.1339 + adaptor->getNotifier(Edge()).erase(edges);
1.1340 + }
1.1341
1.1342 -// };
1.1343 + const AdaptorBase* adaptor;
1.1344 + };
1.1345 +
1.1346 +
1.1347 + mutable NodeNotifier node_notifier;
1.1348 + mutable EdgeNotifier edge_notifier;
1.1349 +
1.1350 + NodeNotifierProxy node_notifier_proxy;
1.1351 + EdgeNotifierProxy edge_notifier_proxy;
1.1352 +
1.1353 + };
1.1354 +
1.1355 + /// \ingroup graph_adaptors
1.1356 + ///
1.1357 + /// \brief SplitGraphAdaptor class
1.1358 + ///
1.1359 + /// This is an graph adaptor which splits all node into an in-node
1.1360 + /// and an out-node. Formaly, the adaptor replaces each \f$ u \f$
1.1361 + /// node in the graph with two node, \f$ u_{in} \f$ node and
1.1362 + /// \f$ u_{out} \f$ node. If there is an \f$ (v, u) \f$ edge in the
1.1363 + /// original graph the new target of the edge will be \f$ u_{in} \f$ and
1.1364 + /// similarly the source of the original \f$ (u, v) \f$ edge will be
1.1365 + /// \f$ u_{out} \f$. The adaptor will add for each node in the
1.1366 + /// original graph an additional edge which will connect
1.1367 + /// \f$ (u_{in}, u_{out}) \f$.
1.1368 + ///
1.1369 + /// The aim of this class is to run algorithm with node costs if the
1.1370 + /// algorithm can use directly just edge costs. In this case we should use
1.1371 + /// a \c SplitGraphAdaptor and set the node cost of the graph to the
1.1372 + /// bind edge in the adapted graph.
1.1373 + ///
1.1374 + /// By example a maximum flow algoritm can compute how many edge
1.1375 + /// disjoint paths are in the graph. But we would like to know how
1.1376 + /// many node disjoint paths are in the graph. First we have to
1.1377 + /// adapt the graph with the \c SplitGraphAdaptor. Then run the flow
1.1378 + /// algorithm on the adapted graph. The bottleneck of the flow will
1.1379 + /// be the bind edges which bounds the flow with the count of the
1.1380 + /// node disjoint paths.
1.1381 + ///
1.1382 + ///\code
1.1383 + ///
1.1384 + /// typedef SplitGraphAdaptor<SmartGraph> SGraph;
1.1385 + ///
1.1386 + /// SGraph sgraph(graph);
1.1387 + ///
1.1388 + /// typedef ConstMap<SGraph::Edge, int> SCapacity;
1.1389 + /// SCapacity scapacity(1);
1.1390 + ///
1.1391 + /// SGraph::EdgeMap<int> sflow(sgraph);
1.1392 + ///
1.1393 + /// Preflow<SGraph, int, SCapacity>
1.1394 + /// spreflow(sgraph, SGraph::outNode(source),SGraph::inNode(target),
1.1395 + /// scapacity, sflow);
1.1396 + ///
1.1397 + /// spreflow.run();
1.1398 + ///
1.1399 + ///\endcode
1.1400 + ///
1.1401 + /// The result of the mamixum flow on the original graph
1.1402 + /// shows the next figure:
1.1403 + ///
1.1404 + /// \image html edge_disjoint.png
1.1405 + /// \image latex edge_disjoint.eps "Edge disjoint paths" width=\textwidth
1.1406 + ///
1.1407 + /// And the maximum flow on the adapted graph:
1.1408 + ///
1.1409 + /// \image html node_disjoint.png
1.1410 + /// \image latex node_disjoint.eps "Node disjoint paths" width=\textwidth
1.1411 + ///
1.1412 + /// The second solution contains just 3 disjoint paths while the first 4.
1.1413 + ///
1.1414 + /// This graph adaptor is fully conform to the
1.1415 + /// \ref concept::StaticGraph "StaticGraph" concept and
1.1416 + /// contains some additional member functions and types. The
1.1417 + /// documentation of some member functions may be found just in the
1.1418 + /// SplitGraphAdaptorBase class.
1.1419 + ///
1.1420 + /// \sa SplitGraphAdaptorBase
1.1421 + template <typename _Graph>
1.1422 + class SplitGraphAdaptor : public AlterableSplitGraphAdaptor<_Graph> {
1.1423 + public:
1.1424 + typedef AlterableSplitGraphAdaptor<_Graph> Parent;
1.1425 +
1.1426 + typedef typename Parent::Node Node;
1.1427 + typedef typename Parent::Edge Edge;
1.1428 +
1.1429 + /// \brief Constructor of the adaptor.
1.1430 + ///
1.1431 + /// Constructor of the adaptor.
1.1432 + SplitGraphAdaptor(_Graph& graph) {
1.1433 + Parent::setGraph(graph);
1.1434 + }
1.1435 +
1.1436 + /// \brief NodeMap combined from two original NodeMap
1.1437 + ///
1.1438 + /// This class adapt two of the original graph NodeMap to
1.1439 + /// get a node map on the adapted graph.
1.1440 + template <typename InNodeMap, typename OutNodeMap>
1.1441 + class CombinedNodeMap {
1.1442 + public:
1.1443 +
1.1444 + typedef Node Key;
1.1445 + typedef typename InNodeMap::Value Value;
1.1446 +
1.1447 + /// \brief Constructor
1.1448 + ///
1.1449 + /// Constructor.
1.1450 + CombinedNodeMap(InNodeMap& _inNodeMap, OutNodeMap& _outNodeMap)
1.1451 + : inNodeMap(_inNodeMap), outNodeMap(_outNodeMap) {}
1.1452 +
1.1453 + /// \brief The subscript operator.
1.1454 + ///
1.1455 + /// The subscript operator.
1.1456 + Value& operator[](const Key& key) {
1.1457 + if (Parent::inNode(key)) {
1.1458 + return inNodeMap[key];
1.1459 + } else {
1.1460 + return outNodeMap[key];
1.1461 + }
1.1462 + }
1.1463 +
1.1464 + /// \brief The const subscript operator.
1.1465 + ///
1.1466 + /// The const subscript operator.
1.1467 + Value operator[](const Key& key) const {
1.1468 + if (Parent::inNode(key)) {
1.1469 + return inNodeMap[key];
1.1470 + } else {
1.1471 + return outNodeMap[key];
1.1472 + }
1.1473 + }
1.1474 +
1.1475 + /// \brief The setter function of the map.
1.1476 + ///
1.1477 + /// The setter function of the map.
1.1478 + void set(const Key& key, const Value& value) {
1.1479 + if (Parent::inNode(key)) {
1.1480 + inNodeMap.set(key, value);
1.1481 + } else {
1.1482 + outNodeMap.set(key, value);
1.1483 + }
1.1484 + }
1.1485 +
1.1486 + private:
1.1487 +
1.1488 + InNodeMap& inNodeMap;
1.1489 + OutNodeMap& outNodeMap;
1.1490 +
1.1491 + };
1.1492 +
1.1493 +
1.1494 + /// \brief Just gives back a combined node map.
1.1495 + ///
1.1496 + /// Just gives back a combined node map.
1.1497 + template <typename InNodeMap, typename OutNodeMap>
1.1498 + static CombinedNodeMap<InNodeMap, OutNodeMap>
1.1499 + combinedNodeMap(InNodeMap& in_map, OutNodeMap& out_map) {
1.1500 + return CombinedNodeMap<InNodeMap, OutNodeMap>(in_map, out_map);
1.1501 + }
1.1502 +
1.1503 + template <typename InNodeMap, typename OutNodeMap>
1.1504 + static CombinedNodeMap<const InNodeMap, OutNodeMap>
1.1505 + combinedNodeMap(const InNodeMap& in_map, OutNodeMap& out_map) {
1.1506 + return CombinedNodeMap<const InNodeMap, OutNodeMap>(in_map, out_map);
1.1507 + }
1.1508 +
1.1509 + template <typename InNodeMap, typename OutNodeMap>
1.1510 + static CombinedNodeMap<InNodeMap, const OutNodeMap>
1.1511 + combinedNodeMap(InNodeMap& in_map, const OutNodeMap& out_map) {
1.1512 + return CombinedNodeMap<InNodeMap, const OutNodeMap>(in_map, out_map);
1.1513 + }
1.1514 +
1.1515 + template <typename InNodeMap, typename OutNodeMap>
1.1516 + static CombinedNodeMap<const InNodeMap, const OutNodeMap>
1.1517 + combinedNodeMap(const InNodeMap& in_map, const OutNodeMap& out_map) {
1.1518 + return CombinedNodeMap<const InNodeMap,
1.1519 + const OutNodeMap>(in_map, out_map);
1.1520 + }
1.1521 +
1.1522 + /// \brief EdgeMap combined from an original EdgeMap and NodeMap
1.1523 + ///
1.1524 + /// This class adapt an original graph EdgeMap and NodeMap to
1.1525 + /// get an edge map on the adapted graph.
1.1526 + template <typename GraphEdgeMap, typename GraphNodeMap>
1.1527 + class CombinedEdgeMap
1.1528 + : public MapBase<Edge, typename GraphEdgeMap::Value> {
1.1529 + public:
1.1530 + typedef MapBase<Edge, typename GraphEdgeMap::Value> Parent;
1.1531 +
1.1532 + typedef typename Parent::Key Key;
1.1533 + typedef typename Parent::Value Value;
1.1534 +
1.1535 + /// \brief Constructor
1.1536 + ///
1.1537 + /// Constructor.
1.1538 + CombinedEdgeMap(GraphEdgeMap& _edge_map, GraphNodeMap& _node_map)
1.1539 + : edge_map(_edge_map), node_map(_node_map) {}
1.1540 +
1.1541 + /// \brief The subscript operator.
1.1542 + ///
1.1543 + /// The subscript operator.
1.1544 + void set(const Edge& edge, const Value& val) {
1.1545 + if (Parent::origEdge(edge)) {
1.1546 + edge_map.set(edge, val);
1.1547 + } else {
1.1548 + node_map.set(edge, val);
1.1549 + }
1.1550 + }
1.1551 +
1.1552 + /// \brief The const subscript operator.
1.1553 + ///
1.1554 + /// The const subscript operator.
1.1555 + Value operator[](const Key& edge) const {
1.1556 + if (Parent::origEdge(edge)) {
1.1557 + return edge_map[edge];
1.1558 + } else {
1.1559 + return node_map[edge];
1.1560 + }
1.1561 + }
1.1562 +
1.1563 + /// \brief The const subscript operator.
1.1564 + ///
1.1565 + /// The const subscript operator.
1.1566 + Value& operator[](const Key& edge) {
1.1567 + if (Parent::origEdge(edge)) {
1.1568 + return edge_map[edge];
1.1569 + } else {
1.1570 + return node_map[edge];
1.1571 + }
1.1572 + }
1.1573 +
1.1574 + private:
1.1575 + GraphEdgeMap& edge_map;
1.1576 + GraphNodeMap& node_map;
1.1577 + };
1.1578 +
1.1579 + /// \brief Just gives back a combined edge map.
1.1580 + ///
1.1581 + /// Just gives back a combined edge map.
1.1582 + template <typename GraphEdgeMap, typename GraphNodeMap>
1.1583 + static CombinedEdgeMap<GraphEdgeMap, GraphNodeMap>
1.1584 + combinedEdgeMap(GraphEdgeMap& edge_map, GraphNodeMap& node_map) {
1.1585 + return CombinedEdgeMap<GraphEdgeMap, GraphNodeMap>(edge_map, node_map);
1.1586 + }
1.1587 +
1.1588 + template <typename GraphEdgeMap, typename GraphNodeMap>
1.1589 + static CombinedEdgeMap<const GraphEdgeMap, GraphNodeMap>
1.1590 + combinedEdgeMap(const GraphEdgeMap& edge_map, GraphNodeMap& node_map) {
1.1591 + return CombinedEdgeMap<const GraphEdgeMap,
1.1592 + GraphNodeMap>(edge_map, node_map);
1.1593 + }
1.1594 +
1.1595 + template <typename GraphEdgeMap, typename GraphNodeMap>
1.1596 + static CombinedEdgeMap<GraphEdgeMap, const GraphNodeMap>
1.1597 + combinedEdgeMap(GraphEdgeMap& edge_map, const GraphNodeMap& node_map) {
1.1598 + return CombinedEdgeMap<GraphEdgeMap,
1.1599 + const GraphNodeMap>(edge_map, node_map);
1.1600 + }
1.1601 +
1.1602 + template <typename GraphEdgeMap, typename GraphNodeMap>
1.1603 + static CombinedEdgeMap<const GraphEdgeMap, const GraphNodeMap>
1.1604 + combinedEdgeMap(const GraphEdgeMap& edge_map,
1.1605 + const GraphNodeMap& node_map) {
1.1606 + return CombinedEdgeMap<const GraphEdgeMap,
1.1607 + const GraphNodeMap>(edge_map, node_map);
1.1608 + }
1.1609 +
1.1610 + };
1.1611 +
1.1612
1.1613 } //namespace lemon
1.1614