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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users