Filter Node Iterator (FilterNodeIt)

Definition

An instance it of class FilterNodeIt<Predicate,Iter> encapsulates an object of type Iter and creates a restricted view on the set of nodes over which this internal iterator iterates. More specifically, all nodes that do not fulfill the predicate defined by Predicate are filtered out during this traversal.

Class FilterEdgeIt and FilterAdjIt are defined analogously, i.e. can be used for edge iterators or adjacency iterators, respectively.

Precondition: The template parameter Iter must be a node iterator, e.g. NodeIt, SafeNodeIt or FilterNodeIt<pred,NodeIt>. Predicate must be a class which provides a method operator() according to the following signature: bool operator() (Iter).

Creation

FilterNodeIt<Predicate,Iter>	it;	introduces a variable it of this class, not bound to a predicate or iterator.
FilterNodeIt<Predicate,Iter>	it(Predicate pred, Iter base_it);
		introduces a variable it of this class bound to pred and base_it.

Operations

void	it.init(Predicate pred, Iter base_it)
		initializes it, which is bound to pred and base_it afterwards. Precondition: it is not yet bound to a predicate or iterator.

Implementation

Constant overhead.

Example

Suppose that each node has an own colour and we only want to see those with a specific colour, for example red (we use the LEDA colours). At first the data structures:

  GRAPH<color,double> G;
  NodeIt it(G);

We would have to write something like this:

  while(it.valid()) {
    if (G[it.get_node()]==red) do_something(it);
    ++it; }

With the filter wrapper class we can add the test if the node is red to the behaviour of the iterator.

  struct RedPred {
    bool operator() (const NodeIt& it) const {
    return G[it.get_node()]==red; }
  } redpred;
  FilterNodeIt<RedPred,NodeIt> red_it(redpred,it);

This simplifies the loop to the following:

  while(red_it.valid()) {
    do_something(red_it);
    ++red_it; }

All ingredients of the comparison are hard-wired in struct RedPred: the type of the compared values (color), the comparison value (red) and the binary comparison (equality). The following class CompPred renders these three choices flexible.