src/xbt/graph.c

   1 /*      $Id$     */
   2
   3 /* a generic graph library.                                                 */
   4
   5 /* Copyright (c) 2006 Darina Dimitrova, Arnaud Legrand.
   6    All rights reserved.                  */
   7
   8 /* This program is free software; you can redistribute it and/or modify it
   9  * under the terms of the license (GNU LGPL) which comes with this package. */
  10
  11 #include "xbt/sysdep.h"
  12 #include "xbt/log.h"
  13 #include "xbt/graph.h"
  14 #include "graph_private.h"
  15 #include "xbt/graphxml_parse.h"
  16
  17 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(graph,xbt,"Graph");
  18
  19 /** Constructor
  20  * \return a new graph
  21  */
  22 xbt_graph_t xbt_graph_new_graph(unsigned short int directed, void *data)
  23 {
  24   xbt_graph_t graph=NULL;
  25   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), free);
  29   graph->edges= xbt_dynar_new(sizeof(xbt_edge_t), free);
  30
  31   return graph;
  32 }
  33
  34 xbt_node_t xbt_graph_new_node(xbt_graph_t g, void *data)
  35 {
  36   xbt_node_t node=NULL;
  37   node=xbt_new0(struct xbt_node,1);
  38   node->data=data;
  39   node->in=xbt_dynar_new(sizeof(xbt_node_t), free);
  40   node->out=xbt_dynar_new(sizeof(xbt_node_t), free);
  41   xbt_dynar_push(g->nodes,node);
  42
  43   return node;
  44 }
  45
  46
  47 xbt_edge_t xbt_graph_new_edge(xbt_graph_t g,
  48                              xbt_node_t src, xbt_node_t dst, void *data)
  49 {
  50   xbt_edge_t edge=NULL;
  51
  52   edge=xbt_new0(struct xbt_edge,1);
  53   xbt_dynar_push(src->out,edge);
  54   xbt_dynar_push(dst->in,edge);
  55   edge->data=data;
  56   edge->src=src;
  57   edge->dst=dst;
  58   if(!g->directed)
  59    {
  60      xbt_dynar_push(src->in,edge);
  61      xbt_dynar_push(dst->out,edge);
  62    }
  63  xbt_dynar_push(g->edges,edge);
  64
  65  return edge;
  66 }
  67
  68
  69 /** Destructor
  70  * \param l poor victim
  71  *
  72  * Free the graph structure.
  73  */
  74 void xbt_graph_free_graph(xbt_graph_t g,
  75                           void node_free_function(void * ptr),
  76                           void edge_free_function(void * ptr),
  77                           void graph_free_function(void * ptr))
  78 {
  79   int cursor;
  80   xbt_node_t node=NULL;
  81   xbt_edge_t edge=NULL;
  82
  83   xbt_dynar_foreach(g->nodes,cursor,node)
  84     xbt_graph_remove_node(g,node,node_free_function);
  85
  86   xbt_assert0(!xbt_dynar_length(g->edges),
  87               "Damnit, there are some remaining edges!");
  88
  89   xbt_dynar_foreach(g->edges,cursor,edge)
  90       xbt_graph_remove_edge(g,edge,edge_free_function);
  91
  92   xbt_dynar_free(&(g->nodes));
  93   xbt_dynar_free(&(g->edges));
  94
  95 /*  void xbt_dynar_free(g->edges); */
  96
  97
  98   return;
  99 }
 100
 101 void xbt_graph_remove_node(xbt_graph_t g, xbt_node_t n, void free_function(void * ptr))
 102 {
 103   int cursor;
 104   xbt_node_t node=NULL;
 105
 106   if ((free_function)&&(n->data))
 107    free_function(n->data);
 108   xbt_dynar_free_container(&(n->in));
 109   xbt_dynar_free_container(&(n->out));
 110   xbt_dynar_foreach(g->nodes,cursor,node)
 111     {
 112       if (node==n)
 113         xbt_dynar_cursor_rm(g->nodes,&cursor);
 114
 115     }
 116   return;
 117
 118 }
 119 void xbt_graph_remove_edge(xbt_graph_t g, xbt_edge_t e, void free_function(void * ptr))
 120 {
 121    int cursor=0;
 122    xbt_edge_t edge=NULL;
 123    xbt_node_t node=NULL;
 124    xbt_node_t temp=NULL;
 125
 126    if ((free_function)&&(e->data))
 127      free_function(e->data);
 128    xbt_dynar_foreach(g->nodes,cursor,node)
 129      {
 130        if (node==e->src)
 131          xbt_dynar_pop(node->out,temp);
 132        if (g->directed)
 133          xbt_dynar_pop(node->in,temp);
 134
 135      }
 136    node=NULL;
 137    cursor=0;
 138    xbt_dynar_foreach(g->nodes,cursor,node)
 139      {
 140         if (node==e->dst)
 141           xbt_dynar_pop(node->in,temp);
 142         if (g->directed)
 143           xbt_dynar_pop(node->out,temp);
 144
 145      }
 146    cursor=0;
 147    xbt_dynar_foreach(g->edges,cursor,edge)
 148      if (edge==e)
 149        {
 150          xbt_dynar_cursor_rm(g->edges,&cursor);
 151          break;
 152        }
 153
 154 }
 155
 156 static xbt_graph_t parsed_graph=NULL;
 157
 158 static void  __parse_graph_begin(void) {
 159   DEBUG0("<graph>");
 160 }
 161 static void  __parse_graph_end(void) {
 162   DEBUG0("</graph>");
 163 }
 164 static void __parse_node(void) {
 165   DEBUG1("<node label=\"%s\"/>",A_node_name);
 166 }
 167 static void __parse_edge(void) {
 168   DEBUG2("<edge source=\"%s\" target=\"%s\"/>",A_edge_source,A_edge_target);
 169 }
 170
 171 xbt_graph_t xbt_graph_read(const char *filename)
 172 {
 173   xbt_graph_t graph = xbt_graph_new_graph(1,NULL);
 174
 175   parsed_graph = graph;
 176
 177   xbt_graph_parse_reset_parser();
 178
 179   STag_graph_fun = __parse_graph_begin;
 180   ETag_graph_fun = __parse_graph_end;
 181   ETag_node_fun = __parse_node;
 182   ETag_edge_fun = __parse_edge;
 183
 184   xbt_graph_parse_open(filename);
 185   xbt_assert1((!xbt_graph_parse()),"Parse error in %s",filename);
 186   xbt_graph_parse_close();
 187
 188   parsed_graph = NULL;
 189
 190   return graph;
 191 }