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

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

Some Pathfinder updates:

  • removed some deprecated code,
  • slight API change,
  • added progress callback functionality.
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
29using namespace std;
30
31// Some typedefs for a cleaner code
32typedef vector< vector<double> > Matrix;
33typedef vector< double > Vector;
34
35/**
36 * Class implementing the pq element used in sparse pf.
37 */
38template <class Key>
39class SPFNode : public PQNode<Key> {
40public:
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};
52typedef SPFNode<double> SparseNode;
53
54/**
55 * Class implementing the queue element used in BFS
56 */
57class BFSNode {
58public:
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
69OMWRAPPER(Pathfinder)
70
71class ORANGEOM_API TPathfinder : public TOrange {
72public:
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
107private:
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.