//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: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 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