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

From: François Duranleau (duranlef_at_[hidden])
Date: 2007-10-09 11:20:33

On Mon, 8 Oct 2007, Suresh Gupta wrote:

> 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--;
>     }
>   }
>
>  }

You are not resetting in_degree to zeros before recomputing it. Actually, 
if you want to write it this way, you don't need this vector. You could 
write something like this (untested):

Graph::vector_iterator it , iend ;
int count = num_vertices( g ) ;
int cycle = 0 ;
while ( count > 0 )
{
     cout << "Nodes in Cycle " << cycle << ":" << endl ;
     for ( tie( it , iend ) = vertices( g ) ; it != iend ; ++ it )
     {
         // in_degree below is a BGL free function
         if ( in_degree( * it , g ) == 0 )
         {
             cout << " " << * it ;
             clear_vertex( * it , g ) ;
             -- count ;
         }
     }
     cout << endl ;
     ++ cycle ;
}

However, if you want a better performance, I suggest using an algorithm 
like I proposed earlier.

-- 
Francois Duranleau

_______________________________________________
Boost-users mailing list
Boost-users_at_[hidden]
http://lists.boost.org/mailman/listinfo.cgi/boost-users