Een gerichte graaf bestaat uit knopen die elk via een unieke string geïdentificeerd worden. De adjacencymatrix van deze graaf wordt in een tekstbestand opgeslagen. In de eerste rij en de eerste kolom van het bestand vind je de knopen van de graaf terug (waarbij de volgorde niet noodzakelijk gelijk is), voorafgegaan door een aantal te negeren spaties.
a b c ... b 0 0 1 ... c 1 0 1 ... a 0 1 0 ... . . . . ... . . . . ... . . . . ...In de matrix vind je op rij
r en kolom k een 0 of een 1 terug, naargelang er al dan niet een pijl
vertrekt uit de knoop op rij r naar de knoop op kolom k. Op een regel zijn alle
elementen via een spatie van mekaar gescheiden.
Schrijf volgende functies :
lees_adj(): deze functie heeft als enig argument de naam van een
tekstbestand waarin de informatie over de gerichte graaf (zie hierboven) te vinden is.
Het resultaat is een woordenboek met als sleutel een knoop van de graaf en als
bijhorende waarde de verzameling (Python set) van knopen waarheen een pijl vertrekt vanuit
de sleutelknoop. Indien er geen pijlen vertrekken vanuit deze sleutelknoop (rij van nullen in het tekstbestand),
is dit een lege verzameling. niet_gebruikt(): deze functie heeft 2 argumenten, namelijk een
woordenboek die een gerichte graaf voorstelt (formaat zoals hierboven weergegeven),
en een lijst van paden in deze graaf. Elk pad wordt op zijn beurt voorgesteld door een lijst van
graafknopen. Het is de bedoeling om in de graaf deze paden af te lopen. Het resultaat van de functie is een
verzameling (Python set) van graaftakken die NIET voorkomen in de opgegeven lijst van paden.
Elke niet-gebruikte graaftak wordt voorgesteld door een tuple met 2 elementen,
namelijk de startknoop van de ongebruikte tak en de doelknoop van de ongebruikte tak.h j k o p f i m a g k 0 1 1 1 0 1 0 0 1 0 a 1 0 1 1 1 1 0 1 0 1 g 1 1 0 0 1 1 0 1 1 0 o 1 0 1 1 1 0 0 1 1 0 i 0 0 1 1 1 1 1 0 1 1 p 1 0 0 0 1 1 0 1 0 1 j 1 1 0 1 1 0 0 0 1 0 m 0 1 1 1 1 0 1 1 1 1 f 0 1 0 0 0 0 0 1 1 0 h 0 1 0 0 0 1 1 1 1 0Inhoud van 'Adjacency_1.txt
c n b l h j m f l 0 0 0 0 0 0 1 0 f 1 0 0 1 0 0 0 0 b 0 0 0 0 1 0 0 0 m 0 0 1 0 0 1 0 0 n 0 0 1 0 0 0 0 0 j 0 0 0 0 0 0 0 1 h 0 0 1 0 0 0 0 0 c 0 0 0 0 1 0 0 0Inhoud van 'Adjacency_20.txt
aaa bbb HH cc aa ii DD kK ii 0 0 1 1 0 1 1 0 bbb 0 1 1 0 1 1 0 1 aaa 1 0 0 0 1 1 0 1 HH 1 0 1 0 0 1 0 1 DD 1 1 1 0 1 0 1 0 kK 0 1 1 1 1 1 1 1 aa 1 0 0 0 1 1 0 0 cc 1 1 0 0 1 0 0 1
lees_adj('Adjacency_0.txt')
#{'h': {'f', 'j', 'i', 'a', 'm'}, 'i': {'i', 'o', 'f', 'p', 'a', 'k', 'g'}, 'o': {'h', 'o', 'm', 'p', 'a', 'k'}, 'a': {'h', 'o', 'm', 'f', 'p', 'k', 'g'}, 'm': {'i', 'o', 'm', 'k', 'p', 'a', 'j', 'g'}, 'f': {'j', 'a', 'm'}, 'k': {'f', 'j', 'o', 'a', 'k'}, 'g': {'h', 'm', 'f', 'p', 'a', 'j'}, 'j': {'h', 'j', 'o', 'a', 'p'}, 'p': {'h', 'g', 'f', 'p', 'm'}}
lees_adj('Adjacency_1.txt')
#{'c': {'h'}, 'h': {'b'}, 'n': {'b'}, 'm': {'j', 'b'}, 'f': {'c', 'l'}, 'j': {'f'}, 'b': {'h'}, 'l': {'m'}}
lees_adj('Adjacency_20.txt')
#{'ii': {'HH', 'DD', 'ii', 'cc'}, 'kK': {'kK', 'cc', 'ii', 'aa', 'DD', 'bbb', 'HH'}, 'DD': {'HH', 'aa', 'DD', 'bbb', 'aaa'}, 'bbb': {'HH', 'aa', 'ii', 'bbb', 'kK'}, 'aaa': {'ii', 'aa', 'aaa', 'kK'}, 'HH': {'HH', 'kK', 'ii', 'aaa'}, 'aa': {'ii', 'aa', 'aaa'}, 'cc': {'aa', 'bbb', 'aaa', 'kK'}}
niet_gebruikt({'h': {'f', 'j', 'i', 'a', 'm'}, 'i': {'i', 'o', 'f', 'p', 'a', 'k', 'g'}, 'o': {'h', 'o', 'm', 'p', 'a', 'k'}, 'a': {'h', 'o', 'm', 'f', 'p', 'k', 'g'}, 'm': {'i', 'o', 'm', 'k', 'p', 'a', 'j', 'g'}, 'f': {'j', 'a', 'm'}, 'k': {'f', 'j', 'o', 'a', 'k'}, 'g': {'h', 'm', 'f', 'p', 'a', 'j'}, 'j': {'h', 'j', 'o', 'a', 'p'}, 'p': {'h', 'g', 'f', 'p', 'm'}}, [['p', 'g', 'm'], ['a', 'k', 'a', 'o', 'm'], ['k']])
#{('p', 'p'), ('j', 'h'), ('g', 'p'), ('j', 'j'), ('p', 'h'), ('j', 'a'), ('m', 'm'), ('i', 'g'), ('k', 'f'), ('m', 'i'), ('m', 'o'), ('h', 'f'), ('a', 'p'), ('m', 'p'), ('o', 'o'), ('k', 'j'), ('m', 'g'), ('p', 'f'), ('k', 'o'), ('a', 'm'), ('o', 'p'), ('i', 'p'), ('g', 'f'), ('g', 'j'), ('j', 'p'), ('i', 'f'), ('m', 'j'), ('k', 'k'), ('a', 'g'), ('f', 'a'), ('i', 'k'), ('a', 'f'), ('j', 'o'), ('o', 'k'), ('o', 'h'), ('m', 'a'), ('p', 'm'), ('f', 'j'), ('g', 'h'), ('h', 'a'), ('m', 'k'), ('h', 'j'), ('i', 'o'), ('i', 'i'), ('h', 'i'), ('i', 'a'), ('h', 'm'), ('o', 'a'), ('a', 'h'), ('g', 'a'), ('f', 'm')}
niet_gebruikt({'c': {'h'}, 'h': {'b'}, 'n': {'b'}, 'm': {'j', 'b'}, 'f': {'c', 'l'}, 'j': {'f'}, 'b': {'h'}, 'l': {'m'}}, [['m'], ['f', 'l', 'm'], ['j', 'f', 'l']])
#{('n', 'b'), ('m', 'j'), ('c', 'h'), ('f', 'c'), ('b', 'h'), ('h', 'b'), ('m', 'b')}
niet_gebruikt({'h': {'k'}, 'k': {'j', 'k'}, 'p': {'h', 'l'}, 'j': {'h', 'j', 'p'}, 'l': {'h', 'p', 'l'}}, [['k', 'k', 'k'], ['k', 'j'], ['k', 'k']])
#{('j', 'p'), ('p', 'l'), ('j', 'h'), ('j', 'j'), ('h', 'k'), ('p', 'h'), ('l', 'p'), ('l', 'h'), ('l', 'l')}