Een topologische ordening van een gerichte acyclische graaf is een ordening van de toppen van deze graaf zodanig dat, als er een pad is van \(u\) naar \(v\), dan \(v\) in de ordening na \(u\) komt.
Opmerking: Het is duidelijk dat een topologische ordening niet mogelijk is als de graaf een gerichte cykel bevat. Voor elke twee toppen \(v\) en \(w\) op dergelijke cykel is er immers een pad van \(v\) naar \(w\) en een pad van \(w\) naar \(v\). Dus elke ordening van \(v\) en \(w\) zou contradictorisch zijn met één van beide paden.
Implementeer een functie bepaal_topologische_ordening(graaf:DirectedGraph) die, gegeven een adjacentielijst, een topologische ordering van de toppen teruggeeft. Wanneer dit onmogelijk is omdat de graaf een cykel bevat, moet een AssertionError opgeworpen worden met de boodschap “de graaf bevat een cykel”.
We maken bij deze oefening gebruik van een eenvoudige grafenbibliotheek graphlib. De API van de deze bibliotheek vind je hier1. Neem eerst en vooral eens de API en de bibliotheek zelf door en stel eventueel vragen hierover voor je begint te programmeren.
Belangrijke opmerking: om met de grafenbibliotheek te kunnen werken in PyCharm moet je het bestand graph_library.py2 toevoegen aan dezelfde directory als waarin je ze gebruikt. Dan kun je ze gebruiken door ze te importeren met
from graph_library import *
Dit import statement mag wel niet mee ingediend worden op dodona.
Het is niet toegestaan om de input graph van de methode bepaal_topologische_ordening aan te passen. Indien je dit wel doet, zal de test falen. Je mag eventueel wel een kopie van je invoergraaf maken.
>>> graph01 = directed_graph_from_dict({3: [7], 7: [5], 2: [7, 5], 5: []})
>>> bepaal_topologische_ordening(graph01)
[Node(2), Node(3), Node(7), Node(5)]
>>> graph02 = directed_graph_from_dict({8: [13], 15: [8, 9, 13], 3: [8, 15, 9, 7], 10: [8, 9], 6: [8, 15, 3, 9], 7: [], 9: [], 13: []})
>>> bepaal_topologische_ordening(graph02)
[Node(6), Node(3), Node(7), Node(10), Node(15), Node(8), Node(9), Node(13)]