cookInterface.c

Go to the documentation of this file.

/* Copyright (c) 2005 by John M. Boyer, All Rights Reserved.  Please see
 * License.txt for use and redistribution license. */
#include "cookInterface.h"

/* Load a graph in Cook Format */
int loadCookGraph (char *file_name,
                   int *nnodes,
                   int *nedges,
                   int **edges,
                   double **weight)
{
  int i,
    h,
    t;
  double w;
  FILE *file;
  file = fopen (file_name, "r");
  TEST (!file, "error opening file");
  fscanf (file, "%d %d", nnodes, nedges);
  (*edges) = (int *) malloc (sizeof (int) * (*nedges) * 2);
  TEST (!(*edges), "error allocating memory");
  if (weight)
    (*weight) = (double *) malloc (sizeof (double) * (*nedges));
  for (i = 0; i < *nedges; i++)

  {
    fscanf (file, "%d %d %lf", &h, &t, &w);
    (*edges)[2 * i] = h;
    (*edges)[2 * i + 1] = t;
    if (weight)
      (*weight)[i] = w;
  }
  fclose (file);
  return 0;
}


/* Input a graph in Bill Cook Format */
int cook2boyerGraph (graphP bGraph,
                     int nnodes,
                     int nedges,
                     int *edges)
{
  int i,
    rval = 0;
  rval = gp_InitGraph (bGraph, nnodes);
  for (i = 0; i < nedges && !rval; i++)
    if (!gp_IsNeighbor (bGraph, edges[2 * i], edges[2 * i + 1]))

    {
      rval = gp_AddEdgeWid (bGraph, edges[2 * i], 1, edges[2 * i + 1], 1, i);
      TEST (rval, "error converting graph");
    }
  return rval;
}


/********************************************************************
 gp_AddEdgeWid()
 Adds the undirected edge (u,v) to the graph by placing edge records
 representing u into v's circular edge record list and v into u's
 circular edge record list.

 upos receives the location in G where the u record in v's list will be
        placed, and vpos is the location in G of the v record we placed in
 u's list.  These are used to initialize the short circuit links.

 ulink (0|1) indicates whether the edge record to v in u's list should
        become adjacent to u by its 0 or 1 link, i.e. u[ulink] == vpos.
 vlink (0|1) indicates whether the edge record to u in v's list should
        become adjacent to v by its 0 or 1 link, i.e. v[vlink] == upos.

 ********************************************************************/
int gp_AddEdgeWid (graphP theGraph,
                   int u,
                   int ulink,
                   int v,
                   int vlink,
                   int id)
{
  int upos,
    vpos;
  if (theGraph == NULL || u < 0 || v < 0 || u >= 2 * theGraph->N
      || v >= 2 * theGraph->N)

  {
    __EG_PRINTLOC2__;
    return NOTOK;
  }

  /* We enforce the edge limit */
  if (theGraph->M >= EDGE_LIMIT * theGraph->N)

  {
    __EG_PRINTLOC2__;
    return NONEMBEDDABLE;
  }
  vpos = 2 * theGraph->N + 2 * theGraph->M;
  upos = gp_GetTwinArc (theGraph, vpos);
  _AddArcWid (theGraph, u, v, vpos, ulink, id);
  _AddArcWid (theGraph, v, u, upos, vlink, id);
  theGraph->M++;
  return OK;
}


/********************************************************************
 _AddArcWid()
 This routine adds arc (u,v) to u's edge list, storing the record for
 v at position arcPos.  The record is either added to the link[0] or
 link[1] side of vertex u, depending on the link parameter.
 The links of a vertex record can be viewed as previous (link[0]) and
 next (link[1]) pointers.  Thus, an edge record is appended to u's
 list by hooking it to u.link[0], and it is prepended by hooking it
 to u.link[1].  The use of exclusive-or (i.e. 1^link) is simply to get
 the other link (if link is 0 then 1^link is 1, and vice versa).
 ********************************************************************/
void _AddArcWid (graphP theGraph,
                 int u,
                 int v,
                 int arcPos,
                 int link,
                 int id)
{
  theGraph->G[arcPos].id = id;
  theGraph->G[arcPos].v = v;
  if (theGraph->G[u].link[0] == NIL)

  {
    theGraph->G[u].link[0] = theGraph->G[u].link[1] = arcPos;
    theGraph->G[arcPos].link[0] = theGraph->G[arcPos].link[1] = u;
  }

  else

  {
    int u0 = theGraph->G[u].link[link];
    theGraph->G[arcPos].link[link] = u0;
    theGraph->G[arcPos].link[1 ^ link] = u;
    theGraph->G[u].link[link] = arcPos;
    theGraph->G[u0].link[1 ^ link] = arcPos;
  }
}


/* */
int extractCookEdgeIds (graphP theGraph,
                        int *nmnodes,
                        int *nmedges,
                        int *medges)
{
  int I,
    J,
    cnt = 0;
  if (theGraph == NULL)
    return NOTOK;
  *nmnodes = theGraph->N;
  *nmedges = theGraph->M;
  for (I = 0; I < theGraph->N; I++)

  {
    J = theGraph->G[I].link[1];
    while (J >= theGraph->N)

    {
      if (theGraph->G[J].v > I)
        medges[cnt++] = theGraph->G[J].id;
      J = theGraph->G[J].link[1];
    }
  }
  return OK;
}

int DPprintEmbed (graphP theGraph,
                  FILE * file)
{

  /* local variables */
  int I,
    J;

  /* check integrity */
  if (theGraph == NULL || file == NULL)
    return NOTOK;

  /* loop through the nodes and print the adjacency list for them (in embed
   * order if we have called gp_Embed and return OK ) */
  fprintf (file, "N=%d\n", theGraph->N);
  for (I = 0; I < theGraph->N; I++)

  {
    fprintf (file, "%d:", I);
    J = theGraph->G[I].link[1];

    /* print the adjcency list for the current node */
    while (J >= theGraph->N)

    {
      fprintf (file, " %d", theGraph->G[J].v);
      J = theGraph->G[J].link[1];
    }
    fprintf (file, " %d\n", NIL);
  }
  return OK;
}

---