Commencer facilement avec Boost Graph

Boost Graph propose de nombreux outils qui nécessitent un certain temps pour tout appréhender. Cependant, il est possible d'utiliser la classe adjacent_list comme boîte à outils généraliste.

#include <boost/graph/adjacency_list.hpp>

Les informations relatives à chaque élément d'un graphe sont enregistrées dans des structures :

struct VertexProperties { ... };
struct EdgeProperties { ... };
struct GraphProperties { ... };

On peut alors créer un graphe générique basé sur adjacent_list. Pour des raisons pratiques, il est préférable de créer un typedef sur cette structure puisqu'elle sera réutilisée plusieurs fois :

typedef boost::adjacency_list<
   boost::vecS, boost::vecS, boost::bidirectionalS,
   boost::property<boost::vertex_bundle_t, VertexProperties>,
   boost::property<boost::edge_bundle_t, EdgeProperties>,
   boost::property<boost::graph_bundle_t, GraphProperties>
> Graph;

Graph  g;

Le type correspondant à la description d'un sommet est accessible via la classe de traits graph_traits :

typedef boost::graph_traits<Graph>::vertex_descriptor vertex_t;

La fonction add_vertex permet d'ajouter un sommet dans un graphe. Les informations attachées au sommet peuvent être spécifiées lors de la création :

struct VertexProperties 
{ 
   std::string name;
   unsigned id;
   VertexProperties() : name(""), id(0) {}
   VertexProperties(std::string const& n, unsigned i) : name(n), id(i) {}
};

vertex_t v1 = boost::add_vertex(g);

vertex_t v2 = boost::add_vertex(VertexProperties("toto", 12), g);

L'opérateur [] permet de récupérer les informations d'un sommet. Il retourne une référence, ce qui permet de pouvoir modifier les informations :

VertexProperties const& vertexProperties = g[v1];
std::cout << "Vertex name : " <<  vertexProperties.name << std::endl;

VertexProperties& vertexProperties = g[v2];
v2.id = 17;

La fonction num_vertices permet de connaître le nombre de sommet dans un graphe :

boost::graph_traits<Graph>::vertices_size_type s = num_vertices(g);

Le type correspondant à la description d'un arc est accessible via la classe de traits graph_traits :

typedef boost::graph_traits<Graph>::edge_descriptor edge_t;

La fonction add_edge permet de connecter deux sommets. Les informations attachées à l'arc peuvent être spécifiées lors de la création :

struct EdgeProperties 
{ 
   float weight;
   float distance;
   EdgeProperties() : weight(0.0), distance(0.0) {}
   EdgeProperties(float w, float d) : weight(w), distance(d) {}
};

std::pair<Graph::edge_descriptor, bool> e1 = boost::add_edge(v1, v2, g);

std::pair<Graph::edge_descriptor, bool> e2 = 
   boost::add_edge(v1, v2, EdgeProperties(1.0, 50.0), g);

L'opérateur [] permet de récupérer les informations d'un arc. Il retourne une référence, ce qui permet de pouvoir modifier les informations :

EdgeProperties const& edgeProperties = g[e1];
std::cout << "Edge weight : " <<  edgeProperties. weight << std::endl;

EdgeProperties& edgeProperties = g[e2];
e2. distance = 103.8;

La fonction num_edges permet de connaître le nombre de sommets dans un graphe :

boost::graph_traits<Graph>::edges_size_type s = num_edges(g);

Il est possible de récupérer les descripteurs des sommets associés à un arc à l'aide des fonctions source() et target() :

Graph::target_descriptor v1 = boost::target(e1, g);
Graph::target_descriptor v2 = boost::source(e5, g);
if (v1 == v2)
   std::cout << "Same vertex" << std::endl;

Boost Graph fournit plusieurs fonctions pour supprimer des éléments d'un graphe. Attention, ces fonctions invalident les itérateurs existants.

clear(g);

clear_in_edges(v1, g);
clear_out_edges(v2, g);

clear_vertex(v1, g);

remove_edge(v1, v2, g);
remove_edge(e3, g);

// il est nécessaire de supprimer les arcs liés à un sommet...
clear_vertex(v1, g);
// ... avant de le supprimer
remove_vertex(v1, g);

Boost Graph fournit des fonctions pour récupérer des itérateurs sur les sommets ou les arcs d'un graphe. Il est ensuite possible de les utiliser directement dans les algorithmes de la bibliothèque standard.

std::pair<vertex_iterator_t, vertex_iterator_t> it = boost::vertices(g);

std::pair<edge_iterator_t, edge_iterator_t> it = boost::edges(g);

std::pair<out_edge_iterator_t, out_edge_iterator_t> it = boost::out_edges(v1, g);

std::pair<in_edge_iterator_t, in_edge_iterator_t> it = boost::in_edges(v1, g);

std::pair<adjacency_iterator_t, adjacency_iterator_t> it =
    boost::adjacent_vertices(v1, g);

On peut alors parcourir tous les éléments sélectionnés. Par exemple, pour afficher le nom de tous les sommets :

std::pair<vertex_iterator_t, vertex_iterator_t> it = boost::vertices(g);
for( ; it.first != it.second; ++it.first)
   std::cout << get(boost::vertex_bundle, g)[*it.first].name << std::endl;

• Breadth First Search
• Connected Components
• Depth First Search
• Strongly Connected Components
• Uniform Cost Search
• Dynamic Connected Components
• Dijkstra's Shortest Paths
• Topological Sort
• Bellman-Ford Shortest Paths
• Transpose
• Johnson's All-Pairs Shortest Paths
• Reverse Cuthill Mckee Ordering
• Kruskal's Minimum Spanning Tree
• Smallest Last Vertex Ordering
• Prim's Minimum Spanning Tree
• Sequential Vertex Coloring

Voir la documentation de Boost Graph pour l'utilisation de ces algorithmes.

La fonction tie de boost/tuple/tuple.hpp permet de récupérer une std::pair directement dans deux variables :

Graph::edge_descriptor e1;
bool succes;
tie(e1, succes) = boost::add_edge(v1, v2, g);
if (succes)
   // using edge e1

adjacency_list est une classe template acceptant plusieurs paramètres permettant de spécifier le comportement de cette classe. Ces paramètres permettent de choisir les types de conteneurs utilisés en interne (OutEdgeList, VertexList et EdgeList), les propriétés associées aux éléments du graphe (VertexProperties, EdgeProperties, GraphProperties et Directed).

Voici la liste des paramètres et les valeurs par défaut de adjacency_list :

adjacency_list<
   OutEdgeList         = vecS, 
   VertexList         = vecS, 
   Directed        = directedS,
   VertexProperties    = no_property,  
   EdgeProperties     = no_property,
   GraphProperties     = no_property, 
   EdgeList        = listS
>

Les types de conteneurs (OutEdgeList, VertexList et EdgeList) peuvent être choisir en utilisant les tags précisés dans la liste suivante :

vecS        = std::vector
listS        = std::list
slistS        = std::slist
setS        = std::set
multisetS    = std::multiset
hash_setS    = std::hash_set

Le choix du type de conteneur aura une influence sur les performances des algorithmes utilisés. La complexité des fonctions de Boost Graph en fonction du type de conteneur est indiquée dans la page suivante : using_adjacency_list.

Le paramètre Directed permet de préciser si le graphe est orienté ou non et si les arcs seront unidirectionnels ou bidirectionnels.

undirectedS        = graphe non orienté
directedS        = graphe orienté avec des arcs unidirectionnels
bidirectionalS        = graphe orienté avec des arcs bidirectionnels

En fonction du type de graphe, certaines fonctions ne seront pas disponibles. Par exemple, avec un graphe orienté unidirectionnel, la fonction in_edges, permettant de récupérer la liste des arcs entrants, n'est pas utilisable. De même, certains algorithmes ne seront possibles que pour certains types de graphes.

directedS ne permet pas de récupérer les arcs entrants dans un sommet (in_edges) d'où l'existence de bidirectionalS. Tous deux sont des graphes orientés au niveau conceptuel. Par défaut, on choisit entre undirectedS ou birectionalS en fonction de la nature du graphe (non orienté / orienté). directedS sera une optimisation possible pour consommer moins de mémoire.

Pour les propriétés associées aux éléments d'un graphe, on peut soit utiliser le mot clé no_property pour ne pas associer d'informations, soit utiliser la méthode décrite dans les chapitres 3-B pour les sommets et 3-C pour les arcs, soit utiliser une des méthodes décrites ensuite.

Il existe deux approches possibles pour enregistrer les informations dans un graphe : utiliser des conteneurs externes (« external property storage ») ou directement dans un graphe (« internal properties »).

III-E-1. Enregistrer les informations dans des conteneurs externes▲

typedef std::map<vertex_t, std::string> names_property_t;
names_property_t names;
boost::associative_property_map<names_property_t> names_map(names);
 
typedef std::map<edge_t, float> weights_property_t;
weights_property_t weights;
boost::associative_property_map<weights_property_t> weights_map(weights);

std::string v1_name = get(names_map, v1) ;
put(names_map, v2, "toto");

std::string v1_name = names_map[v1];
names_map[v2] = "toto";

III-E-2. Enregistrer les informations directement dans le graphe▲

// typedef
typedef boost::property<boost::vertex_name_t, std::string> VertexProperties;
 
// création d'un sommet
vertex_t v1 = boost::add_vertex("toto", g);
 
// récupérer le nom
std::cout << "Vertex name : " <<  g[v1] << std::endl;
 
// modifier le nom
v1 = "titi";

namespace boost {
    enum vertex_data_t { vertex_data };
    BOOST_INSTALL_PROPERTY(vertex, data);
}
typedef property<data_t, int> VertexProperties;

boost::property <boost::vertex_name_t, std::string,            // nom
    boost::property<boost::vertex_index1_t, unsigned,        // id
        boost::property<boost::vertex_distance_t, float> > >    // distance

// modifier le nom
get(boost::vertex_name_t, g)[v1] = "titi";
 
// afficher le nom
std::cout << "Vertex name : " << get(boost::vertex_name_t, g)[v1] << std::endl;

La classe adjacent_list utilise en interne une liste de sommets auxquels sont associés une liste d'arcs. Il existe une autre structure, adjacent_matrix, qui utilise un tableau 2D pour représenter chaque arc, ce qui permet un accès en O(1) aux arcs.