Finding distinct routes for a graph considering a max distance

Question

So here it's my problem:

I'm trying to find all different paths from C to C, where the max distance is 30.

I think that there's a problem with my stop conditions, but I have trying this for so long that I can't see what is wrong (prints 2 but it should be 7).

There's a implementation in Java for my problems, but I wanted to do it in Python (problem 10): link

My code:

            from collections import defaultdict, deque


        class Graph(object):
            def __init__(self):
                self.nodes = set()
                self.edges = defaultdict(list)
                self.distances = {}

            def add_node(self, value):
                self.nodes.add(value)

            def add_edge(self, from_node, to_node, distance):
                self.edges[from_node].append(to_node)
                self.distances[(from_node, to_node)] = distance

        def are_these_nodes_adjacents(from_node, to_node):
            return to_node in graph.edges[from_node]

        def count_distance(graph, u, v, k, max_distance):
            if(k > 0 and u == v and k != max_distance): 
                return 1
            if(k > 0 and are_these_nodes_adjacents(u, v)): 
                return 1
            if(k <= 0): 
                return 0

            count = 0

            for i in ['A', 'B', 'C', 'D', 'E']:
                if(are_these_nodes_adjacents(u, i)):
                        count += count_distance(graph, i, v, k-graph.distances[(u, i)], max_distance)
            return count

        if __name__ == '__main__':
            graph = Graph()

            for node in ['A', 'B', 'C', 'D', 'E']:
                graph.add_node(node)

            graph.add_edge('A', 'B', 5)
            graph.add_edge('B', 'C', 4)
            graph.add_edge('C', 'D', 8)
            graph.add_edge('D', 'C', 8)
            graph.add_edge('D', 'E', 6)
            graph.add_edge('A', 'D', 5)
            graph.add_edge('C', 'E', 2)
            graph.add_edge('E', 'B', 3)
            graph.add_edge('A', 'E', 7)

            u = 'C'
            v = 'C'
            k = 30
            print(count_distance(graph, u, v, k, k))

Answer 1

The following condition in your code:

if(k > 0 and u == v and k != max_distance):  
         return 1

You are returning and stopping the search as soon as you go back to node C again. Instead of doing that, you need to add 1 to count, and continue the search.

And you should delete the following condition:

if(k > 0 and are_these_nodes_adjacents(u, v)): 
                return 1

Why do you have it?

This is the resulting code which prints 7 as needed:

from collections import defaultdict


class Graph(object):
    def __init__(self):
        self.nodes = set()
        self.edges = defaultdict(list)
        self.distances = {}

    def add_node(self, value):
        self.nodes.add(value)

    def add_edge(self, from_node, to_node, distance):
        self.edges[from_node].append(to_node)
        self.distances[(from_node, to_node)] = distance

def are_these_nodes_adjacents(from_node, to_node):
    return to_node in graph.edges[from_node]

def count_distance(graph, u, v, k, max_distance):
    if(k <= 0): 
        return 0

    count = 0

    if(k > 0 and u == v and k != max_distance): 
        count += 1

    for i in ['A', 'B', 'C', 'D', 'E']:
        if(are_these_nodes_adjacents(u, i)):
                count += count_distance(graph, i, v, k-graph.distances[(u, i)], max_distance)
    return count

if __name__ == '__main__':
    graph = Graph()

    for node in ['A', 'B', 'C', 'D', 'E']:
        graph.add_node(node)

    graph.add_edge('A', 'B', 5)
    graph.add_edge('B', 'C', 4)
    graph.add_edge('C', 'D', 8)
    graph.add_edge('D', 'C', 8)
    graph.add_edge('D', 'E', 6)
    graph.add_edge('A', 'D', 5)
    graph.add_edge('C', 'E', 2)
    graph.add_edge('E', 'B', 3)
    graph.add_edge('A', 'E', 7)

    u = 'C'
    v = 'C'
    k = 30
    print(count_distance(graph, u, v, k, k))