Introduction

Un graphe c’est un outil qui nous permet de représenter des données (des noeuds ou sommets) qui peuvent être liées les unes au autres grâce à des liens (des arrêtes). Les graphes permettent de :

• trier des données et accélérer leur recherche ;
• modéliser un réseau routier ou de transports ;
• découper la grammaire d’une ligne de code ;
• découper une opération arithmétique ;
• représenter les interactions et les gens que vous suivez et qui vous suivent sur les réseaux sociaux ;
• représenter un organigramme au travail ;
• modéliser un système de fichier ;
• représenter de la logique booléenne.

Certains de ces champs d’application des graphes nécessitent des arbres (des graphes où les nœuds ont une relation parent-enfant et où un lien en dehors de cette relation ne peut pas exister). Certains arbres limitent au nombre de deux les noeuds enfant d’un même parents, on parle alors d’arbre binaire.

En anglais on utilisera les termes de :

• node pour la donnée ;
• link, edge, arc pour les arrêtes entre les données ;
• tree pour les abres
• binary tree pour les arbres binaires.

Exercice en classe : s’habituer aux types de graphes

Pendant : 20 minutes.

Tirez au sorts les groupes de 2 personnes et pour chaque groupe 3 concepts qui peuvent être représentés par des graphes. Pour chaque concept de graphe tiré au sort essayez d’en trouver un exemple sur internet ou d’en fabriquer un. Essayez de donner une situation précise dans laquelle un graphe est utilisé.

Vous présenterez et expliquerez à la classe :

• comment vous interprétez le graphe ;
• s’il s’agit d’un type de graphe spécifique (comme un arbre, un arbre binaire, un arbre équilibré, ou un graphe).

Besoin de quoi pour coder un graphe ?

Un graphe c’est un mélange de données et de liens entre ces données. Quand on implémente un graphe on doit choisir comment stocker ces liens :

• soit dans la structure de la donnée directement ;
• soit dans un collection à côté de la donnée.

Stockage des liens avec la donnée

Exemple en typescript, où on stockerait les liens dans les deux sens pour faciliter les retours en arrière. Notez : ça n’est pas toujours utile d’avoir des liens bi-directionnels.

type GraphNode = {
	text: string;
	linked_nodes: GraphNode[];
};

const graph: GraphNode = {
	text: "Root Node",
	linked_nodes: [],
};

const node_1: GraphNode = {
	text: "Node 1",
	linked_nodes: [graph],
}
graph.linked_nodes.push(node_1);

const node_2: GraphNode = {
	text: "Node 2",
	linked_nodes: [graph],
}
graph.linked_nodes.push(node_2);

const node_1_1: GraphNode = {
	text: "Node 1/1",
	linked_nodes: [node_1],
}
node_1.linked_nodes.push(node_1_1);
const node_1_2: GraphNode = {
	text: "Node 1/2",
	linked_nodes: [node_1],
}
node_1.linked_nodes.push(node_1_2);

Ensuite il est possible de visiter le graph avec cet algorithme :

• on ajoute le noeud actuel à la liste des noeuds visités ;
• pour chaque lien on regarde si le noeud de l’autre côté à déjà été visité ;
• s’il n’a jamais été visité on applique cet algorithme de façon récursive.

Il peut être implémenté ainsi en typescript (avec des tabulations en fonctions de la profondeur, pour rendre la sortie plus lisible) :

class Visitor {
	visited: GraphNode[];

	constructor() {
		this.visited = [];
	}

	visit(root: GraphNode, depth = 0) {
		this.visited.push(root);
		console.log(`${"\t".repeat(depth)}visiting ${root.text}`);
		for (const linked of root.linked_nodes) {
			if (!this.visited.some((item) => item == linked)) {
				this.visit(linked, depth + 1);
			} else {
				console.log(`${"\t".repeat(depth + 1)}NOT visiting ${linked.text} again`);
			}
		}
	}
}

Cet algorithme à un nom : il s’agit d’un algorithme de traversée en profondeur, ou depth-first. C’est parce qu’il visite les éléments liés immédiatement après les avoir trouvé, ce qui signifie qu’on s’enfonce dans l’arbre. On visitera le Node 2 qu’après avoir visité tous les nœuds reliés au Node 1.

Cet algorithme a un frère, l’algorithme de traversée en largeur, breadth-first. breadth étant un synonyme de width.

Son implémentation nécessite de mettre dans une file d’attente les nouveaux noeuds que l’on vient de trouver, pour finir de traiter les noeuds du niveau actuel.

Algorithme de traversée en largeur :

• on ajoute le noeud actuel à la liste des noeuds visités ;
• on ajoute le noeud actuel à la file d’attente ;
• pour chaque noeud en file d’attente
  • on affiche que l’on a visité le noeud
  • pour chaque noeud lié, s’il n’est pas dans la liste des noeuds visités
    • on l’ajoute à la liste des noeuds visités
    • on l’ajoute à la file d’attente

Exercice

En suivant cette algorithme sur le même exemple que la traversée en largeur, déterminez quelle sera sa sortie.

Stockage à plat

Si notre donnée est identifiable par une clé stable (comme un identifiant numérique typique aux bases de donnée ou une chaîne de caractères qui lui est unique), alors il est possible d’organiser son stockage ainsi :

type FlatGraph<T> = {
	data: {
		[id: number]: T;
	};
	links: [number, number][],
}

const flat_graph: FlatGraph<string> = {
	data: {
		1: "Root",
		2: "Node 1",
		3: "Node 2",
		4: "Node 1/1",
		5: "Node 1/2"
	},
	links: [
		[1, 2],
		[1, 3],
		[2, 4],
		[2, 5],
	]
};

L’avantage du stockage à plat ?

• gestion de la mémoire simplifiée dans les langages où elle peut être difficile ;
• sérialisation simplifiée, on peut plus facilement enregistrer le graph dans un fichier ou une base de donnée.

Voici ce que Gemini 3 flash a à dire sur ce sujet (ref) :

En rust

En rust il est possible de se représenter un graphe avec les deux méthodes, avec des références (potentiellement circulaires) et en utilisant des HashMap et Vec plats.

La technique des références circulaires nécessite l’utilisation de :

• std::rc::Rc le reference counter :
  • il permet de détenir un pointeur vers une donnée,
  • de libérer la mémoire lorsque la dernière instance est drop
  • mais il ne permet pas de modifier la donnée ;
• std::cell::RefCell :
  • elle permet la modification d’une donnée contenue dans un contexte constant comme celui d’un reference counter,
  • la vérification est faite à l’exécution (là où en rust, les vérification sont souvent faites à la compilation).

Voici un exemple qui reprend la traversée en profondeur que nous avons vu en typescript au dessus, remarquez :

• qu’on se souvent des nœuds visités grâce à leur adresse en mémoire ;
• que l’on doit .borrow() un RefCell pour lire ce qu’il contient ;
• que l’on doit .borrow_mut() un RefCell pour modifier ce qu’il contient ;
• que l’on doit .clone() un Rc pour le passer à une fonction qui attend un Rc et que l’on ne veut pas le déplacer (comme on ferait avec une String.

use colored::Colorize;
use std::{cell::RefCell, collections::HashSet, rc::Rc};

struct GraphNode {
    text: String,
    links: Vec<Rc<RefCell<GraphNode>>>,
}

struct NodeVisitor {
    visited: HashSet<*const GraphNode>,
}

impl NodeVisitor {
    fn visit(&mut self, node: Rc<RefCell<GraphNode>>) {
        self.visit_internal(node, 0);
    }

    fn visit_internal(&mut self, node: Rc<RefCell<GraphNode>>, depth: usize) {
        self.visited.insert(node.as_ptr());
        let borrowed_node = node.borrow();
        for _ in 0..depth {
            print!("\t");
        }
        println!("visited {}", borrowed_node.text);
        for item in &borrowed_node.links {
            if !self.visited.contains(&(item.as_ptr() as *const _)) {
                self.visit_internal(item.clone(), depth + 1);
            } else {
                for _ in 0..depth + 1 {
                    print!("\t");
                }
                println!(
                    "{}",
                    format!("already visited {}", item.borrow().text).red()
                );
            }
        }
    }
}

fn main() {
    let node1 = Rc::new(RefCell::new(GraphNode {
        text: "Root".to_string(),
        links: vec![],
    }));

    let node1_1 = Rc::new(RefCell::new(GraphNode {
        text: "Level 1 - Branch A".to_string(),
        links: vec![],
    }));

    let node1_2 = Rc::new(RefCell::new(GraphNode {
        text: "Level 1 - Branch B".to_string(),
        links: vec![],
    }));

    let node1_3 = Rc::new(RefCell::new(GraphNode {
        text: "Level 1 - Branch C".to_string(),
        links: vec![],
    }));

    {
        let mut base = node1.borrow_mut();
        base.links.push(node1_1.clone());
        base.links.push(node1_2.clone());
        base.links.push(node1_3.clone());
    }
}

Essayez d’ajouter des noeuds vous même et de créer des références circulaires pour voir comment se comporte le programme.