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. Thanks, Suresh
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
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
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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
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
participants (2)
-
François Duranleau -
Suresh Gupta