Tri topologique : Python, C++ Exemple d'algorithme

Qu’est-ce que l’algorithme de tri topologique ?

Le tri topologique est également connu sous le nom d'algorithme de Kahn et est un algorithme de tri populaire. En utilisant un graphe orienté comme entrée, Topological Sort trie les nœuds afin que chacun apparaisse avant celui vers lequel il pointe.

Cet algorithme est appliqué sur un DAG (Directed Acyclic Graph) afin que chaque nœud apparaisse dans le tableau ordonné avant que tous les autres nœuds ne pointent vers lui. Cet algorithme suit certaines règles à plusieurs reprises jusqu'à ce que le tri soit terminé.

Pour simplifier, regardez l'exemple suivant :

Ici, nous pouvons voir que « A » n’a pas de diplôme. Cela signifie le bord qui pointe vers un nœud. « B » et « C » ont un pré-requis de « A », puis « E » a un pré-requis de nœuds « D » et « F ». Certains nœuds dépendent d’autres nœuds.

Voici une autre représentation du graphique ci-dessus :

Ainsi, lorsque nous passons le DAG (Directed Acyclic Graph) au tri topologique, cela nous donnera un tableau avec un ordre linéaire, où le premier élément n'a aucune dépendance.

Cet exemple montre un graphique avec un cycle :

Voici les étapes pour ce faire :

Étape 1) Trouvez le nœud avec zéro arête entrante, un nœud avec zéro degré.

Étape 2) Stockez qui remet à zéro le nœud en degré dans une file d'attente ou une pile et supprime le nœud du graphique.

Étape 3) Supprimez ensuite le bord sortant de ce nœud.

Cela diminuera le nombre de degrés pour le nœud suivant.

L'ordre topologique nécessite que la structure des données du graphique n'ait aucun cycle.

Un graphique sera considéré comme un DAG s’il respecte ces exigences :

• Un ou plusieurs nœuds avec une valeur indegree de zéro.
• Le graphique ne contient aucun cycle

Tant qu'il y a des nœuds dans le graphique et que le graphique est toujours DAG, nous exécuterons les trois étapes ci-dessus. Sinon, l'algorithme tombera dans la dépendance cyclique et l'algorithme de Kahn ne pourra pas trouver un nœud avec un degré nul.

Comment fonctionne le tri topologique

Ici, nous utiliserons « l'algorithme de Kahn » pour le tri topologique. Disons que nous avons le graphique suivant :

Voici les étapes de l'algorithme de Kahn :

Étape 1) Calculez le degré entrant ou le bord entrant de tous les nœuds du graphique.

À noter:

• Indegree signifie les bords dirigés pointant vers le nœud.
• Outdegree désigne les arêtes dirigées provenant d’un nœud.

Voici le degré d'entrée et de sortie du graphique ci-dessus :

Étape 2) Trouvez le nœud avec zéro degré ou zéro arête entrante.

Le nœud avec un degré nul signifie qu'aucun bord ne se dirige vers ce nœud. Le nœud « A » a zéro degré, ce qui signifie qu'il n'y a aucun bord pointant vers le nœud « A ».

Nous allons donc effectuer les actions suivantes :

• Supprimez ce nœud et ses bords extérieurs (bords sortants)
• Placez le nœud dans la file d'attente pour la commande.
• Mettez à jour le nombre de degrés du nœud voisin de « A ».

Étape 3) Nous devons trouver un nœud avec une valeur indegree de zéro. Dans cet exemple, « B » et « C » ont un degré nul.

Ici, nous pouvons prendre l’un ou l’autre de ces deux. Prenons « B » et supprimons-le du graphique.

Mettez ensuite à jour les valeurs indegree des autres nœuds.

Après avoir effectué ces opérations, notre graphique et notre file d'attente ressembleront à ce qui suit :

Étape 4) Le nœud « C » n'a pas de bord entrant. Nous allons donc supprimer le nœud « C » du graphique et le placer dans la file d'attente.

Nous pouvons également supprimer le bord sortant de « C ».

Maintenant, notre graphique ressemblera à ceci :

Étape 5) On peut voir que les nœuds « D » et « F » ont le degré zéro. Nous allons prendre un nœud et le mettre dans la file d'attente.

Supprimons d'abord « D ». Ensuite, le nombre de degrés pour le nœud « E » sera de 1. Désormais, il n'y aura plus de nœud de D à E.

Nous devons faire la même chose pour le nœud « F », notre résultat sera le suivant :

Étape 6) Le degré entrant (bords entrants) et le degré sortant (bords sortants) du nœud « E » sont devenus nuls. Nous avons donc rempli tous les pré-requis pour le nœud « E ».

Ici, nous mettons « E » à la fin de la file d’attente. Il ne nous reste donc plus aucun nœud, donc l'algorithme se termine ici.

Pseudo-code pour le tri topologique

Voici le pseudo-code pour le tri topologique en utilisant l'algorithme de Kahn.

function TopologicalSort( Graph G ):
  for each node in G:
    calculate the indegree
  start = Node with 0 indegree
  G.remove(start)
  topological_list = [start]
  While node with O indegree present:
    topological_list.append(node)
    G.remove(node)
    Update Indegree of present nodes
  Return topological_list

Le tri topologique peut également être implémenté à l'aide du DFS (Première recherche en profondeur) méthode. Cependant, cette approche est la méthode récursive. L'algorithme de Kahn est plus efficace que l'approche DFS.

C++ Implémentation du tri topologique

#include<bits/stdc++.h>
using namespace std;
class graph{
  int vertices;
  list<int> *adjecentList;
public:
  graph(int vertices){
    this->vertices = vertices;
    adjecentList = new list<int>[vertices];
  }
  void createEdge(int u, int v){
    adjecentList[u].push_back(v);
  }
  void TopologicalSort(){
    // filling the vector with zero initially
    vector<int> indegree_count(vertices,0);

    for(int i=0;i<vertices;i++){
      list<int>::iterator itr;
      for(itr=adjecentList[i].begin(); itr!=adjecentList[i].end();itr++){
        indegree_count[*itr]++;
      }
    }
    queue<int> Q;
    for(int i=0; i<vertices;i++){
      if(indegree_count[i]==0){
        Q.push(i);
      }
    }
    int visited_node = 0;
    vector<int> order;
    while(!Q.empty()){
      int u = Q.front();
      Q.pop();
      order.push_back(u);

      list<int>::iterator itr;
      for(itr=adjecentList[u].begin(); itr!=adjecentList[u].end();itr++){
        if(--indegree_count[*itr]==0){
          Q.push(*itr);
        }
      }
      visited_node++;
    }
    if(visited_node!=vertices){
      cout<<"There's a cycle present in the Graph.\nGiven graph is not DAG"<<endl;
      return;
    }
    for(int i=0; i<order.size();i++){
      cout<<order[i]<<"\t";
    }
  }
};
int main(){
  graph G(6);
  G.createEdge(0,1);
  G.createEdge(0,2);
  G.createEdge(1,3);
  G.createEdge(1,5);
  G.createEdge(2,3);
  G.createEdge(2,5);
  G.createEdge(3,4);
  G.createEdge(5,4);
  G.TopologicalSort();
}

Sortie

0       1       2       3       5       4

Python Implémentation du tri topologique

from collections import defaultdict
class graph:
    def __init__(self, vertices):
        self.adjacencyList = defaultdict(list) 
        self.Vertices = vertices  # No. of vertices
    # function to add an edge to adjacencyList
    def createEdge(self, u, v):
        self.adjacencyList[u].append(v)
    # The function to do Topological Sort.
    def topologicalSort(self):
        total_indegree = [0]*(self.Vertices)
        for i in self.adjacencyList:
            for j in self.adjacencyList[i]:
                total_indegree[j] += 1
        queue = []
        for i in range(self.Vertices):
            if total_indegree[i] == 0:
                queue.append(i)
        visited_node = 0
        order = []
        while queue:
            u = queue.pop(0)
            order.append(u)
            for i in self.adjacencyList[u]:
                total_indegree[i] -= 1

                if total_indegree[i] == 0:
                    queue.append(i)
            visited_node += 1
        if visited_node != self.Vertices:
            print("There's a cycle present in the Graph.\nGiven graph is not DAG")
        else:
            print(order)
G = graph(6)
G.createEdge(0,1)
G.createEdge(0,2)
G.createEdge(1,3)
G.createEdge(1,5)
G.createEdge(2,3)
G.createEdge(2,5)
G.createEdge(3,4)
G.createEdge(5,4)
G.topologicalSort()

Sortie

[0, 1, 2, 3, 5, 4]

Graphiques cycliques de l'algorithme de tri topologique

Un graphe contenant un cycle ne peut pas être ordonné topologiquement. Comme le graphique cyclique a la dépendance de manière cyclique.

Par exemple, vérifiez ce graphique :

Ce graphique n'est pas DAG (Directed Acyclic Graph) car A, B et C créent un cycle. Si vous remarquez, il n’y a aucun nœud avec une valeur en degré nulle.

Selon l'algorithme de Kahn, si l'on analyse le graphique ci-dessus :

• Trouvez un nœud avec zéro degré (pas de bords entrants).
• Supprimez ce nœud du graphique et placez-le dans la file d'attente.
  Cependant, dans le graphique ci-dessus, il n’y a aucun nœud avec zéro en degrés. Chaque nœud a une valeur en degré supérieure à 0.
• Renvoie une file d'attente vide, car elle n'a trouvé aucun nœud avec zéro en degrés.

Nous pouvons détecter les cycles en utilisant l'ordre topologique avec les étapes suivantes :

Étape 1) Effectuez un tri topologique.

Étape 2) Calculez le nombre total d’éléments dans la liste triée topologiquement.

Étape 3) Si le nombre d’éléments est égal au nombre total de sommets, alors il n’y a pas de cycle.

Étape 4) S'il n'est pas égal au nombre de sommets, alors il y a au moins un cycle dans la structure de données du graphique donnée.

Analyse de complexité du tri topologique

Il existe deux types de complexité dans les algorithmes. Ils sont

1. Complexité temporelle
2. Complexité spatiale

Ces complexités sont représentées par une fonction qui fournit une complexité générale.

Complexité temporelle: Toute complexité temporelle est la même pour le tri topologique. Il existe des scénarios pires, moyens et meilleurs en matière de complexité temporelle.

La complexité temporelle pour le tri topologique est O(E + V), ici, E signifie le nombre d'arêtes dans le graphe et V signifie le nombre de sommets dans le graphe.

Brisons cette complexité :

Étape 1) Au début, nous calculerons tous les degrés. Pour ce faire, nous devons parcourir toutes les arêtes et, dans un premier temps, nous attribuerons à zéro tous les degrés du sommet V. Ainsi, les étapes progressives que nous accomplirons seront O(V+T).

Étape 2) Nous trouverons le nœud avec une valeur de degré nulle. Nous devons rechercher à partir du numéro V du sommet. Ainsi, les étapes complétées seront O (V).

Étape 3) Pour chaque nœud avec zéro degré, nous supprimerons ce nœud et décrémenterons le degré. Effectuer cette opération pour tous les nœuds prendra O(E).

Étape 4) Enfin, nous vérifierons s'il y a un cycle ou non. Nous vérifierons si le nombre total d'éléments dans le tableau trié est égal au nombre total de nœuds. Ça prendra O (1).

Il s'agissait donc de la complexité temporelle individuelle pour chaque étape du tri topologique ou de l'ordre topologique. Nous pouvons dire que la complexité temporelle du calcul ci-dessus sera O( V + E ) ; ici, O signifie la fonction de complexité.

Complexité de l'espace: Nous avions besoin d'espaces O(V) pour exécuter l'algorithme de tri topologique.

Voici les étapes pour lesquelles nous avions besoin d'espace pour le programme :

• Nous avons dû calculer tous les degrés de nœuds présents dans le graphique. Comme le graphique a un total de nœuds V, nous devons créer un tableau de taille V. Ainsi, l'espace requis était O (V).
• Une structure de données Queue a été utilisée pour stocker le nœud avec un degré nul. Nous avons supprimé les nœuds avec un degré nul du graphique d'origine et les avons placés dans la file d'attente. Pour cela, l'espace requis était O (V).
• Le tableau est nommé « ordre ». Cela a stocké les nœuds dans l'ordre topologique. Cela nécessitait également O (V) les espaces.

Il s'agissait de la complexité de l'espace individuel. Nous devons donc maximiser ces espaces au moment de l’exécution.

La complexité spatiale signifie O(V), où V désigne le numéro du sommet dans le graphique.

Application du tri topologique

Le tri topologique est très utilisé. En voici quelques uns:

• Il est utilisé lorsque Système exploitation doit effectuer l’allocation des ressources.
• Trouver un cycle dans le graphique. Nous pouvons valider si le graphe est DAG ou non avec un tri topologique.
• Ordre des phrases dans les applications de saisie semi-automatique.
• Il est utilisé pour détecter impasses.
• Différents types de planification ou de planification de cours utilisent le tri topologique.
• Résoudre les dépendances. Par exemple, si vous essayez d'installer un package, ce package peut également nécessiter d'autres packages. L'ordre topologique découvre tous les packages nécessaires pour installer le package actuel.
• Linux utilise le tri topologique dans « apt » pour vérifier la dépendance des packages.