-
-xbt_node_t* xbt_graph_topo_sort(xbt_graph_t g)
-{
-
- xbt_node_t* sorted;
- int cursor,idx;
- xbt_node_t node;
- unsigned long n;
-
- n= xbt_dynar_length(g->nodes);
- idx=n-1;
-
- sorted=xbt_malloc(n*sizeof(xbt_node_t));
- xbt_dynar_foreach(g->nodes,cursor , node)
- {
- node->xbtdata=xbt_new0(int,1);
- }
-
- xbt_dynar_foreach(g->nodes,cursor , node)
- {
- xbt_graph_depth_visit(g,node,sorted,&idx);
- }
-
- return sorted;
-}
-
-void xbt_graph_depth_visit(xbt_graph_t g,xbt_node_t n,xbt_node_t* sorted,int* idx )
-{
- int cursor;
- xbt_edge_t edge;
-
- if (*((int*)(n->xbtdata))==ALREADY_EXPLORED)
- return;
- else if (*((int*)(n->xbtdata))==CURRENTLY_EXPLORING)
- THROW0(0,0,"There is a cycle");
- else
- {
- *((int*)(n->xbtdata))=CURRENTLY_EXPLORING;
-
- xbt_dynar_foreach(n->out,cursor, edge)
- {
- xbt_graph_depth_visit(g,edge->dst,sorted,idx);
- }
-
- *((int*)(n->xbtdata))=ALREADY_EXPLORED;
- sorted[(*idx)--]=n;
- }
-}