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.
Ontwerp en implementeer een algoritme dat de toppen van een gerichte acyclische graaf topologisch sorteert. Implementeer hiervoor de interface TopologischSorteren1 in een klasse genaamd MijnTopologischSorteren. Hiervoor schrijf je een methode public List<Node<String>> bepaalTopologischeOrdening(DirectedGraph<String> graph), die een gerichte graaf als argument heeft. De uitvoer is een lijst van toppen in de volgorde waarin ze in de topologische ordening voorkomen. Merk op dat een gerichte acyclische graaf meerdere topologische ordeningen kan hebben. In deze oefening volstaat om het even welke legale ordening. Wanneer de gerichte graaf een cykel bevat, bestaat er geen topologische ordening en moet het algoritme een IllegalArgumentException opgooien.
We maken bij deze oefening gebruik van een eenvoudige grafenbibliotheek graphlib. Deze bevat onder meer de klassen DirectedGraph en Node. De API van deze bibliotheek vind je hier2. Neem eerst en vooral eens de API door en stel eventueel vragen hierover voor je begint te programmeren.
Belangrijke opmerking: om met de grafenbibliotheek te kunnen werken in IntelliJ, moet je het bestand graphlib.jar3 toevoegen aan je project. Hiervoor ga je naar File -> Project Structure…. Vervolgens kies je Libraries en klik je op de knop met het plusteken (+). Kies voor Java en navigeer naar het gedownloade bestand graphlib.jar.
Gebruik eventueel de testklasse SimpleTest4 om je oplossing lokaal te testen. Je kan hierin eenvoudig extra testgevallen toevoegen.
Het is niet toegestaan om de input graph van de methode bepaalTopologischeOrdening aan te passen. Indien je dit wel doet, zal de test falen. Je mag eventueel wel een kopie van je invoergraaf maken.