Parcours de graphes

Je veux implémenter l’algorithme de parcours en profondeur dans mes systèmes de séquenceurs en forme de graphe. Je verrai de quelles façons je peux me servir de cet algorithme pour créer des formes visuelles et des séquences musicales intéressantes. Je ne sais pas vraiment comment je pourrais utiliser cet algorithme pour son usage habituel (parcourir un graphe afin de déterminer s’il existe un chemin d’un sommet à un autre), mais pour l’instant, j’imagine qu’il pourrait me servir à créer des motifs déterministes à l’intérieurs de mes graphes. D’une façon générale, j’aimerais voir comment je pourrais traverser mes graphes de façons déterministes, puisque mes premières expérimentations ne sont que des parcours stochastiques.

Ordre de sélection des voisins à visiter

Une question importante qui n’est pas nécessairement soulevée par l’algorithme de parcours en profondeur, c’est l’ordre dans lequel sont sélectionnés les voisins à visiter. Et pour cause : ça n’a normalement pas d’importance. Enfin… je ne crois pas. Répondre à la question « y a-t-il un chemin entre ces deux sommets ? » n’implique pas de choisir ces sommets à visiter dans un ordre particulier. Mais dans mon cas, comme je m’intéresse aux formes que j’obtiendrai en appliquant cet algorithme, et comme je cherche une solution déterministe, l’ordre de sélection sera important.

Ma première idée, ce serait de visiter les voisins dans le sens des aiguilles d’une montre. J’ai trouvé intéressant d’apprendre que ces solutions géométriques n’ont déjà plus aucun rapport avec la théorie générale des graphes, théorie qui ne se préoccupe pas, je crois, de choses comme les angles et les longueurs des arêtes. J’ai trouvé un article Wikipedia intéressant sur la « théorie des graphes géométriques » qui serait « un sous-champ large et amorphe de la théorie des graphes ». L’article n’existe pas en français.En considérant que chaque arête s’élance d’un sommet à un angle $\alpha$, je pourrais trier ces arêtes selon l’angle qu’elles forment, commençant par $0$ et finissant par $2\pi$.

Pour l’instant, dans mon prototype Vertex, la méthode addEdge est définie ainsi :

Vertex.prototype.addEdge = function(e) {
    this.edges.push(e);
};

Donc, this.edges n’est qu’un simple Array qui contient des objets de type Edge. Ce qu’il me faudrait probablement, c’est créer plutôt un objet littéral et envoyer celui-ci dans this.edges :

Vertex.prototype.addEdge = function(e) {
    let edge = {
        e: e,
        angle: this.calculateAngle(e)
    };
    this.edges.push(edge);
};

À noter qu’il serait aussi peut-être nécessaire de recalculer ces angles à chaque image d’animation puisque j’aurai souvent des animations dans lesquelles les sommets se déplacent dans l’espace cartésien. Ça complique les choses.

Ce pourrait être intéressant pour plusieurs autres raisons d’avoir cette définition plus compliquée d’une arête. Par exemple, une arête pourrait contenir le moment précis où elle a été créée (la valeur frameCount), et un algorithme d’exploration différent pourrait choisir les arêtes à emprunter en fonction de cette valeur.

Le calcul de l’angle lui-même se fera avec la fonction atan2 :

var angle = atan2(vec2.y - vec1.y, vec2.x - vec1.x);

Contexte

Cette note de blog fait partie de mon projet de recherche Vers un cinéma algorithmique, démarré en avril 2018. Je vous invite à consulter la toute première note du projet pour en apprendre davantage.