Graphes et Julia

Julia est un langage de programmation orienté vers les applications scientifiques. Ces dernières ont assez souvent besoin de travailler avec des graphes, des structures de données assez courantes. LightGraphs.jl est une implémentation de haute performance tant de la structure de données que d'algorithmes classiques sur des graphes.

3 commentaires Donner une note  l'article (5)

Article lu   fois.

L'auteur

Profil Pro

Liens sociaux

Viadeo Twitter Facebook Share on Google+   

1. Écosystème de LightGraphs.jl

LightGraphs.jl est le paquet central des graphes en Julia (d'autres implémentations des graphes existent, mais ne sont plus développées, comme Graphs.jl ou Graft.jl). Il propose une implémentation des graphes dirigés et non dirigés, mais sans métadonnées. LightGraphsExtras.jl propose une série d'algorithmes supplémentaires, nécessitant un solveur d'optimisation mathématique (ce qui a justifié leur non-intégration au paquet de base).

Pour associer des métadonnées au graphe, SimpleWeightedGraphs.jl permet d'ajouter des poids à chaque arête (avec une représentation adaptée) et MetaGraphs.jl des métadonnées plus génériques à n'importe quelle arête ou n'importe quel nœud.

GraphIO.jl implémente une série de formats de graphe, comme GML ou DOT. GraphPlot.jl met à disposition des visualisations de graphes (en se basant sur Compose.jl).

Tous ces paquets sont inscrits dans le gestionnaire de paquets de Julia. Leur installation peut donc se faire depuis l'interface en ligne de commande de Julia. L'entrée dans le mode gestion de paquets se fait avec la touche ], puis l'installation comme ceci :

 
Sélectionnez
add LightGraphs
add LightGraphsExtras SimpleWeightedGraphs MetaGraphs GraphIO GraphPlot

2. Création d'un graphe

La manière la plus simple de créer un graphe est de le spécifier arête par arête. Il n'y a pas besoin de déclarer les nœuds : en général, on les numérote simplement par des entiers (en commençant par 1, comme d'habitude en Julia). Par contre, dès la construction du graphe, il faut indiquer le nombre de nœuds :

 
Sélectionnez
using LightGraphs

g = Graph(3)
add_edge!(g, 1, 2)
add_edge!(g, 1, 3)
add_edge!(g, 2, 3)

Pour créer un graphe dirigé, le type de base est plutôt DiGraph :

 
Sélectionnez
g = DiGraph(3)
add_edge!(g, 1, 2)
add_edge!(g, 1, 3)
add_edge!(g, 2, 3)

2.1. Graphes pondérés

Les graphes pondérés utilisent une syntaxe légèrement différente, puisqu'il faut indiquer le poids de chaque arête lors de sa création :

 
Sélectionnez
using LightGraphs, SimpleWeightedGraphs

g = SimpleWeightedGraph(3)
add_edge!(g, 1, 2, 0.3)
add_edge!(g, 1, 3, 0.5)
add_edge!(g, 2, 3, 0.2)

De manière similaire, SimpleWeightedDiGraph permet de créer un graphe dirigé pondéré.

2.2. Graphes avec métadonnées

MetaGraph est une généralisation des graphes pondérés : cette structure de données propose, par défaut, de stocker un poids pour chaque arête, mais aussi n'importe quelle autre information. Si rien n'est précisé, chaque arête a un poids unitaire.

 
Sélectionnez
using LightGraphs, MetaGraphs

g = MetaGraph(3) 
add_edge!(g, 1, 2)
add_edge!(g, 1, 3)
add_edge!(g, 2, 3)

set_prop!(g, 1, 2, :weight, 0.3)
# Équivalent : set_prop!(g, Edge(1, 2), :weight, 0.3)
set_prop!(g, 1, 3, :desc, "An edge") # Propriété d'une arête
set_prop!(g, 1, :name, "One") # Propriété d'un nœud
set_prop!(g, :name, "Graph 1") # Propriété du graphe

get_prop(g, 1, 3, :desc) # "An edge"
get_prop(g, 1, :name) # "One"
get_prop(g, :name) # "Graph 1"

props(g) # Dictionnaire des propriétés associées au graphe
# Dict{Symbol,Any} with 1 entry:
#   :name => "Graph 1"

Comme d'habitude, la variante dirigée est nommée MetaDiGraph.

Si Julia accueille l'un de ces codes avec un message d'erreur comme no method matching add_edge!, assurez-vous d'avoir bien importé le paquet LightGraphs !

3. Calcul de plus court chemin

La famille d'algorithmes la plus utilisée sur les graphes est sans conteste le calcul de plus court chemin. Il s'agit de déterminer une séquence d'arêtes, depuis l'origine jusqu'à la destination, qui minimise une mesure de distance (soit la somme des poids associés à chaque arête, soit le nombre d'arêtes traversées). La magie de LightGraphs est que ces algorithmes fonctionnent peu importe la représentation du graphe (pondéré ou avec métadonnées).

L'algorithme le plus courant pour le calcul de plus court chemin est sûrement celui de Dijkstra (à prononcer dɛɪkstra). Il détermine le plus court chemin vers tous les nœuds du graphe depuis une source, de manière exacte. L'une de ses hypothèses est que les poids sont positifs ou nuls.

 
Sélectionnez
using LightGraphs

g = Graph(3)
add_edge!(g, 1, 2)
add_edge!(g, 1, 3)
add_edge!(g, 2, 3)

p = dijkstra_shortest_paths(g, 1)

L'objet retourné, un DijkstraState, n'est pas forcément le plus facile à interpréter. Au moins, chaque fonction de calcul de plus court chemin renvoie une structure similaire, légèrement adaptée aux spécificités de chaque algorithme. Une conséquence directe est que toutes les instructions qui suivent peuvent s'adapter à chaque algorithme de plus court chemin (sauf ceux de Floyd-Warshall et de Yen). Le champ dists renvoie la distance vers chacun des nœuds du graphe :

 
Sélectionnez
julia> p.dists
3-element Array{Int64,1}:
 0
 1
 1

La fonction enumerate_paths renvoie, pour chaque nœud, la liste des nœuds (intermédiaires, origine et destination) constituant le plus court chemin.

 
Sélectionnez
julia> enumerate_paths(p)
3-element Array{Array{Int64,1},1}:
 []
 [1, 2]
 [1, 3]

Elle peut aussi prendre un argument pour le nœud de destination, la valeur de retour est alors un seul chemin :

 
Sélectionnez
julia> enumerate_paths(p, 2)
2-element Array{Int64,1}:
 1
 2

LightGraphs propose d'autres algorithmes de calcul de plus court chemin entre deux points : l'algorithme de Bellman-Ford, qui prend en charge les poids négatifs (bellman_ford_shortest_paths) ; l'algorithme de D'Esopo-Pape, souvent plus rapide que celui de Dijkstra, mais avec une complexité asymptotique moins avantageuse (desopo_pape_shortest_paths) ; A*, une variante heuristique de l'algorithme de Dijkstra. Les deux premiers algorithmes s'utilisent de la même manière ; A*, au contraire, prend en entrée le nœud d'origine, celui de destination, ainsi qu'une fonction heuristique (en option).

3.1. Poids pour les arêtes

Jusqu'à présent, les calculs de chemins se faisaient en considérant un poids unitaire pour chaque arête : les algorithmes cherchaient à minimiser le nombre d'arêtes dans chaque chemin, ce qui ne convient pas à toutes les applications.

Dans ce cas, les algorithmes de calcul de plus court chemin prennent un nouvel argument, une matrice de poids. Pour les graphes pondérés, on peut utiliser simplement weights(g). Pour un graphe non pondéré, on peut utiliser une matrice pour indiquer les poids. L'entrée m[i, j] donne le poids de l'arête allant de i vers j :

 
Sélectionnez
m = zeros(3, 3)
m[1, 2] = 1.0
m[1, 3] = 0.1
m[3, 2] = 0.2

De là, le calcul de chemin devient :

 
Sélectionnez
p = dijkstra_shortest_paths(g, 1, m)
p.dists # [0.0, 0.3, 0.1]

La fonction enumerate_paths s'utilise de la même manière que précédemment.

3.2. Algorithme de Floyd-Warshall

L'algorithme de Floyd-Warshall ne calcule pas un plus court chemin, mais tous les plus courts chemins pour toutes les paires origine-destination du graphe. L'appel est donc plus simple (il ne faut pas préciser de source), mais la structure de données renvoyée plus complexe.

 
Sélectionnez
p = floyd_warshall_shortest_paths(g)

Le champ dists est désormais une matrice, le premier indice correspondant à la source et le second à la destination.

 
Sélectionnez
julia> p.dists
3×3 Array{Int64,2}:
 0  1  1
 1  0  1
 1  1  0

enumerate_paths prend en argument la source et la destination :

 
Sélectionnez
julia> enumerate_paths(p, 1, 2)
2-element Array{Int64,1}:
 1
 2

3.3. Algorithme de Yen

Finalement, l'algorithme de Yen détermine les k plus courts chemins entre deux nœuds : le plus court, puis celui qui a une distance totale directement supérieure, jusqu'à atteindre k chemins. De ce fait, l'algorithme prend en entrée tant la source que la destination, mais aussi les poids des arêtes (de manière obligatoire), ainsi que le nombre de chemins à retourner. Ce nombre est un maximum : si l'algorithme de Yen n'en trouve pas autant, il s'arrête, tout simplement.

 
Sélectionnez
p = yen_k_shortest_paths(g, 1, 2, weights(g), 3)

La structure YenState renvoyée ne se traite pas du tout comme les autres structures dans le cadre de plus courts chemins. Elle dispose de deux champs : paths, la liste des chemins trouvés ; dists, leur distance.

 
Sélectionnez
julia> p.paths, p.dists
(Array{Int64,1}[[1, 2], [1, 3, 2]], [1, 2])

4. Visualisation

GraphPlot.jl fournit une fonction magique pour afficher des graphes, gplot. Celle-ci renvoie une structure de données peu intelligible, mais Compose.jl peut la transformer en image. Avec les paquets Cairo et Fontconfig, on peut par exemple l'exporter en PNG.

 
Sélectionnez
using LightGraphs, GraphPlot, Compose, Cairo, Fontconfig

p = gplot(g)
draw(PNG("C:\\Users\\Thibaut\\g.png", 16cm, 16cm), p)
Image non disponible
Résultat de la commande

La fonction gplot prend une série d'arguments pour paramétrer le rendu. Par exemple, on peut spécifier manuellement les positions de chaque nœud, par exemple calculées avec une fonction de disposition de GraphPlot.jl (pour afficher plusieurs fois le graphe avec les mêmes positions pour chaque élément, par exemple) :

 
Sélectionnez
x, y = spring_layout(g)
p = lot(g, x, y)

nodelabel sert à indiquer le nom de chaque nœud et nodefillc la couleur de remplissage de chaque boule. Pour les arêtes, edgestrokec paramètre la couleur du trait et edgelinewidth sont épaisseur.

 
Sélectionnez
node_names = [get_prop(od.g, n, :name) for n in vertices(od.g)]
edge_colours = [(src(e) == 1) ? colorant"red" : colorant"lightgray" for e in edges(g)]
edge_widths = [src(e) for e in edges(g)]
p = gplot(g, nodelabel=node_names, edgestrokec=edge_colours, edgelinewidth=edge_widths)

Pour les couleurs, Colors.jl fournit une manière élégante de les représenter à partir d'un nom : colorant, suivi d'une chaîne de caractères donnant le nom de la couleur : ici, rouge ("red") et gris clair ("lightray").

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+   

  

Copyright © 2019 Thibaut Cuvelier. Aucune reproduction, même partielle, ne peut être faite de ce site ni de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.