commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Thomas Neidhart <thomas.neidh...@gmail.com>
Subject Re: [graph] Doubts on DFS algorithm implementation
Date Wed, 29 Feb 2012 20:08:00 GMT
On 02/27/2012 07:35 PM, Claudio Squarcella wrote:
> Hello,
> 
> if you want to postpone the edge visit to the right time (i.e. when the
> corresponding tail vertex is removed from the "waiting list") then I
> guess the waiting list itself should also keep track of the edge and/or
> the predecessor (vertex). The class PredecessorsList probably does that
> job fairly well.
> 
> Rephrasing a bit: we are seeking a unified implementation for both
> standard "graph searches" (only concerned with vertices) and more
> general "graph visits" (e.g. the one needed for max flow algorithms). So
> yeah, let's use our brains for something cool :)

Hi,

I have followed the discussion and implemented the discussed changes
right away:

 - a unified graph search method using a wrapper class as James
   suggested
 - discoverEdge / finishEdge are called in the correct order according
   to the chosen strategy (depth or breadth search)

The call order is as follows:

 - discover the edge that lead to the vertex
   unless we are at the start vertex of course
 - call finishEdge, when we shall finish, skip the next steps
 - if we shall expand the edge, discover the vertex
 - find all connections from this vertex and add to the queue/stack
 - finish vertex

Proper unit tests are still missing, but will be added as a next step.

Thomas

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org


Mime
View raw message