Method ComputeDiameterThread

Algorithms/spatial_validation.cpp:147–205

}
    
void SpatialValidationComponent::ComputeDiameterThread(int start, int end)
{
    int n = (int)elements.size();
    
    
    for (int i = start; i <= end; ++i) {
        int e = elements[i];
        int longest_shortestpath = 0;
        
        // steps from e to others
        std::map<int, int> steps;
        for (int j = 0; j < n; ++j) {
            steps[elements[j]] = elements[j] == e ? 0 :INT_MAX;
        }
        
        std::map<int, bool> visited;
        
        std::vector<Step> cands;
        cands.push_back(Step(e, steps));
        
        std::queue<int> q;
        q.push(e);
        
        while (!q.empty()) {
            int tmpid = q.front();
            q.pop();
            
            //std::make_heap(cands.begin(), cands.end());
            //std::pop_heap(cands.begin(), cands.end());
            
            //Step item = cands.back();
            //cands.pop_back();
            
            //int tmpid = item.eid;
            visited[tmpid] = true;
            
            std::vector<int> nbrs = edges[tmpid];
            for (int j = 0; j < (int)nbrs.size(); ++j) {
                int nb = nbrs[j];
                
                // steps from e -> nb
                int new_steps = steps[tmpid] + 1;
                if (new_steps < steps[nb]) {
                    steps[nb] = new_steps;
                    if (new_steps > longest_shortestpath) {
                        longest_shortestpath = new_steps;
                    }
                }
                
                if (visited.find(nb) == visited.end()) {
                    //cands.push_back(Step(nb, steps));
                    q.push(nb);
                    visited[nb] = true;
                }
            }
        }
        shortest_paths[i] = longest_shortestpath;
    }