Speed up your algorithms (cpp)

Run Forrest! Run !

Solution

Here is a possible solution with use of templates. You can note that we have queried the index of the property "isAlong" only once at the initialisation to avoid to recompute static information. In a more usual way using classes, you could create a map with all the "static" indexes.

#include <iostream>
#include <vector>
#include <string>

#include "ontologenius/OntologyManipulatorIndex.h"

onto::OntologyManipulatorIndex* onto_;
int64_t is_along_ = 0;

void displayRoute(std::vector<int64_t> route)
{
std::vector<std::string> indentifier_route = onto_->conversion.individualsIndex2Id(route);
for(auto& path : indentifier_route)
std::cout << path << " - ";
std::cout << std::endl;
}

template<typename T>
std::vector<std::vector<T> > findRoutes(T path_from, T path_to, T selector)
{
std::vector<std::vector<T> > routes;
bool found = false;

std::vector<T> tmp;
tmp.push_back(path_from);
routes.push_back(tmp);

if(path_from == path_to)
found = true;

while(found == false)
{
std::vector<std::vector<T> > tmp_routes;
for(auto& route : routes)
{
std::vector<T> intersections = onto_->individuals.getFrom(is_along_, route.back());

for(auto& intersection : intersections)
{
std::vector<T> paths = onto_->individuals.getOn(intersection, is_along_, selector);

for(size_t i = 0; i < paths.size();)
if(std::find(route.begin(), route.end(), paths[i]) != route.end())
paths.erase(paths.begin() + i);
else
i++;

for(auto& path : paths)
{
tmp = route;
tmp.push_back(intersection);
tmp.push_back(path);
tmp_routes.push_back(tmp);
if(path == path_to)
found = true;
}
}
}
routes.swap(tmp_routes);
}

return routes;
}

template<typename T>
std::vector<T> find(T from, T to, T selector)
{
std::vector<T> solution_route;
size_t min_size = -1;

std::vector<T> paths_from = onto_->individuals.getOn(from, is_along_, selector);
std::vector<T> paths_to = onto_->individuals.getOn(to, is_along_, selector);

for(auto& path_from : paths_from)
for(auto& path_to : paths_to)
{
std::vector<std::vector<T> > routes = findRoutes(path_from, path_to, selector);
for(auto& route : routes)
if(route.back() == path_to)
if(route.size() < min_size)
{
min_size = route.size();
solution_route = route;
}
}

return solution_route;
}
int main(int argc, char** argv)
{
ros::init(argc, argv, "find_our_way");

onto::OntologyManipulatorIndex onto;
onto_ = &onto;

onto.close();

is_along_ = onto.conversion.objectPropertiesId2Index("isAlong");
int64_t pub = onto.conversion.individualsId2Index("pub");
int64_t house = onto.conversion.individualsId2Index("house");
int64_t car = onto.conversion.individualsId2Index("car");
int64_t path = onto.conversion.classesId2Index("path");
int64_t road = onto.conversion.classesId2Index("road");
std::vector<int64_t> route;

route = find(pub, house, path);
displayRoute(route);

route = find(house, car, path);
displayRoute(route);

route = find(car, house, road);
displayRoute(route);

return 0;
}