CODEWITHSUNDEEP
javagraphhashmapstack-overflow
sAlmeida
sAlmeida

Reputation: 99

Java stack overflow error - Graph algorithm

I am using as a data structure for represent a graph,a HashMap - HashMap (one for the locality and one inside the locality in order to represent the destinations) , i had inserted 20 000 localities. Now i need to make a function to know if exist a path between two Localities, this function is recursive and it require me to make a lot of get objects of my hashMap to work with them. For each destination to make i have always to execute the method get in my api, to give me a copy of the hashMap with the destinations Everytime that i run my program, i get a Stackoverflow error. Why this always happen ? it's due the high recursive calls? Or it 's due the constantly call get method to have a copy of the hashMap of the locality's destinations?

thanks.

Upvotes: 4

Views: 209

Answers (5)

sAlmeida
sAlmeida

Reputation: 99

Thank you for the help, the problem is already solved. I decided to forget the recursive calls, and choice the DFS variant .

Upvotes: 1

Untitled
Untitled

Reputation: 790

Does the same thing happen for a smaller graph? If so , you have some bug in your recursion that probably causes an infinite recursion. If doesn't happen for smaller graphs, this is your algorithm that knocks you down.

Upvotes: 0

user3001
user3001

Reputation: 3487

Which algorithm do you use for finding the shortest path? Can it contain circles or negative edge weights? Depending on that, use Dijktra, Prim, Floyd-Warshall or whatsoever. Steven Skiena's "Algorithm Design Manual", p. 206ff gives some good detailed explanations on various shortest path graph algorithms. I'm sure, many of them are iterative rather than recursive.

Upvotes: 0

Francis Upton IV
Francis Upton IV

Reputation: 19443

It's the recursive calls. Each level of recursive call consumes space on the stack, so if you are getting a large number of these calls you will run out of stack space. Change your algorithm to be non-recursive.

Upvotes: 1

templatetypedef
templatetypedef

Reputation: 372684

Stack overflows are caused by the recursion depth exceeding some fixed limit. This probably has nothing to do with copying the HashMap; that would cause an OutOfMemoryError. If you are doing a graph search recursively, the error is likely caused by either

  1. A depth-first search going too deep, or
  2. A bug in your recursion logic.

Without more data I can't say which it is. Do note, though, that DFS can be written iteratively using an explicit stack to store the nodes to explore. Posting more code would help us make a better diagnosis.

Hope this helps!

Upvotes: 2

Related Questions