==================================
Anwendung: Topologisches Sortieren   [TOC]
==================================

Die bislang entwickelte Datenstruktur für eine Hash-Tabelle
kann jetzt bequem genutzt werden, um einen Algorithmus für
das topologische Sortieren zu implementieren.

Die Eingabe besteht dabei aus beliebig vielen Zeilen
und jede Zeile besteht aus beliebig vielen Namen, die
durch Leerzeichen voneinander getrennt sind. Das wird
so interpretiert, dass der erste Name von all den
weiteren Namen in der gleichen Zeile abhängig ist.

Beispiel
========

:import: session08/step04/plan

Aus der ersten Zeile geht hier hervor, dass `essen_kochen`
davon abhängt, dass `einkauf_erledigen` und `zurueckfahren`
erledigt sind. Oder vor dem `tanken` muss `geld_haben`
erledigt sein. Topologisch sortiert erhalten wir folgende
Ausgabe:

---- SHELL (path=session08/step04,hostname=theon) --------
g++ -std=c++17 -o tsort tsort.cpp
./tsort <plan
----------------------------------------------------------

Aufgabe
=======

Entwickeln Sie eine Implementierung für das topologische
Sortieren. Es bietet sich hierzu Kahn's Algorithmus an,
siehe https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm

Der Algorithmus ist abzubrechen, sobald Sie einen Referenzzyklus
entdecken. In dem Fall sind die verbleibenden Elemente mitsamt
ihren Abhängigkeiten auszugeben.

Vorlage
=======

:import: session08/step03/Hash.hpp [fold]
:import: session08/step04/plan [fold]

Folgender Programmtext zeigt, wie die Eingabe erledigt
werden kann:

---- CODE (type=cpp) -------------------------------------------------------
#include <iostream>
#include <sstream>
#include <string>

int main() {
   std::string line;
   while (std::getline(std::cin, line)) {
      std::istringstream in(line);
      std::string name;
      if (!(in >> name)) continue;
      std::string depname;
      while (in >> depname) {
         /* 'name' depends on 'depname' */
      }
   }
}
----------------------------------------------------------------------------

:navigate: up   -> doc:index
           back -> doc:session08/page06
           next -> doc:session08/page08