Nouveautés de Python 3.9 (2) - Tri des graphes non circulés dirigés en Python

introduction

Les nouvelles modifications de Python 3.9 dont la sortie est prévue pour octobre 2020 sont résumées dans l'article Quoi de neuf dans Python 3.9 (Résumé) Je suis. J'ai un article séparé sur un sujet qui semble un peu volumineux, mais c'est le deuxième, sur le tri des graphiques dirigés et non circulés.

Graphiques non circulés dirigés et tris topologiques

Tout d'abord, le graphique n'est pas ici un graphique linéaire, un graphique à barres ou un graphique qui représente visuellement des données, mais un graphique de la théorie des graphes. Un graphe est un type de structure de données qui se compose de nœuds (sommets) et d'arêtes (branches) qui les relient. Vous pouvez représenter des informations pertinentes en donnant une signification aux nœuds ou aux arêtes.

Il existe plusieurs types de graphiques, et si la première fourche a une direction au bord. Celui avec direction s'appelle le graphe orienté (côté gauche), et celui sans direction s'appelle le graphe non orienté (côté droit).

Les arêtes connectent les nœuds, mais vous pouvez utiliser un graphe orienté s'il existe une sorte de relation maître-esclave entre les nœuds connectés, et un graphe non orienté s'il existe une relation d'égalité à la place.

Et que ce soit un graphe de patrouille ou non est également un point. S'il y a un nœud qui vous revient en suivant l'arête, on l'appelle un graphe cyclique, et si ce n'est pas le cas, on l'appelle un graphe non circulaire. Le graphe acyclique dirigé (DAG) a les deux caractéristiques d'être dirigé et non circulant, et c'est le graphe dont nous avons affaire cette fois.

Ce graphe non circulaire dirigé (DAG) peut être utilisé pour représenter une variété d'informations. Dans un exemple étrange, IOTA, un actif cryptographique, utilise DAG. Les actifs cryptographiques ordinaires utilisent la blockchain, et je pense que cela peut être appelé un DAG unidirectionnel, mais IOTA le connecte à un DAG avec plusieurs arêtes. c'est intéressant.

Dans une application légèrement plus courante, il existe un problème de planification des tâches avec les dépendances. Chaque tâche est un nœud et la dépendance de la tâche est représentée par une arête. Par exemple, si A → B, B ne peut pas être démarré avant la fin de A. Même si vous disposez d'une liste de tâches avec des dépendances compliquées, vous pouvez voir qu'elles peuvent être exprimées dans DAG en les décomposant en relations de tâche à tâche.

Par exemple, B et C ne peuvent pas démarrer tant que A n'est pas terminé. Et D ne peut pas commencer tant que B et C ne sont pas terminés, une telle dépendance est exprimée comme suit.

Un exemple plus compliqué serait quelque chose comme ceci:

Un peu hors des sentiers battus, il existe un outil de visualisation de DAG appelé Graphviz. Cela décrit le DAG dans un format unique appelé format de point, le dessine et le convertit en un format d'image tel que PNG. Ce qui est intéressant, c'est qu'il existe plusieurs algorithmes de dessin qui peuvent produire des sorties complètement différentes avec la même entrée.

Par exemple, si vous écrivez le deuxième exemple ci-dessus au format point, il ressemblera à ceci.

digraph example {
  graph [
    labeljust = "c"
  ];
  7, 5, 3, 11, 8, 2, 9, 10;
  7 -> 11;
  7 -> 8;
  5 -> 11;
  3 -> 8;
  3 -> 10;
  11 -> 2;
  11 -> 9;
  11 -> 10;
  8 -> 9;
}

Si vous essayez de produire cela avec l'outil de dessin de Graphviz, vous pouvez faire autant de variations.

c'est intéressant. Il ne ressemble pas vraiment au même DAG, mais ils sont tous tirés du même fichier de points.

Maintenant, il existe une relation d'ordre entre les tâches exprimées dans DAG, vous voulez donc savoir dans quel ordre vous devez les ranger. C'est un problème d'horaire. Pour cela, il est nécessaire de les organiser unidimensionnellement tout en satisfaisant les dépendances, ce qui est appelé ** tri topologique **.

Avec une introduction plus longue, Python 3.9 ajoute une fonctionnalité appelée TopologicalSorter au module fonctools, qui permet de faire ce tri topologique en standard.

Essayez d'utiliser le trieur topologique

Essayons l'exemple avec les nœuds A, B, C, D montrés au tout début.

>>> from functools import TopologicalSorter
>>> ts = TopologicalSorter()
>>> ts.add('B', 'A')
>>> ts.add('C', 'A')
>>> ts.add('D', 'B', 'C')
>>> tuple(ts.static_order())
('A', 'B', 'C', 'D')

Après avoir créé un trieur vide avec TopologySorter (), j'ajoute les nœuds un par un. TopologySorter.add () liste les nœuds à enregistrer dans le premier argument et les nœuds qui ont des dépendances sur les arguments suivants. Les nœuds qui n'ont pas de nœuds dépendants (ʻAdans ce cas) peuvent ignorer l'enregistrement (car ils apparaîtront comme dépendants lors de l'enregistrement d'autres nœuds). Ensuite, le résultat trié parTopologySorter.static_order ()` est retourné par le générateur. Comme il est difficile de le voir tel quel, il est converti en taple et affiché.

Si le graphe est décidé depuis le début, vous pouvez le donner au constructeur et le créer en une seule fois.

>>> from functools import TopologicalSorter
>>> graph = {'B': {'A'}, 'C': {'A'}, 'D': {'B', 'C'}}
>>> ts = TopologicalSorter(graph)
>>> tuple(ts.static_order())
('A', 'B', 'C', 'D')

Ici, ce qui est donné au constructeur, ce sont des données de type dictionnaire, dans lesquelles la clé est un nœud et la valeur dépend d'un (ensemble de) nœuds. Lors de la spécification de plusieurs, le type d'ensemble est utilisé ici, mais il semble qu'il puisse s'agir d'un taple ou d'une liste.

C'est tout ce que vous devez faire pour trier, mais il existe également des méthodes lorsque vous voulez un peu plus de contrôle. Tout d'abord, "ce qui peut être fait pour le moment". Ce sera une liste de tâches dont les dépendances sont satisfaites, en utilisant get_ready ().

À titre d'exemple, utilisons l'exemple légèrement compliqué ci-dessus.

>>> from functools import TopologicalSorter
>>> graph = {
...    2: {11},
...    8: {7, 3},
...    9: {11, 8},
...   10: {11, 3},
...   11: {7, 5},
... }
>>> ts = TopologicalSorter(graph)
>>> ts.prepare()
>>> ts.get_ready()
(3, 7, 5)

Après avoir créé TopologySorter en donnant les données de dépendance du graphe dans le constructeur, commencez par prepare (). Il s'agit d'une méthode qui effectue un prétraitement pour un traitement ultérieur. Nous vérifions également si le graphe enregistré ici est un cycle, et s'il s'agit d'un cycle, un CycleError sera affiché. Dans l'exemple ci-dessus, ce prepare () n'a pas été appelé, mais il est automatiquement appelé dans static_order () (en fait, il est appelé lors de la récupération de la première valeur du générateur).

Les appels suivants à get_ready () renverront (3, 7, 5). Il est répertorié comme "exécutable" parmi les nœuds inclus dans le graphe qui n'ont pas de dépendances. Appeler à nouveau prepare () retournera cette fois (). Cela signifie: "(Pour l'instant) il n'y a rien d'autre."

Je colorierai le graphique ci-dessus. Le vert clair indique que le nœud est viable.

Alors que faire si les «5» et «7» des tâches réalisables sont accomplies? La méthode done () enseigne cela au trieur. Si vous appelez les tâches terminées côte à côte comme arguments, l'état interne changera. Donc, si vous exécutez à nouveau get_ready (), cette fois, il retournera (11,).

>>> ts.done(5,7)
>>> ts.get_ready()
(11,)

Le chiffre est changé en une couleur plus foncée pour indiquer que «5» et «7» sont complets. Et «11» est prêt à être exécuté car toutes les tâches dépendantes sont terminées. Il correspond au résultat de ts.get_ready () ci-dessus.

Nous allons le répéter, mais complétons-le dans l'ordre de «11» → «3» → «8».

>>> ts.done(11)
>>> ts.get_ready()
(2,)
>>> ts.done(3)
>>> ts.get_ready()
(8, 10)
>>> ts.done(8)
>>> ts.get_ready()
(9,)

Vous pouvez vérifier s'il y a des tâches non exécutées dans le graphe avec ʻis_active () `. Dans l'état ci-dessus, «2», «9» et «10» n'ont pas encore été exécutés, donc vous pouvez voir que la valeur de retour de «is_active ()» change avant et après les avoir faites «done ()».

>>> ts.is_active()
True
>>> ts.done(2, 9 ,10)
>>> ts.is_active()
False

Résumé

J'ai étudié et utilisé la nouvelle fonction ToplogicalSorter ajoutée au module functools de Python 3.9. J'ai pensé que cela pourrait être utile pour décider de l'ordre de traitement par lots avec les dépendances.