The CyMeAlg Software (Release 0.01)
pathmean.h
Go to the documentation of this file.
1 /// @addtogroup cymealg
2 /// @{
3 
4 /////////////////////////////////////////////////////////////////////////////
5 ///
6 /// @file
7 ///
8 /// This header file contains a function for the computation of the minimum
9 /// mean path weight. The function is based on Karp's algorithm
10 /// for computing the minimum cycle mean weight.
11 ///
12 /// @author Pawel Pilarczyk
13 ///
14 /////////////////////////////////////////////////////////////////////////////
15 
16 // Copyright (C) 1997-2020 by Pawel Pilarczyk.
17 //
18 // This file is part of my research software. This is free software:
19 // you can redistribute it and/or modify it under the terms of the GNU
20 // General Public License as published by the Free Software Foundation,
21 // either version 3 of the License, or (at your option) any later version.
22 //
23 // This software is distributed in the hope that it will be useful,
24 // but WITHOUT ANY WARRANTY; without even the implied warranty of
25 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
26 // GNU General Public License for more details.
27 //
28 // You should have received a copy of the GNU General Public License
29 // along with this software; see the file "license.txt". If not,
30 // please, see <http://www.gnu.org/licenses/>.
31 
32 // Started in January 2006. Last revision: August 23, 2019.
33 
34 
35 #ifndef _CYMEALG_PATHMEAN_H_
36 #define _CYMEALG_PATHMEAN_H_
37 
38 // include selected header files from the CHomP library
39 #include "chomp/system/config.h"
40 
41 // include selected CyMeAlg header files
42 #include "cymealg/dummyrnd.h"
43 
44 namespace cymealg {
45 
46 /// Runs an algorithm based on Karp's idea to compute the minimum
47 /// mean path weight for paths starting at any of the given
48 /// n vertices and of length not exceeding the number of vertices
49 /// in the graph.
50 /// Returns 0 if no path starts at any of the vertices.
51 template <class wType, class arrayType, class roundType>
53  const roundType &rounding, const arrayType &starting, int_t n)
54 {
55  // allocate arrays for weights and bit fields
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)
62  {
63  F [i] = new wType [nVertices];
64  finite [i]. allocate (nVertices);
65  }
66 
67  // set the zero path lengths from the initial vertices
68  for (int_t i = 0; i < n; ++ i)
69  {
70  int_t v = starting [i];
71  if ((v < 0) || (v >= nVertices))
72  throw "Starting vertex out of range.";
73  F [0] [v] = 0;
74  finite [0]. set (v);
75  }
76 
77  // compute path progressions of given length and average weights
78  wType minWeight (0);
79  bool firstWeight = true;
80  int_t maxLength (nVertices + 1);
81  for (int_t len = 1; len < maxLength; ++ len)
82  {
83  // determine the indices for previous and current paths
84  int_t prevIndex = (len - 1) & 1;
85  int_t curIndex = len & 1;
86  finite [curIndex]. clearall (nVertices);
87 
88  // process source vertices
89  for (int_t source = 0; source < nVertices; ++ source)
90  {
91  if (!finite [prevIndex]. test (source))
92  continue;
93  wType prevWeight = F [prevIndex] [source];
94 
95  // process target vertices (and edges)
96  int_t nEdges = g. countEdges (source);
97  for (int edge = 0; edge < nEdges; ++ edge)
98  {
99  int_t target =
100  g. getEdge (source, edge);
101  wType newWeight = rounding. add_down
102  (prevWeight,
103  g. getWeight (source, edge));
104  if (!finite [curIndex]. test (target))
105  {
106  finite [curIndex]. set (target);
107  F [curIndex] [target] = newWeight;
108  }
109  else if (newWeight < F [curIndex] [target])
110  F [curIndex] [target] = newWeight;
111  }
112  }
113 
114  // update the minimum mean path weight
115  for (int_t vert = 0; vert < nVertices; ++ vert)
116  {
117  if (!finite [curIndex]. test (vert))
118  continue;
119  wType average = rounding. div_down
120  (F [curIndex] [vert], len);
121  if (firstWeight)
122  {
123  minWeight = average;
124  firstWeight = false;
125  }
126  else if (average < minWeight)
127  minWeight = average;
128  }
129  }
130 
131  // release allocated memory
132  for (int i = 0; i < nIndices; ++ i)
133  {
134  finite [i]. free ();
135  delete [] (F [i]);
136  }
137  delete [] finite;
138  delete [] F;
139 
140  // return the computed minimum
141  return minWeight;
142 } /* minMeanPathWeight */
143 
144 // --------------------------------------------------
145 
146 /// The above algorithm without rounding control.
147 template <class wType, class arrayType>
149  const arrayType &starting, int_t n)
150 {
151  const dummyRounding<wType> rounding = dummyRounding<wType> ();
152  return minMeanPathWeight (g, rounding, starting, n);
153 } /* minMeanPathWeight */
154 
155 
156 } // namespace cymealg
157 
158 #endif // _CYMEALG_PATHMEAN_H_
159 
160 /// @}
161 
This class defines a weighted directed graph with very limited number of operations.
Definition: digraph.h:75
A dummy class for rounding operations which does not actually do any rounding.
Definition: dummyrnd.h:45
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&#39;s idea to compute the minimum mean path weight for paths starting at ...
Definition: pathmean.h:52