Finding all nodes on a graph that are N nodes away

user_8351650 0
Viewed 472

You and a few friends are playing a board game. The board of the game is laid out in a large interconnected graph that has many loops. Each player starts at a different location on the board. When it is your turn, you get to roll anything between one to six 6-sided dice (in other words, anything from a 1-36). How do you determine every space that you can possibly go to in a single turn from your current location? (Example: I roll a 13. Find all spots on the board that are 13 spaces away from me.) You can only move forwards but you can loop around to traverse a net total of less than your roll.

Example: If this is your graph and you start at the top-left corner and you rolled a 6, then one place you can move is down, right, right, up, left, left. However you cannot move right, left, right, left, right, left.

  o---o---o---o---o
  |       |   |
  o---o---o---o

Are there any algorithms available that do better than depth-first search?

graph-traversal graph-algorithm algorithm
2 Answers

You don't need to actually traverse the graph at all to solve this problem.

The graph can be encoded by its adjacency matrix: a matrix M such that M(i,j) = 1 if there is an edge from node i to node j and M(i,j) = 0 if there isn't an edge.

This matrix has a super cool property: for any nonnegative integer k, M**k (the k-th power of M, i.e., M multiplied by itself k times) is such that (M**k)(i,j) = number of different walks from i to j.

If (M**k)(i,j) > 0, then node i can be reached from node j in exactly k moves. Note that, if you make sure that every node had an edge to itself, i.e., if the diagonal of M is full of 1s, then the nodes that can be reached in exactly k moves are the same as the nodes that can be reached in at most k moves.

See also: https://en.wikipedia.org/wiki/Adjacency_matrix#Matrix_powers

In most programming languages, there are libraries that handle matrices and matrix operations quite efficiently, so that taking a matrix to a power can be much faster than actually visiting the nodes of a graph one after the other.

On the other hand, if the graph is huge and k is small, and you are only interested in one starting node, then calculating M**k might be less efficient than graph traversal, since M**k answers the question for every node of the graph, rather than just for the starting node you are interested in.

But if you are interested in all possible starting nodes or if k is close to the diameter of the graph, then computing M**k is most likely the best option.

user_30807230

With the restriction that you can go in circles, but not directly back to the node you came from, this is in fact quite an interesting problem. In particular, you can neither just do a BFS or DFS and prune all nodes you've already visited in fewer moves, nor would the clever matrix multiplication work.

Instead, you could use a variant of DFS, but you will have to keep track of both the number of moves you can reach a node in, and the node you came from when visiting that node, and only prune branches if you have seen that exact combination before -- not if you were reaching the node in fewer moves, or coming from another node.

Basic implementation in Python and example:

def search(graph, start, moves):
    stack = [(start, 0, -1)]
    distance = {i: set() for i in range(moves+1)}
    while stack:
        node, dist, prev = stack.pop()
        if (node, prev) in distance[dist]: continue
        distance[dist].add((node, prev))
        if dist < moves:
            stack.extend((x, dist+1, node) for x in graph[node] if x != prev)
    return {node for (node, prev) in distance[moves]}

# 1---2---3---4---5
# |       |   |
# 6---7---8---9
g = {1: [2,6], 2: [1,3], 3: [2,4,8], 4: [3,5,9], 5: [4],
     6: [1,7], 7: [6,8], 8: [3,7,9], 9: [4,8]}
print(search(g, 1, 13))
# {8, 2, 4, 6}
user_16396250
Related