#
source:
orange/source/orangeom/pathfinder.hpp
@
6925:b0923952dc8b

Revision 6925:b0923952dc8b, 4.7 KB checked in by anzevap <anzevap@…>, 4 years ago (diff) |
---|

Line | |
---|---|

1 | /* |

2 | * Pathfinder algorithm for Orange |

3 | * |

4 | * @author: Anze Vavpetic <anze.vavpetic@gmail.com> |

5 | * @summary: Implementation of the binary pathfinder algorithm and an improvement for sparse networks |

6 | */ |

7 | |

8 | #ifndef __PATHFINDER_HPP |

9 | #define __PATHFINDER_HPP |

10 | |

11 | #include "Python.h" |

12 | #include <math.h> |

13 | #include <limits> |

14 | #include <vector> |

15 | #include <algorithm> |

16 | #include <queue> |

17 | |

18 | #include "px/orangeom_globals.hpp" |

19 | #include "root.hpp" |

20 | #include "graph.hpp" |

21 | #include "pq.hpp" |

22 | |

23 | //#define STATISTICS |

24 | #define INFINITY numeric_limits<int>::max() |

25 | #define OUTER 0 |

26 | #define COMPLETED 1 |

27 | #define ACTIVE 2 |

28 | |

29 | using namespace std; |

30 | |

31 | // Some typedefs for a cleaner code |

32 | typedef vector< vector<double> > Matrix; |

33 | typedef vector< double > Vector; |

34 | |

35 | /** |

36 | * Class implementing the pq element used in sparse pf. |

37 | */ |

38 | template <class Key> |

39 | class SPFNode : public PQNode<Key> { |

40 | public: |

41 | /** |

42 | * Class constructor |

43 | * |

44 | * @param v: vertex index |

45 | * @param d: distance to the source vertex |

46 | */ |

47 | SPFNode(const int &v, const double &d, const short int &state); |

48 | |

49 | short int m_state; // State of the vertex |

50 | int m_v; // Vertex index |

51 | }; |

52 | typedef SPFNode<double> SparseNode; |

53 | |

54 | /** |

55 | * Class implementing the queue element used in BFS |

56 | */ |

57 | class BFSNode { |

58 | public: |

59 | /** |

60 | * Class constructor |

61 | */ |

62 | BFSNode(const int &idx, const double &d, const int &len); |

63 | |

64 | int m_idx; // Vertex index |

65 | int m_len; // Number of links between this node and the source for the current distance |

66 | double m_d; // Distance to the source node |

67 | }; |

68 | |

69 | OMWRAPPER(Pathfinder) |

70 | |

71 | class ORANGEOM_API TPathfinder : public TOrange { |

72 | public: |

73 | __REGISTER_CLASS |

74 | |

75 | /** |

76 | * Class constructor. |

77 | */ |

78 | TPathfinder(); |

79 | |

80 | /** |

81 | * Class desctructor. |

82 | */ |

83 | virtual ~TPathfinder(); |

84 | |

85 | /** |

86 | * Transforms the given graph g to a Pathfinder network with the given parameters. |

87 | * |

88 | * Parameters to be used when constructing PFNETs: |

89 | * @param r: Minkowski r-metric, r >= 1. Note: r should be passed as |

90 | * numeric_limits<int>::max() in order to be recognized as 'infinity'! |

91 | * @param q: The maximum number of intermediate links to be considered |

92 | * @param g: Target graph. |

93 | * @param method: The method to be used. Can be "sparse" or "dense". |

94 | * Note that only the sparse method is exported to Orange. |

95 | */ |

96 | void toPFNET(int r, int q, TGraph *g, const string &method); |

97 | |

98 | /** |

99 | * Sets the progress callback function. |

100 | */ |

101 | inline void setProgressCallback(PyObject *cb) { progressCallback = cb; } |

102 | |

103 | /** |

104 | * The progress callback function reference. |

105 | */ |

106 | PyObject *progressCallback; // Progress callback function |

107 | private: |

108 | /** |

109 | * Constructs a PFNET out of the given graph g. |

110 | * |

111 | * @param g: The orange graph to be transformed |

112 | */ |

113 | void toPFNET_binary(TGraph *g); |

114 | |

115 | /** |

116 | * Pathfinder procedure optimized for sparse networks. |

117 | * |

118 | * @param g: The orange graph to be transformed |

119 | */ |

120 | void toPFNET_sparse(TGraph *g); |

121 | |

122 | /** |

123 | * Pathfinder procedure using an adapted BFS for q < |V|-1 |

124 | */ |

125 | void BFS(TGraph *g); |

126 | |

127 | /** |

128 | * Calculates a new distance matrix C as C = A op B, where op is defined by: |

129 | * each element C[k,l] is calculated as |

130 | * |

131 | * MIN{ A[k,l], B[k,l], (A[k,m]^r + B[m,l]^r)^(1/r) } |

132 | * |

133 | * @param A: First distance matrix |

134 | * @param B: Second distance matrix |

135 | * @param result: The resulting matrix |

136 | */ |

137 | void TPathfinder::op(const Matrix &A, const Matrix &B, Matrix &result) const; |

138 | |

139 | /** |

140 | * Calculates all the possible new distances between nodes i and j. |

141 | * |

142 | * @param a: Vector a, the i-th line of distance matrix A |

143 | * @param b: Vector b, the j-th line of distance matrix B |

144 | * @param result: vector of possible distances from node i to j |

145 | */ |

146 | void distances(const Vector &a, const Vector &b, Vector &result) const; |

147 | |

148 | /** |

149 | * Returns the distance based on the Minkowski r-metric formula |

150 | * |

151 | * @param a: distance 1 |

152 | * @param b: distance 2 |

153 | * @return combined distance |

154 | */ |

155 | double distance(const double &a, const double &b) const; |

156 | |

157 | /** |

158 | * Return the i-th column of a square matrix |

159 | * |

160 | * @param m: a matrix |

161 | * @param i: the needed column |

162 | * @param col: the i-ith column |

163 | */ |

164 | void getCol(const Matrix &m, int i, Vector &col) const; |

165 | |

166 | /** |

167 | * Handles the progress callback update. |

168 | */ |

169 | void updateProgress(); |

170 | |

171 | int m_r; // Minkowski r-metric parameter |

172 | int m_q; // Maximum number of intermediate links to be considered |

173 | int m_nodes; // Number of nodes of the current graph |

174 | int m_done; // Number of nodes complete |

175 | }; |

176 | |

177 | #endif |

**Note:**See TracBrowser for help on using the repository browser.