223 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) { |
224 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) { |
224 edge_filter_map=&_edge_filter_map; |
225 edge_filter_map=&_edge_filter_map; |
225 } |
226 } |
226 |
227 |
227 public: |
228 public: |
228 // SubGraphAdaptorBase(Graph& _graph, |
|
229 // NodeFilterMap& _node_filter_map, |
|
230 // EdgeFilterMap& _edge_filter_map) : |
|
231 // Parent(&_graph), |
|
232 // node_filter_map(&node_filter_map), |
|
233 // edge_filter_map(&edge_filter_map) { } |
|
234 |
229 |
235 typedef typename Parent::Node Node; |
230 typedef typename Parent::Node Node; |
236 typedef typename Parent::Edge Edge; |
231 typedef typename Parent::Edge Edge; |
237 |
232 |
238 void first(Node& i) const { |
233 void first(Node& i) const { |
239 Parent::first(i); |
234 Parent::first(i); |
240 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); |
235 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); |
241 } |
236 } |
|
237 |
242 void first(Edge& i) const { |
238 void first(Edge& i) const { |
243 Parent::first(i); |
239 Parent::first(i); |
244 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); |
240 while (i!=INVALID && (!(*edge_filter_map)[i] |
245 } |
241 || !(*node_filter_map)[Parent::source(i)] |
|
242 || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); |
|
243 } |
|
244 |
246 void firstIn(Edge& i, const Node& n) const { |
245 void firstIn(Edge& i, const Node& n) const { |
247 Parent::firstIn(i, n); |
246 Parent::firstIn(i, n); |
248 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); |
247 while (i!=INVALID && (!(*edge_filter_map)[i] |
249 } |
248 || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i); |
|
249 } |
|
250 |
250 void firstOut(Edge& i, const Node& n) const { |
251 void firstOut(Edge& i, const Node& n) const { |
251 Parent::firstOut(i, n); |
252 Parent::firstOut(i, n); |
252 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); |
253 while (i!=INVALID && (!(*edge_filter_map)[i] |
|
254 || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i); |
253 } |
255 } |
254 |
256 |
255 void next(Node& i) const { |
257 void next(Node& i) const { |
256 Parent::next(i); |
258 Parent::next(i); |
257 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); |
259 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); |
258 } |
260 } |
|
261 |
259 void next(Edge& i) const { |
262 void next(Edge& i) const { |
260 Parent::next(i); |
263 Parent::next(i); |
261 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); |
264 while (i!=INVALID && (!(*edge_filter_map)[i] |
262 } |
265 || !(*node_filter_map)[Parent::source(i)] |
|
266 || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); |
|
267 } |
|
268 |
263 void nextIn(Edge& i) const { |
269 void nextIn(Edge& i) const { |
264 Parent::nextIn(i); |
270 Parent::nextIn(i); |
265 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); |
271 while (i!=INVALID && (!(*edge_filter_map)[i] |
266 } |
272 || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i); |
|
273 } |
|
274 |
267 void nextOut(Edge& i) const { |
275 void nextOut(Edge& i) const { |
268 Parent::nextOut(i); |
276 Parent::nextOut(i); |
269 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); |
277 while (i!=INVALID && (!(*edge_filter_map)[i] |
|
278 || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i); |
270 } |
279 } |
271 |
280 |
272 /// This function hides \c n in the graph, i.e. the iteration |
281 /// This function hides \c n in the graph, i.e. the iteration |
273 /// jumps over it. This is done by simply setting the value of \c n |
282 /// jumps over it. This is done by simply setting the value of \c n |
274 /// to be false in the corresponding node-map. |
283 /// to be false in the corresponding node-map. |
312 int i=0; |
321 int i=0; |
313 Edge e; |
322 Edge e; |
314 for (first(e); e!=INVALID; next(e)) ++i; |
323 for (first(e); e!=INVALID; next(e)) ++i; |
315 return i; |
324 return i; |
316 } |
325 } |
317 |
326 }; |
318 |
327 |
|
328 template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap> |
|
329 class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false> |
|
330 : public GraphAdaptorBase<_Graph> { |
|
331 public: |
|
332 typedef _Graph Graph; |
|
333 typedef GraphAdaptorBase<_Graph> Parent; |
|
334 protected: |
|
335 NodeFilterMap* node_filter_map; |
|
336 EdgeFilterMap* edge_filter_map; |
|
337 SubGraphAdaptorBase() : Parent(), |
|
338 node_filter_map(0), edge_filter_map(0) { } |
|
339 |
|
340 void setNodeFilterMap(NodeFilterMap& _node_filter_map) { |
|
341 node_filter_map=&_node_filter_map; |
|
342 } |
|
343 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) { |
|
344 edge_filter_map=&_edge_filter_map; |
|
345 } |
|
346 |
|
347 public: |
|
348 |
|
349 typedef typename Parent::Node Node; |
|
350 typedef typename Parent::Edge Edge; |
|
351 |
|
352 void first(Node& i) const { |
|
353 Parent::first(i); |
|
354 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); |
|
355 } |
|
356 |
|
357 void first(Edge& i) const { |
|
358 Parent::first(i); |
|
359 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); |
|
360 } |
|
361 |
|
362 void firstIn(Edge& i, const Node& n) const { |
|
363 Parent::firstIn(i, n); |
|
364 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); |
|
365 } |
|
366 |
|
367 void firstOut(Edge& i, const Node& n) const { |
|
368 Parent::firstOut(i, n); |
|
369 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); |
|
370 } |
|
371 |
|
372 void next(Node& i) const { |
|
373 Parent::next(i); |
|
374 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); |
|
375 } |
|
376 void next(Edge& i) const { |
|
377 Parent::next(i); |
|
378 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); |
|
379 } |
|
380 void nextIn(Edge& i) const { |
|
381 Parent::nextIn(i); |
|
382 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); |
|
383 } |
|
384 |
|
385 void nextOut(Edge& i) const { |
|
386 Parent::nextOut(i); |
|
387 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); |
|
388 } |
|
389 |
|
390 /// This function hides \c n in the graph, i.e. the iteration |
|
391 /// jumps over it. This is done by simply setting the value of \c n |
|
392 /// to be false in the corresponding node-map. |
|
393 void hide(const Node& n) const { node_filter_map->set(n, false); } |
|
394 |
|
395 /// This function hides \c e in the graph, i.e. the iteration |
|
396 /// jumps over it. This is done by simply setting the value of \c e |
|
397 /// to be false in the corresponding edge-map. |
|
398 void hide(const Edge& e) const { edge_filter_map->set(e, false); } |
|
399 |
|
400 /// The value of \c n is set to be true in the node-map which stores |
|
401 /// hide information. If \c n was hidden previuosly, then it is shown |
|
402 /// again |
|
403 void unHide(const Node& n) const { node_filter_map->set(n, true); } |
|
404 |
|
405 /// The value of \c e is set to be true in the edge-map which stores |
|
406 /// hide information. If \c e was hidden previuosly, then it is shown |
|
407 /// again |
|
408 void unHide(const Edge& e) const { edge_filter_map->set(e, true); } |
|
409 |
|
410 /// Returns true if \c n is hidden. |
|
411 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; } |
|
412 |
|
413 /// Returns true if \c n is hidden. |
|
414 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; } |
|
415 |
|
416 /// \warning This is a linear time operation and works only if s |
|
417 /// \c Graph::NodeIt is defined. |
|
418 /// \todo assign tags. |
|
419 int nodeNum() const { |
|
420 int i=0; |
|
421 Node n; |
|
422 for (first(n); n!=INVALID; next(n)) ++i; |
|
423 return i; |
|
424 } |
|
425 |
|
426 /// \warning This is a linear time operation and works only if |
|
427 /// \c Graph::EdgeIt is defined. |
|
428 /// \todo assign tags. |
|
429 int edgeNum() const { |
|
430 int i=0; |
|
431 Edge e; |
|
432 for (first(e); e!=INVALID; next(e)) ++i; |
|
433 return i; |
|
434 } |
319 }; |
435 }; |
320 |
436 |
321 /*! \brief A graph adaptor for hiding nodes and edges from a graph. |
437 /*! \brief A graph adaptor for hiding nodes and edges from a graph. |
322 |
438 |
323 \warning Graph adaptors are in even more experimental state than the other |
439 \warning Graph adaptors are in even more experimental state than the other |
373 EdgeSubGraphAdaptor. |
489 EdgeSubGraphAdaptor. |
374 |
490 |
375 \author Marton Makai |
491 \author Marton Makai |
376 */ |
492 */ |
377 template<typename _Graph, typename NodeFilterMap, |
493 template<typename _Graph, typename NodeFilterMap, |
378 typename EdgeFilterMap> |
494 typename EdgeFilterMap, bool checked = true> |
379 class SubGraphAdaptor : |
495 class SubGraphAdaptor : |
380 public IterableGraphExtender< |
496 public IterableGraphExtender< |
381 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > { |
497 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > { |
382 public: |
498 public: |
383 typedef _Graph Graph; |
499 typedef _Graph Graph; |
384 typedef IterableGraphExtender< |
500 typedef IterableGraphExtender< |
385 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent; |
501 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent; |
386 protected: |
502 protected: |
405 This adaptor specializes SubGraphAdaptor in the way that only the node-set |
521 This adaptor specializes SubGraphAdaptor in the way that only the node-set |
406 can be filtered. Note that this does not mean of considering induced |
522 can be filtered. Note that this does not mean of considering induced |
407 subgraph, the edge-iterators consider the original edge-set. |
523 subgraph, the edge-iterators consider the original edge-set. |
408 \author Marton Makai |
524 \author Marton Makai |
409 */ |
525 */ |
410 template<typename Graph, typename NodeFilterMap> |
526 template<typename Graph, typename NodeFilterMap, bool checked = true> |
411 class NodeSubGraphAdaptor : |
527 class NodeSubGraphAdaptor : |
412 public SubGraphAdaptor<Graph, NodeFilterMap, |
528 public SubGraphAdaptor<Graph, NodeFilterMap, |
413 ConstMap<typename Graph::Edge,bool> > { |
529 ConstMap<typename Graph::Edge,bool>, checked> { |
414 public: |
530 public: |
415 typedef SubGraphAdaptor<Graph, NodeFilterMap, |
531 typedef SubGraphAdaptor<Graph, NodeFilterMap, |
416 ConstMap<typename Graph::Edge,bool> > Parent; |
532 ConstMap<typename Graph::Edge,bool> > Parent; |
417 protected: |
533 protected: |
418 ConstMap<typename Graph::Edge, bool> const_true_map; |
534 ConstMap<typename Graph::Edge, bool> const_true_map; |
558 \author Marton Makai |
674 \author Marton Makai |
559 */ |
675 */ |
560 template<typename Graph, typename EdgeFilterMap> |
676 template<typename Graph, typename EdgeFilterMap> |
561 class EdgeSubGraphAdaptor : |
677 class EdgeSubGraphAdaptor : |
562 public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>, |
678 public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>, |
563 EdgeFilterMap> { |
679 EdgeFilterMap, false> { |
564 public: |
680 public: |
565 typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>, |
681 typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>, |
566 EdgeFilterMap> Parent; |
682 EdgeFilterMap> Parent; |
567 protected: |
683 protected: |
568 ConstMap<typename Graph::Node, bool> const_true_map; |
684 ConstMap<typename Graph::Node, bool> const_true_map; |