Deep Blog

Algorithmique avec Rust: Graphe


Bonjour, aujourd’hui on va parler de graphe: ce que c’est et comment le représenter en Rust.

Mais avant petite info. Au départ, je pensais parler du tri fusion, toutefois, Vaidehi Joshi à couvert le sujet dans son article Making sense of merge sort. Je vous conseille de le lire, il est très pertinent.

Revenons-en au sujet: les GRAPHES!

"OK, c’est quoi un graphe?"

Pour faire simple, un graphe c’est un ensemble de points, appelés nœuds ou sommets, reliés par des traits, appelés arêtes. Dans certains cas, les arêtes sont orientées, comme des flèches, et dans ce cas le graphe sera dit orienté.

[caption id="" align="aligncenter" width="231"]File:Directed graph no background.svg Graphe orienté[/caption]

Dans le cas contraire, le graphe sera non orienté.

[caption id="" align="aligncenter" width="333"]File:6n-graf.svg Graphe non orienté[/caption]

Je passe sur les familles de graphes pour le moment, plus d’infos sur la page Wikipédia qui en parle très bien.

"OK, mais à quoi ça sert?"

Quel lecteur incroyable, c’est encore une très bonne question!

Et là, je vous réponds avec un scoop! vous les voyez, vous les utilisez et vous ne le savez pas. "Où?" me direz-vous. Les réseaux sociaux, les télécommunications, etc. Même dans la programmation orientée objet vous pouvez voir un graphe (imbrication d’objet).

"OK, un graphe c’est utile. Comment qu’on les programme?"

Comme la série traite du langage Rust, je vais vous montrer UNE méthode pour créer une telle structure dans ce langage.

D’abord, nous pouvons résumer notre graphe par le fait qu’il possède un ensemble de nœuds, un ensemble d’arêtes et qu’il peut être orienté.

struct Graph<'a> {
  nodes: Vec<&'a Node>,
  edges: Vec<Edge<'a>>,
  oriented: bool,
}

Ensuite, nous devons définir les nœuds et les arêtes.

struct Node {}

struct Edge<'a> {
  source_node: &'a Node,
  target_node: &'a Node,
}

Nous avons donc les structures nécessaires pour faire un graphe.

Lien vers l’exemple: lien.

On va s’arrêter là pour aujourd’hui, je ne voudrais pas vous endormir. On se retrouve prochainement pour jouer avec les graphes.

-- Mathieu