Het bepalen van een opspannende boom is een veelvoorkomend grafenprobleem. Een netwerk van ethernetkabels zal bijvoorbeeld vaak aangelegd worden met redundante kabels. Het spanning tree protocol (STP) zal dynamisch een opspannende boom berekenen en daarmee lussen (cykels) vermijden, verbindingen vervangen wanneer kabels (bogen) het begeven en toch steeds de routes (paden) tussen elke paar nodes voorzien.

Bij het opstellen van een opspannende boom tussen nodes is het voordelig om de vertraging (latency) op het netwerk te minimaliseren. Men zou, als we aan elke verbinding de latency op die verbinding toekennen, dit probleem kunnen herformuleren als het bepalen van een minimale-kost opspannende boom. In de praktijk wordt niet de latency tussen elke twee nodes geminimaliseerd, maar de latency tussen elke node en een root node, waar dan de uplink (de weg naar de rest van het internet) van het lokaal netwerk is.

In deze oefening implementeren we het algoritme van Kruskal voor het bepalen van een minimale-kost opspannende boom in een gewogen samenhangende graaf.

Schrijf een functie span(graph) die een gewogen samenhangende graaf als parameter meekrijgt, deze functie moet een deelgraaf van graph teruggegeven die een minimale-kost opspannende boom van graph is.

We maken bij deze oefening gebruik van een eenvoudige grafenbibliotheek graphlib. De API van de deze bibliotheek vind je hier¹. 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.py² 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.

Voorbeeld:

>>> graph = undirected_graph_from_dict({'Alice': ['Bob'], 'Bob': ['Carol'], 'Carol': ['Alice']}, weights = {('Alice', 'Bob'): 10, ('Bob', 'Carol'): 5, ('Carol', 'Alice'): 1})
>>> spanning_tree = span(graph)
>>> spanning_tree.get_all_nodes()
{Node('Alice'), Node('Bob'), Node('Carol')}
>>> spanning_tree.get_all_edges()
{UndirectedEdge(Node('Carol'), Node('Alice'), weight=1), UndirectedEdge(Node('Bob'), Node('Carol'), weight=5)}