In het eerste practicum dient in Python een programma gemaakt te worden dat het volgende doet:

• een willekeurige graaf genereren
• Hamiltonkrings zoeken in grafen
• grafen visualiseren

Grafen genereren

Gegeven een aantal knopen, is een random graaf een graaf waarbij de knopen op willekeurige wijze met elkaar verbonden zijn. Een voorbeeld zijn de Erdos-Renyi grafen, die als volgt gegenereerd worden voor een gegeven aantal knopen n:

• de n knopen worden aanvankelijk zonder bogen in een lege grafe gestopt;
• voor elk paar knopen (x,y) wordt onafhankelijk met dezelfde kans p bepaald of ze met elkaar verbonden worden.

In dit proces is p een parameter. Als p=1 zijn alle knopen met elkaar verbonden; als p=0 zijn geen van de knopen met elkaar verbonden.

Maak nu een Python programma dat gegeven n en p een graaf genereert; dit programma dient een klasse voor de grafe te bevatten, een functie die de graaf willekeurig initialiseert, en een functie die ze wegschrijft in een tekstbestand; dit tekstbestand moet een lijst van bogen bevatten: elke regel bevat twee getallen, die de verbonden knopen aangeven. Maak tenslotte een functie die dit soort bestanden in kan lezen.

De parameters moeten vanaf de command line gelezen worden.

Hamilton krings

Schrijf een programma dat bepaalt of een graaf een Hamiltonkring heeft (een kring die alle knopen precies 1 keer af gaat). De functie moet werken op de klasse van de vorige opgave. Breid hiertoe de klasse van de vorige opgave uit en plaats deze klasse in een aparte module. Aan het einde van deze stap heb je dus:

• een bestand dat je graaf-klasse bevat
• een script dat de graaf-klasse gebruikt om een graaf te genereren (parameters op de command line: p, n en een bestandsnaam)
• een script dat de graaf-klasse gebruikt om Hamiltonkrings te zoeken (de parameter op de command line is de bestandsnaam)

Visualisatie

Schrijf een programma voor het visualiseren van de gegenereerde graaf en de gevonden Hamiltonkring. Tip: kijk hiervoor naar PyDot. Enkele voorbeelden van visualisatie door middel van Python zijn hier te vinden.

Links

• Python is bijzonder goed gedocumenteerd; kijk ook eens naar docs.python.org en in het bijzonder de documentatie van de random bibliotheek.
• Er zijn veel tutorials over Python voor C++ programmeurs op het Internet: zie bijvoorbeeld deze en deze.