2.8.7 💡 Grafen modelleren in Python

class Grafe:
    def __init__(self, knopen, bogen):
        self.knopen = knopen
        self.bogen = bogen

knopen = { 'New York', 'Los Angeles', 'Phoenix' , 'Chicago', 'Houston' }
bogen = {
('Chicago','Los Angeles'),
('Chicago', 'Phoenix'),
('Chicago', 'Houston'),
('Houston','Phoenix'),
('Los Angeles','Phoenix'),
('Los Angeles','New York'),
('New York','Phoenix')
}

steden = Grafe(knopen, bogen)
print(sorted(steden.knopen))
print(sorted(steden.bogen))

2.8.8 💡 Gewogen grafen modelleren in Python

class Grafe:
    def __init__(self, knopen, bogen):
        self.knopen = knopen
        self.bogen = bogen

knopen = { 'New York', 'Los Angeles', 'Phoenix' , 'Chicago', 'Houston' }
bogen = {
('Chicago','Los Angeles', 3250),
('Chicago', 'Phoenix', 2821),
('Chicago', 'Houston', 1743),
('Houston','Phoenix', 1892),
('Los Angeles','Phoenix', 600),
('Los Angeles','New York', 4496),
('New York','Phoenix', 3900)
}

steden = Grafe(knopen, bogen)
print(sorted(steden.knopen))
print(sorted(steden.bogen))

2.8.9 💡 Gerichte grafen modelleren in Python

class Grafe:
    def __init__(self, knopen, bogen):
        self.knopen = knopen
        self.bogen = bogen

knopen = {"kerk", "bakker", "restaurants", "park"}
bogen = {
    ("kerk", "restaurants"),
    ("kerk", "park"),
    ("park", "restaurants"),
    ("restaurants", "park"),
    ("restaurants", "kerk"),
    ("restaurants", "bakker"),
    ("bakker", "kerk"),
    ("bakker", "restaurants")
}

straten = Grafe(knopen, bogen)

print(sorted(straten.knopen))
print(sorted(straten.bogen))

2.8.10 💡 Nieuwe boog

class Grafe:
    def __init__(self, knopen, bogen):
        self.knopen = knopen
        self.bogen = bogen

    def nieuw(self, boog):
        # self.bogen is een verzameling, dus we gebruiken de functie .add()
        self.bogen.add(boog) 
        # een boog is een tupel van twee knopen
        k1 = boog[0]
        k2 = boog[1]
        # de knopen worden toegevoegd aan de verzameling van knopen in de grafe
        # denk eraan dat er geen dubbele elementen in een verzameling zitten
        # er is dus geen risico dat we een knoop meerdere keren toevoegen
        self.knopen.add(k1)
        self.knopen.add(k2) 

knopen = { 'Kortrijk', 'Antwerpen', 'Gent' , 'Brussel', 'Hasselt' }
bogen = {
('Gent','Kortrijk'),
('Antwerpen', 'Gent'),
('Brussel', 'Gent'),
('Antwerpen','Brussel'),
('Antwerpen','Hasselt'),
('Brussel','Hasselt')
}

snelwegen = Grafe(knopen, bogen)

snelwegen.nieuw(('Brussel', 'Leuven'))
snelwegen.nieuw(('Hasselt', 'Leuven'))

snelwegen.nieuw(('Brugge', 'Gent'))
snelwegen.nieuw(('Brugge', 'Kortrijk'))

print(sorted(snelwegen.knopen))
print(sorted(snelwegen.bogen))

2.8.11 🧠 Buren

class Grafe:
    def __init__(self, knopen, bogen):
        self.knopen = knopen
        self.bogen = bogen

    def nieuw(self, boog):
        self.bogen.add(boog) 
        k1 = boog[0]
        k2 = boog[1]
        self.knopen.add(k1)
        self.knopen.add(k2) 

    def buren(self, knoop):
        resultaat = set()
        for boog in self.bogen:
            if boog[0] == knoop:
                resultaat.add(boog[1])
            elif boog[1] == knoop:
                resultaat.add(boog[0])
        return resultaat

2.8.12 🧠 Bestaat de boog?

class Grafe:
    def __init__(self, knopen, bogen):
        self.knopen = knopen
        self.bogen = bogen

    def nieuw(self, boog):
        self.bogen.add(boog) 
        k1 = boog[0]
        k2 = boog[1]
        self.knopen.add(k1)
        self.knopen.add(k2) 

    def buren(self, knoop):
        resultaat = set()
        for boog in self.bogen:
            if boog[0] == knoop:
                resultaat.add(boog[1])
            elif boog[1] == knoop:
                resultaat.add(boog[0])
        return resultaat

    def bestaat_boog(self, k1, k2):
        if (k1, k2) in self.bogen or (k2, k1) in self.bogen:
            return True
        return False

2.8.13 🧠 Aantal buren

class Grafe:
    def __init__(self, knopen, bogen):
        self.knopen = knopen
        self.bogen = bogen

    def nieuw(self, boog):
        self.bogen.add(boog) 
        k1 = boog[0]
        k2 = boog[1]
        self.knopen.add(k1)
        self.knopen.add(k2) 

    def buren(self, knoop):
        resultaat = set()
        for boog in self.bogen:
            if boog[0] == knoop:
                resultaat.add(boog[1])
            elif boog[1] == knoop:
                resultaat.add(boog[0])
        return resultaat

    def bestaat_boog(self, k1, k2):
        if (k1, k2) in self.bogen or (k2, k1) in self.bogen:
            return True
        return False

    def aantal_buren(self, knoop):
        return len(self.buren(knoop))

2.8.14 🧠 Verwijder een boog

class Grafe:
    def __init__(self, knopen, bogen):
        self.knopen = knopen
        self.bogen = bogen

    def nieuw(self, boog):
        self.bogen.add(boog) 
        k1 = boog[0]
        k2 = boog[1]
        self.knopen.add(k1)
        self.knopen.add(k2) 

    def buren(self, knoop):
        resultaat = set()
        for boog in self.bogen:
            if boog[0] == knoop:
                resultaat.add(boog[1])
            elif boog[1] == knoop:
                resultaat.add(boog[0])
        return resultaat

    def bestaat_boog(self, k1, k2):
        if (k1, k2) in self.bogen or (k2, k1) in self.bogen:
            return True
        return False

    def aantal_buren(self, knoop):
        return len(self.buren(knoop))

    def verwijder(self, boog):
        if boog in self.bogen:
            self.bogen.remove(boog)

2.8.15 🧠🧠 Reisplanner

class Grafe:
    def __init__(self, knopen, bogen):
        self.knopen = knopen
        self.bogen = bogen

    def nieuw(self, boog):
        self.bogen.add(boog) 
        k1 = boog[0]
        k2 = boog[1]
        self.knopen.add(k1)
        self.knopen.add(k2) 

    def buren(self, knoop):
        resultaat = set()
        for boog in self.bogen:
            if boog[0] == knoop:
                resultaat.add(boog[1])
            elif boog[1] == knoop:
                resultaat.add(boog[0])
        return resultaat

    def bestaat_boog(self, k1, k2):
        if (k1, k2) in self.bogen or (k2, k1) in self.bogen:
            return True
        return False

    def aantal_buren(self, knoop):
        return len(self.buren(knoop))

    def verwijder(self, boog):
        if boog in self.bogen:
            self.bogen.remove(boog)

    def verbonden(self, stad1, stad2):
        # stap 1: directe verbinding
        if self.bestaat_boog(stad1, stad2):
            return 1

        # stap 2: via een buur
        for buur in self.buren(stad1):
            if self.bestaat_boog(buur, stad2):
                return 2

        # stap 3: niet verbonden
        return 0