Topologinen lajittelualgoritmi: Python, C++ esimerkki

Mikä on topologinen lajittelualgoritmi?

Topologinen lajittelu tunnetaan myös nimellä Kahnin algoritmi, ja se on suosittu lajittelualgoritmi. Käyttämällä suunnattua kuvaajaa syötteenä Topologinen lajittelu lajittelee solmut siten, että jokainen näkyy ennen sitä, johon se osoittaa.

This algorithm is applied on a DAG (Directed Acyclic Graph) so that each node appears in the ordered array before all other nodes that are pointed to by it. This algorithm follows some rules repeatedly until the sort is completed.

Yksinkertaistaaksesi, katso seuraava esimerkki:

Ohjattu graafi

Here, we can see that “A” has no indegree. Indegree means the edge that points to a node. “B” and “C” have a pre-requisite of “A”, then “E” has a pre-requisite of “D” and “F” nodes. Some of the nodes are dependent on other nodes.

Here is another representation of the above Graph:

Jokaisen solmun riippuvuus (lineaarinen järjestys)

Joten kun siirrämme DAG:n (Directed Acyclic Graph) topologiseen lajitteluun, se antaa meille taulukon lineaarisella järjestyksellä, jossa ensimmäisellä elementillä ei ole riippuvuutta.

Voit tehdä tämän seuraavasti:

Vaihe 1) Etsi solmu, jolla on nolla saapuvaa reunaa, solmu, jolla on nolla astetta.

Vaihe 2) Store that zero in-degree node in a Queue or Stack and remove the node from the Graph.

Vaihe 3) Then delete the outgoing edge from that node. This will decrement the in-degree count for the next node.

Topological ordering requires that the graph data structure will not have any cycle. A graph will be considered a DAG if it follows these requirements:

• Yksi tai useampi solmu, jonka asteen arvo on nolla.
• The graph does not contain any cycle.

As long as there are nodes in the Graph and the Graph is still a DAG, we will run the above three steps. Otherwise, the algorithm will fall into the cyclic dependency, and Kahn’s Algorithm will not be able to find a node with zero in-degree.

Kuinka topologinen lajittelu toimii

Here, we will use “Kahn’s Algorithm” for the topological sort. Let us say we have the following Graph:

Here are the steps for Kahn’s Algorithm:

Vaihe 1) Laske kaavion kaikkien solmujen inaste tai sisääntuleva reuna.

Huomautus:

• Indegree tarkoittaa suunnattuja reunoja, jotka osoittavat solmuun.
• Outdegree tarkoittaa suunnattuja reunoja, jotka tulevat solmusta.

Here is the indegree and outdegree of the above Graph:

Vaihe 2) Find the node with zero indegrees or zero incoming edges. The node with zero indegree means no edges are coming toward that node. Node “A” has zero indegrees, meaning there is no edge pointing to node “A”. So, we will do the following actions:

• Remove this node and its outdegree edges (outgoing edges).
• Aseta solmu tilausjonoon.
• Update the in-degree count of the neighbor node of “A”.

Vaihe 3) We need to find a node with an indegree value of zero. In this example, “B” and “C” have zero indegree. Here, we can take either of these two. Let us take “B” and delete it from the Graph. Then update the indegree values of other nodes. After performing these operations, our Graph and Queue will look like the following:

Vaihe 4) Node “C” has no incoming edge. So, we will remove node “C” from the Graph and push it into the Queue. We can also delete the edge that is outgoing from “C”. Now, our Graph will look like this:

Vaihe 5) We can see that nodes “D” and “F” have the indegree of zero. We will take a node and put it in the Queue. Let us take out “D” first. Then the indegree count for node “E” will be 1. Now, there will be no node from D to E. We need to do the same for node “F”, and our result will be like the following:

Vaihe 6) The indegree (ingoing edges) and outdegree (outgoing edges) of node “E” became zero. So, we have met all the pre-requisites for node “E”. Here, we will put “E” at the end of the Queue. So, we do not have any nodes left, and the algorithm ends here.

Pseudo Code topologista lajittelua varten

Here is the pseudo-code for the topological sort while using Kahn’s Algorithm.

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 0 indegree present:
    topological_list.append(node)
    G.remove(node)
    // Update indegree of present nodes
  return topological_list

Topologinen lajittelu voidaan toteuttaa myös DFS:n (Syvyys Ensimmäinen haku) menetelmä. Tämä lähestymistapa on kuitenkin rekursiivinen menetelmä. Kahnin algoritmi on tehokkaampi kuin DFS-lähestymistapa.

C++ Topologisen lajittelun toteutus

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

ulostulo

0       1       2       3       5       4

Python Topologisen lajittelun toteutus

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

ulostulo

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

Topologisen lajittelualgoritmin sykliset kuvaajat

A graph containing a cycle cannot be topologically ordered, as the cyclic Graph has the dependency in a cyclic manner. For example, check this Graph:

This Graph is not a DAG (Directed Acyclic Graph) because A, B, and C create a cycle. If you notice, there is no node with zero in-degree value. According to Kahn’s Algorithm, if we analyze the above Graph:

• Etsi solmu, jossa on nolla astetta (ei sisääntulevia reunoja).
• Remove that node from the Graph and push it to the Queue. However, in the above Graph, there is no node with zero in-degrees. Every node has an in-degree value greater than 0.
• Return an empty queue, as it could not find any node with zero in-degrees.

Voimme havaita syklit käyttämällä topologista järjestystä seuraavilla vaiheilla:

Vaihe 1) Suorita topologinen lajittelu.

Vaihe 2) Laske topologisesti järjestetyn listan elementtien kokonaismäärä.

Vaihe 3) If the number of elements equals the total number of vertices, then there is no cycle.

Vaihe 4) If it is not equal to the number of vertices, then there is at least one cycle in the given graph data structure.

Topologisen lajittelun monimutkaisuusanalyysi

There are two types of complexity in algorithms. They are:

1. Ajan monimutkaisuus
2. Avaruuden monimutkaisuus

Nämä monimutkaisuudet esitetään funktiolla, joka tarjoaa yleisen monimutkaisuuden.

Ajan monimutkaisuus: All time complexity is the same for Topological Sorting. There are worst, average, and best-case scenarios for time complexity. The time complexity for topological Sorting is O(E + V), where E means the number of Edges in the Graph, and V means the number of vertices in the Graph.

Let us break through this complexity:

Vaihe 1) Aluksi laskemme kaikki asteet. Tätä varten meidän täytyy käydä läpi kaikki reunat, ja aluksi määritämme kaikki V-pistein asteet nollaan. Joten suorittamamme vaiheet ovat O(V+E).

Vaihe 2) Löydämme solmun, jonka inastearvo on nolla. Meidän täytyy etsiä kärjen V-numerosta. Joten vaiheet on suoritettu O (V).

Vaihe 3) Jokaisen solmun, jolla on nolla astetta, poistamme kyseisen solmun ja vähennämme astetta. Tämän toiminnon suorittaminen kaikille solmuille kestää O(E).

Vaihe 4) Lopuksi tarkistamme, onko sykliä vai ei. Tarkistamme, onko lajitellun taulukon elementtien kokonaismäärä yhtä suuri kuin solmujen kokonaismäärä. Se tulee ottamaan O (1).

So, these were the individual time complexities for each step of the topological Sorting or topological ordering. We can say that the time complexity from the above calculation will be O(V + E); here, O means the complexity function.

Avaruuden monimutkaisuus: We needed O(V) spaces for running the topological sorting algorithm. Here are the steps where we needed the space for the program:

• Meidän piti laskea kaikki kaaviossa olevien solmujen asteet. Koska kaaviossa on yhteensä V-solmuja, meidän on luotava joukko, jonka koko on V. Tarvittava tila oli siis O (V).
• Jonotietorakennetta käytettiin solmun tallentamiseen nolla-asteella. Poistimme nolla-astetta sisältävät solmut alkuperäisestä kaaviosta ja asetimme ne jonoon. Tätä varten tarvittava tila oli O (V).
• The array is named “order”, which stored the nodes in topological order. That also required O (V) tilat.

These were the individual space complexities. So, we need to maximize these spaces in the run time. Space complexity stands for O(V), where V means the number of the vertex in the Graph.

Topologisen lajittelun soveltaminen

There is a huge use for Topological Sorting. Here are some of them:

• It is used when an Operating-järjestelmä täytyy suorittaa resurssien allokointi.
• Finding a cycle in the Graph. We can validate if the Graph is a DAG or not with topological sort.
• Lausejärjestys automaattisen täydennyksen sovelluksissa.
• It is used for detecting umpikujaan.
• Different types of Scheduling or course scheduling use the topological sort.
• Riippuvuuden ratkaiseminen. Jos esimerkiksi yrität asentaa paketin, se saattaa tarvita myös muita paketteja. Topologinen järjestys selvittää kaikki nykyisen paketin asentamiseen tarvittavat paketit.
• Linux käyttää topologista lajittelua "apt":ssa tarkistaakseen pakettien riippuvuuden.

UKK