eg_dijkstra.h

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 
 * */
#ifndef _EGDIJKSTRA
#define _EGDIJKSTRA

#include<stdio.h>
#include<limits.h>

#include "eg_mempool.h"
#include "eg_macros.h"
#include "eg_heap.h"
#include "eg_list.h"
#include "eg_dgraph.h"

#define EG_DIJ_DIST       0
#define EG_DIJ_NDIST      1
#define EG_DIJ_FATHER     2
#define EG_DIJ_MARKER     3
#define EG_DIJ_HCONNECTOR 4
#define EG_DIJ_ELENGTH    5

/* ========================================================================= */
/* Here we define what kind of cost type to use, there are several choices, as
 * default we use double */
#ifndef EG_DIJKSTRA_COST_TYPE
#define EG_DIJKSTRA_COST_TYPE FP25_TYPE
#endif

#if EG_DIJKSTRA_COST_TYPE != EG_HEAP_COST_TYPE
#warning Dijkstra cost type is different than heap cost type.
#endif

/* ========================================================================= */
/* case the cost is any of the internal types */
#if EG_DIJKSTRA_COST_TYPE == DBL_TYPE
typedef double EGdijkstraCost_t;
#endif
#if EG_DIJKSTRA_COST_TYPE == FLT_TYPE
typedef float EGdijkstraCost_t;
#endif
#if EG_DIJKSTRA_COST_TYPE == INT_TYPE
typedef int EGdijkstraCost_t;
#endif
#if ( (EG_DIJKSTRA_COST_TYPE == DBL_TYPE) || (EG_DIJKSTRA_COST_TYPE == FLT_TYPE)\
  || (EG_DIJKSTRA_COST_TYPE == INT_TYPE) )
#define EGdijkstraCostAdd(a,b) ((a)+(b))
#define EGdijkstraCostSub(a,b) ((a)-(b))
#define EGdijkstraCostIsLess(a,b) ((a)<(b))
#define EGdijkstraCostDiv(a,b) ((a)/(b))
#define EGdijkstraCostMul(a,b) ((a)*(b))
#define EGdijkstraCostToLf(a) ((double)a)
#define EGdijkstraCostMinus(a) (-1*a)
#define EGdijkstraToCost(a) ((EGdijkstraCost_t)(a))
#define EG_DIJKSTRA_COST_MAX INT_MAX

/* ========================================================================= */
/* case the cost is Fixed points with 10 bits for fractional values */
#elif EG_DIJKSTRA_COST_TYPE == FP10_TYPE
typedef EGfp10_t EGdijkstraCost_t;
#define EGdijkstraCostAdd(a,b) EGfpAdd10(a,b)
#define EGdijkstraCostSub(a,b) EGfpSub10(a,b)
#define EGdijkstraCostIsLess(a,b) ((a)<(b))
#define EGdijkstraCostDiv(a,b) EGfpDiv10(a,b)
#define EGdijkstraCostMul(a,b) EGfpMul10(a,b)
#define EGdijkstraCostToLf(a) fptolf10(a)
#define EGdijkstraToCost(a) lftofp10(a)
#define EGdijkstraCostMinus(a) EGfpMinus10(a)
#define EG_DIJKSTRA_COST_MAX EGdijstraToCost(EGFP_MAX10)

/* ========================================================================= */
/* case the cost is Fixed points with 20 bits for fractional values */
#elif EG_DIJKSTRA_COST_TYPE == FP20_TYPE
typedef EGfp20_t EGdijkstraCost_t;
#define EGdijkstraCostAdd(a,b) EGfpAdd20(a,b)
#define EGdijkstraCostSub(a,b) EGfpSub20(a,b)
#define EGdijkstraCostIsLess(a,b) ((a)<(b))
#define EGdijkstraCostDiv(a,b) EGfpDiv20(a,b)
#define EGdijkstraCostMul(a,b) EGfpMul20(a,b)
#define EGdijkstraCostToLf(a) fptolf20(a)
#define EGdijkstraToCost(a) lftofp20(a)
#define EGdijkstraCostMinus(a) EGfpMinus20(a)
#define EG_DIJKSTRA_COST_MAX EGdijkstraToCost(EGFP_MAX20)

/* ========================================================================= */
/* case the cost is Fixed points with 28 bits for fractional values */
#elif EG_DIJKSTRA_COST_TYPE == FP28_TYPE
typedef EGfp28_t EGdijkstraCost_t;
#define EGdijkstraCostAdd(a,b) EGfpAdd28(a,b)
#define EGdijkstraCostSub(a,b) EGfpSub28(a,b)
#define EGdijkstraCostIsLess(a,b) ((a)<(b))
#define EGdijkstraCostDiv(a,b) EGfpDiv28(a,b)
#define EGdijkstraCostMul(a,b) EGfpMul28(a,b)
#define EGdijkstraCostToLf(a) fptolf28(a)
#define EGdijkstraToCost(a) lftofp28(a)
#define EGdijkstraCostMinus(a) EGfpMinus28(a)
#define EG_DIJKSTRA_COST_MAX EGdijkstraToCost(EGFP_MAX28)

/* ========================================================================= */
/* case the cost is Fixed points with 28 bits for fractional values */
#elif EG_DIJKSTRA_COST_TYPE == FP25_TYPE
typedef EGfp25_t EGdijkstraCost_t;
#define EGdijkstraCostAdd(a,b) EGfpAdd25(a,b)
#define EGdijkstraCostSub(a,b) EGfpSub25(a,b)
#define EGdijkstraCostIsLess(a,b) ((a)<(b))
#define EGdijkstraCostDiv(a,b) EGfpDiv25(a,b)
#define EGdijkstraCostMul(a,b) EGfpMul25(a,b)
#define EGdijkstraCostToLf(a) fptolf25(a)
#define EGdijkstraToCost(a) lftofp25(a)
#define EGdijkstraCostMinus(a) EGfpMinus25(a)
#define EG_DIJKSTRA_COST_MAX EGdijkstraToCost(EGFP_MAX25)

/* ========================================================================= */
/* if we reach this line this means that the type is unsupported */
#else
#error UNSUPORTED VALUE TYPE
#endif


/* ========================================================================= */
/* constant values definitions */

/* EG_DIJKSTRA_EPSILON:
 
 This constant indicates how much a potential has to change by means of an 
 incoming arc for its potential to be updated                                */

#ifndef EG_DIJKSTRA_EPSILON
#define EG_DIJKSTRA_EPSILON EGdijkstraToCost(0.0000)
#endif

/* EG_DIJKSTRA_OPTERROR:

  This constant indicates how far we must be from the optimal solution 
  value before stopping the algorithm.                                       */

#ifndef EG_DIJKSTRA_OPTERROR
#define EG_DIJKSTRA_OPTERROR EGdijkstraToCost(0.0)
#endif

#ifndef EG_DIJKSTRA_NEGATIVE_CHECK
#define EG_DIJKSTRA_NEGATIVE_CHECK 0
#endif


/* ========================================================================= */
/* access macro declarations */
#define EGdijkstraSetFather(n,os,f) EGosSetData(((EGdGraphNode_t*)(n))->data,os[EG_DIJ_FATHER],EGdGraphEdge_t*,f)
#define EGdijkstraSetDist(n,os,d) EGosSetData(((EGdGraphNode_t*)(n))->data,os[EG_DIJ_DIST],EGdijkstraCost_t,d)
#define EGdijkstraSetNdist(n,os,d) EGosSetData(((EGdGraphNode_t*)(n))->data,os[EG_DIJ_NDIST],unsigned int,d)
#define EGdijkstraSetMarker(n,os,m) EGosSetData(((EGdGraphNode_t*)(n))->data,os[EG_DIJ_MARKER],unsigned int,m)
#define EGdijkstraSetEdgeLength(e,os,l) (EGosSetData(((EGdGraphEdge_t*)(e))->data, os[EG_DIJ_ELENGTH], EGdijkstraCost_t, l))
#define EGdijkstraSetHeapConnector(n,os,h) EGosSetData(((EGdGraphNode_t*)(n))->data,os[EG_DIJ_HCONNECTOR],EGheapConnector_t*,h)

#define EGdijkstraGetDist(v,os) (EGosGetData(((EGdGraphNode_t*)(v))->data,os[EG_DIJ_DIST],EGdijkstraCost_t))
#define EGdijkstraGetNdist(v,os) (EGosGetData(((EGdGraphNode_t*)(v))->data,os[EG_DIJ_NDIST],unsigned int))
#define EGdijkstraGetFather(v,os) (EGosGetData(((EGdGraphNode_t*)(v))->data,os[EG_DIJ_FATHER],EGdGraphEdge_t*))
#define EGdijkstraGetMarker(v,os) (EGosGetData(((EGdGraphNode_t*)(v))->data,os[EG_DIJ_MARKER],unsigned int))
#define EGdijkstraGetEdgeLength(e,os) (EGosGetData(((EGdGraphEdge_t*)(e))->data, os[EG_DIJ_ELENGTH], EGdijkstraCost_t))
#define EGdijkstraGetHeapConnector(e,os) (EGosGetData(((EGdGraphNode_t*)(e))->data, os[EG_DIJ_HCONNECTOR], EGheapConnector_t*))

/* ========================================================================= */
/* main function */
int EGpartialDijkstra (EGdGraphNode_t * s,
                       EGdGraphNode_t * t,
                       EGdijkstraCost_t ubound,
                       size_t * os,
                       EGheap_t * my_heap,
                       EGdGraph_t * G);

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

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

#endif

---