Ordinamento topologico: Python, C++ Esempio di algoritmo

Cos'è l'algoritmo di ordinamento topologico?

L'ordinamento topologico è noto anche come algoritmo di Kahn ed è un algoritmo di ordinamento popolare. Utilizzando un grafico diretto come input, l'ordinamento topologico ordina i nodi in modo che ciascuno appaia prima di quello a cui punta.

Questo algoritmo viene applicato su un DAG (grafico aciclico diretto) in modo che ciascun nodo appaia nell'array ordinato prima che tutti gli altri nodi vengano puntati ad esso. Questo algoritmo segue ripetutamente alcune regole fino al completamento dell'ordinamento.

Per semplificare, guarda il seguente esempio:

Grafico diretto
Grafico diretto

Qui possiamo vedere che “A” non ha grado. Significa il bordo che punta ad un nodo. I nodi “B” e “C” hanno il prerequisito “A”, quindi “E” ha il prerequisito dei nodi “D” e “F”. Alcuni nodi dipendono da altri nodi.

Ecco un'altra rappresentazione del grafico sopra:

Dipendenza di ciascun nodo

Dipendenza di ciascun nodo (ordinamento lineare)

Quindi, quando passiamo il DAG (grafico aciclico diretto) all'ordinamento topologico, ci darà un array con ordinamento lineare, dove il primo elemento non ha dipendenza.

Algoritmo di ordinamento topologico

Questo esempio mostra un grafico con un ciclo:

Ecco i passaggi per eseguire questa operazione:

Passo 1) Trova il nodo con zero bordi entranti, un nodo con zero gradi.

Passo 2) Memorizza che azzera il nodo di grado in una coda o in uno stack e rimuove il nodo dal grafico.

Passo 3) Quindi elimina il bordo in uscita da quel nodo.

Ciò diminuirà il conteggio dei gradi per il nodo successivo.

L'ordinamento topologico richiede che la struttura dei dati del grafico non abbia alcun ciclo.

Un grafico sarà considerato un DAG se segue questi requisiti:

  • Uno o più nodi con un valore di grado pari a zero.
  • Il grafico non contiene alcun ciclo

Finché ci sono nodi nel Graph e il Graph è ancora DAG, eseguiremo i tre passaggi precedenti. Altrimenti, l'algoritmo cadrà nella dipendenza ciclica e l'algoritmo di Kahn non sarà in grado di trovare un nodo con grado di ingresso zero.

Come funziona l'ordinamento topologico

Qui, useremo l'algoritmo di Kahn per l'ordinamento topologico. Supponiamo di avere il seguente grafico:

Lavori di ordinamento topologico

Ecco i passaggi per l'algoritmo di Kahn:

Passo 1) Calcola il grado ingrado o il bordo entrante di tutti i nodi nel grafico.

Nota:

  • Ingrado indica i bordi diretti che puntano al nodo.
  • Per gradi esterni si intendono i bordi diretti che provengono da un nodo.

Ecco i gradi in e out del grafico sopra:

Lavori di ordinamento topologico

Passo 2) Trova il nodo con zero gradi o zero archi entranti.

Il nodo con grado zero significa che nessun bordo viene verso quel nodo. Il nodo "A" ha zero gradi, il che significa che non ci sono bordi che puntano al nodo "A".

Quindi, faremo le seguenti azioni:

  • Rimuovi questo nodo e i suoi bordi esterni (bordi uscenti)
  • Posiziona il nodo nella coda per l'ordine.
  • Aggiorna il conteggio dei gradi del nodo vicino di "A".

Lavori di ordinamento topologico

Passo 3) Dobbiamo trovare un nodo con un valore di grado pari a zero. In questo esempio, “B” e “C” hanno zero gradi.

Qui possiamo prendere uno di questi due. Prendiamo “B” e cancelliamolo dal grafico.

Quindi aggiorna i valori dei gradi degli altri nodi.

Dopo aver eseguito queste operazioni, il nostro grafico e la nostra coda appariranno come segue:

Lavori di ordinamento topologico

Passo 4) Il nodo “C” non ha alcun fronte in entrata. Quindi, rimuoveremo il nodo "C" dal grafico e lo inseriremo nella coda.

Possiamo anche eliminare il bordo uscente da “C”.

Ora, il nostro grafico sarà simile a questo:

Lavori di ordinamento topologico

Passo 5) Possiamo vedere che i nodi “D” e “F” hanno grado pari a zero. Prenderemo un nodo e lo inseriremo nella coda.

Prima eliminiamo la "D". Quindi il conteggio degli gradi per il nodo "E" sarà 1. Ora non ci sarà alcun nodo da D a E.

Dobbiamo fare lo stesso per il nodo “F”, il nostro risultato sarà simile al seguente:

Lavori di ordinamento topologico

Passo 6) Il grado interno (bordi entranti) e il grado esterno (bordi uscenti) del nodo "E" sono diventati zero. Quindi, abbiamo soddisfatto tutti i prerequisiti per il nodo “E”.

Qui inseriamo la "E" alla fine della coda. Quindi, non ci sono più nodi, quindi l'algoritmo finisce qui.

Lavori di ordinamento topologico

Pseudocodice per l'ordinamento topologico

Ecco lo pseudo-codice per l'ordinamento topologico durante l'utilizzo dell'algoritmo di 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

L'ordinamento topologico può essere implementato anche utilizzando il DFS (Prima ricerca in profondità) metodo. Tuttavia, questo approccio è il metodo ricorsivo. L'algoritmo di Kahn è più efficiente dell'approccio DFS.

C++ Implementazione dell'ordinamento topologico

#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();
}

Uscita

0       1       2       3       5       4

Python Implementazione dell'ordinamento topologico

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()

Uscita

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

Grafici ciclici dell'algoritmo di ordinamento topologico

Un grafo contenente un ciclo non può essere ordinato topologicamente. Poiché il grafico ciclico ha la dipendenza in modo ciclico.

Ad esempio, controlla questo grafico:

Grafici ciclici dell'algoritmo di ordinamento topologico

Questo grafico non è DAG (grafico aciclico diretto) perché A, B e C creano un ciclo. Se noti, non c'è nessun nodo con valore in gradi pari a zero.

Secondo l'algoritmo di Kahn, se analizziamo il grafico sopra:

  • Trova un nodo con zero gradi (nessun arco entrante).
  • Rimuovi quel nodo dal grafico e inseriscilo nella coda.
    Tuttavia, nel grafico sopra, non c'è nessun nodo con zero in gradi. Ogni nodo ha un valore in gradi maggiore di 0.
  • Restituisce una coda vuota, poiché non è stato possibile trovare alcun nodo con zero in gradi.

Possiamo rilevare i cicli utilizzando l'ordinamento topologico con i seguenti passaggi:

Passo 1) Eseguire l'ordinamento topologico.

Passo 2) Calcolare il numero totale di elementi nell'elenco ordinato topologicamente.

Passo 3) Se il numero di elementi è uguale al numero totale di vertici, non c'è ciclo.

Passo 4) Se non è uguale al numero di vertici, allora c'è almeno un ciclo nella struttura dati del grafico data.

Analisi della complessità dell'ordinamento topologico

Ci sono due tipi di complessità negli algoritmi. Sono

  1. Complessità temporale
  2. Complessità spaziale

Queste complessità sono rappresentate da una funzione che fornisce una complessità generale.

Complessità temporale: Tutta la complessità temporale è la stessa per il Topological Sorting. Ci sono scenari peggiori, medi e migliori per la complessità temporale.

La complessità temporale per l'ordinamento topologico è O(E + V), dove E indica il numero di spigoli nel grafico e V indica il numero di vertici nel grafico.

Cerchiamo di superare questa complessità:

Passo 1) All'inizio calcoleremo tutti gli ingradi. Per fare ciò, dobbiamo passare attraverso tutti gli spigoli e inizialmente assegneremo a zero tutti gli gradi del vertice V. Quindi, i passaggi incrementali che completeremo saranno O(V+E).

Passo 2) Troveremo il nodo con valore di grado zero. Dobbiamo cercare dal numero V del vertice. Quindi, i passaggi completati saranno O(V).

Passo 3) Per ogni nodo con zero gradi, rimuoveremo quel nodo e decrementeremo il grado. Sarà necessario eseguire questa operazione per tutti i nodi O(E).

Passo 4) Infine, controlleremo se è presente o meno un ciclo. Controlleremo se il numero totale di elementi nell'array ordinato è uguale al numero totale di nodi. Ci vorrà O (1).

Quindi, queste erano le singole complessità temporali per ogni passaggio dell'ordinamento topologico o ordinamento topologico. Possiamo dire che la complessità temporale dal calcolo precedente sarà O( V + E ); qui, O indica la funzione di complessità.

Complessità spaziale: Avevamo bisogno di spazi O(V) per eseguire l'algoritmo di ordinamento topologico.

Ecco i passaggi in cui avevamo bisogno di spazio per il programma:

  • Dovevamo calcolare tutti gli gradi dei nodi presenti nel Grafico. Poiché il grafico ha un totale di nodi V, dobbiamo creare un array di dimensioni V. Quindi, lo spazio richiesto era O(V).
  • Per memorizzare il nodo con grado zero è stata utilizzata una struttura dati coda. Abbiamo rimosso i nodi con grado zero dal grafico originale e li abbiamo inseriti nella coda. Per questo, lo spazio richiesto era O(V).
  • L'array è denominato "ordine". Ciò memorizzava i nodi in ordine topologico. Anche questo richiedeva O(V) spazi.

Questa era la complessità dello spazio individuale. Quindi, dobbiamo massimizzare questi spazi nel tempo di esecuzione.

La complessità dello spazio è rappresentata da O(V), dove V indica il numero del vertice nel grafico.

Applicazione dell'ordinamento topologico

C'è un enorme utilizzo per l'ordinamento topologico. Ecco qui alcuni di loro:

  • Si usa quando Operasistema di ting deve eseguire l’allocazione delle risorse.
  • Trovare un ciclo nel grafico. Possiamo verificare se il grafico è DAG o meno con ordinamento topologico.
  • Ordinamento delle frasi nelle app di completamento automatico.
  • È utilizzato per il rilevamento situazioni di stallo.
  • Diversi tipi di pianificazione o pianificazione dei corsi utilizzano l'ordinamento topologico.
  • Risoluzione delle dipendenze. Ad esempio, se provi a installare un pacchetto, quel pacchetto potrebbe richiedere anche altri pacchetti. L'ordinamento topologico individua tutti i pacchetti necessari per installare il pacchetto corrente.
  • Linux utilizza l'ordinamento topologico in "apt" per verificare la dipendenza dei pacchetti.