Re: [jgrapht-users] DFS Question

[Welson S. <wel...@ya...>]

Thanks for the prompt reply and fix.

One related question is that if the SCC decomposition function in JGraphT
uses this DFS function? It should be easy to find out, but I am just
lazy............. 

-----Original Message-----
From: John V. Sichi [mailto:js...@gm...] 
Sent: Friday, August 04, 2006 10:45 PM
To: Welson Sun
Cc: jgr...@li...
Subject: Re: [jgrapht-users] DFS Question

Welson Sun wrote:
> Since it is impossible to share my source code due to various reasons, 
> I have attached a very simple Java code which reproduce this problem. 
> It creates a graph with the same topology, and use 
> org._3pq.jgrapht.traverse.DepthFirstIterator to do DFS. See the .jpg 
> for the graph, and the DFS output is:
> 
> A
> B
> C
> G
> I
> F
> E
> H
> D  <---- This is wrong
> J
> K
> L

Doh.  This is embarrassing.  Looks like the bug has been there from the very
first version in which DFS appeared (0.4.1), even before I joined the
project, but has survived numerous refactorings by me!  The problem is that
encounterVertexAgain should be promoting J when it sees it the second time,
but it currently just leaves it where it is in the middle of the stack.

At some point certain parties even made an attempt to tell me about it, but
because I couldn't understand their description and they didn't follow up
with a testcase, I closed the bug:

http://sourceforge.net/tracker/index.php?func=detail&aid=1169182&group_id=86
459&atid=579687

So thank you very much for raising it.  A simple fix is to change
DepthFirstIterator.encounterVertexAgain to do this:

int i = m_stack.indexOf(vertex);
if (i != -1) {
     m_stack.remove(i);
     m_stack.add(vertex);
}

I'll see if I can come up with something efficient when I fix it permanently
in 0.7.1.  There have been requests to keep track of the discovery and
finish time, so I can probably kill two birds with one stone by keeping this
info in the "seen data" and using it to know whether something is still on
the stack or not without linear search.

JVS