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

From: Suresh Gupta (gupta.suresh_at_[hidden])
Date: 2007-10-08 13:53:31

Thanks for the reply Francois.
    Well, i have written some code from my side. But every time it is giving
me the same nodes in a particular cycle. Hence scheduling is not working.
Code :
//===============================================

//Graph vertex in_degree:
  std::vector<int> in_degree(num_vertices, 0);
  Graph::vertex_iterator it, iend;
  Graph::out_edge_iterator j, jend;
  int count=num_vertices;
  int cycle=0;
 int a =0;
  while(count > 0)
  {
   std::cout << std::endl;
   printf("In Degree of the unscheduled nodes:\n");
   for (boost::tie(it, iend) = vertices(g); it != iend; ++it)
    for (boost::tie(j, jend) = out_edges(*it, g); j != jend; ++j)
   {
     std::cout << in_degree[target(*j, g)] << " ";
     in_degree[target(*j, g)] += 1;
   }
    printf("\nNodes in Cycle %d:\n",cycle);
    cycle++;
  // Search vertex with zero in-degree.
    for (tie(it, iend) = vertices(g); it != iend; ++it) {
     if (in_degree[*it] == 0) {
      std::cout << *it;
      std::cout << "  ";
      clear_vertex(*it, g);
      //      print_graph(g, get(vertex_index, g));
      count--;
     }
   }

  }

//=======================================================

My input graph is:

Adjacency List of the graph entered:
0 --> 2 5
1 --> 2
2 --> 3
3 -->
4 --> 5 8
5 --> 6
6 -->
7 --> 8
8 --> 9
9 -->

And the result I am getting from the above code is:

In Degree of the unscheduled nodes:
0 0 1 0 1 0 0 1 0
Nodes in Cycle 0:
0  1  4  7
In Degree of the unscheduled nodes:
1 1 1
Nodes in Cycle 1:
0  1  4  7
In Degree of the unscheduled nodes:
2 2 2
Nodes in Cycle 2:
0  1  4  7

Can you please suggest me, where is the problem.

Thanks a lot.

Suresh

On 10/8/07, François Duranleau <duranlef_at_[hidden]> wrote:
>
> 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
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>