0

Graph contains 'n' nodes and 'n-1' edges, hence, a unique path between any two nodes.

OK, so I know how we can find the vertices that lie on a path(given: source, destination) in a graph. It can easily be done by using DFS or BFS.

Example:

enter image description here

Input
List of entries, each entry contain Source and Destination vertices
Output
List of entries, each entry containing 'Vertices on path' corresponding to input entry.

Source Destination  Vertices on path
  5         4           5 4
  3         5           3 4 5
  1         3           1 5 4 3
  3         5           3 4 5
  5         4           5 4

My current solution
Currently I am running iterative DFS on each given path and finding the vertices that lie on that path.

Issue/Problem
When the no of nodes and no of paths given are large(~100,000) then finding the vertices on each given path(for all paths) is time consuming task.(Running DFS on each path for 100,000 paths for graph having 100,000 nodes). I want to know the better method of solving this problem. What data-structure or algorithm I may use instead of my current solution. Sometimes, I am also getting StackOverflow error, which I think is due to deep recursion.

Dominique Fortin
  • 2,212
  • 15
  • 20
ash
  • 156
  • 3
  • 12
  • Are you trying to list the vertices on the SHORTEST PATH or just A PATH from Start -> Goal on the graph? There is quite a big difference... If it's the latter, you don't need DFS or BFS or any other graph search algorithm, just keep a hasmap of paths and follow edges until there are no paths left on the graph that aren't in the hashmap. – Thomas Cook Apr 09 '18 at 12:25
  • Huh, turns out I'm a big mouthed know it all... My comment above is INCORRECT! Finding every path on a graph is NP-hard: https://stackoverflow.com/questions/9535819/find-all-paths-between-two-graph-nodes?utm_medium=organic&utm_source=google_rich_qa&utm_campaign=google_rich_qa – Thomas Cook Apr 09 '18 at 12:32
  • Thanks for the response. I forgot to mention that the graph contains 'n' nodes and 'n-1' edges. Hence, a unique path between any two nodes. – ash Apr 09 '18 at 12:52
  • You question seems to indicate that you are already provided with all the paths as part of your input: `"When the no of nodes and no of paths given are large(~100,000) then finding the vertices on each given path(for all paths) is time consuming task."` If you already have the paths, then surely listing the vertices is as simple as looping over the paths and storing each of the verts in an array? However, I assume finding the paths in the first place is part of your problem. In that case, if each node has 1 path to each other node, you should just follow the edges and store the verts in array. – Thomas Cook Apr 09 '18 at 13:09
  • Yes, paths are provided as input. `"If you already have the paths, then surely listing the vertices is as simple as looping over the paths and storing each of the verts in an array?".` Sure, that is what I am doing currently. Imagine I am provided 100,000 paths and the graph is also of 100,000 nodes. Iterating 100,000 time on 100,000 nodes is huge task. Storing each of the vertex on path in an array is not an issue. Yes, thats what we have to do. In which fashion to traverse the graph or tree is the main concern such that time consumed is less. – ash Apr 09 '18 at 13:19
  • You don't need to traverse the graph to get the verts of a path if you've been given the paths... just traverse the paths. In fact, the paths are essentially lists of nodes so your problem has already been solved no? – Thomas Cook Apr 09 '18 at 13:22
  • @ThomasCook Apologies if I was not clear in my question. I have edited it to make it more clear. Only a list of input is provided, each entry of list contains a source vertex and destination vertex. Need to find out all the vertices that lie on the path between the given input vertices. – ash Apr 09 '18 at 13:30
  • Oh, so you don't have all the paths as input? See the SO post I linked a few comments ago then (i.e. it's NP-hard, so if you figure it out make sure to write a paper on it ;-) ) – Thomas Cook Apr 09 '18 at 13:40
  • 2
    @ThomasCook NP-hard assumes a general graph. In this case there is a unique path between any two vertices, so the total number of paths is *O(n^2)* rather than exponential. – beaker Apr 09 '18 at 17:58
  • @beaker Thanks. Yes for calculating the path i.e. DFS, time complexity will be O(n) and if 'n' inputs are there, then time complexity will O(n^2). I am looking for a way to reduce this timing. – ash Apr 09 '18 at 19:27
  • @Ashish If you're calculating *O(n^2)* answers, and each answer has length *O(n)*, there's not much you can do to reduce the complexity of finding all the answers. The question becomes, why do you need to calculate *all* of the answers? – beaker Apr 09 '18 at 19:58

0 Answers0