def _backtracking()

in openr/py/openr/cli/commands/decision.py [0:0]

• 38 lines of code
• 12 McCabe index (conditional complexity)

        def _backtracking(cur, path, hop, visited, in_fib):
            """
            Depth-first search (DFS) for traversing graph and getting paths
            from src to dst with lowest metric in total.

            Attributes:
                cur: current starting node
                path: a list of the nodes who form the path from src to the current node
                hop: how many hops from src node to the current node
                visited: a set of visited nodes
                in_fib: if current node is in fib path
            """
            if hop > max_hop:
                return

            # get the longest prefix match for dst_addr from current node's advertising prefixes
            cur_lpm_len = self.get_lpm_len_from_node(cur, dst_addr)
            # get the next hop nodes
            next_hop_nodes = self.get_nexthop_nodes(
                client.getRouteDbComputed(cur),
                dst_addr,
                cur_lpm_len,
                if2node,
                fib_routes,
                in_fib,
            )

            if len(next_hop_nodes) == 0:
                if hop != 1:
                    paths.append((in_fib, path[:]))
                return

            for next_hop_node in next_hop_nodes:
                next_hop_node_name = next_hop_node[0]
                # prevent loops
                if next_hop_node_name in visited:
                    return

                path.append([hop] + next_hop_node)
                visited.add(next_hop_node_name)

                # check if next hop node is in fib path
                is_nexthop_in_fib_path = False
                for nexthop in fib_routes[cur]:
                    if (
                        next_hop_node[3] == ipnetwork.sprint_addr(nexthop.addr)
                        and next_hop_node[1] == nexthop.ifName
                    ):
                        is_nexthop_in_fib_path = True

                # recursion - extend the path from next hop node
                _backtracking(
                    next_hop_node_name,
                    path,
                    hop + 1,
                    visited,
                    is_nexthop_in_fib_path and in_fib,
                )
                visited.remove(next_hop_node_name)
                path.pop()