How can I search a graph for a path?

Question

Say I have a list of edges each containing two nodes (to and from). What is the best way to find the edge two given nodes? Note that nodes in the edge may repeat.

Say I have edge in this format:

1 <-> 5

3 <-> 7

5 <-> 6

2<-> 6

Then query such as 1 5 will return true.

Then query such as 5 2 will return true because 5 connects 6 and 6 connects to 2.

Then query such as 1 7 will return false.

Then query such as 7 4 will return false since 4 doesnt exist, it means it is edge-less node.

Answer 1

You are basically looking forward to test if a given pair of nodes have a path in between them or not. This is a general case of the shortest path problem. Note, however, it suffices if we can find a shortest path between the pair of nodes in question. Use whatever representation suits you (adjacency matrix, adjacency list, edge-sets, union-find ...) and go ahead with a BFS/Djikstra implementation for all pair of nodes. It is then only a matter of servicing queries. Or, you can run Djikstra/BFS on a lazy basis (and cache past computations on an incremental manner).

Answer 2

Check out JGraphT library, it specializes in graph algorithms and does what you need.

Answer 3

It sounds to me like you are just asking if a path exists between two vertices in an undirected graph, but not necessarily what that path might be. This is the same as asking if the two vertices are in the same connected component of the graph.

If you really do only need to know if the two vertices are in the same connected component, then there is a simple and efficient algorithm using a Disjoint-set data structure.

initialize the disjoint set structure (DSS)
for each edge:
  for each vertex in edge:
    if the vertex does not exist in the DSS:
      create a new subset in the DSS containing only the vertex
  merge the subsets of the two vertices

To determine if a path exists between two vertices after processing all the edges, just check if the two vertices are in the same subset. If they are, then some path exists between them.

With an efficient implementation of the DSS, this algorithm achieves just slightly worse than linear time, and even with a simple linked-list implementation of the DSS it's O(n*log(n)). As j_random_hacker mentions, Floyd-Warshall is O(n^3) time and O(n^2) storage no matter if you are only calculating transitive closure or not, and using Dijkstra's algorithm requires an O(n*log(n)) calculation for each query.

Answer 4

You probably want some variation of Floyd algorithm for finding shortest paths between all graph verteces. As far as I can tell, you need only transitive closure of an undirected graph. Here is pseudocode:

for k = 1 to n
  for i = 1 to n
    for j = 1 to n
      W[i][j] = W[i][j] or (W[i][k] and W[k][j])

W before running this code should be a binary adjacency matrix for a graph (W[i][j] == 1 <-> there is an edge from i to j). After it will be a transitive closure. I.e. W[i][j] would be equal to 1 if and only if j is reachable from i.