eg_dgraph.c

Go to the documentation of this file.

/* EGlib "Efficient General Library" provides some basic structures and
 * algorithms commons in many optimization algorithms.
 *
 * Copyright (C) 2005 Daniel Espinoza and Marcos Goycoolea.
 * 
 * This library is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License as published by the
 * Free Software Foundation; either version 2.1 of the License, or (at your
 * option) any later version.
 *
 * This library is distributed in the hope that it will be useful, but 
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 
 * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public 
 * License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this library; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA 
 * */
#include "eg_dgraph.h"

/* this function re-enumerate the node-id from zero to n_nodes-1 */
int EGdGraphResetNodeId (EGdGraph_t * G)
{
  /* local variables */
  EGlistNode_t *cur_node;
  unsigned int cur_id = 0;

  /* reset max_id conuter */
  G->node_id_max = G->nodes->size;

  /* loop through all nodes in graph */
  for (cur_node = G->nodes->begin; cur_node; cur_node = cur_node->next)
  {
    ((EGdGraphNode_t *) cur_node->this)->id = cur_id++;
  }
  return 0;
}

/* this function re-enumerate the edges-id from zero to n_edges-1 */
int EGdGraphResetEdgeId (EGdGraph_t * G)
{
  /* local variables */
  EGlistNode_t *cur_node,
   *cur_edge;
  unsigned int cur_id = 0;

  /* reset max_id conuter */
  G->edge_id_max = G->nedges;

  /* loop through all nodes in graph */
  for (cur_node = G->nodes->begin; cur_node; cur_node = cur_node->next)
  {
    for (cur_edge = ((EGdGraphNode_t *) cur_node->this)->out_edges->begin;
         cur_edge; cur_edge = cur_edge->next)
    {
      ((EGdGraphEdge_t *) cur_edge->this)->id = cur_id++;
    }
  }
  return 0;
}

/* EGdGraphAttachNode :                                                       *
 *                                                                            *
 * Adds a node to graph *G but does not update the node's id.                 *
 * Also, it attaches all loose edges connected to 'n'. This function assumes  *
 * that all of the edges connected to 'n' are not attached to graph 'G' and   *
 * that bucle-edges are listed both in in_edges and out_edges. Finally, note  *
 * that this funtion will update the nedges counter of 'G'.                   */

int EGdGraphAttachNode (EGdGraph_t * G,
                        EGdGraphNode_t * n)
{

  EGlistNode_t *e_it;
  EGdGraphEdge_t *e;

  EGlistAttach (G->nodes, n->cn);

  /* We must incorporate the edges connected to 'n' to graph 'G'.             */
  for (e_it = n->in_edges->begin; e_it; e_it = e_it->next)
  {
    e = (EGdGraphEdge_t *) (e_it->this);

    /* If the edge is not a bucle, we add it to its tail node.                */
    if (e->tail != n)
    {
      EGlistAttach (e->tail->out_edges, e->tail_cn);
      G->nedges++;
    }
    /* If the edge is a bucle, we simply update the edge counter.             */
    else
      G->nedges++;
  }

  for (e_it = n->out_edges->begin; e_it; e_it = e_it->next)
  {
    e = (EGdGraphEdge_t *) (e_it->this);
    /* If the edge is a bucle-edge, we already attached it. Hence, we only    *
     * consider the case in which the edge is not a bucle.                    */
    if (e->head != n)
    {
      EGlistAttach (e->head->in_edges, e->head_cn);
      G->nedges++;
    }
  }

  return 0;

}

/* EGdGraphAttachEdge:                                                        *
 *                                                                            *
 * This function assumes that both ends of 'e' are in 'G' and that 'e' is not *
 * listed as incident to either the head or tail.                             */

int EGdGraphAttachEdge (EGdGraph_t * G,
                        EGdGraphEdge_t * e)
{

  int rval;

  G->nedges += 1;

  rval = EGlistAttach (e->head->in_edges, e->head_cn);
  CHECKRVAL (rval);
  rval = EGlistAttach (e->tail->out_edges, e->tail_cn);
  CHECKRVAL (rval);

  return 0;

}

/* EGdGraphUnattachNode                                                       *
 *                                                                            *
 * This function unattaches node n from the graph 'nodes' list. The arcs      *
 * that are incident to 'n' are removed from the lists of nodes corresponding *
 * to ends other than n. The edge counter is updated.                         */

int EGdGraphUnattachNode (EGdGraph_t * G,
                          EGdGraphNode_t * n)
{

  int rval;

  EGdGraphEdge_t *e;
  EGlistNode_t *e_it;

  rval = EGlistUnattach (G->nodes, n->cn);

  for (e_it = n->out_edges->begin; e_it; e_it = e_it->next)
  {
    e = (EGdGraphEdge_t *) (e_it->this);
    if (e->head != n)
    {
      EGlistUnattach (e->head->in_edges, e->head_cn);
      G->nedges -= 1;
    }
    else
      G->nedges -= 1;
  }

  for (e_it = n->in_edges->begin; e_it; e_it = e_it->next)
  {
    e = (EGdGraphEdge_t *) (e_it->this);
    if (e->tail != n)
    {
      EGlistUnattach (e->tail->out_edges, e->tail_cn);
      G->nedges -= 1;
    }
  }

  return 0;

}

/* EGdGraphUnattachEdge                                                       *
 *                                                                            *
 *
 *                                                                            */

int EGdGraphUnattachEdge (EGdGraph_t * G,
                          EGdGraphEdge_t * e)
{

  EGlistUnattach (e->head->in_edges, e->head_cn);
  EGlistUnattach (e->tail->out_edges, e->tail_cn);

  G->nedges -= 1;

  return 0;

}

/* EGdnewDGraph                                                               *
 *                                                                            *
 *
 *                                                                            */

EGdGraph_t *EGnewDGraph (EGmemPool_t * mem)
{

  EGdGraph_t *G;

  G = (EGdGraph_t *) EGmemPoolMalloc (mem, sizeof (EGdGraph_t));
  memset (G, 0, sizeof (EGdGraph_t));

  G->nodes = EGnewList (mem);
  G->mem = mem;
  G->node_id_max = 0;
  G->edge_id_max = 0;
  G->id = UINT_MAX;

  return G;

}

/* EGdnewDGraphNode                                                           *
 *                                                                            *
 *
 *                                                                            */

EGdGraphNode_t *EGnewDGraphNode (EGmemPool_t * mem)
{

  EGdGraphNode_t *n;
  n = (EGdGraphNode_t *) EGmemPoolMalloc (mem, sizeof (EGdGraphNode_t));

  n->cn = 0;
  n->data = 0;
  n->in_edges = EGnewList (mem);
  n->out_edges = EGnewList (mem);
  n->id = UINT_MAX;

  return (n);

}

/* EGdnewDGraphEdge                                                           *
 *                                                                            *
 *
 *                                                                            */

EGdGraphEdge_t *EGnewDGraphEdge (EGmemPool_t * mem)
{

  EGdGraphEdge_t *e;

  e = (EGdGraphEdge_t *) EGmemPoolMalloc (mem, sizeof (EGdGraphEdge_t));
  memset (e, 0, sizeof (EGdGraphEdge_t));

  e->id = UINT_MAX;

  return (e);

}

void EGfreeDGraphEdge (void *v,
                       EGmemPool_t * mem)
{
  EGmemPoolFree (v, sizeof (EGdGraphEdge_t), mem);
  return;
}

void EGfreeDGraphNode (void *v)
{
  EGmemPool_t *mem;
  EGdGraphNode_t *n;

  n = (EGdGraphNode_t *) (v);
  mem = n->in_edges->mempool;

  EGlistClearMP (n->out_edges, EGfreeDGraphEdge, mem);
  EGlistClearMP (n->in_edges, EGfreeDGraphEdge, mem);

  EGfreeList (n->in_edges);
  EGfreeList (n->out_edges);

  EGmemPoolFree (v, sizeof (EGdGraphNode_t), mem);

  return;
}

void EGfreeDGraph (void *v)
{
  EGmemPool_t *mem;
  EGdGraph_t *G;

  G = (EGdGraph_t *) (v);
  mem = G->mem;

  EGlistClear (G->nodes, EGfreeDGraphNode);
  EGfreeList (G->nodes);

  EGmemPoolFree (v, sizeof (EGdGraph_t), mem);

  return;
}

void EGdGraphClear (EGdGraph_t * G,
                    EGfree_f userFreeEdgeData,
                    EGfree_f userFreeNodeData,
                    EGfree_f userFreeGraphData)
{
  EGlistNode_t *n_it;
  EGdGraphNode_t *n;

  if (userFreeGraphData && G->data)
    userFreeGraphData (G->data);

  G->data = 0;

  while ((n_it = G->nodes->begin) != 0)
  {
    n = (EGdGraphNode_t *) (n_it->this);
    EGdGraphEraseNode (G, n, userFreeEdgeData, userFreeNodeData);
  }

  G->node_id_max = 0;
  G->edge_id_max = 0;

  return;

}

void EGdGraphClearMP (EGdGraph_t * G,
                      EGfreeMP_f userFreeEdgeDataMP,
                      EGfreeMP_f userFreeNodeDataMP,
                      EGfreeMP_f userFreeGraphDataMP,
                      EGmemPool_t * edge_data_mem,
                      EGmemPool_t * node_data_mem,
                      EGmemPool_t * graph_data_mem)
{

  EGlistNode_t *n_it;
  EGdGraphNode_t *n;

  if (userFreeGraphDataMP && G->data)
    userFreeGraphDataMP (G->data, graph_data_mem);

  G->data = 0;

  while ((n_it = G->nodes->begin) != 0)
  {
    n = (EGdGraphNode_t *) (n_it->this);
    EGdGraphEraseNodeMP (G, n, userFreeEdgeDataMP, userFreeNodeDataMP,
                         node_data_mem, edge_data_mem);
  }

  G->node_id_max = 0;
  G->edge_id_max = 0;

  return;

}

void EGdGraphEraseEdge (EGdGraph_t * G,
                        EGdGraphEdge_t * e,
                        EGfree_f userFreeEdgeData,
                        EGmemPool_t * mem)
{

  EGlist_t *out_list,
   *in_list;
  EGlistNode_t *e_hc,
   *e_tc;

  e_tc = e->tail_cn;
  e_hc = e->head_cn;

  if (userFreeEdgeData && e->data)
    userFreeEdgeData ((void *) (e->data));

  out_list = e->tail->out_edges;
  in_list = e->head->in_edges;

  EGlistEraseMP (out_list, e_tc, EGfreeDGraphEdge, mem);
  EGlistErase (in_list, e_hc, nullFree);

  G->nedges--;

  return;

}

void EGdGraphEraseEdgeMP (EGdGraph_t * G,
                          EGdGraphEdge_t * e,
                          EGfreeMP_f userFreeEdgeDataMP,
                          EGmemPool_t * edge_data_mem,
                          EGmemPool_t * mem)
{

  EGlist_t *in_list,
   *out_list;
  EGlistNode_t *e_hc,
   *e_tc;

  e_tc = e->tail_cn;
  e_hc = e->head_cn;

  if (userFreeEdgeDataMP && e->data)
    userFreeEdgeDataMP ((void *) (e->data), edge_data_mem);

  out_list = e->tail->out_edges;
  in_list = e->head->in_edges;

  EGlistEraseMP (out_list, e_tc, EGfreeDGraphEdge, mem);
  EGlistErase (in_list, e_hc, nullFree);

  G->nedges--;

  return;

}

void EGdGraphEraseNode (EGdGraph_t * G,
                        EGdGraphNode_t * n,
                        EGfree_f userFreeEdgeData,
                        EGfree_f userFreeNodeData)
{

  EGlistNode_t *n_it,
   *e_it;
  EGdGraphEdge_t *e;

  n_it = n->cn;

  if (userFreeNodeData && n->data)
    userFreeNodeData ((void *) (n->data));

  while ((e_it = n->in_edges->begin) != 0)
  {
    e = (EGdGraphEdge_t *) (e_it->this);
    EGdGraphEraseEdge (G, e, userFreeEdgeData, n->in_edges->mempool);
  }

  while ((e_it = n->out_edges->begin) != 0)
  {
    e = (EGdGraphEdge_t *) (e_it->this);
    EGdGraphEraseEdge (G, e, userFreeEdgeData, n->out_edges->mempool);
  }

  EGlistErase (G->nodes, n_it, EGfreeDGraphNode);

  return;

}

void EGdGraphEraseNodeMP (EGdGraph_t * G,
                          EGdGraphNode_t * n,
                          EGfreeMP_f userFreeEdgeDataMP,
                          EGfreeMP_f userFreeNodeDataMP,
                          EGmemPool_t * node_data_mem,
                          EGmemPool_t * edge_data_mem)
{

  EGlistNode_t *n_it,
   *e_it;
  EGdGraphEdge_t *e;

  n_it = n->cn;

  if (userFreeNodeDataMP && n->data)
    userFreeNodeDataMP ((void *) (n->data), node_data_mem);

  while ((e_it = n->in_edges->begin) != 0)
  {
    e = (EGdGraphEdge_t *) (e_it->this);
    EGdGraphEraseEdgeMP (G, e, userFreeEdgeDataMP, edge_data_mem,
                         n->in_edges->mempool);
  }

  while ((e_it = n->out_edges->begin) != 0)
  {
    e = (EGdGraphEdge_t *) (e_it->this);
    EGdGraphEraseEdgeMP (G, e, userFreeEdgeDataMP, edge_data_mem,
                         n->out_edges->mempool);
  }

  EGlistErase (G->nodes, n_it, EGfreeDGraphNode);

  return;

}

EGdGraphNode_t *EGdGraphAddNode (EGdGraph_t * G,
                                 void *data)
{
  EGdGraphNode_t *n;

  n = EGnewDGraphNode (G->mem);
  n->data = data;
  n->id = G->node_id_max++;

  EGlistPushBack (G->nodes, n);
  n->cn = G->nodes->end;

  return n;
}

EGdGraphEdge_t *EGdGraphAddEdge (EGdGraph_t * G,
                                 void *data,
                                 EGdGraphNode_t * head,
                                 EGdGraphNode_t * tail)
{
  EGdGraphEdge_t *e;

  e = EGnewDGraphEdge (G->mem);

  e->data = data;
  e->head = head;
  e->tail = tail;

  e->id = G->edge_id_max++;

  EGlistPushBack (e->head->in_edges, e);
  e->head_cn = e->head->in_edges->end;

  EGlistPushBack (e->tail->out_edges, e);
  e->tail_cn = e->tail->out_edges->end;

  G->nedges += 1;

  return e;
}

int EGdGraphDisplay (EGdGraph_t * G,
                     EGdisplay_f userDisplayDGraphData,
                     EGdisplay_f userDisplayNodeData,
                     EGdisplay_f userDisplayEdgeData,
                     FILE * file)
{

  /* local variables */
  EGlistNode_t *It1,
   *It2;
  EGdGraphNode_t *v;
  EGdGraphEdge_t *e;

  /* this function display an output for the graph */
  /* first main graph-related displays */
  fprintf (file, "\nGraph :%p Graph_id :%u\n nnodes :%u nedges :%u "
           "max_edge_id :%u max_node_id :%u",
           (void *) G, G->id, G->nodes->size, G->nedges, G->edge_id_max,
           G->node_id_max);
#if __EG_DGRAPH_CHECK__
  fprintf (file, " (%p){nodes=%p data=%p mem=%p id=%u nedges=%u node_id_max="
           "%u edge_id_max=%u} ", (void *) G, (void *) G->nodes,
           (void *) G->data, (void *) G->mem, G->id, G->nedges, G->node_id_max,
           G->edge_id_max);
#endif
  if (userDisplayDGraphData)
  {
    fprintf (file, "[");
    userDisplayDGraphData (G->data, file);
    fprintf (file, "]\n");
  }
  else
    fprintf (file, "\n");
  /* now node-related displays */
  for (It1 = G->nodes->begin; It1; It1 = It1->next)
  {
    v = (EGdGraphNode_t *) It1->this;
    fprintf (file, "Node %u: ", v->id);
#if __EG_DGRAPH_CHECK__
    fprintf (file, "(%p){out_edges=%p in_edges=%p cn=%p data=%p id=%u} ",
             (void *) v, (void *) v->out_edges, (void *) v->in_edges,
             (void *) v->cn, (void *) v->data, v->id);
#endif
    if (userDisplayNodeData)
    {
      fprintf (file, "[");
      userDisplayNodeData (v->data, file);
      fprintf (file, "]\n");
    }
    else
      fprintf (file, "\n");
    for (It2 = v->out_edges->begin; It2; It2 = It2->next)
    {
      e = (EGdGraphEdge_t *) It2->this;
      fprintf (file, "%u: (%u,%u) ", e->id, e->tail->id, e->head->id);
#if __EG_DGRAPH_CHECK__
      fprintf (file, "(%p){head=%p tail=%p head_cn=%p tail_cn=%p data=%p "
               "id=%u}\n", (void *) e, (void *) e->head, (void *) e->tail,
               (void *) e->head_cn, (void *) e->tail_cn, (void *) e->data,
               e->id);
#endif
      if (userDisplayEdgeData)
      {
        fprintf (file, "[");
        userDisplayEdgeData (e->data, file);
        fprintf (file, "] ");
      }
    }                           /* end for It2 */
    fprintf (file, "\n");
    for (It2 = v->in_edges->begin; It2; It2 = It2->next)
    {
      e = (EGdGraphEdge_t *) It2->this;
      fprintf (file, "%u: (%u,%u) ", e->id, e->tail->id, e->head->id);
#if __EG_DGRAPH_CHECK__
      fprintf (file, "(%p){head=%p tail=%p head_cn=%p tail_cn=%p data=%p "
               "id=%u}\n", (void *) e, (void *) e->head, (void *) e->tail,
               (void *) e->head_cn, (void *) e->tail_cn, (void *) e->data,
               e->id);
#endif
      if (userDisplayEdgeData)
      {
        fprintf (file, "[");
        userDisplayEdgeData (e->data, file);
        fprintf (file, "] ");
      }
    }                           /* end for It2 */
    fprintf (file, "\n");
  }                             /* end for It1 */

  /* ending */
  return 0;
}

---