eg_dijkstra_app.c

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 
 * */
#include "eg_dijkstra_app.h"

EGdijkstraEdgeData_t *EGnewDijkstraEdgeData (EGmemPool_t * mem)
{
  EGdijkstraEdgeData_t *ed;
  ed =
    (EGdijkstraEdgeData_t *) EGmemPoolMalloc (mem,
                                              sizeof (EGdijkstraEdgeData_t));
  *ed = 0;
  return (ed);
}

EGdijkstraNodeData_t *EGnewDijkstraNodeData (EGmemPool_t * mem)
{
  EGdijkstraNodeData_t *nd;
  nd =
    (EGdijkstraNodeData_t *) EGmemPoolMalloc (mem,
                                              sizeof (EGdijkstraNodeData_t));
  nd->dist = EG_DIJKSTRA_COST_MAX;
  nd->ndist = UINT_MAX;
  nd->marker = UINT_MAX;
  nd->father = 0;
  nd->hc = 0;
  return nd;
}

void EGfreeDijkstraEdgeDataMP (void *v,
                               EGmemPool_t * mem)
{
  if (v)
    EGmemPoolFree (v, sizeof (EGdijkstraCost_t), mem);
  return;
}

void EGfreeDijkstraNodeDataMP (void *v,
                               EGmemPool_t * mem)
{
  if (v)
    EGmemPoolFree (v, sizeof (EGdijkstraNodeData_t), mem);
  return;
}

EGdGraph_t *EGnewDijkstraDGraph (EGmemPool_t * mem,
                                 unsigned int nnodes,
                                 unsigned int nedges,
                                 unsigned int *edges,
                                 EGdijkstraCost_t * weight)
{

  unsigned int i;
  EGdGraphNode_t **lnode;
  EGdGraphEdge_t **ledge;
  EGdGraph_t *G;

  G = EGnewDGraph (mem);
  lnode =
    (EGdGraphNode_t **) EGmemPoolMalloc (mem,
                                         sizeof (EGdGraphNode_t *) * nnodes);
  ledge =
    (EGdGraphEdge_t **) EGmemPoolMalloc (mem,
                                         sizeof (EGdGraphEdge_t *) * 2 *
                                         nedges);

  for (i = 0; i < nnodes; i++)
  {
    lnode[i] = EGdGraphAddNode (G, 0);
    lnode[i]->data = EGnewDijkstraNodeData (mem);
  }

  for (i = 0; i < nedges; i++)
  {
    ledge[2 * i] =
      EGdGraphAddEdge (G, 0, lnode[edges[2 * i]], lnode[edges[2 * i + 1]]);
    ledge[2 * i]->data =
      (EGdijkstraCost_t *) EGmemPoolMalloc (mem, sizeof (EGdijkstraCost_t));
    *((EGdijkstraEdgeData_t *) (ledge[2 * i]->data)) = weight[i];

    ledge[2 * i + 1] =
      EGdGraphAddEdge (G, 0, lnode[edges[2 * i + 1]], lnode[edges[2 * i]]);
    ledge[2 * i + 1]->data =
      (EGdijkstraCost_t *) EGmemPoolMalloc (mem, sizeof (EGdijkstraCost_t));
    *((EGdijkstraEdgeData_t *) (ledge[2 * i + 1]->data)) = weight[i];

  }

  EGmemPoolFree (lnode, sizeof (EGdGraphNode_t *) * nnodes, mem);
  EGmemPoolFree (ledge, sizeof (EGdGraphEdge_t *) * nedges, mem);

  return (G);

}

EGdGraph_t *EGnewDijkstraDGraph_simple (EGmemPool_t * mem,
                                        unsigned int nnodes,
                                        unsigned int nedges,
                                        unsigned int *edges,
                                        EGdijkstraCost_t * weight)
{

  unsigned int i;
  EGdGraphNode_t **lnode;
  EGdGraphEdge_t *edge;
  EGdGraph_t *G;

  G = EGnewDGraph (mem);
  lnode =
    (EGdGraphNode_t **) EGmemPoolMalloc (mem,
                                         sizeof (EGdGraphNode_t *) * nnodes);

  for (i = 0; i < nnodes; i++)
  {
    lnode[i] = EGdGraphAddNode (G, 0);
    lnode[i]->data = EGnewDijkstraNodeData (mem);
  }

  for (i = 0; i < nedges; i++)
  {
    edge = EGdGraphAddEdge (G, 0, lnode[edges[2 * i + 1]], lnode[edges[2 * i]]);
    edge->data =
      (EGdijkstraCost_t *) EGmemPoolMalloc (mem, sizeof (EGdijkstraCost_t));
    *((EGdijkstraEdgeData_t *) (edge->data)) = weight[i];
  }

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

  return (G);

}

void EGdijkstraClearDGraphMP (void *v,
                              EGmemPool_t * mem)
{
  EGdGraphClearMP ((EGdGraph_t *) v, EGfreeDijkstraEdgeDataMP,
                   EGfreeDijkstraNodeDataMP, 0, mem, mem, 0);
  return;
}

int EGdijkstraShortestPath (EGdGraphNode_t * s,
                            EGdGraphNode_t * t,
                            EGdijkstraCost_t ubound,
                            EGdijkstraCost_t * dist,
                            EGdGraphEdge_t * prec,
                            EGdGraph_t * G)
{

  unsigned int rval;
  size_t os[5];
  EGheap_t *my_heap;

  TEST (s == t, "s must be different than t");
  TEST (!dist, "dist is null");
  TEST (!prec, "prec is null");
  TEST (!G, "G is null");

  os[EG_DIJ_DIST] = offsetof (EGdijkstraNodeData_t, dist);
  os[EG_DIJ_NDIST] = offsetof (EGdijkstraNodeData_t, ndist);
  os[EG_DIJ_FATHER] = offsetof (EGdijkstraNodeData_t, father);
  os[EG_DIJ_MARKER] = offsetof (EGdijkstraNodeData_t, marker);
  os[EG_DIJ_HCONNECTOR] = offsetof (EGdijkstraNodeData_t, hc);
  os[EG_DIJ_ELENGTH] = 0;

  my_heap = EGnewHeap (G->mem, 3, G->nodes->size);

  //EGdGraphDisplay(G, 0, EGdijkstraDisplayNode, EGdijkstraDisplayEdge, stderr);

  rval = EGpartialDijkstra (s, t, ubound, os, my_heap, G);
  CHECKRVAL (rval);

  EGfreeHeap (my_heap, G->mem);

  //if (t) fprintf(stderr, "Solution: d(s,t) = %lf\n", EGdijkstraGetDist(t, os));
  //EGdGraphDisplay(G, 0, EGdijkstraDisplayNode, EGdijkstraDisplayEdge, stderr);
  return 0;

}

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

  EGdijkstraNodeData_t *nd;

  nd = (EGdijkstraNodeData_t *) v;

  fprintf (file, "d=%lf, nd=%u, m=%u, f=%p, hc=%p",
           EGdijkstraCostToLf (nd->dist), (unsigned int) (nd->ndist),
           (unsigned int) (nd->marker), (void *) nd->father, (void *) nd->hc);

  return;

}

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

  EGdijkstraEdgeData_t *ed;

  ed = (EGdijkstraEdgeData_t *) v;

  fprintf (file, "%lf", EGdijkstraCostToLf (*ed));

  return;

}

EGdGraph_t *EGdijkstraLoadGraph (FILE * file,
                                 EGmemPool_t * mem)
{

  unsigned int i;
  unsigned int *edges;
  double w;
  EGdijkstraCost_t *weight;
  unsigned int nnodes,
    nedges;

  EGdGraph_t *dg;

  fscanf (file, "%u %u", &nnodes, &nedges);
  edges = EGmemPoolSMalloc (mem, unsigned int,
                            2 * nedges);
  weight = EGmemPoolSMalloc (mem, EGdijkstraCost_t, nedges);

  for (i = 0; i < nedges; i++)
  {
    fscanf (file, "%u %u %lf", &edges[2 * i], &edges[2 * i + 1], &w);
    weight[i] = EGdijkstraToCost (w);
    ADVTESTL (1, edges[2 * i] > (nnodes - 1), 0,
              "Edge %u (head) out of bounds", i);
    ADVTESTL (1, edges[2 * i + 1] > (nnodes - 1), 0,
              "Edge %u (tail) out of bounds", i);
  }

  dg = EGnewDijkstraDGraph_simple (mem, nnodes, nedges, edges, weight);

  EGmemPoolSFree (edges, unsigned int,
                  2 * nedges,
                  mem);
  EGmemPoolSFree (weight, EGdijkstraCost_t, nedges, mem);

  return dg;

}

/* assumes that *path is not allocated */
int EGdijkstraGetOptimalPath (EGdGraph_t * G,
                              EGdGraphNode_t * t,
                              size_t * os,
                              unsigned int *npath,
                              EGdGraphEdge_t *** path,
                              EGmemPool_t * mem)
{

  if (EGdijkstraGetNdist (t, os) == 0)
  {
    *path = 0;
    *npath = 0;
    return 0;
  }

  EGdGraphNode_t *node;

  *npath = EGdijkstraGetNdist (t, os);
  *path = EGmemPoolSMalloc (mem, EGdGraphEdge_t *, *npath);

  node = t;

  while (EGdijkstraGetNdist (node, os) != 0)
  {
    (*path)[EGdijkstraGetNdist (node, os) - 1] = EGdijkstraGetFather (node, os);
    node = (EGdijkstraGetFather (node, os))->tail;
  }

  return 0;

}

---