USE EXAMPLE: SHORTEST PATH PROBLEM

The previous sections explain how to build the library and how to create a program based on it. Here we present a short example in order to show how to use the components of the library with more details. To illustrate that, we choose a shortest path problem, which is very easy to understand. We consider a network of buses represented by the following graph.

The nodes represent bus stations and the arcs represent the possible move the user can do between the stations using a bus. Each arc has a distance and a speed, representing respectively the distance between the stations and the mean speed of the bus. So, the division distance / speed represents the time it takes to move from a station to another using a particular bus (symbolized by the arc). In the figure, each arc carries three values. The first is the key to identify the arc, the second is the distance and the third is the speed.

One problem can be to find the best way to move from a bus station to another in the network, taking the minimum of time. It is easy to understand that this problem can be seen as a shortest path problem where the lengths of the arcs are in fact the durations distance / speed. The shortest path problem is to find a path between two given nodes in the graph with the shortest length.

The B++ Library provides algorithms to solve this problem. In fact, it actually implements three well-known algorithms: Bellman, Dijkstra and Ford-Bellman. In our example, we will use Dijkstra's algorithm because the lengths of the arcs are positive (condition for using Dijkstra's algorithm) and there are circuits in the graph (condition for not using Bellman's algorithm). Ford and Bellman's algorithm can also be used. We will see now how to code the program that solves our problem, just by using components of the library.

To write the program, we first need to indicate which part of the library we want to use, i.e. which module(s) we want to use. If we look at , we see that there is a submodule named Shortest_path in the module Graph_problem. It provides algorithms to solve the shortest path problem. Here is the code to indicate that we want to use it.

#include <bpp/graph_problem/shortest_path.hpp>

Usually, every time we use an element of the module, for instance a function fct, we should indicate that it comes from the module by identifying the function the following way.

bpp::graphProblemShortestPath::fct(...)

In order to avoid that, we add the following line meaning that we work with the shortest path module.

using namespace bpp::graphProblemShortestPath;

We will need other modules like Graph, but it is automatically included with the module we chose. In fact, any module is designed so the modules it needs are automatically included when we use it.

Then, we have to define a graph structure to model our problem. The B++ Library already provides a structure that is parameterized on the data the nodes and the arcs can carry. That means we only have to define this data to get a full graph structure. The following code specifies the class representing the data carried by an arc.

class arc_data_t {
 public:
 //----------------------------------------------------Data
 tyReal distance;
 tyReal speed;
 //-------------------------------------Default Constructor
 arc_data_t(void) : distance(0.0),speed(0.0) {}
 //---------------------------------Constructor From Stream
 arc_data_t(clInStream & stream_,tyBoolean) {
  clString separator;
  stream_ >> distance >> separator >> speed;
 }
 //--------------------------------------Output Into Stream
 void out(clOutStream & stream_,tyBoolean) const {
  stream_ << distance << " , " << speed;
 }
 //--------------------------------------------------Length
 tyReal length(void) { return distance/speed; }
};

First, we indicates the data carried by an arc: the distance between the two nodes of the arc and the speed of the bus on this arc. Then, two constructors are required. We must implement them if we want the algorithms to be applicable on our graph structure. There are a default constructor (the default values of an arc) and a constructor that reads data from a stream (i.e. a file or the keyboard). Then, there is the out method requested to write into a stream (i.e. a file or the screen). In order to use the shortest path algorithms, we need a method called length that returns the length of the arc. Here, the length is the division distance / speed. The shortest path algorithms need the length information on the arcs. If we do not implement it, the call to the shortest path algorithm will not compile. In the case of flow problems, it will be methods like flow that will be requested; if there is a cost, it will be cost... For the nodes, there is the same kind of specification, but nothing is required from the shortest path algorithms.

class node_data_t {
 public:
 //----------------------------------------------------Data
 clString name;
 //-------------------------------------Default Constructor
 node_data_t(void) : name("") {}
 //---------------------------------Constructor From Stream
 node_data_t(clInStream & stream_,tyBoolean)
 { stream_ >> name; }
 //--------------------------------------Output Into Stream
 void out(clOutStream & stream_,tyBoolean) const
 { stream_ << name; }
};

In order to have a clear code, we redefine some types with shorter names.

typedef clDijkstraAlgo<arc_data_t,node_data_t> algo_t;
typedef clArc<arc_data_t,node_data_t>          arc_t;
typedef clGraph<arc_data_t,node_data_t>        network_t;
typedef clNode<arc_data_t,node_data_t>         node_t;
typedef std::vector<arc_t *>                   path_t;

We choose here to use Dijkstra's algorithm to solve the problem. The algorithm is represented by a class parameterized, as the graph structure, on the data carried by the arcs and the nodes. The code above defines the type algo_t that is Dijkstra's algorithm for the specific kind of data we use for our problem. The same way, we define the arc, the node and the graph types. We also define the type of the path we will find, the structure of the path is simply a vector (i.e. an array) of pointers on the arcs forming the path.

When a structure or an algorithm is parameterized, we must "instantiate" them by specifying the parameters. Here, from a generalized graph structure and a generalized Dijkstra's algorithm for shortest path, we instantiate a graph structure and a Dijkstra's algorithm specifically for our problem. Finally, we have all the elements to write the program.

#include <bpp/display/console.hpp>

int main(void) {
 // B++ Library Initialization //
 bpp::displayConsole::clDisplay display;
 bpp::standard::openLibrary(display);

 try {
  // Local Variables //
  clInFile  input;
  network_t network;
  clOutFile output;
  path_t    path;

  // Input Reading //
  input.open("network.dat",ios::in);
  input >> network;
  input.close();

  // Shortest Path Resolution //
  algo_t().run(network,0,6,path);

  // Output Writing //
  output.open("path.dat",ios::out);
  output << "Path = " << path;
  output.close();
 }

 catch (...)
 { std::cout << "An error occurred !" << std::endl; }

 // B++ Library Termination //
 bpp::standard::closeLibrary();

 exit(0);
}

First, we have to initialize the library (we have to choose a display, here we use the one in the Display/Console module). Then, we declare variables: a graph structure that will represent our problem, two files, one contains the input data, the other one the output data, and a path structure that represents the shortest path found by Dijkstra's algorithm. Then, we read data from a file called network.dat. The algorithm is asked to find a shortest path between node A (0) and node G (6). The result path is written into a file named path.dat. Finally, the B++ Library must be terminated. The use of the library is supervised using try and catch in order to verify if an error is thrown.

Note that the library needs to be initialized. For this reason, you can not declare static elements from the library, because you use the library before its initialization. If you need static elements from the library, you have to declare pointers instead and deal yourself with the allocation of the objects.

The B++ Library uses a specific format to import and export graph structures into files. In our example, here is what the input data file containing the network looks like.

<graph_start>

nb_nodes = 10
nb_arcs = 15
solved = no

<nodes_start>
node 0 = A
node 1 = B
node 2 = C
node 3 = D
node 4 = E
node 5 = F
node 6 = G
node 7 = H
node 8 = I
node 9 = J
<nodes_end>

<arcs_start>
arc 0 = 1 , 3 ; 4 , 5
arc 1 = 7 , 1 ; 16 , 6
arc 2 = 1 , 6 ; 10 , 6
arc 3 = 5 , 6 ; 3 , 4
arc 4 = 3 , 4 ; 4 , 5
arc 5 = 7 , 9 ; 12 , 6
arc 6 = 4 , 2 ; 8 , 7
arc 7 = 0 , 7 ; 7 , 4
arc 8 = 9 , 1 ; 9 , 5
arc 9 = 5 , 9 ; 14 , 6
arc 10 = 8 , 0 ; 13 , 3
arc 11 = 9 , 2 ; 17 , 4
arc 12 = 8 , 1 ; 8 , 5
arc 13 = 3 , 8 ; 11 , 7
arc 14 = 2 , 6 ; 10 , 6
<arcs_end>

<graph_end>

The nodes and the arcs are listed. They are identified by a number. For each node, the data it carries is listed. Here, there is only its name. For each arc, the source and the target nodes are specified, and then the data the arc carries is listed. In our example, there are the distance and the speed. Here is now what the output file looks like.

Path = 2 1 7

It simply describes the shortest path by enumerating the keys of the arcs forming it.

You can find here the whole program previously described. To compile this program, see the section . It is just a little example of what can be done with the B++ Library. However most of the modules of the library work the same way, especially the modules to solve problems in graphs. To get a better idea of the possibilities offered by the library, you should look at and that are tools designed with the B++ Library.