Kaikki polut

Annettuna on suunnattu syklitön verkko, jonka solmut ovat $1,2,\dots,n$. Tehtäväsi on laskea, montako erilaista polkua verkossa on.

Polku on solmujen jono, jossa jokaisen kahden peräkkäisen solmun välillä on eteenpäin menevä kaari. Myös yksittäinen solmu lasketaan poluksi.

Toteuta tiedostoon allpaths.py 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.

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

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

    def count(self):
        # TODO

if __name__ == "__main__":
    counter = AllPaths(4)

    counter.add_edge(1, 2)
    counter.add_edge(1, 3)
    counter.add_edge(2, 4)
    counter.add_edge(3, 4)

    print(counter.count()) # 10

    counter.add_edge(2, 3)

    print(counter.count()) # 14

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$