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 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 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
Usually, every time we use an element of the module, for instance a function
In order to avoid that, we add the following line meaning that we work with the shortest path module.
We will need other modules like
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.
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
In order to have a clear code, we redefine some types with shorter names.
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 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.
First, we have to initialize the library (we have to choose a display, here we use the one in the 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.
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.
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. |