Re: [Boost-users] how to schedule nodes in graph

From: François Duranleau (duranlef_at_[hidden])
Date: 2007-10-08 12:05:36

On Mon, 8 Oct 2007, Suresh Gupta wrote:

> Hi,
>   I want to do the following:
> I have a graph in boost. Now I want to schedule the graph nodes in
> topological order as follows:
> 1. The nodes which do not have any parents are to be scheduled in first
> cycle. Record the list of these nodes.
> 2. Remove already recorded nodes (in step 1) from the graph.
> 3. Repeat 1 and 2 on the remaining graph and so on.
> How to do the above?
> I need functions:
> 1. Get all nodes which do not have parents.
> 2. To remove the nodes from graph.
>
> Please suggest me about the functions in boost so do the same.

You just need to ensure that your graph type implements the following two 
concepts:

http://www.boost.org/libs/graph/doc/BidirectionalGraph.html
http://www.boost.org/libs/graph/doc/MutableGraph.html

You can then use boost::in_degree to detect vertices with no parents (the 
value should be zero), and boost::remove_vertex to delete vertices.

Personaly, I would rather resort to an additional vertex property (let's 
call it in_degree2 by lack of imagination) that is initialized to their 
in-degrees. And then, the algorithm would be something like (untested, of 
course):

Let g be the graph, and q be an empty queue

for each vertex v in g :
   copy in_degree to in_degree2
   if v's in_degree2 is zero :
     push v in q

while q is not empty do:
   v = pop q
   "output" v
   for each u neighbors of v in g: // iterate over v's out_edges in g
                                   // and u is the edge's target
     if u's in_degree2 > 0 : // otherwise it is already in the queue
       decrement u's in_degree2
       if u's in_degree2 has reached zero :
         push u in q

This should cost O(V+E) instead of O(V^2) as your algorithm suggests 
above, and relying on a property instead of dynamically modifying the 
graph should also be more efficient. If you need to clearly separate the 
different "cycles", one way would be to use two queues.

Let g be the graph, q1 and q2 with two empty queues,

for each vertex v in g :
   copy in_degree to in_degree2
   if v's in_degree2 is zero :
     push v in q1

while q1 and q2 are not empty do:
   while the q1 is not empty do:
     v = pop q1
     "output in current cycle" v
     for each u neighbors of v in g:
       if u's in_degree2 > 0 :
         decrement u's in_degree2
         if u's in_degree2 has reached zero :
           push u in q2
   swap q1 and q2
   step to next cycle

That should be roughly as efficient, assuming that swapping the queue's is 
implement the right way.

-- 
Francois Duranleau