path_finder.h

Go to the documentation of this file.

 
 
#include <memory>
#include <vector>
#include <string>
#include <cassert>
#include <iostream>
 
namespace HF {
    // Forward declares so we don't need to include these in the header.
    namespace SpatialStructures {
        class Graph;
        class Path;
        class PathMember;
    }
 
    namespace Pathfinding {
        class BoostGraph; // Forward declared to prevent clients from importing boost.  
 
        struct BoostGraphDeleter {
        public:
 
 
            void operator()(BoostGraph * bg) const;
        };
 
        std::unique_ptr<BoostGraph,BoostGraphDeleter> CreateBoostGraph(
            const HF::SpatialStructures::Graph & g,
            const std::string & cost_type = ""
        );
        
 
        HF::SpatialStructures::Path FindPath(BoostGraph * bg, int start_id, int end_id);
        
        std::vector<HF::SpatialStructures::Path> FindPaths(
            BoostGraph * bg,
            const std::vector<int> & start_points,
            const std::vector<int> & end_points
        );
 
 
        std::vector<HF::SpatialStructures::Path> FindAllPaths(BoostGraph * bg);
        
        void InsertPathsIntoArray(
            const BoostGraph* bg,
            const std::vector<int>& start_points,
            const std::vector<int>& end_points,
            HF::SpatialStructures::Path** out_paths,
            HF::SpatialStructures::PathMember** out_path_members,
            int* out_sizes
        );
 
        struct DistanceAndPredecessor{
            std::vector<float>* dist;
            std::vector<int>* pred;
 
            int size = 0; 
 
            inline DistanceAndPredecessor(int size) {
                
                // Preallocate enough space in both arrays to hold n^2 values
                int arr_count = pow(size, 2);
                dist = new std::vector<float>(arr_count, -1);
                pred = new std::vector<int>(arr_count, -1);
 
                this->size = size;
            }
 
            inline float * GetRowOfDist(int i) {
                // Check bounds in debug mode
                assert(i >= 0 && i < size);
 
                return dist->data() + (i * size);
            }
 
 
            inline int * GetRowOfPred(int i) {
                // Check bounds in debug mode
                assert(i >= 0 && i < size);
 
                return pred->data() + (i * size);
            }
        };
            
        DistanceAndPredecessor GenerateDistanceAndPred(const BoostGraph& bg);
            
        void InsertAllToAllPathsIntoArray(BoostGraph* bg, HF::SpatialStructures::Path** out_paths, HF::SpatialStructures::PathMember** out_path_members, int* out_sizes);
    }
}
 
inline std::ostream & operator<<(std::ostream& os, HF::Pathfinding::DistanceAndPredecessor & dist_pred) {
    const int num_nodes = dist_pred.size;
 
    // create strings to add to
    std::string dist_string = "[";
    std::string pred_string = "[";
 
 
    // Iterate through every row
    for (int row = 0; row < num_nodes; row++) {
 
        // Get pointers to beginning and end of both matricies
        const float* dist_row = dist_pred.GetRowOfDist(row);
        const int* pred_row = dist_pred.GetRowOfPred(row);
 
        // Iterate through every column in this row
        for (int col = 0; col < num_nodes; col++) {
            
            // Get values from matricies
            const float dist_value = dist_row[col];
            const int pred_value = pred_row[col];
 
            // Convert values to strings
            dist_string += std::to_string(dist_value);
            pred_string += std::to_string(pred_value);
 
            // Don't print a comma if this is the last element
            if (!(row == num_nodes-1 && col == num_nodes-1)) {
                dist_string += ", ";
                pred_string += ", ";
            }
        }
    }
 
    // cap off both strings
    dist_string += "]";
    pred_string += "]";
 
    // Print dist then predecessor
    os << dist_string << std::endl << pred_string;
    return os;
}