35 #ifndef _CYMEALG_PATHMEAN_H_ 36 #define _CYMEALG_PATHMEAN_H_ 39 #include "chomp/system/config.h" 51 template <
class wType,
class arrayType,
class roundType>
53 const roundType &rounding,
const arrayType &starting, int_t n)
56 const int nIndices = 2;
57 wType **F =
new wType * [nIndices];
58 chomp::homology::BitField *finite =
59 new chomp::homology::BitField [nIndices];
60 int_t nVertices (g. countVertices ());
61 for (
int i = 0; i < nIndices; ++ i)
63 F [i] =
new wType [nVertices];
64 finite [i]. allocate (nVertices);
68 for (int_t i = 0; i < n; ++ i)
70 int_t v = starting [i];
71 if ((v < 0) || (v >= nVertices))
72 throw "Starting vertex out of range.";
79 bool firstWeight =
true;
80 int_t maxLength (nVertices + 1);
81 for (int_t len = 1; len < maxLength; ++ len)
84 int_t prevIndex = (len - 1) & 1;
85 int_t curIndex = len & 1;
86 finite [curIndex]. clearall (nVertices);
89 for (int_t source = 0; source < nVertices; ++ source)
91 if (!finite [prevIndex]. test (source))
93 wType prevWeight = F [prevIndex] [source];
96 int_t nEdges = g. countEdges (source);
97 for (
int edge = 0; edge < nEdges; ++ edge)
100 g. getEdge (source, edge);
101 wType newWeight = rounding. add_down
103 g. getWeight (source, edge));
104 if (!finite [curIndex]. test (target))
106 finite [curIndex].
set (target);
107 F [curIndex] [target] = newWeight;
109 else if (newWeight < F [curIndex] [target])
110 F [curIndex] [target] = newWeight;
115 for (int_t vert = 0; vert < nVertices; ++ vert)
117 if (!finite [curIndex]. test (vert))
119 wType average = rounding. div_down
120 (F [curIndex] [vert], len);
126 else if (average < minWeight)
132 for (
int i = 0; i < nIndices; ++ i)
147 template <
class wType,
class arrayType>
149 const arrayType &starting, int_t n)
158 #endif // _CYMEALG_PATHMEAN_H_ This class defines a weighted directed graph with very limited number of operations.
A dummy class for rounding operations which does not actually do any rounding.
This header file contains the definition of a dummy rounding class.
wType minMeanPathWeight(const diGraph< wType > &g, const roundType &rounding, const arrayType &starting, int_t n)
Runs an algorithm based on Karp's idea to compute the minimum mean path weight for paths starting at ...