eg_dgraph.h

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 
 * */
/* ========================================================================= */
/** Implementation of basic digraph support, the idea is that this structure
 * should be flexible enough to support fast graph algorithm.
 *
 * 2003-07-02 - First implementation (Marcos).
 *
 * */
/* ========================================================================= */

#ifndef _EGdGraph
#define _EGdGraph
#include <stdio.h>
#include <limits.h>
#include <stddef.h>
#include "eg_config.h"
#include "eg_macros.h"
#include "eg_io.h"
#include "eg_list.h"
#include "eg_listint.h"
#include "eg_mempool.h"

typedef struct
{
  EGlist_t *in_edges;
  EGlist_t *out_edges;
  EGlistNode_t *cn;
  void *data;
  unsigned int id;
}
EGdGraphNode_t;

typedef struct
{
  EGdGraphNode_t *head;
  EGdGraphNode_t *tail;
  EGlistNode_t *head_cn,
   *tail_cn;
  void *data;
  unsigned int id;
}
EGdGraphEdge_t;

typedef struct
{
  EGlist_t *nodes;
  void *data;
  EGmemPool_t *mem;
  unsigned int id;
  unsigned int nedges;
  unsigned int node_id_max;
  unsigned int edge_id_max;
}
EGdGraph_t;

#define __EG_DGRAPH_CHECK__ 0

int EGdGraphAttachNode (EGdGraph_t * G,
                        EGdGraphNode_t * n);
int EGdGraphAttachEdge (EGdGraph_t * G,
                        EGdGraphEdge_t * e);

int EGdGraphUnattachNode (EGdGraph_t * G,
                          EGdGraphNode_t * n);
int EGdGraphUnattachEdge (EGdGraph_t * G,
                          EGdGraphEdge_t * e);

EGdGraph_t *EGnewDGraph (EGmemPool_t * mem);
EGdGraphNode_t *EGnewDGraphNode (EGmemPool_t * mem);
EGdGraphEdge_t *EGnewDGraphEdge (EGmemPool_t * mem);

void EGfreeDGraph (void *v);
void EGfreeDGraphNode (void *v);
void EGfreeDGraphEdge (void *v,
                       EGmemPool_t * mem);

void EGdGraphClear (EGdGraph_t * G,
                    EGfree_f userFreeEdgeData,
                    EGfree_f userFreeNodeData,
                    EGfree_f userFreeGraphData);

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);

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

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

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

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

EGdGraphNode_t *EGdGraphAddNode (EGdGraph_t * G,
                                 void *ndata);

EGdGraphEdge_t *EGdGraphAddEdge (EGdGraph_t * G,
                                 void *edata,
                                 EGdGraphNode_t * head,
                                 EGdGraphNode_t * tail);

int EGdGraphResetNodeId (EGdGraph_t * G);
int EGdGraphResetEdgeId (EGdGraph_t * G);

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


#endif

---