The goal of this problem is to cover all roads with cameras. A camera placed at a station can cover all the roads connected to it. For example, if we place a camera at station 0, the roads (or edges) (0,3) and (0,8) are covered. Note: the edges (0,3) and (3,0) are the same. We want to find all solutions that can cover a network. For example, one solution is to place a camera at each station will cover all roads. In G2, which has 10 stations, this solution is the set {0,1,2,3,4,5,6,7,8,9} or [True, True, True, True, True, True, True True, True, True). Another solution for G2 is {2, 3, 5, 8} or [False, False, True, True, False, True, False, False, True, False, False]. Any road/edge in G2 is connected to one of these 2 or 3 or 5 or 8. Therefore, {2,3,5, 8} is one of the solutions we look for. The code below is almost complete in printing out all solutions, i.e. sets of stations that cover an entire network. What you need to do for this problem is modyfing the is_coverage function, which returns True if the solution is a coverage, and False if it is not. At this time, it's just a placeholder, which always returns True. This is obviously incorrect. You need to fix it. [42]: def is_coverage (solution, G): return True def get_stations(s): return set([i for i in range(len(s)) if s[i]==True]) def cover(G, solution, i): if i==len(solution): if is_coverage (solution, G): print(get_stations ( solution)) else: solution[i] = True cover(G, solution, i+1) solution[i] = False cover(G, solution, i+1)
