EGlib: eg_dijkstra_app.h Source File

00001 /* EGlib "Efficient General Library" provides some basic structures and
00002  * algorithms commons in many optimization algorithms.
00003  *
00004  * Copyright (C) 2005 Daniel Espinoza and Marcos Goycoolea.
00005  * 
00006  * This library is free software; you can redistribute it and/or modify it
00007  * under the terms of the GNU Lesser General Public License as published by the
00008  * Free Software Foundation; either version 2.1 of the License, or (at your
00009  * option) any later version.
00010  *
00011  * This library is distributed in the hope that it will be useful, but 
00012  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 
00013  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public 
00014  * License for more details.
00015  *
00016  * You should have received a copy of the GNU Lesser General Public License
00017  * along with this library; if not, write to the Free Software Foundation,
00018  * Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA 
00019  * */
00020 #ifndef _EGDIJKSTRAAPP
00021 #define _EGDIJKSTRAAPP
00022 
00023 #include "eg_dijkstra.h"
00024 
00025 #define EGdijkstraSetOs(os) { \
00026   os[EG_DIJ_DIST] = offsetof (EGdijkstraNodeData_t, dist); \
00027   os[EG_DIJ_NDIST] = offsetof (EGdijkstraNodeData_t, ndist); \
00028   os[EG_DIJ_FATHER] = offsetof (EGdijkstraNodeData_t, father); \
00029   os[EG_DIJ_MARKER] = offsetof (EGdijkstraNodeData_t, marker); \
00030   os[EG_DIJ_HCONNECTOR] = offsetof (EGdijkstraNodeData_t, hc); \
00031   os[EG_DIJ_ELENGTH] = 0; \
00032   } \
00033 
00034 typedef struct
00035 {
00036 
00037   EGdijkstraCost_t dist;
00038   unsigned int ndist;
00039   unsigned int marker;
00040   EGdGraphEdge_t *father;
00041   EGheapConnector_t *hc;
00042   void *data;
00043 
00044 }
00045 EGdijkstraNodeData_t;
00046 
00047 typedef EGdijkstraCost_t EGdijkstraEdgeData_t;
00048 
00049 EGdijkstraNodeData_t *EGnewDijkstraNodeData (EGmemPool_t * mem);
00050 
00051 EGdGraph_t *EGdijkstraLoadGraph (FILE * file,
00052                                  EGmemPool_t * mem);
00053 
00054 EGdGraph_t *EGnewDijkstraDGraph (EGmemPool_t * mem,
00055                                  unsigned int nnodes,
00056                                  unsigned int nedges,
00057                                  unsigned int *edges,
00058                                  EGdijkstraCost_t * weight);
00059 
00060 EGdGraph_t *EGnewDijkstraDGraph_simple (EGmemPool_t * mem,
00061                                         unsigned int nnodes,
00062                                         unsigned int nedges,
00063                                         unsigned int *edges,
00064                                         EGdijkstraCost_t * weight);
00065 
00066 EGdijkstraEdgeData_t *EGnewDijkstraEdgeData (EGmemPool_t * mem);
00067 
00068 void EGfreeDijkstraEdgeDataMP (void *v,
00069                                EGmemPool_t * mem);
00070 void EGfreeDijkstraNodeDataMP (void *v,
00071                                EGmemPool_t * mem);
00072 void EGdijkstraClearDGraphMP (void *v,
00073                               EGmemPool_t * mem);
00074 
00075 int EGdijkstraShortestPath (EGdGraphNode_t * s,
00076                             EGdGraphNode_t * t,
00077                             EGdijkstraCost_t ubound,
00078                             EGdijkstraCost_t * dist,
00079                             EGdGraphEdge_t * prec,
00080                             EGdGraph_t * G);
00081 
00082 void EGdijkstraDisplayEdge (void *v,
00083                             FILE * file);
00084 
00085 void EGdijkstraDisplayNode (void *v,
00086                             FILE * file);
00087 
00088 int EGdijkstraGetOptimalPath (EGdGraph_t * G,
00089                               EGdGraphNode_t * t,
00090                               size_t * os,
00091                               unsigned int *npath,
00092                               EGdGraphEdge_t *** path,
00093                               EGmemPool_t * mem);
00094 
00095 #endif