Sélectionner les sommets :
Sélectionner les arêtes :
Désélectionner les sommets :
Désélectionner les arêtes :
Sélectionner :
Désélectionner :
Zoom :
Délimitez un rectangle sur le canevas pour zoomer/dézoomer sur cette zone.
Sur la moitié en haut ou à gauche de la page se trouve le canevas sur lequel vous pouvez dessiner un graphe.
Utilisez le clic gauche de la souris pour modifier le graphe et sélectionner ses éléments :
Vous pouvez utiliser les touches numériques du clavier pour changer facilement de mode.
Certaines touches du clavier ont un effet sur la sélection :
Sur écran tactile, faites un appui long sur un élément pour modifier sa valeur. En mode Sélectionner, l’appui long permet de supprimer les éléments sélectionnés.
Jusqu’à 50 actions peuvent être annulées et restaurées.
Les raccourcis clavier ne fonctionnent pas si le curseur se trouve dans un élément de formulaire (cliquez alors sur une zone vide ou appuyez sur Échap pour les réactiver).
Pour charger un graphe enregistré, vous pouvez utiliser le glisser-déposer : glissez votre fichier ou son contenu (code SVG complet) sur la page. Il en est de même pour les algorithmes et leurs résultats.
Il y a une petite prise en charge des graphes au format SVG générés par Graphviz. Le code SVG doit contenir le mot « graphviz » (généralement placé dans un commentaire). Les seules données utilisées sont : le titre des sommets (qui doit être numérique), le titre des arêtes, le type de la première arête (orientée ou non) et les coordonnées du centre de chaque sommet. En général, le graphe chargé débordera en haut, il faut utiliser l’outil « Déplacer » pour le rendre visible.
Une liste d’arêtes au format simple de GenGraph peut être chargée dans l’onglet Graphe > Représentations. Le nombre de sommets n’est pas pris en compte : il faut les générer au préalable. Les arêtes auront toutes une longueur de 1 et leur orientation n’est pas prise en compte ; cette dernière doit être configurée dans l’onglet Graphe > Paramètres. Seule la lecture de chemins est prise en charge.
Les graphes enregistrés peuvent être visionnés en dehors de l’application. Cependant, si celle-ci n’est pas exécutée via un serveur web, les règles de style ne sont pas incorporées aux documents enregistrés, et le rendu n’est alors pas bon.
Visionneuse web d’algorithmes de graphes, version 1.1 (janvier 2024).
Application par Sylvain Chiron, sous licence GNU AGPL v3. Conçue à partir du cours d’algorithmique des graphes de František Kardoš à l’Université de Bordeaux.
Dépôt du projet : https://gitlab.com/Frigory33/graph-algos-viewer-web
Représentations numériques du graphe :
Résultats des algorithmes :
formatArraysForVertices ?
Fonctionnalités des algorithmes ou pour les algorithmes :
parentsToEdges
dans le code des algorithmes, pour prendre en charge les graphes non simples ?
Infinity plutôt que null pour initialiser les distances ?
Pour aligner facilement les sommets, vous pouvez configurer une grille. Ses données ne sont pas enregistrées dans le graphe.
Taille d’une cellule (largeur × hauteur, en pixels) : ×
Dans les listes d’arêtes, les listes d’adjacence et la matrice d’incidence reçues par les algorithmes, les arêtes ont le même ordonnancement que dans l’arbre XML/SVG du graphe. Vous pouvez facilement altérer cet ordre avec les touches Début et Fin du clavier, ou en utilisant l’une des fonctions de tri proposées ci-dessous.
Choisissez un ordre de tri des arêtes :
Liste d’arêtes : — Format simple de GenGraph :
Listes de successeurs : — Listes de prédécesseurs :
Matrice d’adjacence :
Matrice d’incidence :
| Type d’opération | Nombre d’invocations | Équivalent à |
|---|
Le parcours en largeur et le parcours en profondeur sont les deux techniques élémentaires pour parcourir un graphe tout en construisant des chemins. Elles permettent toutes les deux d’explorer un graphe, avec un ordre de parcours différent et en allant d’un sommet à l’autre en passant par une arête (tant que cela est possible), ce qui conduit l’exploration à construire une forêt couvrante du graphe. Toutefois, l’implémentation de parcours en largeur fournie ici n’explore que les sommets accessibles depuis les sommets initiaux.
L’implémentation de ces algorithmes est très similaire ; la seule différence repose sur la structure de données utilisée pour déterminer dans quel ordre explorer les sommets : le parcours en largeur utilise une file, et le parcours en profondeur utilise une pile. Le parcours en profondeur est le plus souvent implémenté avec une fonction récursive plutôt qu’avec une pile explicite. Ainsi, le parcours en largeur explore les sommets de proche en proche, tandis que le parcours en profondeur avance tant qu’il peut et ne revient en arrière que quand il n’y a plus de chemin disponible.
Le parcours en largeur explore donc les sommets dans l’ordre de leur distance par rapport aux sommets de départ. Dans le cas où le graphe est un arbre, le parcours en largeur l’explorera ligne par ligne. Le parcours en profondeur, lui, peut associer à chaque sommet des dates de début et de fin de visite, ce qui lui permet notamment de trier les arcs en quatre catégories : arcs de liaison, arcs de retour, arcs d’avant et arcs transverses. Le parcours en profondeur permet aussi d’obtenir un tri topologique du graphe : si le graphe est orienté et sans circuit, une fois les sommets triés par ordre de fin de visite, tous les arcs iront dans le même sens, de sorte qu’aucun sommet n’a un descendant situé avant lui, ce qui est intéressant lorsque le graphe est un graphe de dépendances.
Complexité : O(n + m).
Les algorithmes de Kosaraju et de Tarjan permettent de délimiter les composantes fortement connexes du graphe, c’est-à-dire les plus grandes régions du graphe dans lesquelles il est possible d’accéder à chaque sommet depuis tout autre sommet de la région.
L’algorithme de Kosaraju fait simplement deux parcours en profondeur du graphe, le deuxième étant fait avec les sommets triés par ordre de fin de visite et en parcourant les arcs dans le sens inverse. L’algorithme de Tarjan utilise une autre technique, qui consiste à calculer, pour chaque sommet, la date de début de visite du sommet accessible le plus proche du début de la pile du parcours au profondeur, qui se rapproche à peu près de la date de découverte de sa composante fortement connexe.
Complexité : O(n + m).
Les algorithmes de Kruskal et de Prim permettent de calculer l’arbre couvrant de poids minimum de chaque composante connexe du graphe. L’algorithme de Kruskal parcourt les arêtes dans l’ordre croissant de leur poids et décide ou non s’il faut les prendre. L’algorithme de Prim, semblablement à l’algorithme de Dijkstra, part d’un sommet et avance d’arête en arête en utilisant une file à priorité. Avec une petite adaptation, l’algorithme de Kruskal permettrait de trouver tous les arbres couvrants de poids minimum (il peut y en avoir plusieurs si certaines arêtes ont le même poids) des composantes connexes du graphe. L’algorithme de Kruskal utilise une structure de données de type unir-trouver (union-find) pour déterminer si deux sommets sont déjà connectés par les arêtes précédemment sélectionnées.
Application : déterminer la manière la plus économique de relier tous les éléments d’un réseau.
Complexité : O(n + m log n).
L’algorithme de Dijkstra est semblable à l’algorithme de parcours en largeur, à ceci près qu’il prend en compte les poids des arcs et utilise une file à priorité pour déterminer de façon gloutonne le prochain sommet à visiter. Il détermine ainsi, depuis un sommet, comment aller le plus vite vers chacun des autres sommets ; ou le contraire : comment aller le plus vite vers un sommet depuis chacun des autres sommets (si on inverse le sens des arcs). L’algorithme de Dijkstra peut être trompé par l’existence de poids négatif, et ainsi n’est prévu que pour les graphes dont tous les poids sont positifs ou nuls.
Si l’objectif est d’aller d’un sommet à un autre le plus rapidement possible et que les poids des arcs se rapprochent fortement de la distance réelle entre les sommets, l’algorithme de Dijkstra peut être inutilement lent. L’algorithme A* est une généralisation de l’algorithme de Dijkstra qui prend en compte les données géométriques afin d’aller plus directement vers la destination.
Complexité : O(m + n log n).
L’algorithme de Bellman permet d’explorer un graphe orienté sans circuit (tel qu’un graphe de dépendances), depuis les sommets sans prédécesseur jusqu’aux sommets sans successeur. Il calcule pour cela, pour chaque sommet, le nombre de ses prédécesseurs non encore visités. Lorsque ce nombre tombe à zéro, le sommet est ajouté dans la file pour être exploré prochainement. L’algorithme de Bellman permet de déterminer la distance entre chaque sommet et le plus proche sommet sans prédécesseur, ainsi que le rang de chaque sommet, qui est tel que tous les sommets de même rang auraient pu être visités dans n’importe quel ordre (le rang des sommets sans prédécesseur est de zéro, et le rang des autres sommets est un de plus que le plus élevé des rangs de leurs prédécesseurs).
Complexité : O(n + m).
L’algorithme de Bellman-Ford permet de calculer les plus courts chemins depuis un sommet vers tous les autres et ce, contrairement à l’algorithme de Dijkstra, même s’il y a des poids négatifs. La technique est de vérifier plusieurs fois si emprunter une arête permet d’aller plus vite vers le sommet au bout de l’arc. L’algorithme permet de détecter les circuits absorbants du graphe, c’est-à-dire les circuits dont les sommets sont tous à distance -∞.
Complexité : O(n m).
L’algorithme de Floyd-Warshall permet de calculer tous les plus courts chemins entre tous les couples de sommets du graphe, avec une technique algorithmique simple : pour chaque sommet, et pour tout couple de sommets, déterminer si emprunter le premier sommet permet d’aller plus vite d’un sommet du couple à l’autre, et si c’est le cas, profiter du raccourci. L’algorithme permet de détecter les circuits absorbants.
Complexité : O(n³ + m).
L’algorithme d’Edmonds-Karp permet d’obtenir un flot maximum pour un réseau de flot. Un réseau de flot est un graphe dans lequel les arcs sont bornés par des capacités, qui déterminent combien d’éléments peuvent traverser l’arc en même temps. La technique consiste à déterminer un à un des chemins améliorants à l’aide de parcours en largeur successifs, qui indiquent parfois qu’il faut moins utiliser une arête. L’algorithme d’Edmonds-Karp est une précision de l’algorithme de Ford-Fulkerson, qui est identique à ceci près qu’il ne précise pas comment trouver les chemins améliorants.
Application : déterminer comment utiliser un réseau le plus efficacement possible.
Complexité : O(n + m²).
Entrée : — Sortie : — Fichier :
Exécution :
Télécharger :
Pour appliquer un algorithme sur un graphe de l’application, téléchargez la bibliothèque et le squelette correspondant à votre langage, puis complétez le squelette. Il s’agit d’écrire une fonction recevant un graphe en paramètre.
Quel que soit votre langage, comme cela est montré dans les squelettes,
l’exécution de votre fonction doit reposer sur un appel runAlgorithm(votreFonction).
Des exemples plus complets, implémentant l’algorithme de Dijkstra, sont disponibles pour mieux vous montrer comment utiliser la bibliothèque de chaque langage.
Les sections ci-dessous décrivent précisément comment utiliser les bibliothèques.
Pour que votre programme reconnaisse le graphe, vous devez lui fournir sa description en entrée. Commencez par sélectionner les éléments que votre algorithme doit privilégier le cas échéant. Ensuite, cliquez sur l’un des boutons ci-dessus (« Minimale » ou « Avec positions ») pour obtenir des données d’entrée, et récupérez le texte produit (cliquez dessus puis utilisez les raccourcis clavier Ctrl+A et Ctrl+C pour copier le texte) ou cliquez sur le bouton pour l’enregistrer dans un fichier. Fournissez le texte d’entrée à votre programme, soit en redirigeant son entrée vers le fichier enregistré, soit en collant directement le texte dans un terminal exécutant votre programme.
Le graphe fourni en paramètre à votre fonction est un objet ou une structure ayant les champs suivants :
nbVertices : le nombre de sommets du graphe ;nbEdges : le nombre d’arêtes du graphe ;isUndirected : vrai si le graphe est non orienté, faux sinon ;selectedVertices : la liste des numéros des sommets sélectionnés ;selectedEdges : la liste des numéros des arêtes sélectionnées ;edges : la liste (de taille nbEdges) des arêtes du graphe,
chaque élément ayant les champs suivants :
src : le numéro du sommet source,dest : le numéro du sommet destination,weight : le poids de l’arête,num : le numéro de l’arête (identique à sa position dans la liste) ;succLists : la liste (de taille nbVertices) des listes de successeurs,
indexées par le numéro du sommet source, chaque élément ayant les champs suivants :
vertex : le numéro du sommet à l’autre extrémité,weight : le poids de l’arête,num : le numéro de l’arête ;predLists : la liste (de taille nbVertices) des listes de prédécesseurs,
au même format que succLists, et contenant les mêmes éléments
si le graphe est non orienté ;
adjMatrix : la matrice d’adjacence du graphe
(adjMatrix[vertex1][vertex2] est le poids de l’arête allant de
vertex1 à vertex2, ou 0 s’il n’y en a pas).
Certains champs sont facultatifs. Pour les obtenir, vous devez remplacer le dernier nombre de la toute première ligne de l’entrée par la somme (ou l’union des bits) des nombres qui sont indiqués entre crochets à côté du nom des champs que vous voulez. Les champs facultatifs sont :
verticesPos [1] (vous devez prendre l’entrée « Avec positions ») :
la liste (de taille nbVertices) des positions des sommets,
représentées par deux champs x et y ;
incMatrix [2] : la matrice d’incidence du graphe
(incMatrix[vertex][edge] est le poids de edge
si c’est une arête sortante de vertex, l’opposé de son poids
si c’est une arête entrante de vertex, 0 sinon).
Votre fonction doit retourner un tableau de tableaux de dictionnaires (les dictionnaires étant des tableaux dont les indices sont ici des chaines de caractères), qui seront convertis en JSON par la bibliothèque et envoyés sur la sortie. Une fois que vous avez cette sortie, collez-la dans la zone de texte ci-dessus (en l’ayant préalablement vidée de son contenu : utilisez le raccourci clavier Ctrl+A pour sélectionner facilement tout le texte afin de le supprimer) et cliquez sur le bouton « Traiter » pour visionner les données retournées par l’algorithme. Vous pouvez aussi utiliser le glisser-déposer : glissez les données JSON ou le fichier les contenant sur la page.
Chaque tableau contenu dans le tableau principal correspond à un état de l’algorithme,
auquel on peut accéder avec les boutons fléchés dans la visualisation des résultats de l’algorithme.
La taille du tableau principal correspond ainsi au nombre d’états visualisables.
Pour construire chaque état, il est recommandé d’avoir une ou plusieurs fonctions spécialisées
(j’ai appelé les miennes addDataToShow) qui ajoutent un état au tableau
(que j’appelle dataToShow) qui sera à la fin renvoyé par votre algorithme,
cette ou ces fonctions étant appelées régulièrement par votre algorithme avec les paramètres adéquats.
Chaque dictionnaire de chaque état doit posséder au moins les clés type et value,
et peut en posséder d’autres, qu’elles soient obligatoires ou optionnelles,
en fonction de la valeur de type. La valeur de type détermine aussi comment
la valeur de value est interprétée.
5 types sont pris en charge : text, table, colorization,
vertexValues et edgeValues.
text : Le champ value sera par défaut interprété comme du simple texte
à insérer dans un paragraphe (balise HTML <p>). Si un champ asHtml
est fourni et vaut true, alors la chaine de caractères contenue dans value
est insérée directement (sans balise <p>) et est interprétée comme du HTML.
table : Le champ value doit contenir un tableau de tableaux
de chaines de caractères, qui seront placées dans un tableau HTML. La première colonne est interprétée
comme un titre et sera mise en gras. La propriété facultative nbHeadRows
permet de définir combien de lignes (forcément les premières du tableau) seront également mises en gras
(0 par défaut) : cela permet notamment d’afficher plus proprement les matrices.
La propriété style peut contenir des propriétés CSS qui seront fournies au tableau
(seulement l’élément principal <table> ; cela peut permettre d’avoir
des tableaux côte à côte plutôt que toujours les uns en dessous des autres).
Par défaut, les valeurs à mettre dans les cellules sont simplement interprétées comme du texte,
mais si un champ asHtml est fourni et vaut true,
alors la chaine de caractères est interprétée comme du HTML.
colorization : Le champ value doit contenir une couleur
(format expliqué ci-dessous).
Il y a un autre champ obligatoire : target, qui doit être un tableau contenant
les données des éléments à colorer. Pour colorer un sommet, il faut simplement donner son numéro.
Pour colorer une arête, il faut donner ses données, ou alors un dictionnaire contenant
une clé num dont la valeur est le numéro de l’arête,
sinon deux clés src et dest
(qui ne permettent pas de gérer les graphes non simples). Si vous fournissez directement
les données d’une arête (ou d’un successeur ou prédécesseur), elles seront converties en dictionnaire.
vertexValues : Le champ value doit être un tableau de taille
nbVertices, contenant le texte à afficher aux côtés de chaque sommet.
Le texte sera interprété en SVG
(ce qui implique qu’il vaut mieux échapper les < et &).
Il y a deux paramètres optionnels : position, un tableau de deux nombres
indiquant la position relative du texte par rapport au sommet
(par défaut [0, -1], c’est-à-dire au-dessus du sommet) ; et color,
la couleur du texte (noir par défaut).
edgeValues : Le champ value doit être un tableau
de taille nbEdges, contenant le texte à afficher à côté de chaque arête.
Le texte sera interprété en SVG et affiché à la place
du poids de l’arête — tous les poids seront masqués si l’état utilise le type edgeValues.
Si vous voulez néanmoins voir les poids des arêtes, il faut les inclure dans le texte de chaque arête.
La clé optionnelle color permet de choisir la couleur du texte.
L’ordre des données de chaque état importe pour les données de type
text et table, qui seront insérées les unes en dessous des autres.
Concernant les données de type colorization,
il faut éviter que plusieurs d’entre elles essaient de colorer le même élément,
car alors la couleur de l’élément n’est pas déterminée
(elle dépend du moment où la couleur est ajoutée dans le document SVG).
Si des nombres plutôt que des chaines de caractères sont fournis comme valeurs pour les données
de type table, vertexValues et edgeValues, ils seront formatés
avec la fonction floatToStr présentée plus bas.
Les couleurs doivent être des chaines de caractères contenant soit un
nom de couleur CSS (recommandé),
soit le code hexadécimal de la couleur (au format #RGB, #RGBA,
#RRGGBB ou #RRGGBBAA). Les autres formats (tels qu’un appel de la fonction
rgb()) ne sont pas pris en charge.
Quelques fonctions utilitaires sont fournies pour vous aider à construire votre sortie (leur utilisation n’est pas du tout obligatoire). Remarquez que certaines s’appuient sur les données du graphe chargé pour votre fonction : le graphe est en effet enregistré dans une variable globale.
getVertexLabel(vertexNum) : renvoie l’étiquette correspondant au numéro de sommet fourni.
floatToStr(nb) : renvoie nb converti en chaine de caractères,
en ayant supprimé l’éventuel « .0 » en fin de nombre entier et en ayant remplacé l’éventuel point
par une virgule francophone. Si nb vaut l’infini positif ou négatif,
∞ ou -∞ est renvoyé.
formatArraysForVertices(rowNames, values) :
génère un tableau de tableaux voué à être utilisé comme valeur de type table.
La première ligne contient le titre « Sommet » et l’étiquette de chaque sommet.
Ensuite, chaque ligne a comme titre rowNames[i] puis comme contenu values[i]
(chaque values[i] doit donc être un tableau). Cela permet d’afficher facilement
des données associées aux sommets. Exemple d’utilisation :
{ type: "table", value: formatArraysForVertices(["Distance", "Père"], [distances, parents])
}.
formatBinaryTree(title, treeAsArray) : renvoie un tableau de tableaux
organisant le contenu du tableau treeAsArray en arbre binaire.
Utile pour afficher les données des files à priorité.
parentsToEdges(parents) : renvoie un tableau de dictionnaires contenant chacun deux clés
src et dest. À chaque destination i est associée la source
parents[i]. Cette fonction permet de colorer facilement les arêtes reliant un sommet à son
père (mais n’est pas idéale pour les graphes non simples).
getEdgesFromBools(edgesToTake) : renvoie un tableau de dictionnaires contenant chacun
une seule clé num contenant la valeur i lorsque edgesToTake[i]
vaut vrai. Cette fonction permet de colorer facilement des arêtes marquées par des booléens.
getVerticesFromBools(verticesToTake) : renvoie un tableau contenant les entiers
i pour lesquels verticesToTake[i] vaut vrai. Cette fonction permet de
colorer facilement des sommets marqués par des booléens.
Pour compter les opérations effectuées par votre algorithme, vous devez appeler une fonction :
countOperation(name, quantity = 1) : compte quantity opérations
supplémentaires (1 par défaut) de type name.
Les comptages d’opérations effectués avec countOperation seront inclus
dans la sortie JSON de la bibliothèque. Ainsi, vous devez faire un appel
countOperation("Description de l’opération") à chaque endroit où l’opération est effectuée
dans votre algorithme, pour obtenir une ligne correspondante dans le tableau de complexité.
Une classe ou structure PriorityQueue est fournie, pour vous offrir les fonctionnalités
d’une file à priorité avec suivi des indices. Voici ses méthodes et ses champs :
PriorityQueue(priorityFct, saveIndexes = false, opNames = null) :
priorityFct doit être une fonction recevant en paramètres deux éléments de la file
et renvoyant un booléen indiquant si le premier élément est prioritaire par rapport au second,
saveIndexes est un booléen indiquant si la sauvegarde des indices est activée,
et opNames est un tableau de deux chaines de caractères nommant les opérations de rangement
respectivement pour enfilement et pour défilement (si le paramètre vaut null,
countOperation ne sera pas appelée ; valeur conseillée :
["Rangement pour enfilement", "Rangement pour défilement"]) ;
length() : renvoie la taille de la file (0 lorsqu’elle est vide) ;top() : renvoie l’élément au sommet de la file ;push(val) : ajoute un élément à la file ;pop() : enlève de la file l’élément se trouvant au sommet et le renvoie ;data : le tableau sous-jacent utilisé par la structure
(peut être fourni en paramètre à la fonction formatBinaryTree).
Lorsque le suivi des indices est activé, les méthodes et champs suivants peuvent également être utilisés :
upgrade(pos, val) : remplace la valeur de l’élément à la position pos
par val, et fait éventuellement monter l’élément dans la file ;
downgrade(pos, val) : remplace la valeur de l’élément à la position pos
par val, et fait éventuellement descendre l’élément dans la file ;
dataIndexes : un tableau indexé par les valeurs des éléments, contenant leur position
dans la file (dans le tableau data).
Remarquez que pour que le suivi des indices fonctionne, les éléments de la file doivent être
des nombres entiers positifs et tous relativement petits.
En effet, la taille du tableau dataIndexes
est déterminée par la plus grande valeur qui a été mise dans la file.
L’idée est que les éléments de la file soient des numéros de sommets ou bien des numéros d’arêtes,
qui font appel à des données mutables indexées par ces numéros pour connaitre leur niveau de priorité.
Les interfaces de programmation fournies par les bibliothèques dans les différents langages sont très semblables pour l’entrée, mais ont parfois beaucoup de spécificités pour la sortie. Ces spécificités et les autres sont détaillées dans les sections ci-dessous.
La bibliothèque pour le langage C s’appuie sur la petite bibliothèque
HandyMacros, que vous devez avoir installée.
Le tout est puissant et très efficace, mais est aussi évidemment plus difficile à utiliser
que les bibliothèques des langages plus haut niveau.
Pour savoir précisément comment utiliser un élément, consultez le fichier api.h
(une partie du code sert à permettre à cette bibliothèque d’être utilisée en C++,
certaines syntaxes du C n’étant pas acceptées par C++).
Votre fonction doit retourner une valeur de type Slice(Any).
Concernant l’entrée, il n’y a pas grand-chose de spécial, si ce n’est que les champs
selectedVertices, selectedEdges, succLists et
predLists utilisent le type de tableaux dynamiques DynArr d’HandyMacros.
Pour la sortie, il faut utiliser intensivement HandyMacros, et l’arbre JSON est fait
à l’aide du type Any fourni.
Structures de données spécialisées :
Any est fourni. Il permet de stocker une valeur
de n’importe quel type parmi une dizaine (consultez le fichier api.h).
Une macro Any(valeur) est également fournie : elle fonctionne comme un constructeur,
prenant une valeur d’un type accepté et retourne une valeur de type Any
stockant la valeur fournie. Cette macro utilise le mot-clé _Generic de C11,
ainsi qu’une série de minis fonctions annotées static inline.
Petit exemple d’utilisation :
Any vars[] = { Any(1), Any(2.) };
for (int i = 0; i < array_len(vars); ++i) {
if (vars[i].type == INT) {
printf("%d\n", vars[i].i);
} else if (vars[i].type == FLOAT) {
printf("%lg\n", vars[i].f);
}
}
Attention avec les booléens : si vous voulez réellement stocker
true ou false,
vous devrez peut-être convertir explicitement votre paramètre en bool.
Si vous construisez un pointeur complexe qui requiert des parenthèses
(par exemple un pointeur vers une fonction ou vers un tableau),
vous devrez peut-être utiliser AnyT, qui est un synonyme du type Any
qui ne risque pas d’être interprété comme la macro de construction.
destroyAny(val) désalloue récursivement tous les tableaux et dictionnaires
contenus dans l’arbre de la valeur val.
Cette fonction est appelée sur le tableau renvoyé par votre algorithme,
c’est pourquoi il ne doit pas contenir deux fois le même AnyArray ou Dict,
au risque de faire planter le programme. Si vous voulez mettre deux fois la même valeur
dans votre arborescence Any, vous pouvez donner un pointeur vers un Any,
par exemple : anyArrayPush(&tab, Any(&val)).
Outils :
addString(str)
pour que la chaine soit automatiquement désallouée après l’écriture des données JSON.
Cette fonction est appelée par les fonctions renvoyant des chaines de caractères,
y compris les deux fonctions suivantes.
formatStr(format, ...) renvoie une chaine de caractères
correspondant au format fourni, qui est le même que pour printf.
concatStrings(strs) renvoie la concaténation des chaines de caractères
pointées par chaque case du tableau strs.
Le tableau doit avoir la valeur NULL dans sa dernière case.
PQ_ et prennent
en premier paramètre l’adresse de votre file à priorité, sauf la fonction PQ_create.
Il n’y a pas de fonctions PQ_top et PQ_length ;
lisez directement data.v[0] et data.len.
Il y a une fonction PQ_destroy qui se charge de désallouer
(non récursivement) les tableaux data et dataIndexes.
Commande de compilation conseillée (une fois que vous avez renommé le fichier template.c
en algo.c) :
cc -o algo api.c algo.c -std=c17 -Wall -lhandymacros
Rajoutez éventuellement -O2 ou -O3 pour avoir plus d’optimisations.
La bibliothèque C++ est plus complexe à utiliser que celle de langages plus haut niveau tels que Python
et JavaScript, mais est bien plus efficace et demeure confortable si vous avez l’habitude du C++.
Vous pouvez consulter le fichier api.hpp (en particulier les lignes non indentées)
pour voir tous les éléments qu’elle vous offre.
Votre fonction doit retourner une valeur de type DataToShow,
qui est un synonyme de vector<vector<Dict>>, Dict étant un synonyme
de map<string, any>. La construction de la sortie repose en effet sur l’utilisation
du type any de C++17,
et ainsi la compilation ne fonctionnera que si votre compilateur prend en charge C++17.
En pratique, seulement 8 types de valeurs seront convertis en JSON :
string ;char const *
(c’est le type des chaines de caractères constantes comme "celle-ci") ;
int ;double ;bool ;Dict (synonyme de map<string, any>) ;AnyVector (synonyme de vector<any>) ;Table (synonyme de vector<AnyVector>) ;null sera écrite.
Les valeurs des structures de type map<string, any> et vector<any>
seront converties en JSON récursivement.
Le type PriorityQueue n’accepte que des entiers dans sa file, et leurs indices
sont toujours enregistrés dans le tableau dataIndexes (aussi le constructeur n’accepte pas
de paramètre saveIndexes). Si vous voulez mettre autre chose que des entiers
dans votre file à priorité, vous pouvez utiliser le patron de classe priority_queue
de la bibliothèque standard.
La fonction formatBinaryTree n’est pas un patron de fonction (pour éviter d’avoir à inclure
son code dans api.hpp afin de vous permettre de lire ce fichier plus facilement) ;
au lieu de ça, elle prend en paramètre un vector<any>.
Commande de compilation conseillée (une fois que vous avez renommé le fichier template.cpp
en algo.cpp) :
c++ -o algo api.cpp algo.cpp -std=c++17 -Wall
Rajoutez éventuellement -O2 ou -O3 pour avoir plus d’optimisations.
La bibliothèque OCaml n’est probablement pas très bien réussie : elle est essentiellement codée en impératif. Les contributions pour l’améliorer sont les bienvenues.
Les noms de types sont écrits tout en minuscules avec tirets bas.
Pour la sortie JSON, il y a un type json. Votre fonction doit retourner
une liste de listes de listes de couples d’une chaine de caractères
et d’une valeur de type json
(de telles listes de couples sont appelées « listes associatives » en jargon OCaml).
Consultez le début du fichier api.ml pour voir quels constructeurs propose
le type json.
Les listes et les tableaux seront convertis en JSON de manière identique :
que votre valeur soit un JsonArray ou une JsonList,
le même code JSON sera généré.
Les données du graphe sont pour certaines fournies sous forme de tableaux
(pour fournir l’accès direct par indice), pour d’autres sous forme de listes
(lorsque les indices n’ont pas de sens) : consultez le début du fichier api.ml.
Les fonctions utilitaires attendent toutes des tableaux,
et renvoient soit des tableaux de JsonArray
(lorsque leur sortie est un tableau 2D), soit des listes.
La fonction countOperation name n’accepte pas le second paramètre. Si vous voulez compter
plusieurs opérations d’un coup, appelez la fonction countOperations name quantity.
Les files à priorité simulent des tableaux dynamiques en interne, c’est-à-dire que la taille du tableau
est simplement doublée à chaque fois que nécessaire, et le nombre d’éléments effectif est stocké à part.
Lorsque vous appelez la méthode data, vous obtenez une version tronquée du tableau
(toutes les valeurs sont copiées). Les paramètres du constructeur de la classe
priority_queue diffèrent par rapport au canon exposé plus haut :
saveIndexes) est facultatif, mais si vous voulez activer
la sauvegarde des indices, il ne suffit pas de fournir true :
il faut fournir ~assignValue:assignValueWithIndexes
(assignValue est le nom du paramètre facultatif, assignValuesWithIndexes
est la fonction que la file à priorité va utiliser en tant qu’assignValue) ;
opNames) ne peut pas être null :
pour ne pas compter les opérations, fournissez simplement un tableau vide ;
Commande de compilation conseillée (une fois que vous avez renommé le fichier template.ml
en algo.ml) :
ocamlopt -o algo api.ml algo.ml
La bibliothèque Java ressemble fort à celle du C++. Pour des raisons de simplicité, il est recommandé
que votre classe hérite de la classe Api fournie
(qui ne contient que des membres statiques).
Les champs de la classe Graph et de ses sous-classes sont simplement tous publics
(et ces classes n’offrent aucune méthode).
Le type Object est utilisé partout pour la généricité et la conversion en JSON,
sauf dans PriorityQueue qui, comme en C++, n’accepte que des Integer
et enregistre toujours les indices (pour d’autres types,
utilisez la classe java.util.PriorityQueue).
Votre fonction doit renvoyer un objet de type List<List<Map<String, Object>>>.
Parfois les méthodes attendent des tableaux, d’autres fois des List.
Utilisez List.of ou Arrays.asList pour construire facilement une liste
à partir d’un tableau, et la méthode .toArray(new Object[0]) dans le sens inverse.
Chaque élément Object est converti en JSON suivant cette procédure :
null, alors la valeur null est écrite ;Number ou de Boolean,
alors la valeur est écrite directement ;
Map, les clés sont écrites comme des String
et les valeurs sont converties récursivement, le tout mis dans un objet JSON ;
List, les valeurs sont converties récursivement
et mises dans un tableau JSON ;
Graph.EdgeProps ou Graph.EdgeEnd),
un objet JSON contenant la propriété num de l’arête est écrit ;
Pour compiler et exécuter (si vous avez renommé Template.java en Algo.java
et adapté le nom de la classe) :
javac Algo.java java Algo
Aucune remarque sur la bibliothèque Python. Elle est aussi facile à utiliser que la bibliothèque JavaScript.
Si vous utilisez JavaScript, il est inutile de récupérer l’entrée ci-dessus, et il n’y a aucune sortie à coller : collez simplement votre code dans la zone de texte ci-dessus (ou glissez ce code ou le fichier sur la page) et cliquez sur le bouton « JavaScript ». S’il n’y a pas d’erreur, le résultat sera automatiquement affiché dans l’onglet Algorithmes. Vous pouvez obtenir le même résultat en exécutant votre code via la console du navigateur (accessible en appuyant sur F12).
Pour obtenir les champs facultatifs, vous devez passer à la fonction runAlgorithm
le nombre correspondant à ce que vous voulez en deuxième paramètre.
Par exemple, pour avoir les positions des sommets et la matrice d’incidence :
runAlgorithm(myAlgo, 3);
runAlgorithm
ou n’a pas renvoyé de données à afficher.
target, chaque {} correspond à un élément valide) :