X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/4725d7a4bc5ac1fdae3e86222cdc23eaaf6fb226..91715e2f198242d378e33453014dd004fcf9f47e:/src/xbt/graph.c diff --git a/src/xbt/graph.c b/src/xbt/graph.c index 53341c83a6..2079dfc7da 100644 --- a/src/xbt/graph.c +++ b/src/xbt/graph.c @@ -1,9 +1,7 @@ -/* $Id$ */ - /* a generic graph library. */ -/* Copyright (c) 2006 Darina Dimitrova, Arnaud Legrand. */ -/* All rights reserved. */ +/* Copyright (c) 2006, 2007, 2008, 2009, 2010. The SimGrid Team. + * All rights reserved. */ /* This program is free software; you can redistribute it and/or modify it * under the terms of the license (GNU LGPL) which comes with this package. */ @@ -68,7 +66,7 @@ xbt_edge_t xbt_graph_new_edge(xbt_graph_t g, xbt_dynar_push(src->out, &edge); if (g->directed) xbt_dynar_push(dst->in, &edge); - else /* only the "out" field is used */ + else /* only the "out" field is used */ xbt_dynar_push(dst->out, &edge); edge->data = data; @@ -80,19 +78,22 @@ xbt_edge_t xbt_graph_new_edge(xbt_graph_t g, return edge; } -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; xbt_dynar_foreach(src->out, cursor, edge) { - DEBUG3("%p = %p--%p",edge,edge->src,edge->dst); - if((edge->src==src) && (edge->dst==dst)) return edge; + DEBUG3("%p = %p--%p", edge, edge->src, edge->dst); + if ((edge->src == src) && (edge->dst == dst)) + return edge; } - if(!g->directed) { + if (!g->directed) { xbt_dynar_foreach(src->out, cursor, edge) { - DEBUG3("%p = %p--%p",edge,edge->src,edge->dst); - if((edge->dst==src) && (edge->src==dst)) return edge; + DEBUG3("%p = %p--%p", edge, edge->src, edge->dst); + if ((edge->dst == src) && (edge->src == dst)) + return edge; } } return NULL; @@ -140,23 +141,23 @@ void xbt_graph_free_graph(xbt_graph_t g, xbt_dynar_free(&(node->out)); xbt_dynar_free(&(node->in)); if (node_free_function) - (*node_free_function)(node->data); + (*node_free_function) (node->data); } xbt_dynar_foreach(g->edges, cursor, edge) { if (edge_free_function) - (*edge_free_function)(edge->data); + (*edge_free_function) (edge->data); } xbt_dynar_foreach(g->nodes, cursor, node) - free(node); + free(node); xbt_dynar_free(&(g->nodes)); xbt_dynar_foreach(g->edges, cursor, edge) - free(edge); + free(edge); xbt_dynar_free(&(g->edges)); - if(graph_free_function) - (*graph_free_function)(g->data); + if (graph_free_function) + (*graph_free_function) (g->data); free(g); return; @@ -182,15 +183,15 @@ void xbt_graph_free_node(xbt_graph_t g, xbt_node_t n, if ((edge->dst == n) || (edge->src == n)) { xbt_graph_free_edge(g, edge, edge_free_function); } else - cursor ++; + cursor++; } if ((node_free_function) && (n->data)) - (*node_free_function)(n->data); + (*node_free_function) (n->data); cursor = 0; xbt_dynar_foreach(g->nodes, cursor, node) - if (node == n) + if (node == n) xbt_dynar_cursor_rm(g->nodes, &cursor); xbt_dynar_free(&(n->in)); @@ -210,14 +211,14 @@ void xbt_graph_free_edge(xbt_graph_t g, xbt_edge_t e, xbt_edge_t edge = NULL; if ((free_function) && (e->data)) - (*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 */ + } 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); } @@ -260,7 +261,6 @@ xbt_dynar_t xbt_graph_get_edges(xbt_graph_t g) /** @brief Retrieve the node at the source of the given edge */ xbt_node_t xbt_graph_edge_get_source(xbt_edge_t e) { - return e->src; } @@ -270,6 +270,11 @@ xbt_node_t xbt_graph_edge_get_target(xbt_edge_t e) return e->dst; } +/** @brief Retrieve the outgoing edges of the given node */ +xbt_dynar_t xbt_graph_node_get_outedges(xbt_node_t n) +{ + return n->out; +} /** @brief Set the weight of the given edge */ void xbt_graph_edge_set_length(xbt_edge_t e, double length) @@ -314,7 +319,7 @@ double *xbt_graph_get_length_matrix(xbt_graph_t g) 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 */ + else /*case of undirected graphs */ idx = __xbt_find_in_dynar(g->nodes, edge->dst); D(cursor, idx) = edge->length; } @@ -446,7 +451,7 @@ xbt_edge_t *xbt_graph_spanning_tree_prim(xbt_graph_t g) node->xbtdata = (void *) 1; edge_list = node->out; xbt_dynar_foreach(edge_list, cursor, e) - xbt_heap_push(heap, e, -(e->length)); + xbt_heap_push(heap, e, -(e->length)); while ((edge = xbt_heap_pop(heap))) { if ((edge->src->xbtdata) && (edge->dst->xbtdata)) @@ -500,10 +505,10 @@ xbt_node_t *xbt_graph_topo_sort(xbt_graph_t g) sorted = xbt_malloc(n * sizeof(xbt_node_t)); xbt_dynar_foreach(g->nodes, cursor, node) - node->xbtdata = xbt_new0(int, 1); + node->xbtdata = xbt_new0(int, 1); xbt_dynar_foreach(g->nodes, cursor, node) - xbt_graph_depth_visit(g, node, sorted, &idx); + xbt_graph_depth_visit(g, node, sorted, &idx); xbt_dynar_foreach(g->nodes, cursor, node) { free(node->xbtdata); @@ -541,9 +546,9 @@ static xbt_graph_t parsed_graph = NULL; static xbt_dict_t parsed_nodes = NULL; static void *(*__parse_node_label_and_data) (xbt_node_t, const char *, - const char *) = NULL; + const char *) = NULL; static void *(*__parse_edge_label_and_data) (xbt_edge_t, const char *, - const char *) = NULL; + const char *) = NULL; static void __parse_graph_begin(void) { @@ -583,9 +588,9 @@ static void __parse_edge(void) xbt_edge_t edge = xbt_graph_new_edge(parsed_graph, xbt_dict_get(parsed_nodes, A_graphxml_edge_source), - xbt_dict_get(parsed_nodes, - A_graphxml_edge_target), - NULL); + xbt_dict_get(parsed_nodes, + A_graphxml_edge_target), + NULL); if (__parse_edge_label_and_data) edge->data = __parse_edge_label_and_data(edge, A_graphxml_edge_label, @@ -601,11 +606,11 @@ static void __parse_edge(void) /** @brief Import a graph from a file following the GraphXML format */ 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 *)) + const char *, + const char *), + void *(*edge_label_and_data) (xbt_edge_t, + const char *, + const char *)) { xbt_graph_t graph = NULL; @@ -621,7 +626,7 @@ xbt_graph_t xbt_graph_read(const char *filename, ETag_graphxml_edge_fun = __parse_edge; xbt_graph_parse_open(filename); - xbt_assert1((!(*xbt_graph_parse)()), "Parse error in %s", filename); + xbt_assert1((!(*xbt_graph_parse) ()), "Parse error in %s", filename); xbt_graph_parse_close(); graph = parsed_graph;