Algorithm Is Node A Connected to Node B in Graph

Question

I am looking for an algorithm to check for any valid connection (shortest or longest) between two arbitrary nodes on a graph.

My graph is fixed to a grid with logical (x, y) coordinates with north/south/east/west connections, but nodes can be removed randomly so you can't assume that taking the edge with coords closest to the target is always going to get you there.

The code is in python. The data structure is each node (object) has a list of connected nodes. The list elements are object refs, so we can then search that node's list of connected nodes recursively, like this:

for pnode in self.connected_nodes:
    for cnode in pnode.connected_nodes:
        ...etc

I've included a diagram showing how the nodes map to x,y coords and how they are connected in north/east/south/west. Sometimes there are missing nodes (i.e between J and K), and sometimes there are missing edges (i.e between G and H). The presence of nodes and edges is in flux (although when we run the algorithm, it is taking a fixed snapshot in time), and can only be determined by checking each node for it's list of connected nodes.

The algorithm needs to yield a simple true/false to whether there is a valid connection between two nodes. Recursing through every list of connected nodes explodes the number of operations required - if the node is n edges away, it requires at most 4^n operations. My understanding is something like Dijistrka's algorithm works by finding the shortest path based on edge weights, but if there is no connection at all then would it still work?

For some background, I am using this to model 2D destructible objects. Each node represents a chunk of the material, and if one or more nodes do not have a connection to the rest of the material then it should separate off. In the diagram - D, H, R - should pare off from the main body as they are not connected.

UPDATE:

Although many of the posted answers might well work, DFS is quick, easy and very appropriate. I'm not keen on the idea of sticking extra edges between nodes with high value weights to use Dijkstra because node's themselves might disappear as well as edges. The SSC method seems more appropriate for distinguishing between strong and weakly connected graph sections, which in my graph would work if there was a single edge between G and H.

Here is my experiment code for DFS search, which creates the same graph as shown in the diagram.

class node(object):
    def __init__(self, id):
        self.connected_nodes  = []
        self.id               = id

    def dfs_is_connected(self, node):
        # Initialise our stack and our discovered list
        stack      = []
        discovered = []

        # Declare operations count to track how many iterations it took
        op_count = 0

        # Push this node to the stack, for our starting point
        stack.append(self)

        # Keeping iterating while the stack isn't empty
        while stack:
            # Pop top element off the stack
            current_node = stack.pop()

            # Is this the droid/node you are looking for?
            if current_node.id == node.id:
                # Stop!
                return True, op_count

            # Check if current node has not been discovered
            if current_node not in discovered:

                # Increment op count
                op_count += 1

                # Is this the droid/node you are looking for?
                if current_node.id == node.id:
                    # Stop!
                    return True, op_count

                # Put this node in the discovered list
                discovered.append(current_node)

                # Iterate through all connected nodes of the current node
                for connected_node in current_node.connected_nodes:
                    # Push this connected node into the stack
                    stack.append(connected_node)

        # Couldn't find the node, return false. Sorry bud
        return False, op_count


if __name__ == "__main__":

    # Initialise all nodes
    a = node('a')
    b = node('b')
    c = node('c')
    d = node('d')
    e = node('e')
    f = node('f')
    g = node('g')
    h = node('h')
    j = node('j')
    k = node('k')
    l = node('l')
    m = node('m')
    n = node('n')
    p = node('p')
    q = node('q')
    r = node('r')
    s = node('s')

    # Connect up nodes
    a.connected_nodes.extend([b, e])
    b.connected_nodes.extend([a, f, c])
    c.connected_nodes.extend([b, g])
    d.connected_nodes.extend([r])
    e.connected_nodes.extend([a, f, j])
    f.connected_nodes.extend([e, b, g])
    g.connected_nodes.extend([c, f, k])
    h.connected_nodes.extend([r])
    j.connected_nodes.extend([e, l])
    k.connected_nodes.extend([g, n])
    l.connected_nodes.extend([j, m, s])
    m.connected_nodes.extend([l, p, n])
    n.connected_nodes.extend([k, m, q])
    p.connected_nodes.extend([s, m, q])
    q.connected_nodes.extend([p, n])
    r.connected_nodes.extend([h, d])
    s.connected_nodes.extend([l, p])

    # Check if a is connected to q
    print a.dfs_is_connected(q)
    print a.dfs_is_connected(d)
    print p.dfs_is_connected(h)

Answer 1

To find this out, you just need to run simple DFS or BFS algorithm on one of the nodes, it'll find all reachable nodes within a continuous component of the graph, so you just mark it down if you've found the other node during the run of algorithm.

Answer 2

You can find strongly connected components(SCC) of your graph and then check if nodes of interest in one component or not. In your example H-R-D will be first component and rest second, so for H and R result will be true but H and A false. See SCC algorithm here: https://class.coursera.org/algo-004/lecture/53.

Answer 3

You could take a look at the A* Path Finding Algorithm (which uses heuristics to make it more efficient than Dijkstra's, so if there isn't anything you can exploit in your problem, you might be better off using Dijkstra's algorithm. You would need positive weights though. If this is not something you have in your graph, you could simply give each edge a weight of 1).

Looking at the pseudo code on Wikipedia, A* moves from one node to another by getting the neighbours of the current node. Dijkstra's Algorithm keeps an adjacency list so that it knows which nodes are connected to each other.

Thus, if you where to start from node H, you could only go to R and D. Since these nodes are not connected to the others, the algorithm will not go through the other nodes.

Answer 4

There is a way to use Dijkstra to find the path. If there is an edge between two nodes put 1 for weight, if there is no node, put weight of sys.maxint. Then when the min path is calculated, if it is larger than the number of nodes - there is no path between them.

Another approach is to first find the strongly connected components of the graph. If the nodes are on the same strong component then use Dijkstra to find the path, otherwise there is no path that connects them.