C1TP – Parcours d’un graphe et plus court chemin

4-tp-graphes.livemd

Aurélien Noce

@ushu

elixir-course

Share to X

Share to Bluesky

More notebooks

C1TP – Parcours d’un graphe et plus court chemin

Mix.install([
  {:kino, "~> 0.16.1"},
  {:phoenix_live_view, "~> 1.1"}
])

ExUnit.configure(exclude: [:skip])
ExUnit.start(autorun: false)

Objectif(s)

Manipuler les listes et maps.
Implémenter un algorithme simple (parcours en largeur ou profondeur).
Découvrir une représentation graphique / automate d’un problème.
Écrire et composer des fonctions.

1. Représenter un graphe

Qu’est-ce qu’un graphe ?

Un graphe $G = (V, E)$ est un couple constitué :

d’un ensemble $V$ de sommets (ou nœuds),
d’un ensemble $E \subseteq { {u, v} \mid u, v \in V, u \ne v }$ de paires non ordonnées appelées arêtes (ou liens).

On parle alors de graphe non orienté et simple (sans boucles ni arêtes multiples).

Exemple :

$$ V = {A, B, C, D}, \quad E = {{A,B}, {A,D}, {B,C}, {C,D} } $$

correspond au graphe suivant:

graph LR
  A --- B
  A --- D
  B --- C
  C --- D

Représentation informatique du graphe

Il existe beaucoup de manière de représenter un graphe. On peut le représenter par une carte (graphe dessiné, voir ci-dessous), par un ensemble de “noeuds” dans la mémoire de l’ordinateur, par une liste d’adjacence, ou encore une matrice d’adjacence.

Dans ce TP, nous utilisons la liste d’adjacence, qui consiste à associer à chaque noeud du graphe la liste des noeuds qui le suivent.

Toujous sur notre exemple, cela donnerait:

graphe_simple = %{
  "A": [ "B", "D" ], # Les "successeurs de A sont B et D
  "B": [ "C" ],      # Le successeur de B est D
  "C": [ "D" ],      # Le successeur de C est D
}

Un graphe plus complet

On considère un petit comme celui-ci pour représenter notre labyrinthe :

graph LR
  classDef start fill:#dff,stroke:#06c,stroke-width:2px;
  classDef goal  fill:#ffd,stroke:#c60,stroke-width:2px;

  A:::start <--> B <--> C
  A <--> D
  B <--> E
  D <--> E <--> F:::goal
  C <--> F

On peut le représenter par une liste d’adjacence :

graph = %{
  "A" => ["B", "D"],
  "B" => ["A", "C", "E"],
  "C" => ["B", "F"],
  "D" => ["A", "E"],
  "E" => ["B", "D", "F"],
  "F" => ["C", "E"]
}

%{ "A" => ["B", "D"], "B" => ["A", "C", "E"], "C" => ["B", "F"], "D" => ["A", "E"], "E" => ["B", "D", "F"], "F" => ["C", "E"] }

💡 on remarquera que dans ce cas, le graphe n’est pas “orienté”: s’il est permis d’aller de $A$ vers $B$, alors ils est permis d’aller de $B$ vers $A$

Écrire une fonction `GraphInfo.neighbors/2` qui renvoie la liste des voisins d’un nœud.

⚠️ Dans le cas où aucune arrête n’est spécifiée pour un noeud, on renverra une liste vide []

💡 Pensez à consulter la documentation du module Map au besoin

defmodule GraphInfo do

  @doc """
    iex> graph = %{ "A" => ["B", "D"], "B" => ["A", "C", "E"] }
    iex> GraphInfo.neighbors(graph, "A")
    ["B", "D"]

    iex> graph = %{ "A" => ["B", "D"], "B" => ["A", "C", "E"] }
    iex> GraphInfo.neighbors(graph, "C")
    []

  """
  def neighbors(graph, node) do
    []
  end

end

# CORRECTION POSSIBLE

defmodule GraphInfoCorrige do

  @doc """
    iex> graph = %{ "A" => ["B", "D"], "B" => ["A", "C", "E"] }
    iex> GraphInfoCorrige.neighbors(graph, "A")
    ["B", "D"]

    iex> graph = %{ "A" => ["B", "D"], "B" => ["A", "C", "E"] }
    iex> GraphInfo.neighbors(graph, "C")
    []
  """
  def neighbors(graph, node) do
    Map.get(graph, node, [])
  end

end

2. Parcours en largeur (BFS)

Nous voulons désormais parcourir notre graphe “en largeur, c’est à dire:

on donne à notre fonction un un graph et un noeud de départ
il retourne une liste de tous les noeuds, parcourus à partir du noeud courant (voir exemple dans le DocTest)

N’hésitez pas à demander de l’aide à votre encadrant et/ou à vous renseigner sur l’algorithme sur internet.

Concrètement:

vous devrez maintenir une file des noeuds “à parcourir”: à chaque noeud visité on ajoute ses vions dans les noeuds “à visiter plus tard”
une liste des noeuds déjà visités
et par rapport à l’algorithme “usuel” vous devrez utiliser la récursion à la place de l’itération

Pour votre code, vous pourriez utiliser:

l’opérateur in qui permet de tester si un élément est dans une liste: 1 in [1, 2, 3, 4]
la concaténation de deux listes avec ++: [1, 2] ++ [3, 4] == [1, 2, 3, 4]
la fonction Enum.reverse qui “retourne” une liste

defmodule GraphBFS do

  @doc """
    iex> graph = %{ "A" => ["B", "D"], "B" => ["A", "C", "E"], "C" => ["B", "F"], "D" => ["A", "E"], "E" => ["B", "D", "F"], "F" => ["C", "E"] }
    iex> GraphBFS.bfs(graph, "A")
    ["A", "B", "D", "C", "E", "F"]
  """
  def bfs(graph, start) do
    []
  end

end

GraphBFS.bfs(graph, "A")

3. Plus cours chemin (Dijkstra-like)

Votre objectif ici est de reprendre votre code de parcours en largeur afin de trouver le plus cours chemin vers un point “objectif”.

Même si ça peut paraître compliqué, nous avons toutes les briques nécessaires pour réaliser ce calcul.

jusqu’à maintenant, nous construisions une liste de “noeuds visités” que nous retournions à la fin de l’algorithme
vous allez faire évoluer cette liste vers une liste de tuple { "Noeud", [ "Chemin", "vers", "ce", "noeud" ] }
dès que atteindra le noeud objectif, on retournera le chemin vers ce noeud

encore une fois, n’hésitez pas à solliciter l’aide de votre professeur !

À vous de jouer:

defmodule GraphShortestPath do

  @doc """
    iex> graph = %{ "A" => ["B", "D"], "B" => ["A", "C", "E"], "C" => ["B", "F"], "D" => ["A", "E"], "E" => ["B", "D", "F"], "F" => ["C", "E"] }
    iex> GraphShortestPath.shortest_path(graph, "A", "C")
    ["A","B","C"]
  """
  def shortest_path(graph, start, goal) do
    []
  end

end