Hi,
Added an extra check to prevent
discovering multiple edges that lead to the same (already visited) vertex.
cool stuff, thanks for turning human words into computer words :)
I spent a couple minutes running the tests on max-flow algos with
breakpoints and stuff, and apparently they keep av
terrific, indeed!!!
very well done!
-Simo
http://people.apache.org/~simonetripodi/
http://simonetripodi.livejournal.com/
http://twitter.com/simonetripodi
http://www.99soft.org/
On Thu, Mar 1, 2012 at 7:38 PM, Marco Speranza wrote:
> Ok great! now works
> thanks you!
>
> --
> Marco Speranza
>
Ok great! now works
thanks you!
--
Marco Speranza
Google Code: http://code.google.com/u/marco.speranza79/
Il giorno 01/mar/2012, alle ore 19:32, Thomas Neidhart ha scritto:
> On 03/01/2012 07:06 PM, Marco Speranza wrote:
>> Hi Thomas,
>>
>> I run the test and it seems that the BSF explore twi
On 03/01/2012 07:06 PM, Marco Speranza wrote:
> Hi Thomas,
>
> I run the test and it seems that the BSF explore twice the same edge.
>
>
>
> Tests run: 3, Failures: 0, Errors: 1, Skipped: 0, Time elapsed: 0.025 sec <<<
> FAILURE!
>
> Results :
>
> Tests in error:
> verifyBreadthFirst
Hi Thomas,
I run the test and it seems that the BSF explore twice the same edge.
Tests run: 3, Failures: 0, Errors: 1, Skipped: 0, Time elapsed: 0.025 sec <<<
FAILURE!
Results :
Tests in error:
verifyBreadthFirstSearch(org.apache.commons.graph.visit.VisitTestCase): Edge
x <-> y() is
On 03/01/2012 09:10 AM, Simone Tripodi wrote:
> Hi +,
>
> I can report the same test failure:
>
> Failed tests:
> findMaxFlowAndVerify(org.apache.commons.graph.flow.EdmondsKarpTestCase):
> expected:<3> but was:<5>
>
> I just applied trivial modifications without altering the algorithms
> behavio
> But I would like to discuss the visitor behavior in general, as I was
> working on a SCC algorithm (Kosaraju), and found it quite difficult to
> implement the recursive traversal using the visitor.
yep, yesterday night I was trying to implementing Kosaraju algo and I found the
same difficulties
Hi +,
I can report the same test failure:
Failed tests:
findMaxFlowAndVerify(org.apache.commons.graph.flow.EdmondsKarpTestCase):
expected:<3> but was:<5>
I just applied trivial modifications without altering the algorithms
behavior, I am sure the fix is under our eyes :)
Thanks all, have a nice
On Thu, Mar 1, 2012 at 8:34 AM, Marco Speranza wrote:
>
> > In the old BFS implementation, the discoverEdge method in the visitor
> > was even called for nodes that have been already visited, which is not
> > the case anymore. From my understanding the new behavior is correct, or
> > am I missing
> In the old BFS implementation, the discoverEdge method in the visitor
> was even called for nodes that have been already visited, which is not
> the case anymore. From my understanding the new behavior is correct, or
> am I missing something?
I don't think so. in the old algo there was a check
On 02/29/2012 11:07 PM, Marco Speranza wrote:
> Cool good job...
>
> Only one think.. I ran the tests and I experienced one failure:
>
>
> Results :
>
> Failed tests:
> findMaxFlowAndVerify(org.apache.commons.graph.flow.EdmondsKarpTestCase):
> expected:<3> but was:<5>
>
> Tests run: 1
Cool good job...
Only one think.. I ran the tests and I experienced one failure:
Results :
Failed tests:
findMaxFlowAndVerify(org.apache.commons.graph.flow.EdmondsKarpTestCase):
expected:<3> but was:<5>
Tests run: 109, Failures: 1, Errors: 0, Skipped: 1
[INFO] ---
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
+1 to Claudio!
http://people.apache.org/~simonetripodi/
http://simonetripodi.livejournal.com/
http://twitter.com/simonetripodi
http://www.99soft.org/
On Mon, Feb 27, 2012 at 7:35 PM, Claudio Squarcella
wrote:
> Hello,
>
>
>>> the method "discoveryEdge" currently tells whether or not the algori
Hello,
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 --
Hi,
[...] 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).
+1.
So far the algorithm has no control over that, as it simply scans an
"Iterator" of adjacent vertices.
--
C
Hi Claudio
> 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
If you really want to search all edges, why not just make the dual fast to
create and do a DFS on vertices of the dual?
On Sun, Feb 26, 2012 at 11:47 PM, James Carman
wrote:
> On Sun, Feb 26, 2012 at 5:41 PM, Claudio Squarcella
> wrote:
> > the method "discoveryEdge" currently tells whether or n
On domingo, 26 de febrero de 2012 at 9:03 PM, Simone Tripodi wrote:>
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
wa
> 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 st
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 sho
Hi,
Simo you are right, the vertices have visited in the right way, but the edge
handler has called in the wrong way. IMHO we have to modify the code in order
to fire the edge handler in the right way to avoid any error for the user.
the method "discoveryEdge" currently tells whether or not
That would be a smart improvement James, feel free to assign that task
to yourself if you want to participate!
TIA!
-Simo
http://people.apache.org/~simonetripodi/
http://simonetripodi.livejournal.com/
http://twitter.com/simonetripodi
http://www.99soft.org/
On Sun, Feb 26, 2012 at 10:11 PM, Jame
You can just use LinkedList for both implementations (if you want to
avoid a commons-collections dependency). You'd just have a "wrapper"
around it that adds to the tail and removes from either the head or
the tail depending upon the desired behavior (stack removes from the
tail while queue remove
Hola!
> It's a good idea, Now we have implemented two separate methods that visit the
> graph for dfs and bfs. We should do a little refactoring and implement a
> unique method that switches between dfs and bfs simply changing the the type
> of visitedVertex. WDYT?
it would be nice indeed, but
Hi all
> IIRC the vertex order should be guarded by the vertexStack - maybe it
> is just the handler be called in the wrong way
Simo you are right, the vertices have visited in the right way, but the edge
handler has called in the wrong way. IMHO we have to modify the code in order
to fire the
Hi,
On 25/02/2012 19:51, James Carman wrote:
The code shouldn't "visit" each of the connected nodes during the
iteration. It should only visit the "popped" node and then add all
un-visited, connected nodes to the stack. Hopefully we've implemented
this so that all we have to do to switch from
The code shouldn't "visit" each of the connected nodes during the
iteration. It should only visit the "popped" node and then add all
un-visited, connected nodes to the stack. Hopefully we've implemented
this so that all we have to do to switch from dfs to bfs is to swap
out the collection used.
Hi Marco,
IIRC the vertex order should be guarded by the vertexStack - maybe it
is just the handler be called in the wrong way.
Do you have/can you provide please testcases?
TIA,
-SImo
http://people.apache.org/~simonetripodi/
http://simonetripodi.livejournal.com/
http://twitter.com/simonetripod
Hi all. I've a little doubt on DFS algorithm implemented in the
DefaultVisitAlgorithmsSelector.
I think that the visit doesn't serch in depth but in a breadth way.
here is a little code snippet:
[ ... ]
while ( visitingGraph && !vertexStack.isEmpty() )
{
V v = vertexStack.
30 matches
Mail list logo
