eg_menger_app.c

Go to the documentation of this file.

#include "eg_menger_app.h"

EGmengerNodeData_t *EGnewMengerNodeData (EGmemPool_t * mem)
{

  EGmengerNodeData_t *ndata;

  ndata =
    (EGmengerNodeData_t *) EGmemPoolMalloc (mem, sizeof (EGmengerNodeData_t));
  memset (ndata, 0, sizeof (EGmengerNodeData_t));

  ndata->dist = ndata->orig_dist = ndata->pi = EG_DIJKSTRA_COST_MAX;

  return ndata;

}

EGmengerEdgeData_t *EGnewMengerEdgeData (EGmemPool_t * mem)
{

  EGmengerEdgeData_t *edata;

  edata =
    (EGmengerEdgeData_t *) EGmemPoolMalloc (mem, sizeof (EGmengerEdgeData_t));

  edata->cost = edata->reduced_cost = EG_DIJKSTRA_COST_MAX;
  edata->is_in_solution = 0;
  edata->data = 0;

  return edata;

}

void EGfreeMengerEdgeDataMP (void *v,
                             EGmemPool_t * mem)
{
  EGmemPoolFree (v, sizeof (EGmengerEdgeData_t), mem);
  return;
}

void EGfreeMengerNodeDataMP (void *v,
                             EGmemPool_t * mem)
{
  EGmemPoolFree (v, sizeof (EGmengerNodeData_t), mem);
  return;
}

void EGmengerDisplayEdgeData (void *v,
                              FILE * file)
{

  EGmengerEdgeData_t *edata;

  edata = (EGmengerEdgeData_t *) v;

  fprintf (file, "c=%lf, rc=%lf, iis=%d", EGdijkstraCostToLf (edata->cost),
           EGdijkstraCostToLf (edata->reduced_cost),
           (int) (edata->is_in_solution));

  return;

}

void EGmengerDisplayNodeData (void *v,
                              FILE * file)
{

  EGmengerNodeData_t *ndata;

  ndata = (EGmengerNodeData_t *) v;

  fprintf (file, "dist = %lf   odist = %lf   mark = %u   omark = %u",
           EGdijkstraCostToLf (ndata->dist),
           EGdijkstraCostToLf (ndata->orig_dist), ndata->marker,
           ndata->orig_marker);

  return;

}


EGdGraph_t *EGnewMengerGraph (EGmemPool_t * mem,
                              int nNodes,
                              int nEdges,
                              int *edges,
                              EGdijkstraCost_t * weight,
                              size_t ** os)
{

  unsigned int i;

  EGdGraph_t *G;
  EGdGraphNode_t **pnodes;

  EGmengerNodeData_t *ndata;
  EGmengerEdgeData_t *edata;

  EXIT (*os, "*os must be NULL");

  /* Prepare the offset vector.                                               */
  EGmengerSetOs (os, mem);

  /* Prepare the graph.                                                       */
  G = EGnewDGraph (mem);

  pnodes =
    (EGdGraphNode_t **) EGmemPoolMalloc (mem,
                                         sizeof (EGdGraphNode_t *) * nNodes);

  for (i = 0; i < (unsigned) nNodes; i++)
  {
    ndata = EGnewMengerNodeData (mem);
    pnodes[i] = EGdGraphAddNode (G, ndata);
  }
  for (i = 0; i < (unsigned) nEdges; i++)
  {
    edata = EGnewMengerEdgeData (mem);
    edata->cost = weight[i];
    EGdGraphAddEdge (G, edata, pnodes[edges[2 * i]], pnodes[edges[2 * i + 1]]);
    edata = EGnewMengerEdgeData (mem);
    edata->cost = weight[i];
    EGdGraphAddEdge (G, edata, pnodes[edges[2 * i + 1]], pnodes[edges[2 * i]]);
  }

  EGmemPoolFree (pnodes, sizeof (EGdGraphNode_t *) * nNodes, mem);

  return G;

}

int EGmengerPathsBAS (unsigned int s,
                      unsigned int t,
                      EGdijkstraCost_t ubound,
                      EGdijkstraCost_t * menger_val,
                      unsigned int npaths,
                      unsigned int *iedges,
                      unsigned int *iedges_beg,
                      int nNodes,
                      int nEdges,
                      int *edges,
                      EGdijkstraCost_t * weight,
                      EGmemPool_t * mem)
{

  int rval,
    i;

  EGlistNode_t *n_it;
  EGdGraphNode_t *snode,
   *tnode;
  size_t *os;
  EGdGraph_t *G;

  EGdGraphEdge_t **pedges;

  /* Initialize a graph with all of the entries required by the algorithm.    */
  os = 0;
  G = EGnewMengerGraph (mem, nNodes, nEdges, edges, weight, &os);

  /* Initialize the pedges structure.                                         */
  pedges =
    (EGdGraphEdge_t **) EGmemPoolMalloc (mem,
                                         sizeof (EGdGraphEdge_t *) * nEdges);

  /* Obtain the node pointer for 's'.                                         */
  for (n_it = G->nodes->begin; n_it; n_it = n_it->next)
  {
    snode = (EGdGraphNode_t *) (n_it->this);
    if (snode->id == s)
      break;
  }
  TEST (!n_it, "Node 's' not found");

  /* Obtain the node pointer for 't'.                                         */
  for (n_it = G->nodes->begin; n_it; n_it = n_it->next)
  {
    tnode = (EGdGraphNode_t *) (n_it->this);
    if (tnode->id == t)
      break;
  }
  TEST (!n_it, "Node 't' not found");

  /* Run the algorithm.                                                       */
  rval =
    EGmengerPaths (snode, tnode, ubound, menger_val, npaths, pedges, iedges_beg,
                   os, G);
  CHECKRVAL (rval);

  for (i = 0; (unsigned) i < iedges_beg[npaths]; i++)
    iedges[i] = pedges[i]->id;

  {
    int j;
    for (i = 0; (unsigned) i < npaths; i++)
    {
      fprintf (stderr, "path: %u\n", i);
      for (j = iedges_beg[i]; (unsigned) j < iedges_beg[i + 1]; j++)
        fprintf (stderr, "(%u %u) ", pedges[j]->tail->id, pedges[j]->head->id);
      fprintf (stderr, "\n");
    }
  }

  EGdGraphClearMP (G, EGfreeMengerEdgeDataMP, EGfreeMengerNodeDataMP, 0, mem,
                   mem, 0);
  EGfreeDGraph (G);
  EGmemPoolFree (pedges, sizeof (EGdGraphEdge_t *) * nEdges, mem);
  EGmemPoolFree (os, sizeof (size_t) * 13, mem);

  return 0;

}

int EGmengerPaths (EGdGraphNode_t * s,
                   EGdGraphNode_t * t,
                   EGdijkstraCost_t ubound,
                   EGdijkstraCost_t * menger_val,
                   unsigned int npaths,
                   EGdGraphEdge_t ** pedges,
                   unsigned int *pedges_beg,
                   size_t * os,
                   EGdGraph_t * G)
{

  int rval;
  unsigned int found_paths;
  size_t dij_os[6];
  EGheap_t *my_heap;
  EGdijkstraCost_t dij_ubound;

  /* Prepare the offsets which will be used by dijkstra                       */
  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];

  /* Prepare the heap                                                         */
  my_heap = EGnewHeap (G->mem, 2, G->nodes->size);

  /* Compute the ubound                                                       */
  dij_ubound = EG_DIJKSTRA_COST_MAX;

  /* Solve the first dijkstra                                                 */
  rval = EGpartialDijkstra (s, 0, dij_ubound, dij_os, my_heap, G);
  CHECKRVAL (rval);
  rval = EGdijkstraCheckOptimality (s, 0, dij_ubound, dij_os, G);
  TEST (rval, "failed to meet optimality conditions");

  /* Question: can we use a better dij_ubound and somehow 'omit' those nodes
   * which are too far from 's'?                                              */

  rval =
    EGmengerPathsADV (s, t, ubound, npaths, &found_paths, menger_val, my_heap,
                      os, G);
  CHECKRVAL (rval);

  if (found_paths)
  {
    rval =
      EGmengerRecoverGraphAndSolution (G, os, s, t, found_paths, pedges,
                                       pedges_beg);
    CHECKRVAL (rval);
  }

  EGfreeHeap (my_heap, G->mem);

  return 0;

}

void EGmengerSetOs (size_t ** os,
                    EGmemPool_t * mem)
{

  *os = (size_t *) EGmemPoolMalloc (mem, sizeof (size_t) * EG_MENGER_NUMOS);

  (*os)[EG_MENGER_PI] = offsetof (EGmengerNodeData_t, pi);
  (*os)[EG_MENGER_DIST] = offsetof (EGmengerNodeData_t, dist);
  (*os)[EG_MENGER_ORIG_DIST] = offsetof (EGmengerNodeData_t, orig_dist);
  (*os)[EG_MENGER_NDIST] = offsetof (EGmengerNodeData_t, ndist);
  (*os)[EG_MENGER_ORIG_NDIST] = offsetof (EGmengerNodeData_t, orig_ndist);
  (*os)[EG_MENGER_MARK] = offsetof (EGmengerNodeData_t, marker);
  (*os)[EG_MENGER_ORIG_MARK] = offsetof (EGmengerNodeData_t, orig_marker);
  (*os)[EG_MENGER_FATHER] = offsetof (EGmengerNodeData_t, father);
  (*os)[EG_MENGER_ORIG_FATHER] = offsetof (EGmengerNodeData_t, orig_father);
  (*os)[EG_MENGER_HEAP_CONNECTOR] = offsetof (EGmengerNodeData_t, hc);

  (*os)[EG_MENGER_ECOST] = offsetof (EGmengerEdgeData_t, cost);
  (*os)[EG_MENGER_REDUCED_ECOST] = offsetof (EGmengerEdgeData_t, reduced_cost);
  (*os)[EG_MENGER_IS_IN_SOL] = offsetof (EGmengerEdgeData_t, is_in_solution);
  (*os)[EG_MENGER_EDATA] = offsetof (EGmengerEdgeData_t, data);

  return;

}

void EGmengerDisplayEdgeBasic (void *v,
                               FILE * file)
{
  EGdGraphEdge_t *e;
  size_t dij_os[6];

  e = (EGdGraphEdge_t *) (v);

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

  fprintf (file, "(%u %u) [%lf] ", e->tail->id, e->head->id,
           EGdijkstraCostToLf (EGdijkstraGetEdgeLength (e, dij_os)));

  return;
}

EGdijkstraCost_t EGmengerEdgeCost (EGdGraphEdge_t * e)
{
  size_t dij_os[6];
  dij_os[EG_DIJ_ELENGTH] = offsetof (EGmengerEdgeData_t, cost);

  return (EGdijkstraGetEdgeLength (e, dij_os));
}

---