/* 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);
#include "xbt/dict.h"
#include "xbt/heap.h"
+
+
+
XBT_LOG_NEW_DEFAULT_SUBCATEGORY(graph, xbt, "Graph");
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;
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_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));
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;
+ }
+}
#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
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 */