De knopen van een gerichte graaf worden geïdentificeerd via een uniek etiket, van het type str. Een tekstbestand bevat per regel een pad in de graaf, in volgend formaat:

knoop -> knoop -> knoop -> ...

De knopen in het pad worden dus gescheiden door de sequentie ` -> ` (die sequentie start en eindigt met een spatie. De paden in het bestand bevatten alle takken en knopen van de gerichte graaf.

Schrijf volgende functies:

• lees_graaf() : deze functie heeft als enig argument de naam van een tekstbestand waarin de informatie m.b.t. de in te lezen gerichte graaf te vinden is. Het resultaat van de functie is een woordenboek, met als sleutel een knoop waaruit pijlen vertrekken en als bijhorende waarde de set van knopen waar die pijlen toekomen (dus een verzameling van strings).
• doel() : deze functie heeft twee argumenten, namelijk een woordenboek dat een gerichte graaf voorstelt (formaat zoals hierboven aangegeven) en een etiket van een knoop k in deze graaf. Het resultaat is een verzameling (Python set) van alle knopen van waaruit een pijl vertrekt die toekomt op de knoop k.
• buren() : deze functie heeft drie argumenten, namelijk:
  • een woordenboek dat een gerichte graaf voorstelt (formaat zoals hierboven gegeven)
  • een startknoop k (dus van het type str)
  • een positief geheel getal d
  Het resultaat is de verzameling (Python set) van knopen die je startende vanuit k in hoogstens d stappen kan bereiken. De startknoop is steeds in dit resultaat aanwezig, vermits die zeker bereikbaar is.

Voorbeeld

Tabblad 1

Inhoud van 'GerichteGraaf_0.txt'

a -> h -> d -> n
l -> d
j -> l
g -> d
c -> n -> f

Inhoud van 'GerichteGraaf_1.txt'

i -> c -> g
e -> l -> c -> k
i -> b -> p
p -> n -> c -> m
i -> d
n -> f
d -> o -> b -> h -> n

Inhoud van 'GerichteGraaf_2.txt'

c -> b
o -> m -> h -> l
j -> n -> m
g -> a
k -> l
o -> i -> n -> h

lees_graaf('GerichteGraaf_0.txt')
#{'j': {'l'}, 'l': {'d'}, 'n': {'f'}, 'h': {'d'}, 'd': {'n'}, 'g': {'d'}, 'c': {'n'}, 'a': {'h'}}

lees_graaf('GerichteGraaf_1.txt')
#{'l': {'c'}, 'n': {'c', 'f'}, 'b': {'h', 'p'}, 'h': {'n'}, 'p': {'n'}, 'i': {'c', 'b', 'd'}, 'c': {'m', 'g', 'k'}, 'o': {'b'}, 'e': {'l'}, 'd': {'o'}}

lees_graaf('GerichteGraaf_2.txt')
#{'m': {'h'}, 'j': {'n'}, 'n': {'m', 'h'}, 'h': {'l'}, 'i': {'n'}, 'g': {'a'}, 'c': {'b'}, 'o': {'m', 'i'}, 'k': {'l'}}

Tabblad 2

doel({'j': {'l'}, 'l': {'d'}, 'n': {'f'}, 'h': {'d'}, 'd': {'n'}, 'g': {'d'}, 'c': {'n'}, 'a': {'h'}}, 'h')
#{'a'}

doel({'l': {'c'}, 'n': {'c', 'f'}, 'b': {'h', 'p'}, 'h': {'n'}, 'p': {'n'}, 'i': {'c', 'b', 'd'}, 'c': {'m', 'g', 'k'}, 'o': {'b'}, 'e': {'l'}, 'd': {'o'}}, 'o')
#{'d'}

doel({'m': {'h'}, 'j': {'n'}, 'n': {'m', 'h'}, 'h': {'l'}, 'i': {'n'}, 'g': {'a'}, 'c': {'b'}, 'o': {'m', 'i'}, 'k': {'l'}}, 'm')
#{'n', 'o'}

Tabblad 3

buren({'d': {'n'}, 'l': {'d'}, 'c': {'n'}, 'j': {'l'}, 'g': {'d'}, 'h': {'d'}, 'n': {'f'}, 'a': {'h'}}, 'c', 0)
#{'c'}

buren({'o': {'b'}, 'd': {'o'}, 'l': {'c'}, 'c': {'g', 'k', 'm'}, 'n': {'c', 'f'}, 'p': {'n'}, 'b': {'h', 'p'}, 'i': {'b', 'd', 'c'}, 'h': {'n'}, 'e': {'l'}}, 'd', 4)
#{'o', 'h', 'n', 'b', 'd', 'p'}

buren({'o': {'i', 'm'}, 'h': {'l'}, 'k': {'l'}, 'c': {'b'}, 'j': {'n'}, 'g': {'a'}, 'm': {'h'}, 'n': {'h', 'm'}, 'i': {'n'}}, 'k', 2)
#{'k', 'l'}