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

# CORRECTION POSSIBLE

defmodule GraphBFSCorrige 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> GraphBFSCorrige.bfs(graph, "A")
    ["A", "B", "D", "C", "E", "F"]
  """
  def bfs(graph, start) do
    bfs(graph, [start], [])
  end

  defp bfs(_graph, [], visited), do: Enum.reverse(visited)

  defp bfs(graph, [current | rest], visited) do
    if current in visited do
      bfs(graph, rest, visited) # déjà visité
    else
      new_nodes = GraphInfoCorrige.neighbors(graph, current)
      bfs(
        graph,
        rest ++ new_nodes, # on "enqueue" les noeuds à visiter
        [current | visited] # et on rajoute le noeud visite dans la liste
      )
    end
  end

end

GraphBFSCorrige.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

# CORRECTION POSSIBLE

defmodule GraphShortestCorrige 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> GraphShortestCorrige.shortest_path(graph, "A", "C")
    ["A","B","C"]
  """
  def shortest_path(graph, start, goal) do
    shortest_path(graph, [{start, [start]}], goal, [])
  end

  defp shortest_path(_graph, [], _goal, _visited), do: nil

  defp shortest_path(graph, [{current, path} | rest], goal, visited) do
    dbg(visited)
    cond do
      current == goal ->
        # on a trouvé !
        path

      current in visited ->
        # on skip le noeud
        shortest_path(graph, rest, goal, visited)

      true ->
        new_nodes_with_path =
          GraphInfoCorrige.neighbors(graph, current)
          |> Enum.map(fn n ->
            # on crée les tuples { noeud, chemin }
            {n, path ++ [n]}
          end)

        shortest_path(graph, rest ++ new_nodes_with_path, goal, [current | visited])
    end
  end
end

Exercice optionnel: ré-écrire notre algorithme BFS avec la librairie :queue

Nous pouvons utiliser la librairie :queue d’Erlang pour avoir une structure de données, plus adapté.

De plus, cela va nous permettre d’expérimenter l’inter-opérabilité entre ce langage – qui reste le “socle” d’Elixir – et notre progamme écrit en Elixir. De plus, lire de la documentation technique est toujours une bonne expérience !

Vous pouvez créer une “queue” Erlang en appelant :queue.new/0 ou :queue.from_list/1:

queue = :queue.new()

queue = :queue.from_list([1, 2, 3, 4, 5, 6])

Nous remarquons alors plusieurs choses:

• la “queue” est stockée dans une structure constituée d’un tuple qui lui-même contient deux listes
• le premier et le dernier élément de la notre queue sont les premiers éléments des deux listes respectives: f_aites varier les éléments de la queue et vous verrez !

💡 c’est le secret de cette structure, qui maintient une structure permettant d’ajouter et/ou enlever un élément au début ou à la fin de la structure très rapiement.

La librairie fournit un ensemble de méthodes très simples pour manipuler la queue:

• calculer la taille:

:queue.len(queue)

• ajouter un élément:
  • au début avec :queue.in/1 pour insérer à la fin de la liste
  • à la fin avec :queue.in_r/2 pour insérer au début de la liste

queue = :queue.in(7, queue) # ajoute à la fin (première liste du tuple)

 queue = :queue.in_r(0, queue) # ajoute au début (seconde liste du tuple)

• pour enlever un élément, nous pouvons utiliser:
  • :queue.get/1 pour lire au début de la liste
  • :queue.get_r/1 pour lire à la fin de la liste
  • :queue.out/1 pour lire au début de la liste _et retourner la liste sans cet élément
  • :queue.out_r/1 pour lire à la fi de la liste _et retourner la liste sans cet élément
  ⚠️ le _r ne signifie pas “devant” our “derrière” mais signifie que c’est l’inverse du in_r:
  • avec in et out (ou get) on a une FIFO où l’on insère à la fin et on lit au début
  • avec in_r et out_r (ou get_r) on a une FIFO où l’on insère au début et on lit à la fin
  • avec in et out_r (ou get_r) on a une LIFO où l’on insère à la fin et on lit à la fin
  • avec in_r et out (ou get) on a une LIFO où l’on insère au début et on lit au début

# lecture au début
IO.inspect :queue.get(queue), label: "Valeur du début"

# lecture à la fin
IO.inspect :queue.get_r(queue), label: "Valeur finale"

💡 Attention, get et get_r vont lever une erreur si la liste est vide:

queue_vide = :queue.new()
:queue.get(queue_vide)

• une meilleur option sera d’utiliser out et out_r:
  • si la queue n’est pas vide, la valeur de retour sera un tuple: { {:value, valeur }, queue_sans_cette_valeur }
  • si la queue est vide, la valeur de retour sera: { :empty, queue }

# on récupère la valeur au début de la liste et on l'enlève de la liste
{{ :value, value }, queue } = :queue.out(queue)
IO.inspect value, label: "Valeur extraite (première valeur)"

# pour afficher notre liste modifiée, nous pouvons la convertir en liste:
:queue.to_list(queue)

# on récupère la valeur finale de la liste et on l'enlève de la liste
{{ :value, value }, queue } = :queue.out_r(queue)
IO.inspect value, label: "Valeur extraite (dernière valeur)"

# pour afficher notre liste modifiée, nous pouvons la convertir en liste:
:queue.to_list(queue)

À vous de jouer:

defmodule GraphBFSQueue 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> GraphBFSQueue.bfs(graph, "A")
    ["A", "B", "D", "C", "E", "F"]
  """
  def bfs(graph, start) do
    []
  end

end

# CORRECTION POSSIBLE

defmodule GraphBFSQueueCorrige 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> GraphBFSQueueCorrige.bfs(graph, "A")
    ["A", "B", "D", "C", "E", "F"]
  """
  def bfs(graph, start) do
    bfs(graph, :queue.from_list([start]), [])
  end

  defp bfs(_graph, {[], []}, visited), do: Enum.reverse(visited)

  defp bfs(graph, queue, visited) do
    {{:value, current}, rest} = :queue.out(queue)
    if current in visited do
      bfs(graph, rest, visited) # déjà visité
    else
      new_nodes = GraphInfoCorrige.neighbors(graph, current)
      bfs(
        graph,
        :queue.join(rest, :queue.from_list(new_nodes)),
        [current | visited] # et on rajoute le noeud visite dans la liste
      )
    end
  end

end