Adding topological sort.

git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/simgrid/simgrid/trunk@2007 48e7efb5-ca39-0410-a469-dd3cf9ba447f

diff --git a/include/xbt/graph.h b/include/xbt/graph.h
index a98a096..6093733 100644 (file)
--- a/include/xbt/graph.h
+++ b/include/xbt/graph.h
@@ -57,7 +57,16 @@ void xbt_graph_export_graphxml(xbt_graph_t g, const char *filename,
 /* Not implemented yet ! */
 /* void *xbt_graph_to_array(xbt_graph_t g);  */
 xbt_node_t* xbt_graph_shortest_paths(xbt_graph_t g);
 /* Not implemented yet ! */
 /* void *xbt_graph_to_array(xbt_graph_t g);  */
 xbt_node_t* xbt_graph_shortest_paths(xbt_graph_t g);

-void xbt_graph_topological_sort(xbt_graph_t g);
+
+
+
+/* transforms the network structure of a directed acyclic graph given as argument  into a linear structure 
+@return an array containing the nodes of the graph sorted in order reverse to the path of exploration 
+if a cycle is detected an exception is raised  
+  */
+
+xbt_node_t* xbt_graph_topo_sort(xbt_graph_t g);
+

 xbt_edge_t* xbt_graph_spanning_tree_prim(xbt_graph_t g);
 
 
 xbt_edge_t* xbt_graph_spanning_tree_prim(xbt_graph_t g);
 
 

diff --git a/src/xbt/graph.c b/src/xbt/graph.c
index 7886d7d..280ed8d 100644 (file)
--- a/src/xbt/graph.c
+++ b/src/xbt/graph.c
@@ -17,6 +17,9 @@
 #include "xbt/dict.h"
 #include "xbt/heap.h"
 
 #include "xbt/dict.h"
 #include "xbt/heap.h"
 

+
+
+

 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(graph, xbt, "Graph");
 
 
 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(graph, xbt, "Graph");
 
 


@@ -41,10 +44,11 @@ xbt_node_t xbt_graph_new_node(xbt_graph_t g, void *data)
   xbt_node_t node = NULL;
   node = xbt_new0(struct xbt_node, 1);
   node->data = data;
   xbt_node_t node = NULL;
   node = xbt_new0(struct xbt_node, 1);
   node->data = data;

-  node->in = xbt_dynar_new(sizeof(xbt_node_t), NULL);
-  node->out = xbt_dynar_new(sizeof(xbt_node_t), NULL);
+  node->in = xbt_dynar_new(sizeof(xbt_edge_t), NULL);
+  node->out = xbt_dynar_new(sizeof(xbt_edge_t), NULL);

   node->position_x = -1.0;
   node->position_y = -1.0;
   node->position_x = -1.0;
   node->position_y = -1.0;

+

   xbt_dynar_push(g->nodes, &node);
 
   return node;
   xbt_dynar_push(g->nodes, &node);
 
   return node;


@@ -67,6 +71,12 @@ xbt_edge_t xbt_graph_new_edge(xbt_graph_t g,
   edge->data = data;
   edge->src = src;
   edge->dst = dst;
   edge->data = data;
   edge->src = src;
   edge->dst = dst;

+  if (!g->directed) 
+    {
+      xbt_dynar_push(src->in, &edge);
+      xbt_dynar_push(dst->out, &edge);
+    }
+

 
   xbt_dynar_push(g->edges, &edge);
 
 
   xbt_dynar_push(g->edges, &edge);
 


@@ -479,8 +489,7 @@ static void __parse_edge(void)
 
   xbt_graph_parse_get_double(&(edge->length),A_graphxml_edge_length);
 
 
   xbt_graph_parse_get_double(&(edge->length),A_graphxml_edge_length);
 

-  DEBUG4("<edge name=\"%s\"  source=\"%s\" target=\"%s\" length=\"%f\"/>",
-        (char *) edge->data,
+  DEBUG3("<edge  source=\"%s\" target=\"%s\" length=\"%f\"/>",

         (char *) (edge->src)->data,
         (char *) (edge->dst)->data,
         xbt_graph_edge_get_length(edge));
         (char *) (edge->src)->data,
         (char *) (edge->dst)->data,
         xbt_graph_edge_get_length(edge));


@@ -590,3 +599,50 @@ void xbt_graph_export_graphxml(xbt_graph_t g, const char *filename,
   fclose(file);
 }
 
   fclose(file);
 }
 

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

diff --git a/src/xbt/graph_private.h b/src/xbt/graph_private.h
index 6074161..2c7cef2 100644 (file)
--- a/src/xbt/graph_private.h
+++ b/src/xbt/graph_private.h
@@ -10,6 +10,10 @@
 #define _XBT_GRAPH_PRIVATE_H
 #include "xbt/dynar.h"
 
 #define _XBT_GRAPH_PRIVATE_H
 #include "xbt/dynar.h"
 

+#define NOT_EXPLORED 0
+#define CURRENTLY_EXPLORING 1
+#define ALREADY_EXPLORED 2
+

 /* Node structure */
 /* typedef struct xbt_node *xbt_node_t; */
 typedef struct xbt_node 
 /* Node structure */
 /* typedef struct xbt_node *xbt_node_t; */
 typedef struct xbt_node 


@@ -47,6 +51,6 @@ typedef struct xbt_graph
                      beginning of your algorithm if you need to use it */  
 } s_xbt_graph_t;
 void xbt_floyd_algorithm(xbt_graph_t g, double* adj,double* d,  xbt_node_t* p);
                      beginning of your algorithm if you need to use it */  
 } s_xbt_graph_t;
 void xbt_floyd_algorithm(xbt_graph_t g, double* adj,double* d,  xbt_node_t* p);

-
+void xbt_graph_depth_visit (xbt_graph_t g,xbt_node_t n,xbt_node_t* sorted,int* idx);

 
 #endif                         /* _XBT_GRAPH_PRIVATE_H */
 
 #endif                         /* _XBT_GRAPH_PRIVATE_H */