Anwendung: Topologisches Sortieren
Content |
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
essen_kochen einkauf_erledigen zurueckfahren einkauf_erledigen geld_haben ware_nehmen bezahlen ware_nehmen hinfahren geld_haben bezahlen geld_haben ware_nehmen geld_haben geld_abheben geld_abheben zur_bank_gehen geldautomat_bedienen zur_bank_gehen hinfahren geldautomat_bedienen zur_bank_gehen pin_eingeben pin_eingeben zur_bank_gehen zurueckfahren hinfahren tanken tanken geld_haben
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:
theon$ g++ -std=c++17 -o tsort tsort.cpp theon$ ./tsorthinfahren zur_bank_gehen pin_eingeben geldautomat_bedienen geld_abheben geld_haben tanken ware_nehmen bezahlen zurueckfahren einkauf_erledigen essen_kochen theon$
Aufgabe
Entwickeln Sie eine Implementierung für das topologische Sortieren. Es bietet sich hierzu Kahn's Algorithmus an, siehe https://en.wikipedia.org/wiki/Topologicalsorting#Kahn'salgorithm
Der Algorithmus ist abzubrechen, sobald Sie einen Referenzzyklus entdecken. In dem Fall sind die verbleibenden Elemente mitsamt ihren Abhängigkeiten auszugeben.
Vorlage
#ifndef HASH_HPP #define HASH_HPP #include <cassert> #include <cstdlib> #include <functional> #include <memory> #include <utility> template<typename Key, typename Value> class Hash { public: using Object = std::pair<const Key, Value>; private: struct Node; using NodePtr = std::shared_ptr<Node>; struct Node { Node(Object object) : object(std::move(object)) { } Node(Object object, NodePtr next) : object(std::move(object)), next(next) { } Object object; NodePtr next; }; const std::size_t dim; std::shared_ptr<NodePtr[]> bucket; std::hash<Key> hash; std::size_t count; /* number of objects */ public: class Iterator { public: friend Hash; Iterator() : dim(0), index(0) { } Iterator(Hash& hash) : dim(hash.dim), bucket(hash.bucket), index(0) { advance(); } Iterator(Hash& hash, std::size_t index, NodePtr prev, NodePtr node) : dim(hash.dim), bucket(hash.bucket), index(index), prev(prev), node(node) { assert(node && index < dim); } Object& operator*() { return node.lock()->object; } const Object& operator*() const { return node.lock()->object; } Object* operator->() { return &node.lock()->object; } Iterator& operator++() { advance(); return *this; } bool operator==(const Iterator& other) { bool end1 = index >= dim; bool end2 = other.index >= other.dim; if (end1 && end2) return true; if (end1 || end2) return false; return bucket.lock() == other.bucket.lock() && index == other.index && node.lock() == other.node.lock(); } bool operator!=(const Iterator& other) { return !(*this == other); } private: void advance() { /* move to next object */ auto b = bucket.lock(); if (b) { auto n = node.lock(); if (n) { node = n->next; n = node.lock(); if (!n) ++index; } if (!n) { while (index < dim && !b[index]) { ++index; } if (index < dim) { node = b[index]; } } } else { node = NodePtr(); index = dim; } } std::size_t dim; std::weak_ptr<NodePtr[]> bucket; std::size_t index; /* current location in bucket table */ std::weak_ptr<Node> prev; /* previous object, if any in the same list */ std::weak_ptr<Node> node; /* current object at bucket[index] */ }; Hash(std::size_t dim) : // dim(dim), bucket(std::make_shared<NodePtr[]>(dim)) { dim(dim), bucket(new NodePtr[dim]), count(0) { } std::pair<Iterator, bool> insert(Object object) { auto index = hash(object.first) % dim; auto ptr = bucket[index]; NodePtr prev; while (ptr && ptr->object.first != object.first) { prev = ptr; ptr = ptr->next; } bool inserted; if (ptr) { inserted = false; } else { ptr = std::make_shared<Node>(std::move(object), bucket[index]); bucket[index] = ptr; prev = nullptr; inserted = true; ++count; } return std::make_pair(Iterator(*this, index, prev, ptr), inserted); } Iterator find(Key key) { auto index = hash(key) % dim; auto ptr = bucket[index]; NodePtr prev; while (ptr && ptr->object.first != key) { prev = ptr; ptr = ptr->next; } if (ptr) { return Iterator(*this, index, prev, ptr); } else { return Iterator(); } } void erase(Iterator it) { if (it.bucket.lock() == bucket && it.index < dim) { auto node = it.node.lock(); auto prev = it.prev.lock(); if (node) { if (prev) { prev->next = node->next; } else { bucket[it.index] = node->next; } --count; } } } template<typename F> void for_each(F&& f) { for (std::size_t index = 0; index < dim; ++index) { auto ptr = bucket[index]; while (ptr) { f(ptr->object); ptr = ptr->next; } } } Iterator begin() { return Iterator(*this); } Iterator end() { return Iterator(); } std::size_t size() const { return count; } }; #endif
essen_kochen einkauf_erledigen zurueckfahren einkauf_erledigen geld_haben ware_nehmen bezahlen ware_nehmen hinfahren geld_haben bezahlen geld_haben ware_nehmen geld_haben geld_abheben geld_abheben zur_bank_gehen geldautomat_bedienen zur_bank_gehen hinfahren geldautomat_bedienen zur_bank_gehen pin_eingeben pin_eingeben zur_bank_gehen zurueckfahren hinfahren tanken tanken geld_haben
Folgender Programmtext zeigt, wie die Eingabe erledigt werden kann:
#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' */ } } }