eg_ddomino.c

Go to the documentation of this file.

#include "eg_ddomino.h"

EGddomino_t *EGnewDdomino (EGmemPool_t * mem,
                           EGdGraphEdge_t ** path,
                           unsigned int *path_beg,
                           EGdijkstraCost_t val)
{
  unsigned int i;
  EGddomino_t *dom;

  dom = EGmemPoolSMalloc (mem, EGddomino_t, 1);

  dom->DDtype = DOM_DUAL_NORM;
  dom->s = path[0]->tail;
  dom->t = path[path_beg[1] - 1]->head;

  dom->value = EGdijkstraCostSub (val, EGdijkstraToCost (3.0));

  dom->path = EGmemPoolSMalloc (mem, void **,
                                3);
  dom->npath = EGmemPoolSMalloc (mem, unsigned int,
                                 3);

  dom->id = UINT_MAX;

  for (i = 0; i < 3; i++)
  {
    dom->npath[i] = path_beg[i + 1] - path_beg[i];
    dom->path[i] = EGmemPoolSMalloc (mem, void *,
                                     dom->npath[i]);
    memcpy (dom->path[i], path + path_beg[i],
            sizeof (void *) * (dom->npath[i]));
  }

  return dom;
}

void EGfreeDdomino (void *v,
                    EGmemPool_t * mem)
{

  int i;
  EGddomino_t *ddom;

  ddom = (EGddomino_t *) v;

  for (i = 0; i < 3; i++)
    EGmemPoolSFree (ddom->path[i], void *,
                    ddom->npath[i],
                    mem);

  EGmemPoolSFree (ddom->npath, unsigned int,
                  3,
                  mem);
  EGmemPoolSFree (ddom->path, void **,
                  3,
                  mem);

  EGmemPoolSFree (ddom, EGddomino_t, 1, mem);

  return;

}

int EGfreeAllDDominoes (EGlist_t * dlist,
                        EGmemPool_t * mem)
{

  int rval = EGlistClearMP (dlist, EGfreeDdomino, mem);
  CHECKRVAL (rval);

  return rval;

}

/*****************************************************************************/
/* EGddominoComputeAll                                                       */
/*                                                                           */
/* Note: This function is the one which will take the most time. In order to */
/* parallelize this the following steps can be taken:                        */
/* a) For each s create a copy of diG.                                       */
/* b) For each s use a different list (a dlist[s]).                          */
/* c) For each s use a different copy of eCost.                              */
/* d) At the end, merge the lists.                                           */
/* These steps are important because these objects are not constant!! They   */
/* changed over and over during the EGddominoComputeS execution.             */
/*****************************************************************************/

int EGddominoComputeAll (EGmemPool_t * mem,
                         EGdGraph_t * G,
                         EGlist_t * dlist,
                         int k,
                         double percentage)
{
  int i,
    rval;
  unsigned int nnodes;
  //unsigned int prev = 0;
  EGlistNode_t *n_it;
  EGdGraphNode_t *s,
  **nodes;

  nnodes = G->nodes->size;

  nodes =
    (EGdGraphNode_t **) EGmemPoolMalloc (mem,
                                         sizeof (EGdGraphNode_t *) * nnodes);
  for (i = 0, n_it = G->nodes->begin; n_it; n_it = n_it->next, i++)
    nodes[i] = (EGdGraphNode_t *) (n_it->this);

  if (DP_TEETHING && (k == 1))
    EGddominoPerturb (G, EGdijkstraToCost (DP_TEETHING_PERTURBATION));

  fprintf (stdout, "Node: %5d", 0);
  fflush (stdout);
  for (i = 0; (unsigned) i < nnodes; i++)
  {

    s = nodes[i];

    if (s->out_edges->size < 3)
      continue;

    fprintf (stdout, "\rNode: %5d", s->id);
    fflush (stdout);
    rval = EGddominoComputeS (mem, s, G, dlist, k, percentage);
    CHECKRVAL (rval);

  }

  EGmemPoolFree (nodes, sizeof (EGdGraphNode_t *) * nnodes, mem);

  fprintf (stdout, "\r");
  fflush (stdout);

  if (DP_TEETHING && (k == 1))
  {
    EGddominoPerturb (G, EGdijkstraToCost (-1 * DP_TEETHING_PERTURBATION));
    EGddFixValues (dlist);
  }

  return 0;

}

int EGddominoComputeAllRemote (EGmemPool_t * mem,
                               EGdGraph_t * G,
                               EGlist_t * dlist,
                               int k,
                               const char *boss_name,
                               double ddp_heuristic_maxtime)
{

  static int graph_id = 0;
  CC_SFILE *s = (CC_SFILE *) NULL;
  int i,
    rval = 0,
    num;
  EGddomino_t *ddom;
  char request = 'Z';

  EGdGraphEdge_t **dedges;
  EGdGraphNode_t **dnodes;

  if (DP_TEETHING && (k == 1))
    EGddominoPerturb (G, EGdijkstraToCost (DP_TEETHING_PERTURBATION));

  CCutil_printlabel ();

  s = CCutil_snet_open (boss_name, CCtsp_DOMINO_PORT);
  if (!s)
  {
    fprintf (stderr, "CCutil_snet_open failed\n");
    rval = 1;
    goto CLEANUP;
  }

#if DISPLAY_MODE
  fprintf (stdout, "Sending graph id = %u\n", graph_id);
  fflush (stdout);
#endif

  rval = CCutil_swrite_char (s, CCtsp_DOMINO_GRAPH);
  CCcheck_rval (rval, "CCutil_swrite_char failed (GRAPH)");

  rval = CCutil_swrite_int (s, graph_id);
  CCcheck_rval (rval, "Failed to send graph");

  rval = CCutil_swrite_int (s, k);
  CCcheck_rval (rval, "Failed to send graph");

  rval = CCutil_swrite_double (s, ddp_heuristic_maxtime);
  CCcheck_rval (rval, "Failed to send ddp_heuristic_maxtime");

  rval = EGsendRealGraph (s, G, &dedges, &dnodes, mem);
  CCcheck_rval (rval, "Failed to send graph");

#if DISPLAY_MODE
  fprintf (stdout, "Graph sent. Waiting for dominoes.\n");
  fflush (stdout);
#endif

  while (request != CCtsp_DOMINO_SEND)
  {

    CCutil_sclose (s);

    sleep (2);

    s = CCutil_snet_open (boss_name, CCtsp_DOMINO_PORT);
    if (!s)
    {
      fprintf (stderr, "CCutil_snet_open failed\n");
      rval = 1;
      goto CLEANUP;
    }

    rval = CCutil_swrite_char (s, CCtsp_DOMINO_SEND);
    CCcheck_rval (rval, "CCutil_swrite_char failed (SEND)");

    rval = CCutil_sread_char (s, &request);
    CCcheck_rval (rval, "CCutil_swrite_char failed (SEND)");

  }

#if DISPLAY_MODE
  fprintf (stdout, "Preparing to receive dominoes.\n");
  fflush (stdout);
#endif

  rval = CCutil_sread_int (s, &num);
  CCcheck_rval (rval, "receive ndominoes failed");

#if DISPLAY_MODE
  fprintf (stdout, "Receiving %d dominoes.\n", num);
  fflush (stdout);
#endif


  for (i = 0; i < num; i++)
  {
    rval = EGreceiveRealDomino (s, &ddom, dedges, dnodes, mem);
    CCcheck_rval (rval, "receive_dominos failed");
    EGlistPushBack (dlist, ddom);
    ddom->id = i;
  }

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

CLEANUP:

  graph_id += 1;
  if (s)
    CCutil_sclose (s);

  if (DP_TEETHING && (k == 1))
  {
    EGddominoPerturb (G, EGdijkstraToCost (-1 * DP_TEETHING_PERTURBATION));
    EGddFixValues (dlist);
  }

  return rval;

}


int EGddominoComputeS (EGmemPool_t * mem,
                       EGdGraphNode_t * s,
                       EGdGraph_t * G,
                       EGlist_t * dlist,
                       int k,
                       double percentage)
{

  int rval;
  EGmemPool_t *loc_mem;

  EGheap_t *my_heap;
  EGddomino_t *ddom;
  EGlistNode_t *n_it;

  EGdijkstraCost_t val;

  unsigned int *pedges_beg,
    found_paths;
  EGdGraphEdge_t **pedges;
  EGdGraphNode_t *t;
  size_t os[EG_MENGER_NUMOS] = {
    [EG_MENGER_PI] = offsetof (EGmengerNodeData_t, pi),
    [EG_MENGER_DIST] = offsetof (EGmengerNodeData_t, dist),
    [EG_MENGER_ORIG_DIST] = offsetof (EGmengerNodeData_t, orig_dist),
    [EG_MENGER_NDIST] = offsetof (EGmengerNodeData_t, ndist),
    [EG_MENGER_ORIG_NDIST] = offsetof (EGmengerNodeData_t, orig_ndist),
    [EG_MENGER_MARK] = offsetof (EGmengerNodeData_t, marker),
    [EG_MENGER_ORIG_MARK] = offsetof (EGmengerNodeData_t, orig_marker),
    [EG_MENGER_FATHER] = offsetof (EGmengerNodeData_t, father),
    [EG_MENGER_ORIG_FATHER] = offsetof (EGmengerNodeData_t, orig_father),
    [EG_MENGER_HEAP_CONNECTOR] = offsetof (EGmengerNodeData_t, hc),
    [EG_MENGER_ECOST] = offsetof (EGmengerEdgeData_t, cost),
    [EG_MENGER_REDUCED_ECOST] = offsetof (EGmengerEdgeData_t, reduced_cost),
    [EG_MENGER_IS_IN_SOL] = offsetof (EGmengerEdgeData_t, is_in_solution),
    [EG_MENGER_EDATA] = offsetof (EGmengerEdgeData_t, data)
  },
    dij_os[6];

#if DDOM_LARGE_MODE == 1
  EGlist_t *remlist;
#endif

  /* Initialize a local memory pool */
  loc_mem = mem;                //EGnewMemPool (100, EGmemPoolNewSize, EGmemPoolNewSize (1));

  /* Prepare the heap that will be used for all dijkstra runs                 */
  my_heap = EGnewHeap (loc_mem, 2, G->nodes->size);

  /* Prepare space for allocating flow solutions                              */
  pedges = EGmemPoolSMalloc (loc_mem, EGdGraphEdge_t *, G->nedges);
  pedges_beg = EGmemPoolSMalloc (loc_mem, unsigned int,
                                 4);

  /* Prepare the offset arrays                                                */
  dij_os[EG_DIJ_DIST] = os[EG_MENGER_ORIG_DIST];
  dij_os[EG_DIJ_NDIST] = os[EG_MENGER_ORIG_NDIST];
  dij_os[EG_DIJ_FATHER] = os[EG_MENGER_ORIG_FATHER];
  dij_os[EG_DIJ_MARKER] = os[EG_MENGER_ORIG_MARK];
  dij_os[EG_DIJ_HCONNECTOR] = os[EG_MENGER_HEAP_CONNECTOR];
  dij_os[EG_DIJ_ELENGTH] = os[EG_MENGER_ECOST];

#if DDOM_LARGE_MODE == 0

  /* We will use solution to dijkstra from s many times                       */
  rval = EGpartialDijkstra (s, 0, EG_DIJKSTRA_COST_MAX, dij_os, my_heap, G);
  CHECKRVAL (rval);

#endif

#if DDOM_LARGE_MODE == 1

  remlist = EGnewList (mem);

  /* For 1 pies, we only need consider nodes t at distance <= 2.0 from s */
  /* For 2 pies, this bound changes to 4.0                               */
  rval =
    EGpartialDijkstra (s, 0,
                       EGdijkstraToCost (percentage * (2.0 + (k - 1) * 2.0)),
                       dij_os, my_heap, G);
  CHECKRVAL (rval);

  for (n_it = G->nodes->begin; n_it; n_it = n_it->next)
  {

    t = (EGdGraphNode_t *) (n_it->this);

    if (EGmengerGetOrigMark (t, os) > UINT_MAX - 2)
    {
      rval = EGdGraphUnattachNode (G, t);
      CHECKRVAL (rval);
      EGlistPushHead (remlist, t);
    }

  }

#endif

  /* We now call the flow algorithm once for each t > s                       */
  for (n_it = G->nodes->begin; n_it; n_it = n_it->next)
  {

    t = (EGdGraphNode_t *) (n_it->this);

    if (t->id <= s->id)
      continue;

    found_paths = 0;

    rval =
      EGmengerPathsADV (s, t, EGdijkstraToCost (3.0 + 1.0 * k - DDOM_EPSILON),
                        3, &found_paths, &val, my_heap, os, G);

    CHECKRVAL (rval);

    if (found_paths)
    {

      rval =
        EGmengerRecoverGraphAndSolution (G, os, s, t, found_paths, pedges,
                                         pedges_beg);
      if (rval)
      {
        MESSAGE (0,
                 "WARNING!! Problem with menger. Running emergency recovery...");
        rval = EGmengerEmergencyRecovery (G, os);
      }
      CHECKRVAL (rval);

    }

    if (EGdijkstraCostIsLess
        (EGdijkstraToCost (2.0 + 2.0 * k - DDOM_EPSILON), val))
      continue;

    ddom = EGnewDdomino (mem, pedges, pedges_beg, val);
    ddom->id = dlist->size;
    EGlistPushBack (dlist, (void *) ddom);

  }

#if DDOM_LARGE_MODE == 1
  for (n_it = remlist->begin; n_it; n_it = n_it->next)
  {
    t = (EGdGraphNode_t *) (n_it->this);
    EGdGraphAttachNode (G, t);
  }

  EGfreeList (remlist);
#endif

  /* Free allocated space                                                     */
  EGmemPoolFree (pedges, sizeof (EGdGraphEdge_t *) * (G->nedges), loc_mem);
  EGmemPoolFree (pedges_beg, sizeof (unsigned int) * 4, loc_mem);
  EGfreeHeap (my_heap, loc_mem);
  //EGfreeMemPool (loc_mem);

  return 0;

}

void EGddominoDisplay (EGddomino_t * ddom,
                       FILE * file)
{

  unsigned int i,
    j;
  fprintf (file, "s=%u, t=%u, val=%lf type=%s\n", ddom->s->id, ddom->t->id,
           EGdijkstraCostToLf (ddom->value), ddom->DDtype == DOM_DUAL_NORM ?
           "DualDominoNormal" : ddom->DDtype == DOM_CC_ONE ?
           "ConsecutiveOneDomino" : "Unknown type");
  for (i = 0; i < 3; i++)
  {
    fprintf (file, "path %u (%u): ", i, ddom->npath[i]);
    if (ddom->DDtype != DOM_CC_ONE)
      for (j = 0; j < ddom->npath[i]; j++)
        EGmengerDisplayEdgeBasic ((EGdGraphEdge_t *) ddom->path[i][j], file);
    /*
     * fprintf (file, "(%u %u) ",
     * ((EGdGraphEdge_t *) (ddom->path[i][j]))->tail->id,
     * ((EGdGraphEdge_t *) (ddom->path[i][j]))->head->id);
     */
    else if (ddom->DDtype == DOM_CC_ONE)
      for (j = 0; j < ddom->npath[i]; j++)
        fprintf (file, "(%u %u) ", 0, 0);
    /*
     * ((edge *) (ddom->path[i][j]))->end0->number,
     * ((edge *) (ddom->path[i][j]))->end1->number);
     */
    else
      fprintf (file, "Unknown type ");
    fprintf (file, "\n");
  }

  return;

}

int EGddominoPerturb (EGdGraph_t * G,
                      EGdijkstraCost_t epsilon)
{

  size_t dij_os[6];
  EGdijkstraCost_t val;
  EGdGraphNode_t *n;
  EGdGraphEdge_t *e;
  EGlistNode_t *n_it, *e_it;

  dij_os[EG_DIJ_ELENGTH] = offsetof (EGmengerEdgeData_t, cost);

  for (n_it = G->nodes->begin; n_it; n_it = n_it->next)
  {
    n = (n_it->this);
    for (e_it = n->out_edges->begin; e_it; e_it = e_it->next)
    {
      e = e_it->this;
      val = EGdijkstraGetEdgeLength (e, dij_os);
      val = EGdijkstraCostSub (val, epsilon);
      if (fabs (EGdijkstraCostToLf (val)) > fabs (EGdijkstraCostToLf (epsilon)))
        EGdijkstraSetEdgeLength (e, dij_os, val);
    }
  }

  return 0;

}

EGdijkstraCost_t EGddWeight (EGddomino_t * dd)
{

  unsigned int i,
    j;
  EGdijkstraCost_t val;

  size_t dij_os[6];

  val = EGdijkstraToCost (0.0);
  dij_os[EG_DIJ_ELENGTH] = offsetof (EGmengerEdgeData_t, cost);

  for (i = 0; i < 3; i++)
    for (j = 0; j < dd->npath[i]; j++)
      val =
        EGdijkstraCostAdd (val,
                           EGdijkstraGetEdgeLength (dd->path[i][j], dij_os));

  return val;

}

int EGddFixValues (EGlist_t * dd_list)
{

  EGlistNode_t *it;
  EGddomino_t *ddom;

  EGdijkstraCost_t val;

  for (it = dd_list->begin; it; it = it->next)
  {
    ddom = (EGddomino_t *) (it->this);
    val = EGddWeight (ddom);
    ddom->value = EGdijkstraCostSub (val, EGdijkstraToCost (3.0));
  }

  return 0;

}

---