Hi Steve,<div><br></div><div>Thank you for sharing your ideas! </div><div>I think that your proposal of a modular approach is very similar to what Anton and I had discussed already in the past and what we would like to have, too. Though it's difficult to estimate how much effort and work would be required to achieve some usable result. It would probably be too much for a GSoC project.</div>
<div>Honestly I couldn't tell right now how to get started best. I'm concerned to start something and get stuck in the middle without some usable result. It's probably hard to work on such a change without someone volunteer or without some funding. </div>
<div><meta charset="utf-8">It's difficult to keep an open source project active, and I would like to know for example if Ashraf is still engaged in the opengraphrouter project. Is he?</div><div><br></div><div>Daniel</div>
<div><br></div><div><br></div><div><br><br><div class="gmail_quote">2011/3/3 Stephen Woodbridge <span dir="ltr"><<a href="mailto:woodbri@swoodbridge.com">woodbri@swoodbridge.com</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
Daniel and PSC,<br>
<br>
So the opengraphrouter project that I started and was home to a couple of Google Summer of Code projects has stalled out. But the concept of building a library that could be used standalone or integrated in pgRouting or maybe some other databases or projects still has appeal if not downright desirability.<br>
<br>
I'm wonder is this might not be a good place to implement the CH code. I would be all for moving the project management and ownership under the pgRouting PSC.<br>
<br>
I think this would give us more opportunity to be more inclusive of other projects and to get other developers to contribute to a common, multi-use routing project. Then pgRouting would just work on wrapping the libraries and embedding them in postgresql.<br>
<br>
We would need to discuss how to modularize the components for reuse, but just off the top of my head I'm thinking something like:<br>
<br>
o routing engine solvers<br>
- dijkstra solution<br>
- A* solver<br>
- shooting star solver<br>
- CH solver<br>
- etc<br>
o specific data readers<br>
- shapefile reader (simple generic, vendor specific, ie Navteq)<br>
- OSM data reader<br>
- SQL table data loaders<br>
- etc<br>
o data storage managers<br>
- PostGIS<br>
- SpatialLite<br>
- SQLite<br>
- Our data file<br>
- etc<br>
o solution post processors<br>
- drivetime contours<br>
- TSP<br>
- Driving Directions<br>
- etc<br>
<br>
Anyway, this needs some thought, but you get the idea. Each of these could be a library with an API that make is easy to mix and match the components.<br>
<br>
I would be interested in your thoughts on this.<br>
<br>
Best regards,<br>
-Steve<br><div class="im">
<br>
On 2/18/2011 8:57 PM, Daniel Kastl wrote:<br>
</div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">
I may have written this already, but in case I didn't do yet:<br>
OpenTripPlanner also seems to have an implementation of CH:<br>
<a href="http://opentripplanner.org/browser/trunk/opentripplanner-routing/src/main/java/org/opentripplanner/routing/contraction" target="_blank">http://opentripplanner.org/browser/trunk/opentripplanner-routing/src/main/java/org/opentripplanner/routing/contraction</a><br>
<br>
Though their license is LGPL. How does this work?<br>
Because it's their own implementation?<br>
<a href="http://opentripplanner.org/browser/trunk/opentripplanner-routing/src/main/java/org/opentripplanner/routing/contraction/ContractionHierarchy.java#L66" target="_blank">http://opentripplanner.org/browser/trunk/opentripplanner-routing/src/main/java/org/opentripplanner/routing/contraction/ContractionHierarchy.java#L66</a><br>
<br>
Daniel<br>
<br>
<<a href="http://opentripplanner.org/browser/trunk/opentripplanner-routing/src/main/java/org/opentripplanner/routing/contraction" target="_blank">http://opentripplanner.org/browser/trunk/opentripplanner-routing/src/main/java/org/opentripplanner/routing/contraction</a>><br>
<br>
2011/2/19 Daniel Kastl <<a href="mailto:daniel@georepublic.de" target="_blank">daniel@georepublic.de</a><br></div>
<mailto:<a href="mailto:daniel@georepublic.de" target="_blank">daniel@georepublic.de</a>>><div><div></div><div class="h5"><br>
<br>
Hi Jay and Steve,<br>
<br>
This email is getting very long, so I will shorten it a bit.<br>
<br>
<br>
<br>
* <a href="http://routingdemo.geofabrik.de/" target="_blank">http://routingdemo.geofabrik.de/</a><br>
* <a href="http://sourceforge.net/projects/routed/" target="_blank">http://sourceforge.net/projects/routed/</a><br>
<br>
It uses contraction hierarchies algorithm.<br>
<br>
<br>
<br>
Thanks for the links. Are you certain that the above project<br>
uses<br>
contraction hierarchies algorithm by Robert Geisberger? I<br>
went thru the<br>
source, and they are using contraction, but I did not see<br>
where they<br>
have used the node ordering step as proposed in the CH<br>
paper. I did not<br>
find contraction hierarchies mentioned in their readme too:<br>
<a href="http://sourceforge.net/apps/trac/routed/wiki/ReadMe" target="_blank">http://sourceforge.net/apps/trac/routed/wiki/ReadMe</a><br>
<br>
<br>
It is possible that they read the paper and made their own<br>
implementation to avoid the AGPL license. The paper is describes<br>
the algorithms in great detail, so I'm sure this is possible.<br>
<br>
<br>
The notice I read through Twitter:<br>
<a href="http://twitter.com/#!/geofabrik/status/38579590834159616" target="_blank">http://twitter.com/#!/geofabrik/status/38579590834159616</a><br>
According to this is uses CH. And the license is AGPL as well.<br>
<br>
<br>
If we are using the code already made available thru<br>
AGPL (I dont<br>
understand the intricacies of different licences) by Robert<br>
<br>
<br>
I think we need to read and understand the AGPL license and how<br>
it might impact on the current license. These are tricky issues<br>
and it might prohibit us from including their code directly.<br>
<br>
If we wanted to do that we could still use the AGPL code to<br>
build test model that would allow us to validate the our code<br>
was getting reasonable results.<br>
<br>
<br>
As far as I understand AGPL is more strict than GPL in terms of<br>
services delivered with this software. So if you offer a routing<br>
service with this software, you need to also give access to the<br>
source code to the users of this service (GPL licensed software only<br>
cares about the software you pass to someone).<br>
This is probably something that not every pgRouting user would be<br>
happy with.<br>
<br>
Daniel<br>
<br>
<br>
--<br>
Georepublic UG & Georepublic Japan<br></div></div>
eMail: <a href="mailto:daniel.kastl@georepublic.de" target="_blank">daniel.kastl@georepublic.de</a> <mailto:<a href="mailto:daniel.kastl@georepublic.de" target="_blank">daniel.kastl@georepublic.de</a>><br>
Web: <a href="http://georepublic.de" target="_blank">http://georepublic.de</a> <<a href="http://georepublic.de/" target="_blank">http://georepublic.de/</a>><br>
<br>
<br>
<br>
<br>
--<br>
Georepublic UG & Georepublic Japan<div class="im"><br>
eMail: <a href="mailto:daniel.kastl@georepublic.de" target="_blank">daniel.kastl@georepublic.de</a> <mailto:<a href="mailto:daniel.kastl@georepublic.de" target="_blank">daniel.kastl@georepublic.de</a>><br>
Web: <a href="http://georepublic.de" target="_blank">http://georepublic.de</a> <<a href="http://georepublic.de/" target="_blank">http://georepublic.de/</a>><br>
<br>
<br>
<br>
_______________________________________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
</div><div class="im"><a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-dev</a><br>
</div></blockquote><div><div></div><div class="h5">
<br>
_______________________________________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-dev</a><br>
</div></div></blockquote></div><br><br clear="all"><br>-- <br><span style="font-family:arial, sans-serif;font-size:13px;border-collapse:collapse">Georepublic UG & Georepublic Japan<br>eMail: <a href="mailto:daniel.kastl@georepublic.de" style="color:rgb(66, 99, 171)" target="_blank">daniel.kastl@georepublic.de</a><br>
Web: <a href="http://georepublic.de/" style="color:rgb(66, 99, 171)" target="_blank">http://georepublic.de</a></span><br>
</div>