pythongraphbreadth-first-search

Looking to make my program BFS algorithm more efficient

I am working on a program that does a Breadth First Search on a series of connected links, and should output a print statement telling me what links to cut. The links to cut will block a certain agent from going to its present location, to one of the exit gateways scattered around the graph.

enter image description here

The image shows exactly what the program does, and what it shouldn't do at the same time. The green dotted links are those that I am printing, which will cut the path to the red coloured bobnet agent to the light blue coloured exit gateways.

Here is the mapping of the inputs for my program:

Initialization input: Line 1: 3 integers N L E

Next L lines: 2 integers per line (N1, N2), indicating a link between the nodes indexed N1 and N2 in the network.

Next E lines: 1 integer EI representing the index of an exit gateway node.

So what happens in my program is that, as you can see, the program checks the location of the agent, and cuts the most probable link next to it. However, there seems to be a more efficient program, which instead of finishing in 39 moves like in my case, ends with less, and I want to ask for help finding what is wrong with my program to effectively manage to make it more efficient:

import sys
from collections import deque

class Binder:
    
    def __init__(self, id, pre_binder):
        self.id = id
        self.pre_binder = pre_binder
        
class Game:

    def __init__(self):
        # n: the total number of nodes in the level, including the gateways
        # l: the number of links
        # e: the number of exit gateways
        n, l, e = [int(j) for j in input().split()]
        self.graph = {i: [] for i in range(n)}

        for _ in range(l):
            # n1: N1 and N2 defines a link between these nodes
            n1, n2 =  [int(j) for j in input().split()]
            self.graph[n1].append(n2)
            self.graph[n2].append(n1)

        self.exit_gateways = [int(input()) for _ in range(e)] # the index of a gateway node

    def breadth_first_search(self, root):
        print(f"Graph nodes: {self.graph}", file=sys.stderr)

        visited, queue = set(), deque([Binder(root, None)])
        visited.add(root)

        while queue:
            binder = queue.popleft()
            vertex = binder.id
            print(f"Bobnet Location: {self.graph[vertex]}", file=sys.stderr)

            for neighbor in self.graph[vertex]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    new_binder = Binder(neighbor, binder)
                    queue.append(new_binder)

                if neighbor in self.exit_gateways:
                    return Binder(neighbor, binder)
                            
def trace_and_cut_link(result_binder):
    current_binder = result_binder
    while current_binder.pre_binder is not None:
        previous_binder = current_binder.pre_binder
        link_to_cut = (previous_binder.id, current_binder.id)
        print(f'Cutting link: {link_to_cut}', file=sys.stderr)
        current_binder = previous_binder
    print(link_to_cut[0], link_to_cut[1])

game = Game()

while True:
    node_index = int(input())  # The index of the node on which the Bobnet agent is positioned this turn
    result_binder = game.breadth_first_search(node_index)
    trace_and_cut_link(result_binder)


Game information:
Graph nodes: {0: [2, 10, 9, 5, 12, 11, 17, 7, 13, 14, 6, 3, 4, 15, 1, 16, 8], 
1: [2, 17, 0, 37], 
2: [0, 37, 1, 3, 35], 
3: [34, 0, 2, 4], 
4: [5, 33, 0, 3], 
5: [4, 0, 6], 
6: [5, 0, 7], 
7: [8, 0, 6], 
8: [7, 9, 0], 
9: [0, 10, 8], 
10: [0, 11, 9], 
11: [10, 0, 12], 
12: [0, 11, 13], 
13: [14, 0, 12], 
14: [13, 0, 15], 
15: [16, 14, 0], 
16: [17, 15, 0], 
17: [16, 0, 1], 
18: [26, 24, 23, 22, 27, 25, 21, 19, 20], 
19: [27, 20, 18], 
20: [19, 21, 18], 
21: [29, 22, 18, 20], 
22: [18, 23, 21, 36], 
23: [18, 24, 35, 22, 37], 
24: [18, 23, 25, 37], 
25: [26, 24, 18], 
26: [18, 25, 27], 
27: [19, 18, 26], 
28: [36, 32, 34, 31, 35, 29, 33, 30], 
29: [21, 30, 28, 36], 
30: [31, 29, 28], 
31: [30, 28, 32], 
32: [28, 33, 31], 
33: [32, 4, 34, 28], 
34: [3, 35, 28, 33], 
35: [37, 34, 23, 28, 36, 2], 
36: [28, 22, 35, 29], 
37: [35, 2, 23, 1, 24]}

Block the Agent!
Agent is at position 37

Standard Output Stream:
37 35
Game information:
Link [37-35] severed
Agent moved from 37 to 2

Standard Output Stream:
2 0
Game information:
Link [2-0] severed
Agent moved from 2 to 35

Standard Output Stream:
35 28
Game information:
Link [35-28] severed
Agent moved from 35 to 23

Thank you in advance.

Solution

  • There are at least two improvements possible:

    1. Don't only report that an edge ("link") is cut, also remove it from your graph, otherwise you risk to report the same edge in one of the next rounds. And when you do remove it, don't forget to remove it in both directions.

    2. Instead of cutting the edge near the agent, cut the edge that is closest to the exit gateway.

    For the example graph that would ensure you only cut 35 edges as then the exit gateways are completely detached from the rest of the graph.

    If these improvements are not enough, then here is an additional idea:

    1. When finding the shortest path, also find all alternative paths of the same length, and only then exit the breadth-first search. This means your BFS has to be adapted considerably: don't mark nodes as visited until you have found all paths of the same length, where multiple paths may end at the same node. Don't exit the search when you find an exit, but continue a bit more until you have all paths of the same length to that exit.

    Then check which edge in these paths is shared most often, and cut that edge. For example, if you have this situation:

                                *------exit
                           /      /
           *-------*------*------*
          /       /
      agent------*

    ...then you should find 4 different paths from agent to exit, and the edge at the center will be in all four paths. So that is the most frequently used edge and should be cut.