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-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org
