1

How to find all the nodes that lead to certain other node without traversing all the graph? (directed graph)

Is there a way to performed this?

Are there techniques or algorithms that help perform this task without having to traverse all the graph?

UPDATE

Imagine that your graph has 3 paths that can reach A, how do you find those 3 paths without traversing all the graph? I don't want one of the paths but all tree. I'm from relational databases and what cames to my mind is indexes, but graphs are different, so I'm asking if there is a way to find all the nodes that lead to A without traversing all the graph. Or in worst case traversing only once, and from there I can just query the structure for the paths.

In SQL Terms it would be like:

SELECT nodes.id 

FROM Graph 

WHERE node.destination = "A";

node.destination would have to take into account indirect paths.

So this is kinda what I want. a fast way to get all the nodes that can reach node A

Nelssen
  • 1,023
  • 1
  • 17
  • 42

3 Answers3

1

The lazy way

If you do not have time complexity constraints, I would recommend the lazy way by using the Dijkstra-Algorithmus. Most garaph librarys, like jgrapht, implemented this algorithm. You can check if Dijkstra finds a (shortest) path from each node in the graph to the node you want to examine.

UweJ
  • 447
  • 3
  • 10
  • Hi @UweJ, I'm not after the shortest path but all the paths that lead to A. I added additional details in my question that clarifies what I want. Either way I think it my be a good heuristic, so you are suggesting that I calculate the paths for the nodes I want once and then save them in some cache/index and then I can check there for the nodes? – Nelssen May 16 '20 at 08:47
  • 1
    Hi, as I understand you have a directed graph with a lot of nodes, e.g (N1, N2, N3, N4,..., NM) and you want to know whether there exist a path between e.g. the nodes N2, N3, N4,..., NM to node N1. You can use the shortest-path algorithm to find the shortest path between node N1 and N2, N3, N4,..., NM. So you have to execute the shortest path algorithm (M-1) times. Even if you are not interested in the shortest path, the existence of a shortest path shows, that there exists a path. Instead of the Dijkstra algorithm, you can also use the Depth First Search (DFS) recommended by @cOder. – UweJ May 16 '20 at 13:58
  • In case I understand you wrong and you want to find all existing pathes between two distinct nodes, you maybe can use https://jgrapht.org/javadoc/org/jgrapht/alg/shortestpath/AllDirectedPaths.html – UweJ May 16 '20 at 13:58
  • I think you understood right, it's all paths to NM, not between two nodes. Thank you for your effort. it was really valuable – Nelssen May 18 '20 at 14:39
1

There are many search algorithm that search a path without necessarily going through all traversing all the graph:

  • DFS is a simple one. The path it finds is not necessarily the shortest one.
  • BFS is also simple and finds the shortest path.
  • Dijkstra, is an enhanced BFS which finds the shortest path and is likely to transverse less nodes than BFS.
  • A* is an enhanced Dijkstra which finds the shortest path and is likely to transverse less nodes than Dijkstra.

More information as well as visual demonstration of various search algorithm can be found here.

Edit:

Imagine that your graph has 3 paths that can reach A, how do you find those 3 paths without traversing all the graph?

If you want to find all paths from node A to node B you'll have to explore the entire graph because you don't know which path leads to the target and which one is a dead end.

c0der
  • 18,467
  • 6
  • 33
  • 65
  • I @c0der, I'm not after the shortest path but all the paths that lead to A. It looks a bit of a contradiction I know but I'm new to graphs. I added additional details to my question, hope it helps. (That visual demo is sick. thank you for sharing) – Nelssen May 16 '20 at 08:35
1

Finding all nodes which can lead to a given destination node may involve traversal of complete graph. Whether full graph will be traversed or not is function of adjacency and selected destination node.

As you are interested in path, not necessarily shortest, you can use DFS/BFS. You can start with destination node and DFS/BFS by following incoming edges (Not out going edges). As per your query you only need node ids not even path so no need to keep track of traversal sequence also. Indexing and caching can definitely help if query is going to be recurring and graph adjacency doesn't change very frequently.

nkvns
  • 580
  • 3
  • 5
  • This looks closer to an answer, but what bugs me is that you say to follow incoming edges, how do you find the incoming nodes in a directed graph? is that even possible? – Nelssen May 18 '20 at 14:34
  • It should be possible to get incoming edges for a node. Efficiency of this operation is dependent on graph structure and adjacency representation. – nkvns May 19 '20 at 17:18