1 /* a generic graph library. */
3 /* Copyright (c) 2006-2017. The SimGrid Team.
4 * All rights reserved. */
6 /* This program is free software; you can redistribute it and/or modify it
7 * under the terms of the license (GNU LGPL) which comes with this package. */
9 #include "xbt/sysdep.h"
11 #include "xbt/graph.h"
18 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(xbt_graph, xbt, "Graph");
20 /** @brief Constructor
23 xbt_graph_t xbt_graph_new_graph(unsigned short int directed, void *data)
25 xbt_graph_t graph = xbt_new0(struct xbt_graph, 1);
26 graph->directed = directed;
28 graph->nodes = xbt_dynar_new(sizeof(xbt_node_t), NULL);
29 graph->edges = xbt_dynar_new(sizeof(xbt_edge_t), NULL);
34 /** @brief add a node to the given graph */
35 xbt_node_t xbt_graph_new_node(xbt_graph_t g, void *data)
37 xbt_node_t node= xbt_new0(struct xbt_node, 1);
40 /* only the "out" field is used */
41 node->in = xbt_dynar_new(sizeof(xbt_edge_t), NULL);
43 node->out = xbt_dynar_new(sizeof(xbt_edge_t), NULL);
44 node->position_x = -1.0;
45 node->position_y = -1.0;
47 xbt_dynar_push(g->nodes, &node);
52 /** @brief add an edge to the given graph */
53 xbt_edge_t xbt_graph_new_edge(xbt_graph_t g, xbt_node_t src, xbt_node_t dst, void *data)
55 xbt_edge_t edge = xbt_new0(struct xbt_edge, 1);
56 xbt_dynar_push(src->out, &edge);
58 xbt_dynar_push(dst->in, &edge);
59 else /* only the "out" field is used */
60 xbt_dynar_push(dst->out, &edge);
66 xbt_dynar_push(g->edges, &edge);
71 /** @brief Get the edge connecting src and dst */
72 xbt_edge_t xbt_graph_get_edge(xbt_graph_t g, xbt_node_t src, xbt_node_t dst)
77 xbt_dynar_foreach(src->out, cursor, edge) {
78 XBT_DEBUG("%p = %p--%p", edge, edge->src, edge->dst);
79 if ((edge->src == src) && (edge->dst == dst))
83 xbt_dynar_foreach(src->out, cursor, edge) {
84 XBT_DEBUG("%p = %p--%p", edge, edge->src, edge->dst);
85 if ((edge->dst == src) && (edge->src == dst))
92 /** @brief Get the user data associated to a node */
93 void *xbt_graph_node_get_data(xbt_node_t node)
98 /** @brief Set the user data associated to a node */
99 void xbt_graph_node_set_data(xbt_node_t node, void *data)
104 /** @brief Get the user data associated to a edge */
105 void *xbt_graph_edge_get_data(xbt_edge_t edge)
110 /** @brief Set the user data associated to a edge */
111 void xbt_graph_edge_set_data(xbt_edge_t edge, void *data)
116 /** @brief Destructor
117 * @param g: poor victim
118 * @param node_free_function: function to use to free data associated to each node
119 * @param edge_free_function: function to use to free data associated to each edge
120 * @param graph_free_function: function to use to free data associated to g
122 * Free the graph structure.
124 void xbt_graph_free_graph(xbt_graph_t g, void_f_pvoid_t node_free_function, void_f_pvoid_t edge_free_function,
125 void_f_pvoid_t graph_free_function)
131 xbt_dynar_foreach(g->edges, cursor, edge) {
132 if (edge_free_function)
133 edge_free_function(edge->data);
136 xbt_dynar_free(&(g->edges));
138 xbt_dynar_foreach(g->nodes, cursor, node) {
139 xbt_dynar_free(&(node->out));
140 xbt_dynar_free(&(node->in));
141 if (node_free_function)
142 node_free_function(node->data);
145 xbt_dynar_free(&(g->nodes));
147 if (graph_free_function)
148 graph_free_function(g->data);
152 /** @brief Retrieve the graph's nodes as a dynar */
153 xbt_dynar_t xbt_graph_get_nodes(xbt_graph_t g)
158 /** @brief Retrieve the graph's edges as a dynar */
159 xbt_dynar_t xbt_graph_get_edges(xbt_graph_t g)
164 /** @brief Retrieve the node at the source of the given edge */
165 xbt_node_t xbt_graph_edge_get_source(xbt_edge_t e)
170 /** @brief Retrieve the node being the target of the given edge */
171 xbt_node_t xbt_graph_edge_get_target(xbt_edge_t e)
176 /** @brief Retrieve the outgoing edges of the given node */
177 xbt_dynar_t xbt_graph_node_get_outedges(xbt_node_t n)