eg_dijkstra.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.h"

/*****************************************************************************
 * EGpartialDijkstra                                                         *
 *                                                                           *
 * This algorithm requires the following 5 offsets:                          *
 *                                                                           *
 * [0]  name:  dist    where: node_data  type: void*                         *
 *                                                                           *
 * This value is used to store the distance of the node in question to s. To *
 * access the value simply cast the memory address to type (EGdijkstraCost_t).     *
 *                                                                           *
 * [1]  name: ndist    where: node_data  type: void*                         *
 *                                                                           *
 * This value is used to store the number of edges in the current optimal    *
 * path from the node to s.                                                  *
 *                                                                           *
 * [3]  name: marker   where: node_data  type: void*                         *
 *                                                                           *
 * This value is used to indicate the dijkstra iteration in which the node   *
 * was permanently labeled. If the node has not been permanently labeled the *
 * value of this field is UINT_MAX.                                           *
 *                                                                           *
 * [4]  name: heap_cn  where: node_data  type: void*                         *
 *                                                                           *
 * This value is used to hold the memory location of the heap connector used *
 * by the algorithm. After the run this field may-or-may-not mean anything.  *
 * If the value of this field is 0 it means that it was never used in the    *
 * algorithm, hence the distance and ndistance field values will be          *
 * meaningless.                                                              *
 *                                                                           *
 * [2]  name: father   where: node_data  type: void*                         *
 *                                                                           *
 * This value is used to point to the EGdGraphEdge_t of the edge which pre-  *
 * cedes the node in question in the best solution found so far.             *
 *                                                                           *
 * [5]  name: ecost    where: edge_data  type: (EGdijkstraCost_t)                  *
 *                                                                           *
 * This value is used to store the length of the edge in question.           *
 *                                                                           *
 *****************************************************************************/

int EGpartialDijkstra (EGdGraphNode_t * s,
                       EGdGraphNode_t * t,
                       EGdijkstraCost_t ubound,
                       size_t * os,
                       EGheap_t * my_heap,
                       EGdGraph_t * G)
{
  unsigned int tmarked = 0;
  EGdijkstraCost_t value = EGdijkstraToCost (0.0);
  EGdGraphEdge_t *e;
  EGdGraphNode_t *best_node;
  EGlistNode_t *node_it,
   *edge_it;
  EGheapConnector_t *h_c;

  EGmemPool_t *mem;

  mem = s->out_edges->mempool;

#if EG_DIJKSTRA_NEGATIVE_CHECK
  for (node_it = G->nodes->begin; node_it; node_it = node_it->next)
  {
    best_node = (EGdGraphNode_t *) (node_it->this);
    for (edge_it = best_node->out_edges->begin; edge_it;
         edge_it = edge_it->next)
    {
      e = (EGdGraphEdge_t *) (edge_it->this);
      if (EGdijkstraCostToLf (EGdijkstraGetEdgeLength (e, os)) < 0.0)
      {
        fprintf (stderr,
                 "\n\nwarning: found negative weight edge in dijkstra of value %lf.\n",
                 EGdijkstraCostToLf (EGdijkstraGetEdgeLength (e, os)));
        TEST (1, "negative edge");
        return 1;
      }
    }

  }
#endif

  /* For every node in the graph, we initialize its distance to 's' to be as  */
  /* great as possible; that is, to EG_DIJ_COST_MAX.                          */

  if (t)
    EGdijkstraSetDist (t, os, EG_DIJKSTRA_COST_MAX);
  for (node_it = G->nodes->begin; node_it; node_it = node_it->next)
  {
    EGdijkstraSetHeapConnector (node_it->this, os, 0);
    EGdijkstraSetMarker (node_it->this, os, UINT_MAX);
  }

  /* We use the heap to keep track of the 'un-marked' nodes and quickly       *
   * find the 'closest' node to 's'. We clear it, and initialize it with only *
   * 's' belonging to it.                                                     */

  EGheapClear (my_heap, mem);
  h_c = EGheapInsert (my_heap, s, 0, mem);

  /* The distance from 's' to itself is '0'.                                  */
  EGdijkstraSetDist (s, os, EGdijkstraToCost (0.0));

  /* The number of edges in an optimal path from 's' to 's' is '0'.           */
  EGdijkstraSetNdist (s, os, 0);

  /* Node 's' has no father, hence the pointer is set to NULL.                */
  EGdijkstraSetFather (s, os, 0);

  /* Node 's' uses 'h_c' as its heap connector.                               */
  EGdijkstraSetHeapConnector (s, os, h_c);

  while (my_heap->size != 0)
  {

    /* Find the unmarked node in the graph that is closest to s. We remove    *
     * this node from the heap, and mark it.                                  */

    h_c = EGheapGetMin (my_heap);
    best_node = (EGdGraphNode_t *) (h_c->this);
    EGheapDeleteMin (my_heap, mem);
    EGdijkstraSetMarker (best_node, os, tmarked);
    tmarked += 1;
    EGdijkstraSetHeapConnector (best_node, os, 0);

    /* If 't' is among the closest nodes to 's' then we are done.             */

    /* if ( best_node == t ) */
    /* if ( EGdijkstraGetDist(best_node, os) == EGdijkstraGetDist(t, os) )  */
    if (t
        &&
        EGdijkstraCostIsLess (EGdijkstraCostSub
                              (EGdijkstraGetDist (t, os),
                               EGdijkstraGetDist (best_node, os)),
                              EG_DIJKSTRA_OPTERROR))
      break;

    if (EGdijkstraCostIsLess (ubound, EGdijkstraGetDist (best_node, os)))
      return 0;

    /* We update the values of the nodes adjacent to 'best_node'. In order    *
     * to do this we loop through its incident edges.                         */

    for (edge_it = best_node->out_edges->begin; edge_it;
         edge_it = edge_it->next)
    {

      e = (EGdGraphEdge_t *) (edge_it->this);
      TESTL (5, EGdijkstraCostToLf (EGdijkstraGetEdgeLength (e, os)) < 0,
             "Negative edge");
      value =
        EGdijkstraCostAdd (EGdijkstraGetDist (best_node, os),
                           EGdijkstraGetEdgeLength (e, os));

      /* If e->head's distance to 's' is set to EG_DIJ_COST_MAX it means that *
       * its not in the heap. In this case we correct its value and add it.   */

      if (EGdijkstraGetMarker (e->head, os) == UINT_MAX)
      {
        EGdijkstraSetFather (e->head, os, e);
        EGdijkstraSetNdist (e->head, os,
                            EGdijkstraGetNdist (best_node, os) + 1);
        EGdijkstraSetDist (e->head, os, value);
        h_c = EGheapInsert (my_heap, e->head, value, mem);
        EGdijkstraSetHeapConnector (e->head, os, h_c);
        EGdijkstraSetMarker (e->head, os, UINT_MAX - 1);
      }

      /* If e->head's distance to 's' already has a value, we check if going  *
       * through 'best_node' results in a shorter distance. If so, we update  *
       * the parameters of 'e->head' and reorganize the heap.                 */

      else
        if (EGdijkstraCostIsLess
            (EGdijkstraCostAdd (value, EG_DIJKSTRA_EPSILON),
             EGdijkstraGetDist (e->head, os)))
      {

        EGdijkstraSetFather (e->head, os, e);
        EGdijkstraSetNdist (e->head, os,
                            EGdijkstraGetNdist (best_node, os) + 1);
        EGdijkstraSetDist (e->head, os, value);
        EGheapDecreaseVal (my_heap, EGdijkstraGetHeapConnector (e->head, os),
                           value);
      }

    }

  }

  return 0;

}

int EGdijkstraCheckOptimality (EGdGraphNode_t * s,
                               EGdGraphNode_t * t,
                               EGdijkstraCost_t ubound,
                               size_t * os,
                               EGdGraph_t * G)
{

  EGlistNode_t *n_it,
   *e_it;
  EGdGraphEdge_t *e;
  EGdGraphNode_t *n;
  unsigned int hid,
    tid;
  double vh,
    vt,
    ve;

  s = 0;
  t = 0;
  ubound = 0;

  for (n_it = G->nodes->begin; n_it; n_it = n_it->next)
  {
    n = (EGdGraphNode_t *) (n_it->this);
    for (e_it = n->out_edges->begin; e_it; e_it = e_it->next)
    {
      e = (EGdGraphEdge_t *) (e_it->this);
      if (EGdijkstraGetDist (e->head, os) >
          (EGdijkstraGetDist (e->tail, os) + EGdijkstraGetEdgeLength (e, os)))
      {
        hid = e->head->id;
        tid = e->tail->id;
        vh = EGdijkstraCostToLf (EGdijkstraGetDist (e->head, os));
        vt = EGdijkstraCostToLf (EGdijkstraGetDist (e->tail, os));
        ve = EGdijkstraCostToLf (EGdijkstraGetEdgeLength (e, os));
        fprintf (stderr,
                 "c(%u) = %lf  c(%u) = %lf  c(%u, %u) = %lf  c(%u) + c(%u,%u)  = %lf\n",
                 tid, vt, hid, vh, tid, hid, ve, tid, tid, hid, vt + ve);
        return 1;
      }
    }
  }

  return 0;

}

int EGdijkstraExtractSolution (EGdGraphEdge_t ** path,
                               unsigned int *npath,
                               EGdGraphNode_t * s,
                               EGdGraphNode_t * t,
                               size_t * os)
{

  EGdGraphEdge_t *e;
  EGdGraphNode_t *n;
  unsigned int pos;

  s = 0;
  *npath = 0;

  n = t;
  pos = EGdijkstraGetNdist (t, os);
  while (pos)
  {
    e = EGdijkstraGetFather (n, os);
    path[pos - 1] = e;
    n = e->tail;
    pos = EGdijkstraGetNdist (n, os);
    *npath += 1;
  }

  return 0;

}

---