[Neo4j] TransportDublin Route Planner Github Project

Paddy paddyfitz at gmail.com
Fri Aug 27 19:57:45 CEST 2010


Yep sounds like a better way to go instead of running a big Dijkstra. Maybe
an all Paths algorithm?
would monday be good to skype? I'm working on getting the site live,
I have configured nginx to redirect from port 80 to jetty on port 8080
I asked a question on Stack Overflow about the problem i'm having with
Jetty,
http://stackoverflow.com/questions/3509675/problems-with-jetty-crashing-intermittently
.

I started jetty using : java -Xmx900m -server -jar start.jar > stdout.txt 2>
stderr.txt

After running for 30 minutes the Jetty server will shutdown,
it is not processing any requests, I can see in the In the stderr.txt log
that the Shutdown hook is being executed somehow  :

2010-08-27 07:02:01.310:INFO::Shutdown hook executing
2010-08-27 07:02:01.310:INFO::Graceful shutdown
SelectChannelConnector at 0.0.0.0:8080
2010-08-27 07:02:12.156:INFO::Graceful shutdown
org.mortbay.jetty.webapp.WebAppContext at 1d64c37
{/test-jndi,/opt/jetty-6.1.24/contexts/test-jndi.d}
2010-08-27 07:02:12.156:INFO::Graceful shutdown
org.mortbay.jetty.webapp.WebAppContext at 90cb03
{/,file:/opt/jetty-6.1.24/webapps/transportdublin/}
2010-08-27 07:02:12.156:INFO::Graceful shutdown
org.mortbay.jetty.webapp.WebAppContext at d81784
{/,/opt/jetty-6.1.24/webapps/test}
2010-08-27 07:02:12.156:INFO::Graceful shutdown
org.mortbay.jetty.handler.ContextHandler at 1175422
{/javadoc,file:/opt/jetty-6.1.24/javadoc/}
2010-08-27 07:02:12.156:INFO::Graceful shutdown
org.mortbay.jetty.webapp.WebAppContext at fde7ba
{/test-jaas,file:/opt/jetty-6.1.24/webapps/test-jaas/}
2010-08-27 07:02:12.156:INFO::Graceful shutdown
org.mortbay.jetty.webapp.WebAppContext at 178743b
{/cometd,file:/opt/jetty-6.1.24/webapps/cometd/}
2010-08-27 07:02:13.163:INFO::Stopped SelectChannelConnector at 0.0.0.0:8080
2010-08-27
07:02:13.166:INFO:/:org.tuckey.web.filters.urlrewrite.UrlRewriteFilter INFO:
destroy called
2010-08-27 07:02:13.166:INFO:/:Destroying Spring FrameworkServlet 'Spring
MVC Dispatcher Servlet'
2010-08-27 07:02:13.232:INFO::Shutdown hook complete


I have installed http://wiki.eclipse.org/Jetty/Feature/Java-monitor which is
useful, when starting jetty using
java -Dcom.sun.management.jmxremote -jar start.jar etc/jetty-jmx.xml
etc/jetty.xml > stdout.txt 2> stderr.txt
I can monitor the jetty server on their control panel
http://java-monitor.com
 Would it be better to directly access Jconsole remotely? Or can i access
any java logs to investigate further?

Thanks
Paddy




On Thu, Aug 26, 2010 at 8:41 AM, Peter Neubauer <
peter.neubauer at neotechnology.com> wrote:

> Very cool Paddy!
> I have been talking to Craig about this - we are thinking that, with
> knowing a lot of information about your bus stops, there should be a
> lot of possibilities to make the graph smarter than running a big
> Dijkstra over everything. It might be worth to explore if you can
> narrow down the number of possible routes somewhat before doing the
> exhaustive traversals. Not sure on the details but maybe we could have
> a Skype call on that next week?
>
> Cheers,
>
> /peter neubauer
>
> COO and Sales, Neo Technology
>
> GTalk:      neubauer.peter
> Skype       peter.neubauer
> Phone       +46 704 106975
> LinkedIn   http://www.linkedin.com/in/neubauer
> Twitter      http://twitter.com/peterneubauer
>
> http://www.neo4j.org               - Your high performance graph database.
> http://www.thoughtmade.com - Scandinavia's coolest Bring-a-Thing party.
>
>
>
> On Thu, Aug 26, 2010 at 9:59 AM, Paddy <paddyfitz at gmail.com> wrote:
> > To run the Dijkstra algorithm multiple times, I'm assuming it would it be
> > best to use a high CPU ec2 instance?
> >
> > I have been checking Amazon and in US East i can run a Cluster Compute
> > which is a Quadruple Extra Large ec2 instance
> > 33.5 EC2 Compute Units (2 x Intel Xeon X5570, quad-core Nehalem
> > architecture)
> > 23 GB memory,
> > 1690 GB of instance storage
> > 64-bit platform
> > I/O Performance: Very High (10 Gigabit Ethernet)
> > API name: cc1.4xlarge
> >
> > Not bad for $1.60 per hour! Would I need to run the Dijkstra algorithm in
> a
> > multi threaded app?
> > Any help would be great
> >
> > It runs on CentOS:
> > Basic Cluster Instances HVM CentOS 5.4 (AMI Id: ami-7ea24a17)
> > Minimal CentOS 5.4, 64-bit architecture, and HVM-based virtualization for
> > use with Amazon EC2 Cluster Instances.
> >
> >
> > More info here:
> >
> http://www.allthingsdistributed.com/2010/07/cluster_compute_instance_amazon_ec2.html
> >
> >
> > Cheers
> > Paddy
> >
> >
> > On Wed, Aug 25, 2010 at 3:44 AM, Paddy <paddyfitz at gmail.com> wrote:
> >
> >> Hi Mike,
> >> I cced you to the neo4j list, I enjoyed the talk you gave at the nosql
> >> summer Vancouver about running CouchDb in the cloud at www.Coudant.com.
> >> More info about couchdb: https://nosqleast.com/2009/#speaker/<
> https://nosqleast.com/2009/#speaker/miller>
> >> miller <https://nosqleast.com/2009/#speaker/miller>
> >> Hope you can make it back on the 24th of Sept for the talk on neo4j
> >> Any more insight into what I would need to do to run a script to launch
> >> multiple instances would be great.
> >>
> >> Here is my github http://github.com/paddydub/TransportDublin and
> twitter
> >> :) http://twitter.com/TransportDublin
> >>
> >> Should i use cloudera, Hadoop? I don't have much experience with
> >> distributed computing.
> >> What sort of software would i need to use in Amazon?
> >>
> >> Any help would be great! I think it could be used on road networks and
> >> extended to the http://www.openstreetmap.org/ API.
> >> what do u think? :)
> >>
> >> I uploaded a prepopulated sample Dublin Bus time dependent network
> modelled
> >> in a Neo4j database with 1 million
> >>  nodes and 10 million relationships in a Weighted Graph
> >> http://github.com/downloads/paddydub/TransportDublin/neo4j-db.zip
> >>
> >> Also a Json File containing the Stop Information which is used to
> populate
> >> the database with spatial data.
> >> http://github.com/downloads/paddydub/TransportDublin/stops.json
> >>
> >> I will upload the code to github that would be needed to run the
> Dijkstra
> >> algorithm 13,5000  million times on the neo4j database and
> >> to cache the results to store neo4j database as a WeightedGraph Path
> object
> >> and path weight as the cost in minutes.
> >> Possibly with multiple ec2 instances running the Dijkstra algorithm for
> >> different stop departure combinations,
> >>  all writing to a linked EBS, Not sure if this is possible.
> >> http://wiki.neo4j.org/content/Neo4j_in_the_Cloud
> >> Or storing the results to a json file to be inserted using the neo4j
> >> BatchInserteter.
> >> http://wiki.neo4j.org/content/Batch_Insert
> >>
> >> I posted the question below to the neo4j mailing list, what do you
> think?
> >> Can it be done? :)
> >>
> >> Also the http://algo2.iti.kit.edu/routeplanning.php might be of
> interest.
> >> and Fast Route Planning with Peter Sanders:
> >> http://www.youtube.com/watch?v=-0ErpE8tQbw
> >>
> >> If we do not know the end arrival time we can pick all nodes that have
> >> bus's arriving at that stop in the next 3-4 hours.
> >> Then create a link to a new Stop Time temporary end node, which is used
> as
> >> the end node in the Dijkstra algorithm.
> >> To be really accurate there would need to be 15000*15000*60*24 start
> nodes
> >> or what would be the best way to approach this???
> >>
> >> I posted the question below to the neo4j mailing list, what do you
> think?
> >> Can it be done? :)
> >>
> >> If we do not know the end arrival time we can pick all nodes that have
> >> bus's arriving at that stop in the next 3-4 hours.
> >> Then create a link to a newly created node in the neo4j database and use
> >> this temporary node as the end node in the Dijsktra algorithm.
> >>
> >> .....
> >> for (Map.Entry<String, Double> neighbour : neighboursMap.entrySet()) {
> >> String neighbourStopID = neighbour.getKey();
> >>  // Lucene Query: 1100010000109* represents 09* a LuceneFulltextQuery to
> >> find all stoptimes connected with an hour value of "09"
> >> String query = 1 + neighbourStopID + "09*";
> >>
> >> for (Node hit : indexService.getNodes(StopTime.STOPTIMEID,query)) {
> >> StopTime neighbourStopTime = new StopTime(hit);
> >>
> >>
> >>
> >>
> >> ..............First Draft
> >>
> >> import ie.transportdublin.datastructure.json.Data;
> >> import ie.transportdublin.datastructure.json.Data.Stop;
> >> import ie.transportdublin.datastructure.neo4j.RelationshipTypes;
> >> import ie.transportdublin.datastructure.neo4j.StopTime;
> >> import ie.transportdublin.datastructure.neo4j.Waypoint;
> >> import ie.transportdublin.mvc.ajax.pathfinder.SetupGraph;
> >> import ie.transportdublin.mvc.ajax.routeplanner.RoutePlanner;
> >>
> >> import java.io.FileReader;
> >> import java.util.List;
> >> import java.util.Map;
> >>
> >> import org.joda.time.DateTime;
> >> import org.neo4j.graphalgo.CommonEvaluators;
> >> import org.neo4j.graphalgo.CostEvaluator;
> >> import org.neo4j.graphalgo.EstimateEvaluator;
> >> import org.neo4j.graphalgo.GraphAlgoFactory;
> >> import org.neo4j.graphalgo.PathFinder;
> >> import org.neo4j.graphalgo.WeightedPath;
> >> import org.neo4j.graphdb.Direction;
> >> import org.neo4j.graphdb.Expander;
> >> import org.neo4j.graphdb.GraphDatabaseService;
> >> import org.neo4j.graphdb.Transaction;
> >> import org.neo4j.index.IndexService;
> >> import org.neo4j.kernel.EmbeddedGraphDatabase;
> >> import org.neo4j.kernel.Traversal;
> >>
> >> import com.google.gson.Gson;
> >>
> >>
> >> public class DijkstraTest {
> >>
> >> private static GraphDatabaseService graphDbService;
> >> private IndexService indexService;
> >>
> >>     public static void main(String... args) throws Exception {
> >>
> >>      CostEvaluator<Double> costEval = CommonEvaluators
> >>  .doubleCostEvaluator(Waypoint.COST);
> >>
> >>
> >>      Map<String,String> configuration =
> >> EmbeddedGraphDatabase.loadConfigurations( "neo4j_config.props" );
> >>      graphDbService = new EmbeddedGraphDatabase( "my-neo4j-db/",
> >> configuration );
> >>
> >>         // Now do the magic.
> >>         Data data = new Gson().fromJson(new FileReader("/stops.json"),
> >> Data.class);
> >>         List<Stop> stopsList1 =  data.getStops();
> >>         List<Stop> stopsList2 =  stopsList1;
> >> long startTimer = System.currentTimeMillis();
> >>         for(Stop stop :stopsList1)
> >>         {
> >>             // Show it.
> >>
> >>          System.out.println(stop);
> >>          String stopId =  stop.getStopId();
> >>   Expander relExpander = Traversal.expanderForTypes(
> >>   RelationshipTypes.BUS, Direction.OUTGOING);
> >>   PathFinder<WeightedPath> dijkstra =
> >> GraphAlgoFactory.dijkstra(relExpander,
> >>   costEval);
> >>
> >>
> >> /*  The dataset uses 15000 dublin bus stops nodes which are
> >>    stored in a json file. To find all routes at 9.00am on a
> >>    monday for every stop, the Dijkstra algorithm would have
> >>    to be run 15000 x 15000 = 225 million times.
> >>   To find all routes for all times it would need to be run
> >>   for every 1 minute period in a day, it would have to be run
> >>   13,500 million times.
> >>   e.g 225 million x 60 x 24 = 13,500 million
> >>  */
> >>   final int count =  15000*15000*60*24;
> >>   WeightedPath path;
> >>   double weight;
> >>
> >>   while(--count!=0)
> >>   {
> >>   path = dijkstra.findSinglePath(
> >>   start.getUnderlyingNode(),
> >>   end.getUnderlyingNode());
> >>   weight = path.weight();
> >>   }
> >>
> >>
> >>
> >>
> >> long endTimer = System.currentTimeMillis();
> >>  System.out.println("Dijkstra Time:: " + (endTimer - startTimer)
> >> + " milliseconds");
> >>
> >>
> >>
> >>         }
> >>     }
> >>
> >>
> >> WDYT? I would appreciate any help!
> >>
> >> Cheers,
> >> Paddy
> >>
> >> On Tue, Aug 24, 2010 at 12:14 AM, Peter Neubauer <
> >> peter.neubauer at neotechnology.com> wrote:
> >>
> >>> Interesting stuff Paddy!
> >>>
> >>> I would love to explore the combination of precomputed routes and
> >>> Neo4j Spatial to do these calculations! Feel free to keep us updated
> >>> on this, maybe some of the work can be incorporated into Neo4j Spatial
> >>> at some time?
> >>>
> >>> Cheers,
> >>>
> >>> /peter neubauer
> >>>
> >>> COO and Sales, Neo Technology
> >>>
> >>> GTalk:      neubauer.peter
> >>> Skype       peter.neubauer
> >>> Phone       +46 704 106975
> >>> LinkedIn   http://www.linkedin.com/in/neubauer
> >>> Twitter      http://twitter.com/peterneubauer
> >>>
> >>> http://www.neo4j.org               - Your high performance graph
> >>> database.
> >>> http://www.thoughtmade.com - Scandinavia's coolest Bring-a-Thing
> party.
> >>>
> >>>
> >>>
> >>> On Tue, Aug 24, 2010 at 12:15 AM, Paddy <paddyfitz at gmail.com> wrote:
> >>> > Hi,
> >>> > I think a better approach might be to take advantage of Hadoop
> MapReduce
> >>> to
> >>> > precompute all routes by running the Dijkstra algorithm
> >>> > to find the best route for every possible combination.
> >>> >
> >>> > E.g the dataset uses 15000 bus stops nodes
> >>> > To find all routes at 9.00am on a monday for every stop, the Dijkstra
> >>> > algorithm would have to be run 15000 x 15000 = 225 million times.
> >>> > To find all routes for all times it would need to be run for every 1
> >>> minute
> >>> > period in a day, it would have to be run 13,500 million times.
> >>> >  e.g 225 million x 60 x 24 = 13,500 million
> >>> > Each precomputed route would be stored in the neo4j database, with
> the
> >>> total
> >>> > route time and the path also stored in the database
> >>> >  as a Weighted Path of Bus stops and connections times
> >>> >
> >>> > If the best route from Stop 100 to Stop 342 is to take a bus that
> leaves
> >>> > stop 100 at 9.05 and takes 45 minutes to reach Stop 342,
> >>> > the database will be arranged as below to factor in waiting times:
> >>> >
> >>> >
> >>> >  the shortest route from stop 100 to stop 342 at 9.00am takes 50
> >>> Minutes,
> >>> > Path = Stop 100 --(15mins)--> Stop 55 --(15mins)--> Stop 4543
> >>> --(15mins)->
> >>> > Stop 342
> >>> >  the shortest route from stop 100 to stop 342 at 9.01am takes 49
> >>> Minutes,
> >>> > Path = Stop 100 --(15mins)--> Stop 55 --(15mins)--> Stop 4543
> >>> --(15mins)->
> >>> > Stop 342
> >>> >  the shortest route from stop 100 to stop 342 at 9.02am takes 48
> >>> Minutes,
> >>> >  Path = Stop 100 --(15mins)--> Stop 55 --(15mins)--> Stop 4543
> >>> --(15mins)->
> >>> > Stop 342
> >>> >  the shortest route from stop 100 to stop 342 at 9.03am takes 47
> >>> Minutes,
> >>> >  Path = Stop 100 --(15mins)--> Stop 55 --(15mins)--> Stop 4543
> >>> --(15mins)->
> >>> > Stop 342
> >>> >  the shortest route from stop 100 to stop 342 at 9.04am takes 46
> >>> Minutes,
> >>> > Path = Stop 100 --(15mins)--> Stop 55 --(15mins)--> Stop 4543
> >>> --(15mins)->
> >>> > Stop 342
> >>> >  the shortest route from stop 100 to stop 342 at 9.05am takes 45
> >>> Minutes,
> >>> >  Path = Stop 100 --(15mins)--> Stop 55 --(15mins)--> Stop 4543
> >>> --(15mins)->
> >>> > Stop 342
> >>> >
> >>> >
> >>> >  The routing information for each 13,5000 million possible
> connections
> >>> would
> >>> > be stored in the database.
> >>> >
> >>> > -Route Finding
> >>> >
> >>> > -Use neo4j spatial to find all stops within walking distance of the
> >>> start
> >>> > and end coordinate
> >>> > calculate the walking time to each stop in minutes
> >>> > -Using the precalculated routing information and factoring in the
> time
> >>> to it
> >>> > takes to walk to a nearby stop,
> >>> > -This would allow the best route possible route to be found with 2
> neo4j
> >>> > spatial querys
> >>> > and a quick calculation to find the shortest route from every
> possible
> >>> route
> >>> > combination from nearby stops.
> >>> >
> >>> > i.e.
> >>> > calculate walking time to stop 100 using neo4j spatial at runtime = 2
> >>> > minutes.
> >>> >
> >>> > If the departure time is 9.00  and it takes 2 minutes to walk to stop
> >>> 100,
> >>> > it means querying the precomputed routes
> >>> >  database for the already discovered quickest route
> >>> > route from stop 100 to stop 342 at 9.02 which we know takes 48
> minutes
> >>> > +
> >>> > calculate walking time from stop 342 to the end coordinate using
> neo4j
> >>> > spatial at runtime = 4 minutes
> >>> > =
> >>> > Total time for this route is 54 minutes
> >>> >
> >>> > This should be repeated for all combinations of bus stops that are
> >>> within
> >>> > walking distance of the start and end coordinate.
> >>> > Use the route with the lowest total time as this will be the quickest
> >>> route
> >>> > possible .
> >>> >
> >>> > If the route found with the lowest total time is from stop 100 to
> stop
> >>> 342
> >>> > at 9.02
> >>> > The database would be queried to return the route from stop 100 to
> stop
> >>> 342
> >>> > at 9.02
> >>> > This will return a Weighted path object of Bus stops nodes needed to
> >>> travel
> >>> > to and connection times ,
> >>> > latitude and longitude properties of the bus stops are used to
> populate
> >>> the
> >>> > route on the Map.
> >>> > If the route uses multiple bus or train connections, the waiting
> times
> >>> for
> >>> > connections is stored in the weighted path
> >>> >
> >>> >
> >>> > I think this could be achieved somehow a using hadoop MapReduce
> setup,
> >>> maybe
> >>> > with multiple ec2 instances writing
> >>> >  to a shared ec2 ebs neo4j database
> >>> > or routing results being stored locally to a json file an then
> populated
> >>> to
> >>> > the database using the BatchInserter
> >>> > This would speed things up considerably as the A* algorightm would
> not
> >>> have
> >>> > to be run for each routing request
> >>> >  at runtime in the web app.
> >>> > Also the Dijkstra algorithm will find the best route as it is more
> >>> accurate
> >>> > than the A* algorithm.
> >>> >
> >>> > I have no idea how long it would take to run the Dijkstra algorithm
> >>> 13,5000
> >>> > million times. If say it takes on
> >>> > average 1 second to run Dijkstra, it will take 156250 Days on one
> >>> machine ,
> >>> > does anyone have an ideas or experience with Hadoop or MapReduce or
> what
> >>> > would be the best way to go about this
> >>> >  or if it is even possible. I think varations of this method could be
> >>> useful
> >>> > for many different applications of
> >>> >  route planning with Dijkstra.
> >>> >
> >>> > Also an interesting video by Google on how they represent graphs and
> on
> >>> > using MapReduce with graphs for Dijkstra  and PageRank: Parallel
> Graph
> >>> > Algorithms with MapReduce
> >>> > http://www.youtube.com/watch?v=BT-piFBP4fE
> >>> >
> >>> > Also the MapReduce paper is a good read
> >>> > http://labs.google.com/papers/mapreduce-osdi04.pdf
> >>> >
> >>> > Thanks
> >>> > Paddy
> >>> >
> >>> > On Thu, Aug 19, 2010 at 11:17 PM, Peter Neubauer
> >>> > <peter.neubauer at jayway.com>wrote:
> >>> >
> >>> >> Paddy,
> >>> >> depending on your traffic and security setup, either you can
> directly
> >>> >> expose Tomcat/Jetty/Grizzly etc on port 80, or put Apache with a
> >>> >> reverse proxy in front of it that sits on 80 and forwards to 8080 on
> >>> >> localhost or whatever port you are running internally. The advantage
> >>> >> is that in that case your Java app can run as a non-root user since
> >>> >> all ports below 1000 need superuser rights on Unix/Linux
> >>> >>
> >>> >> HTH
> >>> >>
> >>> >> Cheers,
> >>> >>
> >>> >> /peter neubauer
> >>> >>
> >>> >> COO and Sales, Neo Technology
> >>> >>
> >>> >> GTalk:      neubauer.peter
> >>> >> Skype       peter.neubauer
> >>> >> Phone       +46 704 106975
> >>> >> LinkedIn   http://www.linkedin.com/in/neubauer
> >>> >> Twitter      http://twitter.com/peterneubauer
> >>> >>
> >>> >> http://www.neo4j.org               - Your high performance graph
> >>> database.
> >>> >> http://www.thoughtmade.com - Scandinavia's coolest Bring-a-Thing
> >>> party.
> >>> >>
> >>> >>
> >>> >>
> >>> >> On Thu, Aug 19, 2010 at 8:26 AM, Paddy <paddyfitz at gmail.com> wrote:
> >>> >> > Thanks Peter, yes i will do that, it will make the map look a lot
> >>> less
> >>> >> > cluttered. I've just been having some problems keeping it live, I
> >>> have
> >>> >> been
> >>> >> > changing around my runtime settings. I'm running it on a debian ec
> 2
> >>> with
> >>> >> > 1.7 GB ram. I'm starting jetty using the command : java -server
> >>> -Xmx1000m
> >>> >> > -jar start.jar  & 180mb is memory mapped in neo4-config.props.
> Would
> >>> this
> >>> >> be
> >>> >> > the ideal settings?
> >>> >> >
> >>> >> > Also to run Jetty through port 80 is it best to use nginx?
> >>> >> > http://wiki.nginx.org/NginxJavaServers
> >>> >> > Or what method would you recommend?
> >>> >> >
> >>> >> > Thanks
> >>> >> > Paddy
> >>> >> >
> >>> >> >
> >>> >> >
> >>> >> > On Wed, Aug 18, 2010 at 2:03 AM, Peter Neubauer <
> >>> >> > peter.neubauer at neotechnology.com> wrote:
> >>> >> >
> >>> >> >> Very cool Paddy,
> >>> >> >> seems things are progressing at your end! If you could remove
> >>> previous
> >>> >> >> routes and markers when clicking on new information it would
> >>> >> >> de-clutter the UI considerably ...
> >>> >> >>
> >>> >> >> Cheers,
> >>> >> >>
> >>> >> >> /peter neubauer
> >>> >> >>
> >>> >> >> COO and Sales, Neo Technology
> >>> >> >>
> >>> >> >> GTalk:      neubauer.peter
> >>> >> >> Skype       peter.neubauer
> >>> >> >> Phone       +46 704 106975
> >>> >> >> LinkedIn   http://www.linkedin.com/in/neubauer
> >>> >> >> Twitter      http://twitter.com/peterneubauer
> >>> >> >>
> >>> >> >> http://www.neo4j.org               - Your high performance graph
> >>> >> database.
> >>> >> >> http://www.thoughtmade.com - Scandinavia's coolest Bring-a-Thing
> >>> party.
> >>> >> >>
> >>> >> >>
> >>> >> >>
> >>> >> >> On Wed, Aug 18, 2010 at 2:51 AM, Paddy <paddyfitz at gmail.com>
> wrote:
> >>> >> >> > Hi ,
> >>> >> >> > Thanks for the link he has a lot of good information, I'm not
> sure
> >>> >> which
> >>> >> >> is
> >>> >> >> > the best algorithm , he also mentions SPARC which looks like a
> >>> good
> >>> >> >> > algorithm too:
> >>> >> >> > ** <http://www.springerlink.com/index/f464667j140jx36h.pdf
> >>> >> >> >Time-Dependent
> >>> >> >> > SHARC-Routing -
> >>> >> >> i11www.iti.uni-karlsruhe.de/extra/publications/d-tdsr-09.pdf
> >>> >> >> >
> >>> >> >> > I have uploaded a test site also to:
> >>> >> >> > Bus Route Planner :
> >>> http://www.transportdublin.ie:8080/routeplanner
> >>> >> >> > Bus Route Search & Display :
> >>> >> http://www.transportdublin.ie:8080/routes
> >>> >> >> >
> >>> >> >> > The routing algorithm needs to be improved as it is not finding
> >>> the
> >>> >> >> optimal
> >>> >> >> > bus route. E.g it could use 3 bus's when 1 should be used
> instead.
> >>> >> >> > It is using a reduced size database, with a neo4j_config.props
> >>> >> configured
> >>> >> >> > for traversal and hosted on a ec2 instance which improved the
> >>> speed.
> >>> >> >> > The bottle neck for the routing is currently the A*Star
> algorithm,
> >>> I
> >>> >> >> think
> >>> >> >> > the Bidirectional A*Star or the SPARC algorigthm is the way to
> go
> >>> >> >> > Any feedback would be great, I plan to add geocoding and bus
> stop
> >>> >> search
> >>> >> >> > too.
> >>> >> >> >
> >>> >> >> > Thanks
> >>> >> >> > Paddy
> >>> >> >> >
> >>> >> >> >
> >>> >> >> > On Sun, Aug 15, 2010 at 11:30 PM, Peter Neubauer <
> >>> >> >> > peter.neubauer at neotechnology.com> wrote:
> >>> >> >> >
> >>> >> >> >> Paddy,
> >>> >> >> >> you can use the High Availability setup as they become
> available
> >>> -
> >>> >> >> >> would be happy to see how they work out for you!
> >>> >> >> >>
> >>> >> >> >> Also, the OpenGraphRouter project just did an bidirectional A*
> >>> >> >> >> implementation as part of the GSoC,
> >>> >> >> >>
> >>> >> >> >>
> >>> >> >>
> >>> >>
> >>>
> http://sourceforge.net/apps/trac/opengraphrouter/wiki/GSoC2010_report_FinalReport
> >>> >> >> >> , so that might be an interesting field to look at if you feel
> >>> like
> >>> >> >> >> doing it?
> >>> >> >> >>
> >>> >> >> >> Cheers,
> >>> >> >> >>
> >>> >> >> >> /peter neubauer
> >>> >> >> >>
> >>> >> >> >> COO and Sales, Neo Technology
> >>> >> >> >>
> >>> >> >> >> GTalk:      neubauer.peter
> >>> >> >> >> Skype       peter.neubauer
> >>> >> >> >> Phone       +46 704 106975
> >>> >> >> >> LinkedIn   http://www.linkedin.com/in/neubauer
> >>> >> >> >> Twitter      http://twitter.com/peterneubauer
> >>> >> >> >>
> >>> >> >> >> http://www.neo4j.org               - Your high performance
> graph
> >>> >> >> database.
> >>> >> >> >> http://www.thoughtmade.com - Scandinavia's coolest
> Bring-a-Thing
> >>> >> party.
> >>> >> >> >>
> >>> >> >> >>
> >>> >> >> >>
> >>> >> >> >> On Tue, Jul 27, 2010 at 11:13 PM, Paddy <paddyfitz at gmail.com>
> >>> wrote:
> >>> >> >> >> > thanks peter that looks a lot better.
> >>> >> >> >> > I'm working on a Neo4j & Ajax combination to display only
> >>> routes on
> >>> >> >> the
> >>> >> >> >> map.
> >>> >> >> >> > Ajax and Neo4j is a really powerful combination, it is
> useful
> >>> >> feature
> >>> >> >> to
> >>> >> >> >> > display the neo4j database property's,
> >>> >> >> >> > With a jQuery LiveSearch feature & Spring Mvc-Ajax combined
> >>> with
> >>> >> neo4j
> >>> >> >> >> > luceneFullTextQuery, a database can be queried on the fly.
> >>> >> >> >> >
> >>> >> >> >> > What is the best hosting and memory settings for my kind of
> >>> app? I
> >>> >> >> have
> >>> >> >> >> > tested on a amazon ec2 small instance, but it can take from
> 0.1
> >>> to
> >>> >> 10
> >>> >> >> >> > seconds to find a route depending on distance .Can I
> replicate
> >>> the
> >>> >> >> >> database
> >>> >> >> >> > to allow multiple simultanous requests?
> >>> >> >> >> >
> >>> >> >> >> >
> >>> >> >> >> > Thanks
> >>> >> >> >> > Paddy
> >>> >> >> >> >
> >>> >> >> >> >
> >>> >> >> >> > On Tue, Jul 27, 2010 at 7:02 AM, Peter Neubauer <
> >>> >> >> >> > peter.neubauer at neotechnology.com> wrote:
> >>> >> >> >> >
> >>> >> >> >> >> Paddy,
> >>> >> >> >> >> I took the freedom to format the wiki a bit and put a maven
> >>> >> profile
> >>> >> >> >> >> into the pom.xml in order to download and expand the data
> >>> >> >> >> >> automatically if you run
> >>> >> >> >> >>
> >>> >> >> >> >> mvn -P import install jetty:run
> >>> >> >> >> >>
> >>> >> >> >> >> http://github.com/peterneubauer/TransportDublin
> >>> >> >> >> >>
> >>> >> >> >> >> Is that ok? Would it be possible to do the import
> >>> automatically
> >>> >> to,
> >>> >> >> so
> >>> >> >> >> >> we could extract the timetable data live somewhere?
> >>> >> >> >> >>
> >>> >> >> >> >> Cheers,
> >>> >> >> >> >>
> >>> >> >> >> >> /peter neubauer
> >>> >> >> >> >>
> >>> >> >> >> >> COO and Sales, Neo Technology
> >>> >> >> >> >>
> >>> >> >> >> >> GTalk:      neubauer.peter
> >>> >> >> >> >> Skype       peter.neubauer
> >>> >> >> >> >> Phone       +46 704 106975
> >>> >> >> >> >> LinkedIn   http://www.linkedin.com/in/neubauer
> >>> >> >> >> >> Twitter      http://twitter.com/peterneubauer
> >>> >> >> >> >>
> >>> >> >> >> >> http://www.neo4j.org               - Your high performance
> >>> graph
> >>> >> >> >> database.
> >>> >> >> >> >> http://www.thoughtmade.com - Scandinavia's coolest
> >>> Bring-a-Thing
> >>> >> >> party.
> >>> >> >> >> >>
> >>> >> >> >> >>
> >>> >> >> >> >>
> >>> >> >> >> >> On Sun, Jul 25, 2010 at 11:02 AM, Paddy <
> paddyfitz at gmail.com>
> >>> >> wrote:
> >>> >> >> >> >> > I have added a Quick Install Guide on the wiki if anyone
> >>> would
> >>> >> like
> >>> >> >> to
> >>> >> >> >> >> try:
> >>> >> >> >> >> >
> >>> >> >> >> >> > Download source :
> >>> >> >> >> >> > 1. Download latest zip source file from:
> >>> >> >> >> >> >
> http://github.com/paddydub/TransportDublin/archives/master
> >>> >> >> >> >> > 2. Extract zip contents into C:\dev\transportdublin\
> >>> >> >> >> >> >
> >>> >> >> >> >> > Download database:
> >>> >> >> >> >> > 3. Download a prepopulated graph database from
> >>> >> >> >> >> > neo4j-db.zip<
> >>> http://www.transportdublin.ie/neo4j/neo4j-db.zip>
> >>> >> >> >> >> > 4. Extract the neo4j-db.zip file to folder:
> >>> >> >> >> C:\dev\transportdublin\data\
> >>> >> >> >> >> > 5. cd to C:\dev\transportdublin\
> >>> >> >> >> >> >
> >>> >> >> >> >> > Launch Jetty server
> >>> >> >> >> >> > 6. From the command line type: mvn jetty:run
> >>> >> >> >> >> > 7. Point your browser to location
> >>> >> >> >> >> > http://localhost:8080/transportdublin/routeplanner
> >>> >> >> >> >> > 8. Click on two locations on the map to generate a route
> >>> >> >> >> >> >
> >>> >> >> >> >> >
> >>> >> >> >> >> > Thanks
> >>> >> >> >> >> >
> >>> >> >> >> >> > Paddy
> >>> >> >> >> >> >
> >>> >> >> >> >> > On Fri, Jul 23, 2010 at 4:53 PM, Paddy <
> paddyfitz at gmail.com
> >>> >
> >>> >> >> wrote:
> >>> >> >> >> >> >
> >>> >> >> >> >> >> Hi,
> >>> >> >> >> >> >> I have updated the wiki with screen shots and
> information
> >>> >> >> >> >> >>
> >>> >> >> >> >> >>  http://wiki.github.com/paddydub/TransportDublin/
> >>> >> >> >> >> >>
> >>> >> >> >> >> >> and I have uploaded my code and bus stop data sql
> script.
> >>> >> >> >> >> >>
> >>> >> >> >> >> >> Any suggestions or recommendations would be appreciated.
> >>> I'm
> >>> >> >> >> currently
> >>> >> >> >> >> >> populating my graph from a mysql database,
> >>> >> >> >> >> >> I'm working next on implementing the BatchInserter next
> to
> >>> >> speed
> >>> >> >> up
> >>> >> >> >> the
> >>> >> >> >> >> >> graph setup process
> >>> >> >> >> >> >>
> >>> >> >> >> >> >> Thanks
> >>> >> >> >> >> >> Paddy
> >>> >> >> >> >> >>
> >>> >> >> >> >> >>
> >>> >> >> >> >> >> On Wed, Jul 21, 2010 at 3:26 PM, Anders Nawroth <
> >>> >> >> >> >> anders at neotechnology.com>wrote:
> >>> >> >> >> >> >>
> >>> >> >> >> >> >>> Hi Paddy!
> >>> >> >> >> >> >>>
> >>> >> >> >> >> >>> Some interesting stuff you're working on there!
> >>> >> >> >> >> >>>
> >>> >> >> >> >> >>> >   I'd like to  write a bit about the differences in
> >>> neo4j
> >>> >> and
> >>> >> >> sql
> >>> >> >> >> and
> >>> >> >> >> >> >>> why
> >>> >> >> >> >> >>> > neo4j it is a perfect solution for route planning
> >>> systems,
> >>> >> do
> >>> >> >> you
> >>> >> >> >> >> think
> >>> >> >> >> >> >>> a
> >>> >> >> >> >> >>> > wiki would be the best option to display the pics?
> >>> >> >> >> >> >>>
> >>> >> >> >> >> >>> I think the Github wiki of the project good be a good
> >>> place to
> >>> >> >> put
> >>> >> >> >> the
> >>> >> >> >> >> >>> article. Images can be added to the source repo (just
> >>> remember
> >>> >> to
> >>> >> >> >> use
> >>> >> >> >> >> >>> the "raw" version of the images as img src) or can be
> >>> uploaded
> >>> >> as
> >>> >> >> >> >> >>> "downloads" of the project.
> >>> >> >> >> >> >>>
> >>> >> >> >> >> >>> When your writings are in place, it should of course be
> >>> linked
> >>> >> >> from
> >>> >> >> >> the
> >>> >> >> >> >> >>> Neo4j wiki.
> >>> >> >> >> >> >>>
> >>> >> >> >> >> >>> WDYT?
> >>> >> >> >> >> >>>
> >>> >> >> >> >> >>> /anders
> >>> >> >> >> >> >>>
> >>> >> >> >> >> >>> > I will be uploading the
> >>> >> >> >> >> >>> > code today and tomorrow, just making some last minute
> >>> >> changes
> >>> >> >> and
> >>> >> >> >> >> >>> writing
> >>> >> >> >> >> >>> > some documentation.
> >>> >> >> >> >> >>> >
> >>> >> >> >> >> >>> > Cheers
> >>> >> >> >> >> >>> > Paddy
> >>> >> >> >> >> >>> > _______________________________________________
> >>> >> >> >> >> >>> > Neo4j mailing list
> >>> >> >> >> >> >>> > User at lists.neo4j.org
> >>> >> >> >> >> >>> > https://lists.neo4j.org/mailman/listinfo/user
> >>> >> >> >> >> >>> _______________________________________________
> >>> >> >> >> >> >>> Neo4j mailing list
> >>> >> >> >> >> >>> User at lists.neo4j.org
> >>> >> >> >> >> >>> https://lists.neo4j.org/mailman/listinfo/user
> >>> >> >> >> >> >>>
> >>> >> >> >> >> >>
> >>> >> >> >> >> >>
> >>> >> >> >> >> > _______________________________________________
> >>> >> >> >> >> > Neo4j mailing list
> >>> >> >> >> >> > User at lists.neo4j.org
> >>> >> >> >> >> > https://lists.neo4j.org/mailman/listinfo/user
> >>> >> >> >> >> >
> >>> >> >> >> >> _______________________________________________
> >>> >> >> >> >> Neo4j mailing list
> >>> >> >> >> >> User at lists.neo4j.org
> >>> >> >> >> >> https://lists.neo4j.org/mailman/listinfo/user
> >>> >> >> >> >>
> >>> >> >> >> > _______________________________________________
> >>> >> >> >> > Neo4j mailing list
> >>> >> >> >> > User at lists.neo4j.org
> >>> >> >> >> > https://lists.neo4j.org/mailman/listinfo/user
> >>> >> >> >> >
> >>> >> >> >> _______________________________________________
> >>> >> >> >> Neo4j mailing list
> >>> >> >> >> User at lists.neo4j.org
> >>> >> >> >> https://lists.neo4j.org/mailman/listinfo/user
> >>> >> >> >>
> >>> >> >> > _______________________________________________
> >>> >> >> > Neo4j mailing list
> >>> >> >> > User at lists.neo4j.org
> >>> >> >> > https://lists.neo4j.org/mailman/listinfo/user
> >>> >> >> >
> >>> >> >> _______________________________________________
> >>> >> >> Neo4j mailing list
> >>> >> >> User at lists.neo4j.org
> >>> >> >> https://lists.neo4j.org/mailman/listinfo/user
> >>> >> >>
> >>> >> > _______________________________________________
> >>> >> > Neo4j mailing list
> >>> >> > User at lists.neo4j.org
> >>> >> > https://lists.neo4j.org/mailman/listinfo/user
> >>> >> >
> >>> >> _______________________________________________
> >>> >> Neo4j mailing list
> >>> >> User at lists.neo4j.org
> >>> >> https://lists.neo4j.org/mailman/listinfo/user
> >>> >>
> >>> > _______________________________________________
> >>> > Neo4j mailing list
> >>> > User at lists.neo4j.org
> >>> > https://lists.neo4j.org/mailman/listinfo/user
> >>> >
> >>> _______________________________________________
> >>> Neo4j mailing list
> >>> User at lists.neo4j.org
> >>> https://lists.neo4j.org/mailman/listinfo/user
> >>>
> >>
> >>
> > _______________________________________________
> > Neo4j mailing list
> > User at lists.neo4j.org
> > https://lists.neo4j.org/mailman/listinfo/user
> >
> _______________________________________________
> Neo4j mailing list
> User at lists.neo4j.org
> https://lists.neo4j.org/mailman/listinfo/user
>


More information about the User mailing list