0

I need to count a number of bridges in graph, but when I put a test with over 100000 vertexes I randomly get a stackoverflow, sometimes I get a right result and sometimes I get stackoverflow. What does go wrong? (lane 9, to= j.next)

public int findBridgeshelp(int v, int p, boolean[] used, int[] tin, int[] fup, int timer){
    used[v] = true;
    tin[v] = fup[v] = timer++;
    Iterator<Integer> j = lists[v].iterator();
    int count=0;
    for (int i=0; i<lists[v].size(); ++i) {
        int to=0;
        if(j.hasNext())
            to= j.next();
        if (to == p)  continue;
        if (used[to])
            fup[v] = Math.min(fup[v], tin[to]);
        else {
            count=count+ findBridgeshelp(to, v, used, tin, fup, timer);
            fup[v] = Math.min(fup[v], fup[to]);
            if (fup[to] > tin[v])
                count++;
        }
    }
    return count;
}
Popeye The Sailor
  • 151
  • 9
  • 1
    You have a recursive function, maybe you're getting an infinite recursion. You need to debug your code. Or rewrite it in non-recursive manner. – lexicore Mar 05 '18 at 19:04
  • Do you need to do this recursively? – Mick Mnemonic Mar 05 '18 at 19:05
  • @Brian That's palliative. Not a duplicate. – lexicore Mar 05 '18 at 19:05
  • @lexicore If the code sometimes returns and sometimes does not, then it's very likely that it's just a stack memory error, which is exactly what a `StackOverflowError` is. Given that the testing fails periodically with a very large number of vertices, but assumably not less, this is even more likely. – Brian Mar 05 '18 at 19:06
  • @Brian I do not think the problem is the small stack. I think the problem is in the code. You write "just a stack memory error" as it would excuse the code. – lexicore Mar 05 '18 at 19:10
  • The function looks deterministic. It should behave exactly the same way, given the same data. It should not “randomly” fail, unless the data is randomly generated. – AJNeufeld Mar 05 '18 at 19:38
  • @lexicore Assuming Windows 64-bit with a default stack size of 256K: 6 parameters at 4 bytes each, an `Iterator` allocation that is a non-escaped local variable which is another few dozen bytes (let's assume just the rough minimum of 40 bytes), that already limits us to ~16k recursion depth. That's also ignoring function overhead. It is very easy to imagine this algorithm going more than 16k recursions deep with over 100k vertices. – Brian Mar 05 '18 at 19:41
  • @AJNeufeld The only possibly non-deterministic value in the algorithm might be the `lists` variable, e.g. `lists[v].iterator()`, since it appears to be outside the stack/method. But assuming that the lists are not being manipulated during the call (which would probably lead to a `ConcurrentModificationException` since the iterator is being used), I agree, it appears to be deterministic. – Brian Mar 05 '18 at 19:43
  • @Brian "It is very easy to imagine this algorithm going more than 16k recursions deep with over 100k vertices." - then maybe it is not the best algorithm. – lexicore Mar 05 '18 at 19:52

0 Answers0