Kaikki polut

Annettuna on suunnattu syklitön verkko, ja tehtäväsi on laskea, montako erilaista polkua verkossa on.

Toteuta luokka AllPaths, jossa on seuraavat metodit:

• add_edge lisää kaaren kahden solmun välille
• count antaa erilaisten polkujen määrän

Toteuta metodi count tehokkaasti dynaamisella ohjelmoinnilla.

Toteuta luokka tiedostoon allpaths.py seuraavan esimerkin mukaisesti.

class AllPaths:
    def __init__(self, n):
        # TODO

    def add_edge(self, a, b):
        # TODO

    def count(self):
        # TODO

if __name__ == "__main__":
    a = AllPaths(4)
    a.add_edge(1, 2)
    a.add_edge(1, 3)
    a.add_edge(2, 4)
    a.add_edge(3, 4)
    print(a.count()) # 10
    a.add_edge(2, 3)
    print(a.count()) # 14

Selitys: Metodin count ensimmäinen kutsu laskee mukaan seuraavat polut:

• 1
• 1 \rightarrow 2
• 1 \rightarrow 2 \rightarrow 4
• 1 \rightarrow 3
• 1 \rightarrow 3 \rightarrow 4
• 2
• 2 \rightarrow 4
• 3
• 3 \rightarrow 4
• 4