grapheEtChemins

grapheEtCheminsCécile Picard-Limpens [x]

La «proglet» grapheEtChemins.

Cliquer ici pour faire l'activité.
Cliquer ici pour lire le tutoriel.
Cette proglet permet 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.
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é. (Wikipedia)
Pour construire et manipuler un graphe, il faut utiliser la construction javascool. Toutes ces fonctions sont accessibles par l'interface, ou par des fonctions programmable:

// Ajouter ou modifier un noeud existant au graphe:

addNode(String n, int x, int y)
où:
  • n est le nom du noeud.
  • x est l'abscisse du noeud (entre 0 et 900).
  • y est l'ordonnée du noeud (entre 0 et 500).

// Obtenir un noeud à partir d'une position:

String n =getClosestNode(int x, int y)
où:
  • x est l'abscisse de la position (entre 0 et 900).
  • y est l'ordonnée de la position (entre 0 et 500).
  • n est le nom du noeud, qui est renvoyé.

// Détruire un noeud:

removeNode(String n)
où:
  • n est le nom du noeud.

// Obtenir la liste de tous les noeuds:

String[] Listn_ = getAllNodes()
où:
  • Listn_ est le tableau des noms de tous les noeuds, qui est renvoyé.

// Obtenir la liste des noeuds en lien avec un noeud spécifique:

String[] Listn_ = getNodes(String n)
où:
  • n est le nom du noeud spécifique.
  • Listn_ est le tableau des noms des noeuds en lien avec le noeud spécifique n, qui est renvoyé.

// Ajouter ou modifier un lien existant entre deux noeuds:

addLink(String nA, String nB, double p)
où:
  • nA est le nom du premier noeud.
  • nB est le nom du second noeud.
  • p est le poids du lien.

// Détruire un lien existant entre deux noeuds:

removeLink(String nA, String nB)
où:
  • nA est le nom du premier noeud du lien à détruire.
  • nB est le nom du second noeud du lien à détruire.

// Questionner si deux noeuds sont liés:

boolean a = isLink(String nA, String nB)
où:
  • nA est le nom du premier noeud du lien considéré.
  • nB est le nom du second noeud du lien considéré.
  • a est la réponse à la question "Les noeuds nA et nB sont-ils en lien?", soit "vrai" soit "faux", qui est renvoyée.

// Obtenir le poids d'un lien entre deux noeud:

double p = getLink(String nA, String nB)
où:
  • nA est le nom du premier noeud du lien considéré.
  • nB est le nom du second noeud du lien considéré.
  • p est le poids du lien entre les neouds nA et nB, qui est renvoyé.
Un exemple d'utilisation se fait lors du lancement de la proglet avec une fenêtre d'interaction.
Un exemple de programme d'utilisation est disponible ici.
Cette «proglet» est un composant logiciel ouvert dont documentation et code-source sont disponibles ici