typedef struct xbt_graph *xbt_graph_t;
/* Node structure */
-/* Be carfull of what you do with this structure */
+/* Be careful of what you do with this structure */
/* typedef struct xbt_node *xbt_node_t; */
typedef struct xbt_node {
xbt_dynar_t out;
} s_xbt_node_t;
/* edge structure */
-/* Be carfull of what you do with this structure */
+/* Be careful of what you do with this structure */
/* typedef struct xbt_edge *xbt_edge_t; */
typedef struct xbt_edge {
xbt_node_t src;
} s_xbt_edge_t;
/* Graph structure */
-/* Be carfull of what you do with this structure */
+/* Be careful of what you do with this structure */
/* typedef struct xbt_graph *xbt_graph_t; */
typedef struct xbt_graph {
xbt_dynar_t nodes;
} s_xbt_graph_t;
/* API */
-XBT_PUBLIC(xbt_graph_t) xbt_graph_new_graph(unsigned short int directed,
- void *data);
+XBT_PUBLIC(xbt_graph_t) xbt_graph_new_graph(unsigned short int directed, void *data);
XBT_PUBLIC(xbt_node_t) xbt_graph_new_node(xbt_graph_t g, void *data);
-XBT_PUBLIC(xbt_edge_t) xbt_graph_new_edge(xbt_graph_t g, xbt_node_t src,
- xbt_node_t dst, void *data);
+XBT_PUBLIC(xbt_edge_t) xbt_graph_new_edge(xbt_graph_t g, xbt_node_t src, xbt_node_t dst, void *data);
XBT_PUBLIC(void *) xbt_graph_node_get_data(xbt_node_t node);
XBT_PUBLIC(void) xbt_graph_node_set_data(xbt_node_t node, void *data);
XBT_PUBLIC(void *) xbt_graph_edge_get_data(xbt_edge_t edge);
XBT_PUBLIC(void) xbt_graph_edge_set_data(xbt_edge_t edge, void *data);
-XBT_PUBLIC(xbt_edge_t) xbt_graph_get_edge(xbt_graph_t g, xbt_node_t src,
- xbt_node_t dst);
+XBT_PUBLIC(xbt_edge_t) xbt_graph_get_edge(xbt_graph_t g, xbt_node_t src, xbt_node_t dst);
XBT_PUBLIC(void) xbt_graph_edge_set_length(xbt_edge_t e, double length);
XBT_PUBLIC(double) xbt_graph_edge_get_length(xbt_edge_t e);
-XBT_PUBLIC(double *) xbt_graph_get_length_matrix(xbt_graph_t g);
-XBT_PUBLIC(void) xbt_graph_free_node(xbt_graph_t g, xbt_node_t n,
- void_f_pvoid_t node_free_function,
- void_f_pvoid_t edge_free_function);
-XBT_PUBLIC(void) xbt_graph_free_edge(xbt_graph_t g, xbt_edge_t e,
- void_f_pvoid_t free_function);
XBT_PUBLIC(void) xbt_graph_free_graph(xbt_graph_t g,
- void_f_pvoid_t node_free_function,
- void_f_pvoid_t edge_free_function,
- void_f_pvoid_t graph_free_function);
-
-XBT_PUBLIC(int) __xbt_find_in_dynar(xbt_dynar_t dynar, void *p);
+ void_f_pvoid_t node_free_function, void_f_pvoid_t edge_free_function, void_f_pvoid_t graph_free_function);
XBT_PUBLIC(xbt_dynar_t) xbt_graph_get_nodes(xbt_graph_t g);
XBT_PUBLIC(xbt_dynar_t) xbt_graph_get_edges(xbt_graph_t g);
XBT_PUBLIC(xbt_dynar_t) xbt_graph_node_get_outedges(xbt_node_t n);
XBT_PUBLIC(xbt_node_t) xbt_graph_edge_get_source(xbt_edge_t e);
XBT_PUBLIC(xbt_node_t) xbt_graph_edge_get_target(xbt_edge_t e);
-XBT_PUBLIC(xbt_graph_t) xbt_graph_read(const char *filename, void
- *(node_label_and_data) (xbt_node_t,
- const char
- *,
- const char
- *), void
- *(edge_label_and_data) (xbt_edge_t,
- const char
- *,
- const char
- *)
- );
-
-XBT_PUBLIC(void) xbt_graph_export_graphviz(xbt_graph_t g,
- const char *filename, const char
- *(node_name) (xbt_node_t), const char
- *(edge_name) (xbt_edge_t));
-XBT_PUBLIC(void) xbt_graph_export_graphxml(xbt_graph_t g,
- const char *filename, const char
- *(node_name) (xbt_node_t), const char
- *(edge_name) (xbt_edge_t), const char
- *(node_data_print) (void *), const char
- *(edge_data_print) (void *));
-XBT_PUBLIC(xbt_graph_t) xbt_graph_load (const char *filename);
-XBT_PUBLIC(void) xbt_graph_save (xbt_graph_t span,
- const char *filename,
- const char *(nname) (xbt_node_t),
- const char *(ename) (xbt_edge_t));
-
-/* Not implemented yet ! */
-/* void *xbt_graph_to_array(xbt_graph_t g); */
-XBT_PUBLIC(xbt_node_t *) xbt_graph_shortest_paths(xbt_graph_t g);
-
-
-
-/** @brief transforms the network structure of a directed acyclic graph given 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_PUBLIC(xbt_node_t *) xbt_graph_topo_sort(xbt_graph_t g);
-
-XBT_PUBLIC(xbt_edge_t *) xbt_graph_spanning_tree_prim(xbt_graph_t g);
-
-
-
-
-/** Convenient for loop : g is a graph, n a node, e an edge, b a bucket and i an item **/
-
-/* #define xbt_graph_foreachInNeighbor(v,n,i) \ */
-/* for(i=xbt_fifo_get_first_item((v)->in); \ */
-/* ((i)?(n=((xbt_edge_t)((xbt_fifo_get_item_content(i)) */
-/* )->src):(NULL));\ */
-/* i=xbt_fifo_get_next_item(i)) */
-/* #define xbt_graph_foreachOutNeighbor(v,n,i) \ */
-/* for(i=xbt_fifo_get_first_item((v)->out); \ */
-/* ((i)?(n=((xbt_edge_t)(xbt_fifo_get_item_content(i)))->dst):(NULL));\ */
-/* i=xbt_fifo_get_next_item(i)) */
-
+XBT_PUBLIC(void) xbt_graph_export_graphviz(xbt_graph_t g, const char *filename,
+ const char *(node_name) (xbt_node_t), const char *(edge_name) (xbt_edge_t));
SG_END_DECL()
#endif /* _XBT_GRAPH_H */
}
/** @brief add an edge to the given graph */
-xbt_edge_t xbt_graph_new_edge(xbt_graph_t g,
- xbt_node_t src, xbt_node_t dst, void *data)
+xbt_edge_t xbt_graph_new_edge(xbt_graph_t g, xbt_node_t src, xbt_node_t dst, void *data)
{
xbt_edge_t edge = NULL;
}
/** @brief Get the edge connecting src and dst */
-xbt_edge_t xbt_graph_get_edge(xbt_graph_t g, xbt_node_t src,
- xbt_node_t dst)
+xbt_edge_t xbt_graph_get_edge(xbt_graph_t g, xbt_node_t src, xbt_node_t dst)
{
xbt_edge_t edge;
unsigned int cursor;
}
-/** @brief remove the given node from the given graph */
-void xbt_graph_free_node(xbt_graph_t g, xbt_node_t n,
- void_f_pvoid_t node_free_function,
- void_f_pvoid_t edge_free_function)
-{
- unsigned long nbr;
- unsigned long i;
- unsigned int cursor = 0;
- xbt_node_t node = NULL;
- xbt_edge_t edge = NULL;
-
- nbr = xbt_dynar_length(g->edges);
- cursor = 0;
- for (i = 0; i < nbr; i++) {
- xbt_dynar_get_cpy(g->edges, cursor, &edge);
-
- if ((edge->dst == n) || (edge->src == n)) {
- xbt_graph_free_edge(g, edge, edge_free_function);
- } else
- cursor++;
- }
-
- if ((node_free_function) && (n->data))
- node_free_function(n->data);
-
- cursor = 0;
- xbt_dynar_foreach(g->nodes, cursor, node)
- if (node == n)
- xbt_dynar_cursor_rm(g->nodes, &cursor);
-
- xbt_dynar_free(&(n->in));
- xbt_dynar_free(&(n->out));
-
- free(n);
-
- return;
-}
-
-/** @brief remove the given edge from the given graph */
-void xbt_graph_free_edge(xbt_graph_t g, xbt_edge_t e,
- void_f_pvoid_t free_function)
-{
- int idx;
- unsigned int cursor = 0;
- xbt_edge_t edge = NULL;
-
- if ((free_function) && (e->data))
- free_function(e->data);
-
- xbt_dynar_foreach(g->edges, cursor, edge) {
- if (edge == e) {
- if (g->directed) {
- idx = __xbt_find_in_dynar(edge->dst->in, edge);
- xbt_dynar_remove_at(edge->dst->in, idx, NULL);
- } else { /* only the out field is used */
- idx = __xbt_find_in_dynar(edge->dst->out, edge);
- xbt_dynar_remove_at(edge->dst->out, idx, NULL);
- }
-
- idx = __xbt_find_in_dynar(edge->src->out, edge);
- xbt_dynar_remove_at(edge->src->out, idx, NULL);
-
- xbt_dynar_cursor_rm(g->edges, &cursor);
- free(edge);
- break;
- }
- }
-}
-
-int __xbt_find_in_dynar(xbt_dynar_t dynar, void *p)
-{
-
- unsigned int cursor = 0;
- void *tmp = NULL;
-
- xbt_dynar_foreach(dynar, cursor, tmp) {
- if (tmp == p)
- return cursor;
- }
- return -1;
-}
-
/** @brief Retrieve the graph's nodes as a dynar */
xbt_dynar_t xbt_graph_get_nodes(xbt_graph_t g)
{
return edge->length;
}
-
-/** @brief construct the adjacency matrix corresponding to the given graph
- *
- * The weights are the distances between nodes
- */
-double *xbt_graph_get_length_matrix(xbt_graph_t g)
-{
- unsigned int cursor = 0;
- unsigned int in_cursor = 0;
- unsigned long idx, i;
- unsigned long n;
- xbt_edge_t edge = NULL;
- xbt_node_t node = NULL;
- double *d = NULL;
-
-# define D(u,v) d[(u)*n+(v)]
- n = xbt_dynar_length(g->nodes);
-
- d = (double *) xbt_new0(double, n * n);
-
- for (i = 0; i < n * n; i++) {
- d[i] = -1.0;
- }
-
- xbt_dynar_foreach(g->nodes, cursor, node) {
- D(cursor, cursor) = 0;
-
- xbt_dynar_foreach(node->out, in_cursor, edge) {
- if (edge->dst == node)
- idx = __xbt_find_in_dynar(g->nodes, edge->src);
- else /*case of undirected graphs */
- idx = __xbt_find_in_dynar(g->nodes, edge->dst);
- D(cursor, idx) = edge->length;
- }
- }
-
-# undef D
-
- return d;
-}
-
/** @brief Floyd-Warshall algorithm for shortest path finding
*
* From wikipedia:
}
}
}
-
-
-
# undef P
# undef D
}
-/** @brief computes all-pairs shortest paths */
-xbt_node_t *xbt_graph_shortest_paths(xbt_graph_t g)
-{
- xbt_node_t *p;
- xbt_node_t *r;
- unsigned long i, j, k;
- unsigned long n;
-
- double *adj = NULL;
- double *d = NULL;
-
-# define P(u,v) p[(u)*n+(v)]
-# define R(u,v) r[(u)*n+(v)]
-
- n = xbt_dynar_length(g->nodes);
- adj = xbt_graph_get_length_matrix(g);
- d = xbt_new0(double, n * n);
- p = xbt_new0(xbt_node_t, n * n);
- r = xbt_new0(xbt_node_t, n * n);
-
- xbt_floyd_algorithm(g, adj, d, p);
-
- for (i = 0; i < n; i++) {
- for (j = 0; j < n; j++) {
- k = j;
-
- while ((P(i, k)) && (__xbt_find_in_dynar(g->nodes, P(i, k)) != i)) {
- k = __xbt_find_in_dynar(g->nodes, P(i, k));
- }
-
- if (P(i, j)) {
- R(i, j) = *((xbt_node_t *) xbt_dynar_get_ptr(g->nodes, k));
- }
- }
- }
-# undef R
-# undef P
-
- free(d);
- free(p);
- free(adj);
- return r;
-}
-
-/** @brief Extract a spanning tree of the given graph */
-xbt_edge_t *xbt_graph_spanning_tree_prim(xbt_graph_t g)
-{
- int tree_size = 0;
- int tree_size_max = xbt_dynar_length(g->nodes) - 1;
- xbt_edge_t *tree = xbt_new0(xbt_edge_t, tree_size_max);
- xbt_edge_t e, edge;
- xbt_node_t node = NULL;
- xbt_dynar_t edge_list = NULL;
- xbt_heap_t heap = xbt_heap_new(10, NULL);
- unsigned int cursor;
-
- xbt_assert(!(g->directed),
- "Spanning trees do not make sense on directed graphs");
-
- xbt_dynar_foreach(g->nodes, cursor, node) {
- node->xbtdata = NULL;
- }
-
- node = xbt_dynar_getfirst_as(g->nodes, xbt_node_t);
- node->xbtdata = (void *) 1;
- edge_list = node->out;
- xbt_dynar_foreach(edge_list, cursor, e)
- xbt_heap_push(heap, e, -(e->length));
-
- while ((edge = xbt_heap_pop(heap))) {
- if ((edge->src->xbtdata) && (edge->dst->xbtdata))
- continue;
- tree[tree_size++] = edge;
- if (!(edge->src->xbtdata)) {
- edge->src->xbtdata = (void *) 1;
- edge_list = edge->src->out;
- xbt_dynar_foreach(edge_list, cursor, e) {
- xbt_heap_push(heap, e, -(e->length));
- }
- } else {
- edge->dst->xbtdata = (void *) 1;
- edge_list = edge->dst->out;
- xbt_dynar_foreach(edge_list, cursor, e) {
- xbt_heap_push(heap, e, -(e->length));
- }
- }
- if (tree_size == tree_size_max)
- break;
- }
-
- xbt_heap_free(heap);
-
- return tree;
-}
-
-/** @brief Topological sort on the given graph
- *
- * From wikipedia:
- *
- * In graph theory, a topological sort of a directed acyclic graph (DAG) is
- * a linear ordering of its nodes which is compatible with the partial
- * order R induced on the nodes where x comes before y (xRy) if there's a
- * directed path from x to y in the DAG. An equivalent definition is that
- * each node comes before all nodes to which it has edges. Every DAG has at
- * least one topological sort, and may have many.
- */
-xbt_node_t *xbt_graph_topo_sort(xbt_graph_t g)
-{
-
- xbt_node_t *sorted;
- unsigned int cursor;
- int 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);
-
- xbt_dynar_foreach(g->nodes, cursor, node) {
- free(node->xbtdata);
- node->xbtdata = NULL;
- }
-
- return sorted;
-}
-
-/** @brief First-depth graph traversal */
-void xbt_graph_depth_visit(xbt_graph_t g, xbt_node_t n,
- xbt_node_t * sorted, int *idx)
-{
- unsigned int cursor;
- xbt_edge_t edge;
-
- if (*((int *) (n->xbtdata)) == ALREADY_EXPLORED)
- return;
- else if (*((int *) (n->xbtdata)) == CURRENTLY_EXPLORING)
- THROWF(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;
- }
-}
-
/** @brief Export the given graph in the GraphViz formatting for visualization */
void xbt_graph_export_graphviz(xbt_graph_t g, const char *filename,
const char *(node_name) (xbt_node_t),
fprintf(file, "}\n");
fclose(file);
}
-
-/** @brief Export the given graph in the GraphXML format */
-void xbt_graph_export_graphxml(xbt_graph_t g, const char *filename,
- const char *(node_name) (xbt_node_t),
- const char *(edge_name) (xbt_edge_t),
- const char *(node_data_print) (void *),
- const char *(edge_data_print) (void *))
-{
- unsigned int cursor = 0;
- xbt_node_t node = NULL;
- xbt_edge_t edge = NULL;
- FILE *file = NULL;
- const char *name = NULL;
-
- file = fopen(filename, "w");
- xbt_assert(file, "Failed to open %s \n", filename);
-
- fprintf(file, "<?xml version='1.0'?>\n");
- fprintf(file, "<!DOCTYPE graph SYSTEM \"graphxml.dtd\">\n");
- if (g->directed)
- fprintf(file, "<graph isDirected=\"true\">\n");
- else
- fprintf(file, "<graph isDirected=\"false\">\n");
- xbt_dynar_foreach(g->nodes, cursor, node) {
- fprintf(file, " <node name=\"%p\" ", node);
- if ((node_name) && ((name = node_name(node))))
- fprintf(file, "label=\"%s\" ", name);
- if ((node_data_print) && ((name = node_data_print(node->data))))
- fprintf(file, "data=\"%s\" ", name);
- fprintf(file, "/>\n");
- }
- xbt_dynar_foreach(g->edges, cursor, edge) {
- fprintf(file, " <edge source=\"%p\" target =\"%p\" ",
- edge->src, edge->dst);
- if ((edge_name) && ((name = edge_name(edge))))
- fprintf(file, "label=\"%s\" ", name);
- if (edge->length >= 0.0)
- fprintf(file, "length=\"%g\" ", edge->length);
- if ((edge_data_print) && ((name = edge_data_print(edge->data))))
- fprintf(file, "data=\"%s\" ", name);
- fprintf(file, "/>\n");
- }
- fprintf(file, "</graph>\n");
- fclose(file);
-}
-
-/** @brief Load a graph from a file (in the SimGrid Graph format) */
-xbt_graph_t xbt_graph_load (const char *filename)
-{
- FILE *file = NULL;
- ssize_t read;
- file = fopen (filename, "r");
- xbt_assert(file, "Failed to open %s \n", filename);
-
- xbt_dict_t nodes_dict = xbt_dict_new_homogeneous(NULL);
- xbt_graph_t ret = xbt_graph_new_graph (0, NULL);
-
- //read the number of nodes
- size_t size;
- char *nnodes_str = NULL;
- read = xbt_getline (&nnodes_str, &size, file);
- if (read == -1)
- THROWF(system_error, 0, "xbt_getline failed to read the number of nodes (errno = %d)", errno);
- int i, nnodes = atoi (nnodes_str);
- free (nnodes_str);
-
- //read all nodes
- for (i = 0; i < nnodes; i++){
- char *node_str = NULL;
- read = xbt_getline (&node_str, &size, file);
- if (read == -1)
- THROWF(system_error, 0, "xbt_getline failed to read all nodes (errno = %d)", errno);
- xbt_node_t n;
- char *name = xbt_strdup (node_str);
- xbt_str_subst (name, '\n', '\0', 0);
- n = xbt_graph_new_node (ret, name);
- xbt_dict_set (nodes_dict, name, n, NULL);
- free (node_str);
- }
-
- //read the number of edges
- char *nedges_str = NULL;
- read = xbt_getline (&nedges_str, &size, file);
- if (read == -1)
- THROWF(system_error, 0, "xbt_getline failed to read the number of edges (errno = %d)", errno);
- int nedges = atoi (nedges_str);
- free (nedges_str);
-
- //read all edges
- for (i = 0; i < nedges; i++){
- char *edge_str = NULL, edge_id[200], node_source[200], node_target[200];
- read = xbt_getline (&edge_str, &size, file);
- if (read == -1)
- THROWF(system_error, 0, "xbt_getline failed to read all edges (errno = %d)", errno);
- sscanf (edge_str, "%s %s %s", edge_id, node_source, node_target);
- free (edge_str);
- xbt_str_subst (edge_id, '\n', '\0', 0);
- xbt_str_subst (node_source, '\n', '\0', 0);
- xbt_str_subst (node_target, '\n', '\0', 0);
-
- xbt_node_t source = xbt_dict_get (nodes_dict, node_source);
- xbt_node_t target = xbt_dict_get (nodes_dict, node_target);
- xbt_graph_new_edge (ret, source, target, xbt_strdup(edge_id));
- }
- xbt_dict_free (&nodes_dict);
- return ret;
-}
-
-/** @brief Save a graph from a file (in the SimGrid Graph format) */
-void xbt_graph_save (xbt_graph_t span,
- const char *filename,
- const char *(nname) (xbt_node_t),
- const char *(ename) (xbt_edge_t))
-{
- FILE *file = NULL;
- file = fopen(filename, "w");
- xbt_assert(file, "Failed to open %s \n", filename);
-
- xbt_dynar_t nodes = xbt_graph_get_nodes (span);
- xbt_dynar_t edges = xbt_graph_get_edges (span);
- unsigned int cpt;
- xbt_node_t node;
- fprintf (file, "%lu\n", xbt_dynar_length (nodes));
- xbt_dynar_foreach (nodes, cpt, node) {
- if (nname){
- fprintf (file, "%s\n", nname(node));
- }else{
- fprintf (file, "%p\n", node);
- }
- }
- fprintf (file, "%lu\n", xbt_dynar_length (edges));
- xbt_edge_t edge;
- xbt_dynar_foreach (edges, cpt, edge) {
- xbt_node_t source = xbt_graph_edge_get_source (edge);
- xbt_node_t target = xbt_graph_edge_get_target (edge);
- if (ename){
- if (nname){
- fprintf (file, "%s %s %s\n", ename(edge), nname(source), nname(target));
- }else{
- fprintf (file, "%s %p %p\n", ename(edge), source, target);
- }
- }else{
- if (nname){
- fprintf (file, "%p %s %s\n", edge, nname(source), nname(target));
- }else{
- fprintf (file, "%p %p %p\n", edge, source, target);
- }
- }
- }
- fclose (file);
-}