[SANDBOX] Adding one more shortest path algo toGraph?

[Rodion Efremov <ro...@cs.helsinki.fi>]

Hello all!

I am interested to contribute to Sandbox's Graph library with an 
implementation of bidirectional Dijkstra's algorithm.

At this point, these are ready:
- the algo itself as applying*() construct in the 
DefaultShortestPathAlgorithmSelector.java,
- unit tests; so far so good,
- performance benchmark; shows a dramatic improvement in performance 
compared to applyingDijkstra().

A word on bidirectional Dijkstra's algorithm:
   Grows simultaneously two search balls A and B around source and 
target vertices, respectively.
   Ball A grows along the edges, B in reversed direction, i.e. along 
reversed edges.
   Initialize M as infinite cost path.
   Each time A and B "meet" in a touch node T, find whether the path P 
through T improves M, set M <- P if it does.
   Terminate when OPEN_A.top().gScore + OPEN_B.top().gScore >= cost(M).
   ---
   Geometric argument: Assume that a shortest path exists and consists 
of R edges; now, unidirectional Dijkstra does approximately V = 4 * Pii 
* R^3 / 3 amount of work, whereas the bidirectional variant does only 2 
* (4 * Pii * (R / 2)^3 / 3) = Pii * R^3 / 3 = V / 4 amount of work.

The reason I contact you is that I wanted to make sure that I 
understand the process. (Bare with me, as this is the very first time I 
contact ANY open-source community.) Now, is the following procedure 
acceptable?

1. Create an issue I in JIRA with type 'New feature'
2. Clean my working dir with 'mvn clean' to get rid of everything 
irrelevant
3. Create the patch with 'svn diff > my.patch'
4. Attach my.patch to I
5. Wait for any response R from the community
6. If R is of type 'something is unfunky'
7.     Improve local repo
8.     Go to step 2
9. Celebrate

Thanks in advance!

-rodde

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

Re: [SANDBOX] Adding one more shortest path algo to Graph?

[Ted Dunning <te...@gmail.com>]

On Tue, May 14, 2013 at 8:55 AM, Rodion Efremov <
rodion.efremov@cs.helsinki.fi> wrote:

> The reason I contact you is that I wanted to make sure that I understand
> the process. (Bare with me, as this is the very first time I contact ANY
> open-source community.) Now, is the following procedure acceptable?
>
> 1. Create an issue I in JIRA with type 'New feature'
> 2. Clean my working dir with 'mvn clean' to get rid of everything
> irrelevant
> 3. Create the patch with 'svn diff > my.patch'
> 4. Attach my.patch to I
> 5. Wait for any response R from the community
> 6. If R is of type 'something is unfunky'
> 7.     Improve local repo
> 8.     Go to step 2
> 9. Celebrate
>

Yes.  This is a fine procedure to follow.  You might be able to economize
some steps regarding the patch creation, but the flavor is correct.

Also, the polarity of the of 6 might be reversed.  I am sure you have it
right in your head.