commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From James Carman <>
Subject Re: [graph] Doubts on DFS algorithm implementation
Date Sun, 26 Feb 2012 23:47:52 GMT
On Sun, Feb 26, 2012 at 5:41 PM, Claudio Squarcella
<> wrote:
> the method "discoveryEdge" currently tells whether or not the algorithm
> should explore a subtree/branch and add related vertices to the stack/queue.
> So I see no conflict in the implementation. Maybe you are saying that the
> edge should be explored *right before* the vertex it leads to -- but why?
> AFAIK a standard graph search is only concerned with *vertices*. In that
> sense "finishEdge" becomes useless, as the responsibility for returning
> prematurely is entirely covered by "finishVertex". Am I raving mad? :-)

Well, you bring up a good point.  Are we concerned with "visiting"
both the edges and the vertices?  Typically, I just care about the
vertices when doing dfs/bfs on graphs, but I can see how one might
want to do both.  Also, I don't know if we have an abstraction for
this, but the order in which you add your connected vertices can be
important, too (might want to do a "greedy" bfs/dfs).  Unfortunately,
I've not had much time to dig into this code, but I would really love
to find some time.  I like this kind of stuff.  It makes me feel like
all that discrete mathematics stuff I studied wasn't a complete waste!
:)  In the "business" world, you don't get to play with this stuff
that often.

To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message