00001 #ifndef EG_MENGER
00002 #define EG_MENGER
00003
00004 #include <stdio.h>
00005 #include <stdlib.h>
00006 #include "eg_mempool.h"
00007 #include "eg_list.h"
00008 #include "eg_dgraph.h"
00009 #include "eg_dijkstra.h"
00010 #include "eg_heap.h"
00011 #include "eg_bellford.h"
00012
00013
00014 #define MENGER_USE_BELLFORD 0
00015
00016 #define EG_MENGER_NUMOS 14
00017
00018 #define EG_MENGER_PI 0
00019 #define EG_MENGER_DIST 1
00020 #define EG_MENGER_ORIG_DIST 2
00021 #define EG_MENGER_NDIST 3
00022 #define EG_MENGER_ORIG_NDIST 4
00023 #define EG_MENGER_MARK 5
00024 #define EG_MENGER_ORIG_MARK 6
00025 #define EG_MENGER_FATHER 7
00026 #define EG_MENGER_ORIG_FATHER 8
00027 #define EG_MENGER_HEAP_CONNECTOR 9
00028
00029 #define EG_MENGER_ECOST 10
00030 #define EG_MENGER_REDUCED_ECOST 11
00031 #define EG_MENGER_IS_IN_SOL 12
00032 #define EG_MENGER_EDATA 13
00033
00034 #ifndef EG_MENGER_SAFEMODE
00035 #define EG_MENGER_SAFEMODE 0
00036 #endif
00037
00038 #define EGmengerSetPi(n,os,c) \
00039 EGosSetData(((EGdGraphNode_t*)n)->data, os[EG_MENGER_PI], EGdijkstraCost_t, c)
00040 #define EGmengerSetDist(n,os,d) \
00041 EGosSetData(((EGdGraphNode_t*)(n))->data, os[EG_MENGER_DIST], EGdijkstraCost_t, f)
00042 #define EGmengerSetOrigDist(n,os,d) \
00043 EGosSetData(((EGdGraphNode_t*)(n))->data, os[EG_MENGER_ORIG_DIST], EGdijkstraCost_t, d)
00044 #define EGmengerSetNdist(n,os,d) \
00045 EGosSetData(((EGdGraphNode_t*)(n))->data, os[EG_MENGER_NDIST], unsigned int, d)
00046 #define EGmengerSetOrigNdist(n,os,d) \
00047 EGosSetData(((EGdGraphNode_t*)(n))->data, os[EG_MENGER_ORIG_NDIST], unsigned int, d)
00048 #define EGmengerSetMark(n,os,m) \
00049 EGosSetData(((EGdGraphNode_t*)(n))->data, os[EG_MENGER_MARK], unsigned int, m)
00050 #define EGmengerSetOrigMark(n,os,m) \
00051 EGosSetData(((EGdGraphNode_t*)(n))->data, os[EG_MENGER_ORIG_MARK], unsigned int, m)
00052 #define EGmengerSetFather(n,os,f) \
00053 EGosSetData(((EGdGraphNode_t*)(n))->data, os[EG_MENGER_FATHER], EGdGraphEdge_t*, f)
00054 #define EGmengerSetOrigFather(n,os,f) \
00055 EGosSetData(((EGdGraphNode_t*)(n))->data, os[EG_MENGER_ORIG_FATHER], EGdGraphEdge_t*, f)
00056 #define EGmengerSetHeapConnector(n,os,hc) \
00057 EGosSetData(((EGdGraphNode_t*)(n))->data, os[EG_MENGER_HEAP_CONNECTOR], EGheapConnector_t*, hc)
00058
00059 #define EGmengerSetEdgeCost(e,os,c) \
00060 EGosSetData(((EGdGraphEdge_t*)(e))->data, os[EG_MENGER_ECOST], EGdijkstraCost_t, c)
00061 #define EGmengerSetEdgeReducedCost(e,os,c) \
00062 EGosSetData(((EGdGraphEdge_t*)(e))->data, os[EG_MENGER_REDUCED_ECOST], EGdijkstraCost_t, c)
00063 #define EGmengerSetEdgeIsInSolution(e,os,yn) \
00064 EGosSetData(((EGdGraphEdge_t*)(e))->data, os[EG_MENGER_IS_IN_SOL], unsigned int, yn)
00065 #define EGmengerSetEdgeData(e,os,d) \
00066 EGosSetData(((EGdGraphEdge_t*)(e))->data, os[EG_MENGER_EDATA], void*, d)
00067
00068 #define EGmengerGetPi(v,os) \
00069 (EGosGetData(((EGdGraphNode_t*)(v))->data,os[EG_MENGER_PI],EGdijkstraCost_t))
00070 #define EGmengerGetDist(v,os) \
00071 (EGosGetData(((EGdGraphNode_t*)(v))->data,os[EG_MENGER_DIST],EGdijkstraCost_t))
00072 #define EGmengerGetOrigDist(v,os) \
00073 (EGosGetData(((EGdGraphNode_t*)(v))->data,os[EG_MENGER_ORIG_DIST],EGdijkstraCost_t))
00074 #define EGmengerGetNdist(v,os) \
00075 (EGosGetData(((EGdGraphNode_t*)(v))->data,os[EG_MENGER_NDIST],unsigned int))
00076 #define EGmengerGetOrigNdist(v,os) \
00077 (EGosGetData(((EGdGraphNode_t*)(v))->data,os[EG_MENGER_ORIG_NDIST],unsigned int))
00078 #define EGmengerGetMark(v,os) \
00079 (EGosGetData(((EGdGraphNode_t*)(v))->data,os[EG_MENGER_MARK],unsigned int))
00080 #define EGmengerGetOrigMark(v,os) \
00081 (EGosGetData(((EGdGraphNode_t*)(v))->data,os[EG_MENGER_ORIG_MARK],unsigned int))
00082 #define EGmengerGetFather(v,os) \
00083 (EGosGetData(((EGdGraphNode_t*)(v))->data,os[EG_MENGER_FATHER],EGdGraphEdge_t*))
00084 #define EGmengerGetOrigFather(v,os) \
00085 (EGosGetData(((EGdGraphNode_t*)(v))->data,os[EG_MENGER_ORIG_FATHER],EGdGraphEdge_t*))
00086 #define EGmengerGetHeapConnector(v,os) \
00087 (EGosGetData(((EGdGraphNode_t*)(v))->data,os[EG_MENGER_HEAP_CONNECTOR],EGheapConnector_t*))
00088
00089 #define EGmengerGetEdgeCost(v,os) \
00090 (EGosGetData(((EGdGraphEdge_t*)(v))->data,os[EG_MENGER_ECOST],EGdijkstraCost_t))
00091 #define EGmengerGetEdgeReducedCost(v,os) \
00092 (EGosGetData(((EGdGraphEdge_t*)(v))->data,os[EG_MENGER_REDUCED_ECOST],EGdijkstraCost_t))
00093 #define EGmengerGetEdgeIsInSolution(v,os) \
00094 (EGosGetData(((EGdGraphEdge_t*)(v))->data,os[EG_MENGER_IS_IN_SOL],unsigned int))
00095 #define EGmengerGetEdgeData(v,os) \
00096 (EGosGetData(((EGdGraphEdge_t*)(v))->data,os[EG_MENGER_EDATA],graphNodeP))
00097
00098 int EGmengerEmergencyRecovery (EGdGraph_t * G,
00099 size_t * os);
00100
00101 int EGmengerPathsADV (EGdGraphNode_t * s,
00102 EGdGraphNode_t * t,
00103 EGdijkstraCost_t ubound,
00104 unsigned int npaths,
00105 unsigned int *nfpaths,
00106 EGdijkstraCost_t * menger_val,
00107 EGheap_t * h,
00108 size_t * os,
00109 EGdGraph_t * G);
00110
00111 int EGmengerRecoverGraphAndSolution (EGdGraph_t * G,
00112 size_t * os,
00113 EGdGraphNode_t * s,
00114 EGdGraphNode_t * t,
00115 unsigned int npath,
00116 EGdGraphEdge_t ** path,
00117 unsigned int *path_beg);
00118
00119 #endif
