1.1 --- a/lemon/graph_adaptor.h Mon Oct 03 10:16:45 2005 +0000
1.2 +++ b/lemon/graph_adaptor.h Mon Oct 03 10:17:53 2005 +0000
1.3 @@ -65,8 +65,6 @@
1.4 class GraphAdaptorBase {
1.5 public:
1.6 typedef _Graph Graph;
1.7 - /// \todo Is it needed?
1.8 - typedef Graph BaseGraph;
1.9 typedef Graph ParentGraph;
1.10
1.11 protected:
1.12 @@ -93,12 +91,25 @@
1.13 Node source(const Edge& e) const { return graph->source(e); }
1.14 Node target(const Edge& e) const { return graph->target(e); }
1.15
1.16 + typedef NodeNumTagIndicator<Graph> NodeNumTag;
1.17 int nodeNum() const { return graph->nodeNum(); }
1.18 +
1.19 + typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
1.20 int edgeNum() const { return graph->edgeNum(); }
1.21 +
1.22 + typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
1.23 + Edge findEdge(const Node& source, const Node& target,
1.24 + const Edge& prev = INVALID) {
1.25 + return graph->findEdge(source, target, prev);
1.26 + }
1.27
1.28 - Node addNode() const { return Node(graph->addNode()); }
1.29 + Node addNode() const {
1.30 + return Node(graph->addNode());
1.31 + }
1.32 +
1.33 Edge addEdge(const Node& source, const Node& target) const {
1.34 - return Edge(graph->addEdge(source, target)); }
1.35 + return Edge(graph->addEdge(source, target));
1.36 + }
1.37
1.38 void erase(const Node& i) const { graph->erase(i); }
1.39 void erase(const Edge& i) const { graph->erase(i); }
1.40 @@ -156,11 +167,9 @@
1.41 typedef typename Parent::Node Node;
1.42 typedef typename Parent::Edge Edge;
1.43
1.44 - // using Parent::first;
1.45 void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
1.46 void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
1.47
1.48 - // using Parent::next;
1.49 void nextIn(Edge& i) const { Parent::nextOut(i); }
1.50 void nextOut(Edge& i) const { Parent::nextIn(i); }
1.51
1.52 @@ -304,25 +313,8 @@
1.53 /// Returns true if \c n is hidden.
1.54 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
1.55
1.56 - /// \warning This is a linear time operation and works only if s
1.57 - /// \c Graph::NodeIt is defined.
1.58 - /// \todo assign tags.
1.59 - int nodeNum() const {
1.60 - int i=0;
1.61 - Node n;
1.62 - for (first(n); n!=INVALID; next(n)) ++i;
1.63 - return i;
1.64 - }
1.65 -
1.66 - /// \warning This is a linear time operation and works only if
1.67 - /// \c Graph::EdgeIt is defined.
1.68 - /// \todo assign tags.
1.69 - int edgeNum() const {
1.70 - int i=0;
1.71 - Edge e;
1.72 - for (first(e); e!=INVALID; next(e)) ++i;
1.73 - return i;
1.74 - }
1.75 + typedef False NodeNumTag;
1.76 + typedef False EdgeNumTag;
1.77 };
1.78
1.79 template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
1.80 @@ -413,25 +405,8 @@
1.81 /// Returns true if \c n is hidden.
1.82 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
1.83
1.84 - /// \warning This is a linear time operation and works only if s
1.85 - /// \c Graph::NodeIt is defined.
1.86 - /// \todo assign tags.
1.87 - int nodeNum() const {
1.88 - int i=0;
1.89 - Node n;
1.90 - for (first(n); n!=INVALID; next(n)) ++i;
1.91 - return i;
1.92 - }
1.93 -
1.94 - /// \warning This is a linear time operation and works only if
1.95 - /// \c Graph::EdgeIt is defined.
1.96 - /// \todo assign tags.
1.97 - int edgeNum() const {
1.98 - int i=0;
1.99 - Edge e;
1.100 - for (first(e); e!=INVALID; next(e)) ++i;
1.101 - return i;
1.102 - }
1.103 + typedef False NodeNumTag;
1.104 + typedef False EdgeNumTag;
1.105 };
1.106
1.107 /*! \brief A graph adaptor for hiding nodes and edges from a graph.
1.108 @@ -440,7 +415,8 @@
1.109 parts of the lib. Use them at you own risk.
1.110
1.111 SubGraphAdaptor shows the graph with filtered node-set and
1.112 - edge-set.
1.113 + edge-set. If the \c checked parameter is true then it filters the edgeset
1.114 + to do not get invalid edges without source or target.
1.115 Let \f$G=(V, A)\f$ be a directed graph
1.116 and suppose that the graph instance \c g of type ListGraph implements
1.117 \f$G\f$.
1.118 @@ -453,10 +429,11 @@
1.119 SubGraphAdaptor<...>::OutEdgeIt and SubGraphAdaptor<...>::InEdgeIt iterates
1.120 only on edges leaving and entering a specific node which have true value.
1.121
1.122 - We have to note that this does not mean that an
1.123 - induced subgraph is obtained, the node-iterator cares only the filter
1.124 - on the node-set, and the edge-iterators care only the filter on the
1.125 - edge-set.
1.126 + If the \c checked template parameter is false then we have to note that
1.127 + the node-iterator cares only the filter on the node-set, and the
1.128 + edge-iterator cares only the filter on the edge-set. This way the edge-map
1.129 + should filter all edges which's source or target is filtered by the
1.130 + node-filter.
1.131 \code
1.132 typedef ListGraph Graph;
1.133 Graph g;
1.134 @@ -519,8 +496,9 @@
1.135
1.136 An adaptor for hiding nodes from a graph.
1.137 This adaptor specializes SubGraphAdaptor in the way that only the node-set
1.138 - can be filtered. Note that this does not mean of considering induced
1.139 - subgraph, the edge-iterators consider the original edge-set.
1.140 + can be filtered. In usual case the checked parameter is true, we get the
1.141 + induced subgraph. But if the checked parameter is false then we can only
1.142 + filter only isolated nodes.
1.143 \author Marton Makai
1.144 */
1.145 template<typename Graph, typename NodeFilterMap, bool checked = true>
1.146 @@ -703,9 +681,6 @@
1.147 typedef typename Parent::UndirEdge UndirEdge;
1.148 typedef typename Parent::Edge Edge;
1.149
1.150 - /// \bug Why cant an edge say that it is forward or not???
1.151 - /// By this, a pointer to the graph have to be stored
1.152 - /// The implementation
1.153 template <typename T>
1.154 class EdgeMap {
1.155 protected:
1.156 @@ -1122,7 +1097,6 @@
1.157 int edgeNum() const {
1.158 return 2*this->graph->edgeNum();
1.159 }
1.160 - // KEEP_MAPS(Parent, BidirGraphAdaptor);
1.161 };
1.162
1.163
1.164 @@ -1331,6 +1305,371 @@
1.165 };
1.166
1.167 template <typename _Graph>
1.168 + class SplitGraphAdaptorBase
1.169 + : public GraphAdaptorBase<_Graph> {
1.170 + public:
1.171 + typedef GraphAdaptorBase<_Graph> Parent;
1.172 +
1.173 + class Node;
1.174 + class Edge;
1.175 + template <typename T> class NodeMap;
1.176 + template <typename T> class EdgeMap;
1.177 +
1.178 +
1.179 + class Node : public Parent::Node {
1.180 + friend class SplitGraphAdaptorBase;
1.181 + template <typename T> friend class NodeMap;
1.182 + typedef typename Parent::Node NodeParent;
1.183 + private:
1.184 +
1.185 + bool entry;
1.186 + Node(typename Parent::Node _node, bool _entry)
1.187 + : Parent::Node(_node), entry(_entry) {}
1.188 +
1.189 + public:
1.190 + Node() {}
1.191 + Node(Invalid) : NodeParent(INVALID), entry(true) {}
1.192 +
1.193 + bool operator==(const Node& node) const {
1.194 + return NodeParent::operator==(node) && entry == node.entry;
1.195 + }
1.196 +
1.197 + bool operator!=(const Node& node) const {
1.198 + return !(*this == node);
1.199 + }
1.200 +
1.201 + bool operator<(const Node& node) const {
1.202 + return NodeParent::operator<(node) ||
1.203 + (NodeParent::operator==(node) && entry < node.entry);
1.204 + }
1.205 + };
1.206 +
1.207 + /// \todo May we want VARIANT/union type
1.208 + class Edge : public Parent::Edge {
1.209 + friend class SplitGraphAdaptorBase;
1.210 + template <typename T> friend class EdgeMap;
1.211 + private:
1.212 + typedef typename Parent::Edge EdgeParent;
1.213 + typedef typename Parent::Node NodeParent;
1.214 + NodeParent bind;
1.215 +
1.216 + Edge(const EdgeParent& edge, const NodeParent& node)
1.217 + : EdgeParent(edge), bind(node) {}
1.218 + public:
1.219 + Edge() {}
1.220 + Edge(Invalid) : EdgeParent(INVALID), bind(INVALID) {}
1.221 +
1.222 + bool operator==(const Edge& edge) const {
1.223 + return EdgeParent::operator==(edge) && bind == edge.bind;
1.224 + }
1.225 +
1.226 + bool operator!=(const Edge& edge) const {
1.227 + return !(*this == edge);
1.228 + }
1.229 +
1.230 + bool operator<(const Edge& edge) const {
1.231 + return EdgeParent::operator<(edge) ||
1.232 + (EdgeParent::operator==(edge) && bind < edge.bind);
1.233 + }
1.234 + };
1.235 +
1.236 + void first(Node& node) const {
1.237 + Parent::first(node);
1.238 + node.entry = true;
1.239 + }
1.240 +
1.241 + void next(Node& node) const {
1.242 + if (node.entry) {
1.243 + node.entry = false;
1.244 + } else {
1.245 + node.entry = true;
1.246 + Parent::next(node);
1.247 + }
1.248 + }
1.249 +
1.250 + void first(Edge& edge) const {
1.251 + Parent::first(edge);
1.252 + if ((typename Parent::Edge&)edge == INVALID) {
1.253 + Parent::first(edge.bind);
1.254 + } else {
1.255 + edge.bind = INVALID;
1.256 + }
1.257 + }
1.258 +
1.259 + void next(Edge& edge) const {
1.260 + if ((typename Parent::Edge&)edge != INVALID) {
1.261 + Parent::next(edge);
1.262 + if ((typename Parent::Edge&)edge == INVALID) {
1.263 + Parent::first(edge.bind);
1.264 + }
1.265 + } else {
1.266 + Parent::next(edge.bind);
1.267 + }
1.268 + }
1.269 +
1.270 + void firstIn(Edge& edge, const Node& node) const {
1.271 + if (node.entry) {
1.272 + Parent::firstIn(edge, node);
1.273 + edge.bind = INVALID;
1.274 + } else {
1.275 + (typename Parent::Edge&)edge = INVALID;
1.276 + edge.bind = node;
1.277 + }
1.278 + }
1.279 +
1.280 + void nextIn(Edge& edge) const {
1.281 + if ((typename Parent::Edge&)edge != INVALID) {
1.282 + Parent::nextIn(edge);
1.283 + } else {
1.284 + edge.bind = INVALID;
1.285 + }
1.286 + }
1.287 +
1.288 + void firstOut(Edge& edge, const Node& node) const {
1.289 + if (!node.entry) {
1.290 + Parent::firstOut(edge, node);
1.291 + edge.bind = INVALID;
1.292 + } else {
1.293 + (typename Parent::Edge&)edge = INVALID;
1.294 + edge.bind = node;
1.295 + }
1.296 + }
1.297 +
1.298 + void nextOut(Edge& edge) const {
1.299 + if ((typename Parent::Edge&)edge != INVALID) {
1.300 + Parent::nextOut(edge);
1.301 + } else {
1.302 + edge.bind = INVALID;
1.303 + }
1.304 + }
1.305 +
1.306 + Node source(const Edge& edge) const {
1.307 + if ((typename Parent::Edge&)edge != INVALID) {
1.308 + return Node(Parent::source(edge), false);
1.309 + } else {
1.310 + return Node(edge.bind, true);
1.311 + }
1.312 + }
1.313 +
1.314 + Node target(const Edge& edge) const {
1.315 + if ((typename Parent::Edge&)edge != INVALID) {
1.316 + return Node(Parent::target(edge), true);
1.317 + } else {
1.318 + return Node(edge.bind, false);
1.319 + }
1.320 + }
1.321 +
1.322 + static bool entryNode(const Node& node) {
1.323 + return node.entry;
1.324 + }
1.325 +
1.326 + static bool exitNode(const Node& node) {
1.327 + return !node.entry;
1.328 + }
1.329 +
1.330 + static Node getEntry(const typename Parent::Node& node) {
1.331 + return Node(node, true);
1.332 + }
1.333 +
1.334 + static Node getExit(const typename Parent::Node& node) {
1.335 + return Node(node, false);
1.336 + }
1.337 +
1.338 + static bool originalEdge(const Edge& edge) {
1.339 + return (typename Parent::Edge&)edge != INVALID;
1.340 + }
1.341 +
1.342 + static bool bindingEdge(const Edge& edge) {
1.343 + return edge.bind != INVALID;
1.344 + }
1.345 +
1.346 + static Node getBindedNode(const Edge& edge) {
1.347 + return edge.bind;
1.348 + }
1.349 +
1.350 + int nodeNum() const {
1.351 + return Parent::nodeNum() * 2;
1.352 + }
1.353 +
1.354 + typedef CompileTimeAnd<typename Parent::NodeNumTag,
1.355 + typename Parent::EdgeNumTag> EdgeNumTag;
1.356 +
1.357 + int edgeNum() const {
1.358 + return Parent::edgeNum() + Parent::nodeNum();
1.359 + }
1.360 +
1.361 + Edge findEdge(const Node& source, const Node& target,
1.362 + const Edge& prev = INVALID) const {
1.363 + if (exitNode(source) && entryNode(target)) {
1.364 + return Parent::findEdge(source, target, prev);
1.365 + } else {
1.366 + if (prev == INVALID && entryNode(source) && exitNode(target) &&
1.367 + (typename Parent::Node&)source == (typename Parent::Node&)target) {
1.368 + return Edge(INVALID, source);
1.369 + } else {
1.370 + return INVALID;
1.371 + }
1.372 + }
1.373 + }
1.374 +
1.375 + template <typename T>
1.376 + class NodeMap : public MapBase<Node, T> {
1.377 + typedef typename Parent::template NodeMap<T> NodeImpl;
1.378 + public:
1.379 + NodeMap(const SplitGraphAdaptorBase& _graph)
1.380 + : entry(_graph), exit(_graph) {}
1.381 + NodeMap(const SplitGraphAdaptorBase& _graph, const T& t)
1.382 + : entry(_graph, t), exit(_graph, t) {}
1.383 +
1.384 + void set(const Node& key, const T& val) {
1.385 + if (key.entry) { entry.set(key, val); }
1.386 + else {exit.set(key, val); }
1.387 + }
1.388 +
1.389 + typename ReferenceMapTraits<NodeImpl>::Reference
1.390 + operator[](const Node& key) {
1.391 + if (key.entry) { return entry[key]; }
1.392 + else { return exit[key]; }
1.393 + }
1.394 +
1.395 + T operator[](const Node& key) const {
1.396 + if (key.entry) { return entry[key]; }
1.397 + else { return exit[key]; }
1.398 + }
1.399 +
1.400 + private:
1.401 + NodeImpl entry, exit;
1.402 + };
1.403 +
1.404 + template <typename T>
1.405 + class EdgeMap : public MapBase<Edge, T> {
1.406 + typedef typename Parent::template NodeMap<T> NodeImpl;
1.407 + typedef typename Parent::template EdgeMap<T> EdgeImpl;
1.408 + public:
1.409 + EdgeMap(const SplitGraphAdaptorBase& _graph)
1.410 + : bind(_graph), orig(_graph) {}
1.411 + EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t)
1.412 + : bind(_graph, t), orig(_graph, t) {}
1.413 +
1.414 + void set(const Edge& key, const T& val) {
1.415 + if ((typename Parent::Edge&)key != INVALID) { orig.set(key, val); }
1.416 + else {bind.set(key.bind, val); }
1.417 + }
1.418 +
1.419 + typename ReferenceMapTraits<EdgeImpl>::Reference
1.420 + operator[](const Edge& key) {
1.421 + if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
1.422 + else {return bind[key.bind]; }
1.423 + }
1.424 +
1.425 + T operator[](const Edge& key) const {
1.426 + if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
1.427 + else {return bind[key.bind]; }
1.428 + }
1.429 +
1.430 + private:
1.431 + typename Parent::template NodeMap<T> bind;
1.432 + typename Parent::template EdgeMap<T> orig;
1.433 + };
1.434 +
1.435 + template <typename EntryMap, typename ExitMap>
1.436 + class CombinedNodeMap : public MapBase<Node, typename EntryMap::Value> {
1.437 + public:
1.438 + typedef MapBase<Node, typename EntryMap::Value> Parent;
1.439 +
1.440 + typedef typename Parent::Key Key;
1.441 + typedef typename Parent::Value Value;
1.442 +
1.443 + CombinedNodeMap(EntryMap& _entryMap, ExitMap& _exitMap)
1.444 + : entryMap(_entryMap), exitMap(_exitMap) {}
1.445 +
1.446 + Value& operator[](const Key& key) {
1.447 + if (key.entry) {
1.448 + return entryMap[key];
1.449 + } else {
1.450 + return exitMap[key];
1.451 + }
1.452 + }
1.453 +
1.454 + Value operator[](const Key& key) const {
1.455 + if (key.entry) {
1.456 + return entryMap[key];
1.457 + } else {
1.458 + return exitMap[key];
1.459 + }
1.460 + }
1.461 +
1.462 + void set(const Key& key, const Value& value) {
1.463 + if (key.entry) {
1.464 + entryMap.set(key, value);
1.465 + } else {
1.466 + exitMap.set(key, value);
1.467 + }
1.468 + }
1.469 +
1.470 + private:
1.471 +
1.472 + EntryMap& entryMap;
1.473 + ExitMap& exitMap;
1.474 +
1.475 + };
1.476 +
1.477 + template <typename EdgeMap, typename NodeMap>
1.478 + class CombinedEdgeMap : public MapBase<Edge, typename EdgeMap::Value> {
1.479 + public:
1.480 + typedef MapBase<Edge, typename EdgeMap::Value> Parent;
1.481 +
1.482 + typedef typename Parent::Key Key;
1.483 + typedef typename Parent::Value Value;
1.484 +
1.485 + CombinedEdgeMap(EdgeMap& _edgeMap, NodeMap& _nodeMap)
1.486 + : edgeMap(_edgeMap), nodeMap(_nodeMap) {}
1.487 +
1.488 + void set(const Edge& edge, const Value& val) {
1.489 + if (SplitGraphAdaptorBase::originalEdge(edge)) {
1.490 + edgeMap.set(edge, val);
1.491 + } else {
1.492 + nodeMap.set(SplitGraphAdaptorBase::bindedNode(edge), val);
1.493 + }
1.494 + }
1.495 +
1.496 + Value operator[](const Key& edge) const {
1.497 + if (SplitGraphAdaptorBase::originalEdge(edge)) {
1.498 + return edgeMap[edge];
1.499 + } else {
1.500 + return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
1.501 + }
1.502 + }
1.503 +
1.504 + Value& operator[](const Key& edge) {
1.505 + if (SplitGraphAdaptorBase::originalEdge(edge)) {
1.506 + return edgeMap[edge];
1.507 + } else {
1.508 + return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
1.509 + }
1.510 + }
1.511 +
1.512 + private:
1.513 + EdgeMap& edgeMap;
1.514 + NodeMap& nodeMap;
1.515 + };
1.516 +
1.517 + };
1.518 +
1.519 + template <typename _Graph>
1.520 + class SplitGraphAdaptor
1.521 + : public IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > {
1.522 + public:
1.523 + typedef IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > Parent;
1.524 +
1.525 + SplitGraphAdaptor(_Graph& graph) {
1.526 + Parent::setGraph(graph);
1.527 + }
1.528 +
1.529 +
1.530 + };
1.531 +
1.532 + template <typename _Graph>
1.533 class NewEdgeSetAdaptorBase {
1.534 public:
1.535