Un tutoriel sur les graphes (2nde partie).

Objectif.

Le but est de s’approprier les différents éléments caractéristiques d’un graphe, en vue de saisir les algorithmes qui en font usage, comme par exemple, l'algorithme du plus court chemin. Si la première partie de ce tutoriel visait uniquement à introduire la notion de graphe avec un cas concret de parcours d'une voiture, on manipulera ici les notions clés et on élaborera les outils nécessaires pour la construction de l'algorithme du plus court chemin avec cette fois le cas du graphe appliqué à un réseau d'amis qui entre eux possèdent ou non des liens de familiarité.

Introduction.

  1. Un graphe est un ensemble de points dont certaines paires sont directement reliées par un lien. Ces liens peuvent être orientés, d'un point vers un autre ou vice versa. Dans le cas contraire, les liens sont symétriques, et le graphe est non-orienté. Généralement, les points sont appelés les sommets ou les nœuds. Les liens sont appelés arêtes dans les graphes non-orienté et arcs dans un graphe orienté.
  2. Voir les notes d'introduction aux graphes pour permettre de comprendre le contexte historique.
  3. Un cas concret peut être un réseau d'amis où chaque sommet est une personne en particulier, et un lien entre deux personnes met en évidence leur familiarité. Ainsi, on peut se poser la question comment Alice peut entrer en relation avec Bob, et qui plus est de manière optimum, autrement dit en limitant le nombre de personnes intermédiaires.

Travail proposé.

  1. Avant de commencer.

    La première partie de ce tutoriel [METTRE UN LIEN (interface EnVoiture)] a été introductive à la notion de graphe, partant d'un cas concret avec le parcours d'une voiture, de telle sorte à visiter des villes tout en limitant le chemin parcouru. Dans cette partie, on propose de programmer les concepts clés des graphes autour d'un réseau d'amis symbolisés par des noeuds pour les personnes et des liens entre les noeuds pour les liens de familiarité.
  2. Découverte de l'interface.

    Essayer les différentes fonctions de l'interface pour vous familiariser avant de . . le programmer:
    • Pour avoir l'information sur toutes les fonctionnalités, passer la souris sur "info>>>".
    • Pour une manipulation rapide, 'a' génère tous les noeuds disponibles, 'r' génère quelques liens.
    • Pour lancer l'algotithme de calcul du plus court chemin entre 2 noeuds: clic gauche + 'b' pour le noeud de départ, clic gauche + 'e' pour le noeud d'arrivée.
  3. Construire son propre réseau.

    Utiliser les fonctions ci dessous pour définir à partir d'un petit bout de code votre propre réseau:
    • Ajout d'un noeud:
      addNode(String n, int x, int y)
    • Destruction d'un noeud:
      removeNode(String n)
    • Ajout/modification d'un lien entre deux noeuds:
      addLink(String nA, String nB, double poids)
    • Destruction d'un lien existant entre deux noeuds:
      removeLink(String nA, String nB)
  4. Récupérer des informations du réseau.

    Utiliser les fonctions proposées pour calculer le nombre de sommets et de liens, ainsi que la somme des poids des chemins.
  5. Prémisse à un algorithme de plus court chemin.

    Soit un graphe à 4 noeuds, avec un noeud de départ et un noeud d'arrivée (que vous aurez programmé à votre convenance ou pris ci-dessous).
    Depuis le noeud de départ, si le noeud est en lien avec le noeud d'arrivée, c'est fini; sinon choisir le noeud dont le lien a le poids le plus faible. Si la boucle n'est pas fini, repartir du noeud précédent, et refaire le raisonnement. Continuer jusqu'à aboutir au noeud d'arrivée.
    • Programmer cet algorithme et regarder son exécution
    • Prendre conscience que l'algorithme ainsi construit aboutit à la solution, mais est non-optimisé.
      • On imprimera le nom des noeuds parcourus, ici des personnes, et on se rendra compte de la redondance des chemins.
      • De plus, en ajoutant un noeud au graphe, on prendra conscience du temps de calcul exponentiel.
  6. S'attaquer à un problème peut-être plus facile . . .

    On propose d'utiliser le graphe pour calculer le chemin entre deux personnes avec un nombre minimum de personnes intermédiaires.
    Ecrire au crayon l'ébauche de l'algorithme . . l'exploration des cas possibles est-elle plus simple dans ce cas ?
    Qu'en déduire alors ?

Remarques.

  1. Un exemple de graphe:
    void build() {
        int x0 = 450, y0 = 250;
        addNode("Nord", x0, y0 - 100);
        addNode("Est", x0 + 300, y0);
        addNode("Ouest", x0 - 300, y0);
        addNode("Sud", x0, y0 + 100);
        addNode("Centre", x0, y0);
        addLink("Nord", "Est", 1);
        addLink("Sud", "Est", 2);
        addLink("Centre", "Ouest", 3);
        addLink("Sud", "Ouest", 4);
        addLink("Sud", "Centre", 5);
        addLink("Nord", "Centre", 1);
    }
    void unbuild() {
        removeNode("Nord");
        removeNode("Sud");
        removeNode("Est");
        removeNode("Ouest");
        removeNode("Centre");
    }