q14

q14.py

E = {
    "A": [],
    "B": ["A", "E"],
    "C": ["D", "H"],
    "D": ["B"],
    "E": ["F"],
    "F": [],
    "G": ["A"],
    "H": ["B", "G"],
}

def valid(graph, sorted_nodes):
    for i in range(len(sorted_nodes)):
        node = sorted_nodes[i]
        # check if all neighbors of node appear after node in sorted_nodes
        for neighbor in graph[node]:
            if neighbor in sorted_nodes[:i]:
                return False
    return True

def count_naive(graph):
    # create all permutations of graph nodes
    from itertools import permutations
    total = 0
    for perm in permutations(graph.keys()):
        if valid(graph, perm):
            total += 1
    return total

def count_dfs(graph, sorted_nodes):
    if not valid(graph, sorted_nodes):
        return 0
    if len(sorted_nodes) == len(graph):
        print (sorted_nodes)
        return 1
    total = 0
    for node in graph:
        if node not in sorted_nodes:
            extended_nodes = sorted_nodes + [node]
            total += count_dfs(graph, extended_nodes)
    return total


if __name__ == "__main__":
    import time
    start_time = time.time()
    print(count_naive(E))
    print("Naive time: %s seconds" % (time.time() - start_time))

    start_time = time.time()
    print(count_dfs(E, []))
    print("DFS time: %s seconds" % (time.time() - start_time))