Ontologenius Cpp Documentation

Contents

Getting Start

Overview

All C++ Classes


All Python Classes

Advanced knowledge exploration (cpp)

How to go home ?

Find our way

Before starting, here is the body of our program with a function that will allow us to display routes. Routes will be represented by a vector of strings.

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

#include "ros/ros.h"
#include "ontologenius/OntologyManipulator.h"

onto::OntologyManipulator* onto_;

void displayRoute(std::vector<std::string> route)
{
for(auto& path : route)
std::cout << path << " - ";
std::cout << std::endl;
}

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

onto::OntologyManipulator onto;
onto_ = &onto;

onto.close();

/*
We will find the route here
*/

return 0;
}

We can notice the presence of the ontology manipulator as well as its pointer as in the previous tutorial.

std::vector<std::vector<std::string> > findRoutes(const std::string& path_from, const std::string& path_to)
{
bool found = false;

std::vector<std::string> tmp = { path_from };
std::vector<std::vector<std::string> > routes = { tmp };

if(path_from == path_to)
found = true;

while(found == false)
{
std::vector<std::vector<std::string> > tmp_routes;
for(auto& route : routes)
{
std::vector<std::string> intersections = onto_->individuals.getFrom("isAlong", route.back());
for(auto& intersection : intersections)
{
std::vector<std::string> paths = onto_->individuals.getOn(intersection, "isAlong");

// erase paths already present in the current route
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;
}

Well, it's just a breadth-first search but it's still not obvious. We will analyze this together because two lines are particularly interesting.

std::vector<std::vector<std::string> > findRoutes(const std::string& path_from, const std::string& path_to)

Let's start with the beginning. This function was used to search for routes linking "path_from" to "path_to".

std::vector<std::string> tmp = { path_from };
std::vector<std::vector<std::string> > routes = { tmp };

"routes" represents a vector of routes since a route is itself a vector of string an we initialize it with a route only composed of the start path.

std::vector<std::vector<std::string> > tmp_routes;
for(auto& route : routes)

Since we use a breadth-first search, we browse the set of current routes at each itteration and we rank the routes found at the current iteration in the variable tmp_routes.

std::vector<std::string> intersections = onto_->individuals.getFrom("isAlong", route.back());

IMPORTANT:

We can represent the use of a property like this: individual_1 property individual_2
In the case of our paths, it comes down to this: intersection_i isAlong path_j

The getFrom function returns all the red individuals who apply the green property to the blue individual.
That means in our case that we are going to have all of the individuals along the path route.back(). However, that means that we are going to have the intersections as well as the other elements, but that is not a big deal at the moment.

Notice how with a single line we are able to retrieve accurate information from our knowledge base.

for(auto& intersection : intersections)

We are now going through all of our intersections to see where they can lead us.

std::vector<std::string> paths = onto_->individuals.getOn(intersection, "isAlong");

IMPORTANT:

Let's take again the fact that: intersection_i isAlong path_j

The getOn function will make it possible to achieve the inverse of the getFrom function. We will retrieve the set of blue individuals that are connected to the red individual by the green property. In our case, we are going to have all the paths for which the intersection intersection is along.

for(auto& path : paths)

For all paths not already present in route_i, we create a new route which is the route_i plus the intersection leading to the new path as well as the new path.

routes.swap(tmp_routes);

At the end of the current iteration, the new routes of work become the current ones.

Find a route from one place to another

The preceding function can find paths from one path to another except that we want a single path from one place to another. The following algorithm is doing this. We will analyze it quickly together.

std::vector<std::string> find(const std::string& from, const std::string& to)
{
std::vector<std::string> best_route;
size_t min_size = -1;

std::vector<std::string> paths_from = onto_->individuals.getOn(from, "isAlong");
std::vector<std::string> paths_to = onto_->individuals.getFrom("hasAlong", to);

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

return best_route;
}
std::vector<std::string> best_route;
size_t min_size = -1;

"best_route" is going to be our final route and "min_size" will allow us to find the road with the least steps.

By setting "min_size" to -1 while its type is unsigned we have the largest size possible.

std::vector<std::string> paths_from = onto_->individuals.getOn(from, "isAlong");
std::vector<std::string> paths_to = onto_->individuals.getFrom("hasAlong", to);

Now that you know the getOn and getFrom functions, you should understand what we are doing here. In fact, these two lines do exactly the same thing but in two different places (from and to). Indeed, hasAlong is the inverse property of isAlong or getOn is the inverse function of getFrom, so these two lines return to the same.

For each one of the places from and to we recover the paths of which they are along.

In the rest of the algorithm, we perform a search from the start path to the end path and only take the paths that actually lead to the end path and have a size smaller than the last shortest route found.

Update the main function

We can finally add the following lines in our main function to realize the path search for the three bob's itineraries.

std::vector<std::string> route;

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

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

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

Compile and launch the program. You should have the following result:

road_2 - int_7 - pp_4 - int_12 - road_3 -
road_3 - int_11 - pp_3 - int_10 - road_4 -
road_4 - int_10 - pp_3 - int_11 - road_3 -