src/xbt/graph.c

   1 /* a generic graph library.                                                 */
   2
   3 /* Copyright (c) 2006-2017. The SimGrid Team.
   4  * All rights reserved.                                                     */
   5
   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. */
   8
   9 #include "xbt/sysdep.h"
  10 #include "xbt/log.h"
  11 #include "xbt/graph.h"
  12 #include "xbt/dict.h"
  13
  14 #include <errno.h>
  15 #include <stdio.h>
  16 #include <stdlib.h>
  17
  18 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(xbt_graph, xbt, "Graph");
  19
  20 /** @brief Constructor
  21  *  @return a new graph
  22  */
  23 xbt_graph_t xbt_graph_new_graph(unsigned short int directed, void *data)
  24 {
  25   xbt_graph_t graph = xbt_new0(struct xbt_graph, 1);
  26   graph->directed = directed;
  27   graph->data = data;
  28   graph->nodes = xbt_dynar_new(sizeof(xbt_node_t), NULL);
  29   graph->edges = xbt_dynar_new(sizeof(xbt_edge_t), NULL);
  30
  31   return graph;
  32 }
  33
  34 /** @brief add a node to the given graph */
  35 xbt_node_t xbt_graph_new_node(xbt_graph_t g, void *data)
  36 {
  37   xbt_node_t node= xbt_new0(struct xbt_node, 1);
  38   node->data = data;
  39   if (g->directed)
  40     /* only the "out" field is used */
  41     node->in = xbt_dynar_new(sizeof(xbt_edge_t), NULL);
  42
  43   node->out = xbt_dynar_new(sizeof(xbt_edge_t), NULL);
  44   node->position_x = -1.0;
  45   node->position_y = -1.0;
  46
  47   xbt_dynar_push(g->nodes, &node);
  48
  49   return node;
  50 }
  51
  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)
  54 {
  55   xbt_edge_t edge = xbt_new0(struct xbt_edge, 1);
  56   xbt_dynar_push(src->out, &edge);
  57   if (g->directed)
  58     xbt_dynar_push(dst->in, &edge);
  59   else                          /* only the "out" field is used */
  60     xbt_dynar_push(dst->out, &edge);
  61
  62   edge->data = data;
  63   edge->src = src;
  64   edge->dst = dst;
  65
  66   xbt_dynar_push(g->edges, &edge);
  67
  68   return edge;
  69 }
  70
  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)
  73 {
  74   xbt_edge_t edge;
  75   unsigned int cursor;
  76
  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))
  80       return edge;
  81   }
  82   if (!g->directed) {
  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))
  86         return edge;
  87     }
  88   }
  89   return NULL;
  90 }
  91
  92 /** @brief Get the user data associated to a node */
  93 void *xbt_graph_node_get_data(xbt_node_t node)
  94 {
  95   return node->data;
  96 }
  97
  98 /** @brief Set the user data associated to a node */
  99 void xbt_graph_node_set_data(xbt_node_t node, void *data)
 100 {
 101   node->data = data;
 102 }
 103
 104 /** @brief Get the user data associated to a edge */
 105 void *xbt_graph_edge_get_data(xbt_edge_t edge)
 106 {
 107   return edge->data;
 108 }
 109
 110 /** @brief Set the user data associated to a edge */
 111 void xbt_graph_edge_set_data(xbt_edge_t edge, void *data)
 112 {
 113   edge->data = data;
 114 }
 115
 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
 121  *
 122  * Free the graph structure.
 123  */
 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)
 126 {
 127   unsigned int cursor;
 128   xbt_node_t node;
 129   xbt_edge_t edge;
 130
 131   xbt_dynar_foreach(g->edges, cursor, edge) {
 132     if (edge_free_function)
 133       edge_free_function(edge->data);
 134     free(edge);
 135   }
 136   xbt_dynar_free(&(g->edges));
 137
 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);
 143     free(node);
 144   }
 145   xbt_dynar_free(&(g->nodes));
 146
 147   if (graph_free_function)
 148     graph_free_function(g->data);
 149   free(g);
 150 }
 151
 152 /** @brief Retrieve the graph's nodes as a dynar */
 153 xbt_dynar_t xbt_graph_get_nodes(xbt_graph_t g)
 154 {
 155   return g->nodes;
 156 }
 157
 158 /** @brief Retrieve the graph's edges as a dynar */
 159 xbt_dynar_t xbt_graph_get_edges(xbt_graph_t g)
 160 {
 161   return g->edges;
 162 }
 163
 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)
 166 {
 167   return e->src;
 168 }
 169
 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)
 172 {
 173   return e->dst;
 174 }
 175
 176 /** @brief Retrieve the outgoing edges of the given node */
 177 xbt_dynar_t xbt_graph_node_get_outedges(xbt_node_t n)
 178 {
 179   return n->out;
 180 }