eg_util.c

Go to the documentation of this file.

#include "eg_util.h"
/* load a graph into cook's format but reading from a binary file, the memory 
 * is not managed through EGmemPool, we might want to change that later on */
int loadBGraph (const char *file,
                int *nNodes,
                int *nEdges,
                int **edges,
                double **weight)
{
  /* local variables */
  FILE *in;
  int status,
    i;

  /* set-up */
  in = fopen (file, "rb");
  TEST (!in, "in loadGraph, can't open input file");

  /* reading parameters */
  status = fread (nNodes, sizeof (int), 1, in);
  TEST (status != 1, "in loadGraph, can't read from input file");
  status = fread (nEdges, sizeof (int), 1, in);
  TEST (status != 1, "in loadGraph, can't read from input file");
  *edges = (int *) malloc (sizeof (int) * (*nEdges) * 2);
  *weight = (double *) malloc (sizeof (double) * (*nEdges));
  TEST (!*edges || !*weight, "in loadGraph, not enough memory");

  for (i = 0; i < *nEdges; i++)
  {
    status = fread (*edges + 2 * i, sizeof (int), 2, in);
    TEST (status != 2, "in loadGraph, can't read from input file");
    status = fread (*weight + i, sizeof (double), 1, in);
    TEST (status != 1, "in loadGraph, can't read from input file");
  }

  fclose (in);

  return 0;
}

/* load a graph into cook's format, the memory is not managed through EGmemPool,
 * we might want to change that later on */
int loadGraph (const char *file,
               int *nNodes,
               int *nEdges,
               int **edges,
               double **weight)
{
  /* local variables */
  FILE *in;
  int status,
    i;

  /* set-up */
  in = fopen (file, "r");
  TEST (!in, "in loadGraph, can't open input file");

  /* reading parameters */
  status = fscanf (in, "%d%d", nNodes, nEdges);
  TEST (status != 2, "in loadGraph, can't read from input file");

  *edges = (int *) malloc (sizeof (int) * (*nEdges) * 2);
  *weight = (double *) malloc (sizeof (double) * (*nEdges));
  TEST (!*edges, "in loadGraph, not enough memory");

  for (i = 0; i < *nEdges; i++)
  {
    status =
      fscanf (in, "%d%d%lf", *edges + 2 * i, *edges + 2 * i + 1, *weight + i);
    TEST (status != 3, "in loadGraph, can't read from input file");
  }

  fclose (in);

  return 0;
}

int saveGraph (const char *file_name,
               int const nnodes,
               int const nedges,
               int const *const edges,
               double const *const weight)
{

  FILE *logFile;
  int i;

  logFile = fopen (file_name, "w");
  fprintf (logFile, "%d %d\n", nnodes, nedges);
  for (i = 0; i < nedges; i++)
    fprintf (logFile, "%d %d %lf\n", edges[2 * i], edges[2 * i + 1], weight[i]);

  fclose (logFile);

  return 0;

}

int saveSubGraph (const char *file_name,
                  int nnodes,
                  int nsubedges,
                  int *edges,
                  int *subedges,
                  double *weight)
{

  FILE *logFile;
  int i;

  logFile = fopen (file_name, "w");
  fprintf (logFile, "%d %d\n", nnodes, nsubedges);
  for (i = 0; i < nsubedges; i++)
    fprintf (logFile, "%d %d %lf\n", edges[2 * subedges[i]],
             edges[2 * subedges[i] + 1], weight ? weight[i] : 0.0);

  fclose (logFile);

  return 0;

}

int saveBgraph (const char *file_name,
                int nnodes,
                int nedges,
                int *edges,
                double *weight)
{

  FILE *logFile;
  int i;

#if DISPLAY_MODE
  fprintf (stdout, "Saving graph (binary format) to file %s ... ", file_name);
  fflush (stdout);
#endif

  logFile = fopen (file_name, "wb+");
  fwrite (&nnodes, sizeof (int), 1, logFile);
  fwrite (&nedges, sizeof (int), 1, logFile);
  for (i = 0; i < nedges; i++)
  {
    fwrite (edges + (2 * i), sizeof (int), 1, logFile);
    fwrite (edges + (2 * i) + 1, sizeof (int), 1, logFile);
    fwrite (weight + i, sizeof (double), 1, logFile);
  }
  fclose (logFile);

#if DISPLAY_MODE
  fprintf (stdout, "done.\n");
  fflush (stdout);
#endif

  return 0;

}

/* recieve a graph through a socket */
int EGreceiveRealGraph (CC_SFILE * s,
                        EGdGraph_t ** biDualG,
                        EGmemPool_t * mem)
{
  /* local vars */
  int status;
  register unsigned int i;
  unsigned int nnodes,
    nedges,
    tail,
    head;
  EGdGraphNode_t **nodes;
  EGmengerEdgeData_t **edata;
  double dtmp;
  EGmengerNodeData_t *lndata;

  /* read number of nodes and edges */
  status = CCutil_sread_uint (s, &nnodes);
  CHECKRVAL (status);
  status = CCutil_sread_uint (s, &nedges);
  CHECKRVAL (status);
  MESSAGE (1, "\tnnodes = %d\n\tnedges=%d\n\t", nnodes, nedges);
  /* look for memory */
  *biDualG = EGnewDGraph (mem);
  nodes =
    (EGdGraphNode_t **) EGmemPoolMalloc (mem,
                                         sizeof (EGdGraphNode_t *) * nnodes);
  edata =
    (EGmengerEdgeData_t **) EGmemPoolMalloc (mem,
                                             sizeof (EGmengerEdgeData_t *) *
                                             nedges);
  for (i = 0; i < nnodes; i++)
  {
    lndata = EGnewMengerNodeData (mem);
    nodes[i] = EGdGraphAddNode (*biDualG, lndata);
  }

  for (i = 0; i < nedges; i++)
  {
    status = CCutil_sread_uint (s, &tail);
    CHECKRVAL (status);
    status = CCutil_sread_uint (s, &head);
    CHECKRVAL (status);
    edata[i] = EGnewMengerEdgeData (mem);
    EGdGraphAddEdge (*biDualG, edata[i], nodes[head], nodes[tail]);
  }
  for (i = 0; i < nedges; i++)
  {
    status = CCutil_sread_double (s, &dtmp);
    edata[i]->cost = EGdijkstraToCost (dtmp);
    TESTL (1, dtmp < 0, "edge weight our of bounds edge %u value %lf ", i,
           dtmp);
    CHECKRVAL (status);
  }

  /* clean up */
  EGmemPoolFree (nodes, sizeof (EGdGraphNode_t *) * nnodes, mem);
  EGmemPoolFree (edata, sizeof (EGmengerEdgeData_t *) * nedges, mem);
  return 0;
}

/* recieve a graph through a socket */
int EGsendRealGraph (CC_SFILE * s,
                     EGdGraph_t * biDualG,
                     EGdGraphEdge_t *** dedges,
                     EGdGraphNode_t *** dnodes,
                     EGmemPool_t * mem)
{
  /* local vars */
  int status;
  EGdGraphNode_t *cnode;
  EGlistNode_t *lIt,
   *eIt;
  int edge_count = 0;

  /* preset the values */
  *dnodes =
    (EGdGraphNode_t **) EGmemPoolMalloc (mem,
                                         sizeof (EGdGraphNode_t *) *
                                         biDualG->nodes->size);
  *dedges =
    (EGdGraphEdge_t **) EGmemPoolMalloc (mem,
                                         sizeof (EGdGraphEdge_t *) *
                                         biDualG->nedges);

  /* read number of nodes and edges */
  WARNINGL (1, 1, "assuming contiguous and unique ID for nodes");
  status = CCutil_swrite_uint (s, biDualG->nodes->size);
  CHECKRVAL (status);
  MESSAGE (10, "send nnodes=%u", biDualG->nodes->size);
  status = CCutil_swrite_uint (s, biDualG->nedges);
  CHECKRVAL (status);
  MESSAGE (10, "send nedges=%u", biDualG->nedges);
  for (lIt = biDualG->nodes->begin; lIt; lIt = lIt->next)
  {
    cnode = (EGdGraphNode_t *) lIt->this;
    (*dnodes)[cnode->id] = cnode;
    for (eIt = cnode->out_edges->begin; eIt; eIt = eIt->next)
    {
      (*dedges)[edge_count++] = (EGdGraphEdge_t *) (eIt->this);
      status =
        CCutil_swrite_uint (s, ((EGdGraphEdge_t *) (eIt->this))->tail->id);
      CHECKRVAL (status);
      status =
        CCutil_swrite_uint (s, ((EGdGraphEdge_t *) (eIt->this))->head->id);
      CHECKRVAL (status);
    }
  }
  for (lIt = biDualG->nodes->begin; lIt; lIt = lIt->next)
  {
    cnode = (EGdGraphNode_t *) lIt->this;
    for (eIt = cnode->out_edges->begin; eIt; eIt = eIt->next)
    {
      status =
        CCutil_swrite_double (s,
                              EGdijkstraCostToLf (((EGmengerEdgeData_t
                                                    *) (((EGdGraphEdge_t
                                                          *) (eIt->this))->
                                                        data))->cost));
      CHECKRVAL (status);
    }
  }

  return 0;
}

/* recieve a graph through a socket */
int EGreceiveNetGraph (CC_SFILE * s,
                       unsigned int *nnodes,
                       unsigned int *nedges,
                       unsigned int **edges,
                       double **weight,
                       EGmemPool_t * mem)
{
  /* local vars */
  int status;
  register unsigned int i;

  /* preset the values */
  *nedges = 0;
  *nnodes = 0;
  *edges = 0;
  *weight = 0;

  /* read number of nodes and edges */
  status = CCutil_sread_uint (s, nnodes);
  CHECKRVAL (status);
  status = CCutil_sread_uint (s, nedges);
  CHECKRVAL (status);
#if CHECK_MODE
  TEST (*nnodes < 2
        || *nedges < 1, "empty or trivial graph, nnodes=%d, nedges=%d", *nnodes,
        *nedges);
#endif
  *edges =
    (unsigned int *) EGmemPoolMalloc (mem,
                                      sizeof (unsigned int) * (*nedges) * 2);
  *weight = (double *) EGmemPoolMalloc (mem, sizeof (double) * (*nedges));
  for (i = 0; i < *nedges; i++)
  {
    status = CCutil_sread_uint (s, (*edges) + (i << 1));
    CHECKRVAL (status);
    status = CCutil_sread_uint (s, (*edges) + ((i << 1) | 1));
    CHECKRVAL (status);
#if CHECK_MODE
    TEST ((*edges)[i << 1] < 0 || (*edges)[i << 1] >= *nnodes ||
          (*edges)[(i << 1) | 1] < 0 || (*edges)[(i << 1) | 1] >= *nnodes,
          "edge end out of range %d (%d %d)", i, (*edges)[i << 1],
          (*edges)[(i << 1) | 1]);
#endif
  }
  for (i = 0; i < *nedges; i++)
  {
    status = CCutil_sread_double (s, (*weight) + i);
    CHECKRVAL (status);
  }

  return 0;
}

/* recieve a graph through a socket */
int EGsendNetGraph (CC_SFILE * s,
                    unsigned int nnodes,
                    unsigned int nedges,
                    unsigned int *edges,
                    double *weight)
{
  /* local vars */
  int status;
  register unsigned int i;

  /* preset the values */

  /* read number of nodes and edges */
  status = CCutil_swrite_uint (s, nnodes);
  CHECKRVAL (status);
  status = CCutil_swrite_uint (s, nedges);
  CHECKRVAL (status);
  for (i = 0; i < nedges; i++)
  {
    status = CCutil_swrite_uint (s, edges[i << 1]);
    CHECKRVAL (status);
    status = CCutil_swrite_uint (s, edges[(i << 1) | 1]);
    CHECKRVAL (status);
  }
  for (i = 0; i < nedges; i++)
  {
    status = CCutil_swrite_double (s, weight[i]);
    CHECKRVAL (status);
  }

  return 0;
}

/* send dominoes */
int EGreceiveNetDomino (CC_SFILE * s,
                        EGnetDdom_t ** ddom,
                        EGmemPool_t * mem)
{
  /* local vars */
  int status,
    pth;
  register unsigned int i;

  /* reset values */
  *ddom = (EGnetDdom_t *) EGmemPoolMalloc (mem, sizeof (EGnetDdom_t));
  memset (*ddom, 0, sizeof (EGnetDdom_t));

  /* start reading */
  status = CCutil_sread_uint (s, &((*ddom)->s));
  CHECKRVAL (status);
  status = CCutil_sread_uint (s, &((*ddom)->t));
  CHECKRVAL (status);
  status = CCutil_sread_double (s, &((*ddom)->value));
  CHECKRVAL (status);

  /* look for memory */
  (*ddom)->npath =
    (unsigned int *) EGmemPoolMalloc (mem, sizeof (unsigned int) * 3);
  (*ddom)->path =
    (unsigned int **) EGmemPoolMalloc (mem, sizeof (unsigned int *) * 3);

  /* read path lengths */
  status = CCutil_sread_uint (s, &((*ddom)->npath[0]));
  CHECKRVAL (status);
  status = CCutil_sread_uint (s, &((*ddom)->npath[1]));
  CHECKRVAL (status);
  status = CCutil_sread_uint (s, &((*ddom)->npath[2]));
  CHECKRVAL (status);

  /* read all paths */
  for (pth = 0; pth < 3; pth++)
  {
    (*ddom)->path[pth] =
      (unsigned int *) EGmemPoolMalloc (mem,
                                        sizeof (unsigned int) *
                                        ((*ddom)->npath[pth]));
    for (i = 0; i < (*ddom)->npath[pth]; i++)
    {
      status = CCutil_sread_uint (s, ((*ddom)->path[pth]) + i);
      CHECKRVAL (status);
    }
  }

  /* end */
  return 0;
}

/* send dominoes */
int EGsendNetDomino (CC_SFILE * s,
                     EGnetDdom_t * ddom)
{
  /* local vars */
  int status,
    pth;
  register unsigned int i;

  /* start reading */
  status = CCutil_swrite_uint (s, ddom->s);
  CHECKRVAL (status);
  status = CCutil_swrite_uint (s, ddom->t);
  CHECKRVAL (status);
  status = CCutil_swrite_double (s, ddom->value);
  CHECKRVAL (status);

  /* look for memory */

  /* read path lengths */
  status = CCutil_swrite_uint (s, ddom->npath[0]);
  CHECKRVAL (status);
  status = CCutil_swrite_uint (s, ddom->npath[1]);
  CHECKRVAL (status);
  status = CCutil_swrite_uint (s, ddom->npath[2]);
  CHECKRVAL (status);

  /* read all paths */
  for (pth = 0; pth < 3; pth++)
  {
    for (i = 0; i < ddom->npath[pth]; i++)
    {
      status = CCutil_swrite_uint (s, ddom->path[pth][i]);
      CHECKRVAL (status);
    }
  }

  /* end */
  return 0;
}

/* send dominoes */
int EGsendRealDomino (CC_SFILE * s,
                      EGddomino_t * ddom)
{
  /* local vars */
  int status,
    pth;
  register unsigned int i;

  TEST (ddom->DDtype != DOM_DUAL_NORM, "Can't send dominos of type other than "
        "DOM_DUAL_NORM");
  /* start reading */
  status = CCutil_swrite_uint (s, ddom->s->id);
  CHECKRVAL (status);
  status = CCutil_swrite_uint (s, ddom->t->id);
  CHECKRVAL (status);
  status = CCutil_swrite_double (s, EGdijkstraCostToLf (ddom->value));
  CHECKRVAL (status);

  /* look for memory */

  /* read path lengths */
  status = CCutil_swrite_uint (s, ddom->npath[0]);
  CHECKRVAL (status);
  status = CCutil_swrite_uint (s, ddom->npath[1]);
  CHECKRVAL (status);
  status = CCutil_swrite_uint (s, ddom->npath[2]);
  CHECKRVAL (status);

  /* read all paths */
  for (pth = 0; pth < 3; pth++)
  {
    for (i = 0; i < ddom->npath[pth]; i++)
    {
      status =
        CCutil_swrite_uint (s, ((EGdGraphEdge_t *) (ddom->path[pth][i]))->id);
      CHECKRVAL (status);
    }
  }

  /* end */
  return 0;
}

/* send dominoes */
int EGreceiveRealDomino (CC_SFILE * s,
                         EGddomino_t ** ddom,
                         EGdGraphEdge_t ** dedges,
                         EGdGraphNode_t ** dnodes,
                         EGmemPool_t * mem)
{
  /* local vars */
  int status,
    pth;
  unsigned int itmp;
  register unsigned int i;
  double dtmp;

  /* reset values */
  *ddom = EGmemPoolSMalloc (mem, EGddomino_t, 1);
  memset (*ddom, 0, sizeof (EGddomino_t));
  (*ddom)->DDtype = DOM_DUAL_NORM;

  /* start reading */
  status = CCutil_sread_uint (s, &itmp);
  CHECKRVAL (status);
  (*ddom)->s = dnodes[itmp];
  status = CCutil_sread_uint (s, &itmp);
  CHECKRVAL (status);
  (*ddom)->t = dnodes[itmp];
  status = CCutil_sread_double (s, &dtmp);
  CHECKRVAL (status);
  (*ddom)->value = EGdijkstraToCost (dtmp);

  /* look for memory */
  (*ddom)->npath = EGmemPoolSMalloc (mem, unsigned int,
                                     3);
  (*ddom)->path = EGmemPoolSMalloc (mem, void **,
                                    3);

  /* read path lengths */
  status = CCutil_sread_uint (s, &itmp);
  CHECKRVAL (status);
  (*ddom)->npath[0] = itmp;
  status = CCutil_sread_uint (s, &itmp);
  CHECKRVAL (status);
  (*ddom)->npath[1] = itmp;
  status = CCutil_sread_uint (s, &itmp);
  CHECKRVAL (status);
  (*ddom)->npath[2] = itmp;

  /* read all paths */
  for (pth = 0; pth < 3; pth++)
  {
    (*ddom)->path[pth] = EGmemPoolSMalloc (mem, void *,
                                             (*ddom)->npath[pth]);
    for (i = 0; i < (*ddom)->npath[pth]; i++)
    {
      status = CCutil_sread_uint (s, &itmp);
      CHECKRVAL (status);
      (*ddom)->path[pth][i] = dedges[itmp];
    }
  }

  /* end */
  return 0;
}

/* eliminate all small edges (cut-off value is a constant defined here 
 * as maxval ) */
int removeSmallEdges (double maxval,
                      int *orig_edges,
                      int norig_edges,
                      double *orig_weight,
                      int *nedges,
                      int **edges,
                      double **weight,
                      EGmemPool_t * mem)
{

  int i,
    t;

  t = 0;
  for (i = 0; i < norig_edges; i++)
    if (orig_weight[i] > maxval)
      t++;

  (*edges) = EGmemPoolMalloc (mem, sizeof (int) * t * 2);
  (*weight) = EGmemPoolMalloc (mem, sizeof (double) * t);

  t = 0;
  for (i = 0; i < norig_edges; i++)
    if (orig_weight[i] > maxval)
    {

      (*edges)[2 * t] = orig_edges[2 * i];
      (*edges)[2 * t + 1] = orig_edges[2 * i + 1];
      (*weight)[t] = orig_weight[i];
      t++;

    }

  *nedges = t;

  return 0;

}

int EGisCookGraphConnected (int nnodes,
                            int nedges,
                            int *edges,
                            EGmemPool_t * mem)
{

  EGuGraph_t *G;
  int is_connected;

  G = EGuGraphImport (nnodes, nedges, edges, 0, 0, 0, mem);
  is_connected = EGuGraphIsConnected (G, mem);

  EGfreeUGraph (G);

  return is_connected;

}

---