jgrapht-users

Re: [jgrapht-users] DFS Question

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

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


Welson
 

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

Welson Sun wrote:
> I have got a DG (see attached pic), using 
> org._3pq.jgrapht.traverse.DepthFirstIterator I got the following DFS
> sequence:
> 
> START
> input
> ._2biquad.Add
> ._2biquad.b3
> ._2biquad.Add2
> ._2biquad.b
> ._2biquad.a3
> ._2biquad.Add7
> ._2biquad.a2
> ._2biquad.Add1
> output
> STOP
> 
> I don't think this sequence is correct, any insights before I dig into 
> the source code?

The sequence is not correct, but without the source code for a JUnit
testcase reproducing the problem in isolation, it's hard to say more.

JVS

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

Re: [jgrapht-users] DFS Question

[John V. S. <js...@gm...>]

Welson Sun wrote:
> 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............. 

StrongConnectivityInspector uses its own private little DFS routine 
because DepthFirstIterator doesn't provide the discovery/finish times. 
At the time that Christian contributed it, we discussed enhancing 
DepthFirstIterator to be reusable here, but didn't do anything about it. 
  Yet another TODO.

JVS

Re: [jgrapht-users] DFS Question

[John V. S. <js...@gm...>]

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=86459&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

Re: [jgrapht-users] DFS Question

[John V. S. <js...@gm...>]

John V. Sichi wrote:
> 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.

I've checked a more efficient fix into Subversion.  DepthFirstIterator 
now keeps track of the standard WHITE/GRAY/BLACK vertex visit states, 
and uses them to provide a finish event via TraversalListener.  No 
timestamps yet.  Code review by anyone who has time would be 
appreciated; maybe someone can enhance BreadthFirstIterator to publish 
vertex finish events in the same way.

Khanh Vu also reported a problem with CycleDetector, which I fixed.  It 
is now using StrongConnectivityInspector for one of the cases; it should 
probably be using it for more of them; I'll see about that as part of 
changing StrongConnectivityInspector to use DepthFirstIterator.

I'm going to take care of a few of the other recent requests and then 
put out 0.7.1.

JVS