commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Thomas Neidhart <>
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 :)


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

 - a unified graph search method using a wrapper class as James
 - 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.


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

View raw message