Algorithms

Bfs/Dfs

Both Bfs and Dfs are highly adaptable and efficient implementations of the well known algorithms. The algorithms are placed most cases in separated files named after the algorithm itself but lower case as all other header file names. For example the next Bfs class is in the lemon/bfs.h.

Bfs

The algorithm is implemented in the Bfs template class - rather than as function. The class has two template parameters: GR and .
GR is the graph the algorithm runs on. It has ListGraph as default type. TR is a Traits class commonly used to easy the parametrization of templates. In most cases you wont need to modify the default type BfsDefaultTraits<GR>.

To use the class, declare it!

Bfs<ListUGraph>  bfs(gr);
Note the lack of second template argument because of the default parameter.

It provides a simple but powerful interface to control the execution.

int dist = bfs.run(s,t);
It finds the shortest path from node s to node t and returns it, or zero if there is no path from s to t.
If you want the shortest path from a specified node to all other node, just write:
bfs.run(s);
Now the distances and path information are stored in maps which you can access with member functions like distMap() or predMap().
Or more directly whit other member functions like predNode(). Once the algorithm is finished (or to be precise reached that node) dist() or predNode() can be called.

For an example let's say we want to print the shortest path of those nodes which are in a certain distance.

bfs.run(s);

for( ListUGraph::NodeIt  n(gr); n != INVALID; ++n ) {
  if( bfs.reached(n) && bfs.dist(n) <= max_dist ) {
    std::cout << gr.id(n);

    Node  prev = bfs.prevNode(n);
    while( prev != INVALID ) {
      std::cout << "<-" << gr.id(prev);
      prev = bfs.prevNode(n);
    }
    
    std::cout << std::endl;
  }
}

Advanced control

In the previous code we only used run(). Now we introduce the way you can directly control the execution of the algorithm.

First you have to initialize the variables with init().

  bfs.init();

Then you add one or more source nodes to the queue. They will be processed, as they would be reached by the algorithm before. And yes - you can add more sources during the execution.

  bfs.addSource(node_1);
  bfs.addSource(node_2);
  ...

And finally you can start the process with start(), or you can write your own loop to process the nodes one-by-one.

Todo:
demo for bfs advanced control

Dfs

Since Dfs is very similar to Bfs with a few tiny differences we only see a bit more complex example to demonstrate Dfs's capabilities.

We will see a program, which solves the problem of topological ordering. We need to know in which order we should put on our clothes. The program will do the following:

  1. We run the dfs algorithm to all nodes.
  2. Put every node into a list when processed completely.
  3. Write out the list in reverse order.

First of all we will need an own ProcessedMap. The ordering will be done through it.

class SerializingWriteMap
{
public:
  typedef typename GR::Node  Key;
  typedef bool  Value;
  typedef std::list<Key>  OrderedList;

  OrderedList  order;

  SerializingWriteMap( const GR& ) {}

  void  set( const Key& k, const Value& v ) {
    if( v ) order.push_front(k);
  }

  Value  operator[] ( const Key& ) {
    return false;
  }
};
The class meets the WriteMap concept. In it's set() method the only thing we need to do is insert the key - that is the node who's processing just finished - into the beginning of the list.

First we declare the needed data structures: the graph and a map to store the nodes' label.

  ListGraph  gr;
  ListGraph::NodeMap<std::string>  label(gr);

Now we build a graph. But keep in mind that it must be DAG because cyclic graphs has no topological ordering.

    Node  belt = gr.addNode();
    Node  trousers = gr.addNode();
We label them...
    label[belt] = "Belt";
    label[trousers] = "Trousers";
Then add directed edges which represent the precedences between those items.
    gr.addEdge( trousers, belt );

See how easy is to access the internal information of this algorithm trough maps. We only need to set our own map as the class's ProcessedMap.

  Dfs<ListGraph, Dfs<ListGraph>::DefProcessedMapTraits<SerializingWriteMap<ListGraph> > >  dfs(gr);
  SerializingWriteMap<ListGraph>  list(gr);
  dfs.processedMap(list);
  dfs.run();

And now comes the third part. Write out the list in reverse order. But the list was composed in reverse way (with push_front() instead of push_back() so we just iterate it.

  std::cout << "One possible order to dress up:";
  for( SerializingWriteMap<ListGraph>::OrderedList::iterator  it = list.order.begin(); it != list.order.end(); ++it )
    std::cout << "  " << label[*it];
  std::cout << std::endl;

The program is to be found in the demo directory: topological_ordering.cc


Generated on Tue Oct 31 09:49:37 2006 for LEMON by  doxygen 1.5.1