From 139da70d9c161eaeec3e6eb74278c966370c6e62 Mon Sep 17 00:00:00 2001
From: dimitrov <dimitrov@48e7efb5-ca39-0410-a469-dd3cf9ba447f>
Date: Wed, 29 Mar 2006 12:45:05 +0000
Subject: [PATCH 1/1] Adding topological sort.

git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/simgrid/simgrid/trunk@2007 48e7efb5-ca39-0410-a469-dd3cf9ba447f
---
 include/xbt/graph.h     | 11 ++++++-
 src/xbt/graph.c         | 64 ++++++++++++++++++++++++++++++++++++++---
 src/xbt/graph_private.h |  6 +++-
 3 files changed, 75 insertions(+), 6 deletions(-)

diff --git a/include/xbt/graph.h b/include/xbt/graph.h
index a98a096eb2..609373311d 100644
--- 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);
-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);
 
 
diff --git a/src/xbt/graph.c b/src/xbt/graph.c
index 7886d7d0b4..280ed8dfbc 100644
--- a/src/xbt/graph.c
+++ b/src/xbt/graph.c
@@ -17,6 +17,9 @@
 #include "xbt/dict.h"
 #include "xbt/heap.h"
 
+
+
+
 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;
-  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;
+
   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;
+  if (!g->directed) 
+    {
+      xbt_dynar_push(src->in, &edge);
+      xbt_dynar_push(dst->out, &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);
 
-  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));
@@ -590,3 +599,50 @@ void xbt_graph_export_graphxml(xbt_graph_t g, const char *filename,
   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 607416183c..2c7cef294b 100644
--- 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 NOT_EXPLORED 0
+#define CURRENTLY_EXPLORING 1
+#define ALREADY_EXPLORED 2
+
 /* 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);
-
+void xbt_graph_depth_visit (xbt_graph_t g,xbt_node_t n,xbt_node_t* sorted,int* idx);
 
 #endif				/* _XBT_GRAPH_PRIVATE_H */
-- 
2.20.1