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