All paths

You are given a directed acyclic graph with the nodes $1,2,\dots,n$. Your task is to count how many different paths there are in the graph.

A path is a sequence of nodes with a forward directional edge between all pairs of adjacent nodes. A single node counts as a path too.

In a file allpaths.py, implement the class AllPaths with the following methods:

• add_edge adds an edge between two nodes
• count returns the number of different paths

Implement the method count efficiently using dynamic programming.

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

The first call to the method count includes the following paths into the count:

• $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$