This is an interesting problem. I'm not totally sure I've followed the
entire discussion, but here are my thoughts.
Your model is divided into two levels:
- Core model, with routes that specify the bus routes, times between
stops and locations. For example we can say that bus 5 stops at stop 21 as
its third stop, 35 minutes after departure. This does not say anything about
runs, or what time of day the stop will occur.
- Live timetable, which has information for each actual run during the
day.
While you could model only the core and make the live timetable a result of
a query, I think that is not ideal. Personally I would model the live
timetable in the graph also. Almost like a spreadsheet where the columns are
the stops and the rows are the runs, the cells end up being the complete
timetable. And you can traverse from cell to cell up/down and left/right
(for either following one run, or for looking at the times buses arrive at a
particular stop).
So, what I would do is the following:
- Build the core model, linking buses to routes composed of stops
(containing locations on nodes and distances on relationships)
- Extend the core model with runs, specifying multiple start times for
all routes. Each route should have many runs, and each run would be a new
node.
- For each run, duplicate the routes with stop nodes containing the
actual timetable stop times. These nodes dont need locations, because they
can link directly to the original stop nodes (different relationship type of
course).
- Now you have a graph of the complete timetable, but there is one more
thing to add, walking distance between stops should the user need to change
bus. This can be done in two phases also:
- Calculate all walking distances between all core model stops on
different routes. Add relationships between the stops, but only
if less than
some maximum time (why load the graph with relationships that
will never be
used, like walking 2h between bus stops :-)
- Now go to the timetable nodes, and add relationships there. This
time you add relationships between different routes if several conditions
are met:
- The walking distance is short enough (already calculated from the
core model)
- The walking time is less than the time between the stop times
(ie. as you said before)
- Use time between node times as the cost, not the walking time, so
you get the next bus, not the one after that (the one after
gets a higher
cost, since the time difference is higher)
- Finally index all core model stops using a spatial index (eg. Neo4j
Spatial RTree), so you can made the start query you wanted.
- Now you have a graph that contains everything you need to make all
queries. All possible routes are in the graph structure itself, and the cost
is a simple sum of the costs of the relationships.
Does this sound like a useful approach?
Regards, Craig
On Wed, Jun 23, 2010 at 8:36 PM, Paddy <paddyf...@gmail.com> wrote:
> Hi Mattias,
> I'm having trouble implementing the timetable node, what way would the
> timetable data be stored in the node to allow for traversal based on time?
> Would i need a timetable node for each stop or for each route.
> At the moment i have relationships between each connecting stop node with
> cost representing minutes.
> Is there any way to specify the A* to only traverse nodes where the time
> property is greater than the current nodes time?
>
> Thanks
> Paddy
>
>
>
> On Wed, Jun 9, 2010 at 1:57 AM, Mattias Persson
> <matt...@neotechnology.com>wrote:
>
> > For each bus stop node you could have a relationship to that route's
> > timetable, represented by a separate timetable node. So all nodes for
> > a route could just have a relationship to that route's timetable node
> > where the actual timetable is stored, minimizing redundant information
> > in your graph.
> >
> > A cool use of A*, I might add.
> >
> > 2010/6/9 Paddy <paddyf...@gmail.com>:
> > > I have nodes representing bus stops, and relations representing bus
> > > connections with cost values representing minutes it takes for the bus
> to
> > > reach each stop.
> > > I'm currently using the A Star algorithm to find the quickest route for
> > the
> > > bus routes.
> > > what is the best way to integrate the timetable data with a neo4j
> graph.
> > >
> > > Route 117:
> > > (stop: 01) -mins:3 -> (stop:02) -mins:6 -> (stop:03) -mins:3 ->
> > (stop:04)
> > > -mins:3 -> (stop:05)
> > >
> > > Route 203:
> > > (stop: 01) -mins:10 -> (stop:08) -mins:6 -> (stop:09) -mins:3 ->
> > > (stop:11)
> > >
> > > Route 302:
> > > (stop: 03) -mins:9 -> (stop:08) -mins:6.5 -> (stop:06) -mins:3.3 ->
> > > (stop:10) -mins:7 -> (stop:01)
> > >
> > > A trip could be on multiple bus routes e.g a user can get bus route 1
> and
> > > change to bus route 3 at any stop to get the quickest route
> > > There are relationships between stops within walking distance, the cost
> > is
> > > represented by walking time in minutes.
> > >
> > > The timetable is currently stored in SQL as:
> > > Route, Day, Stop #, Time
> > >
> > > 117, Monday, 1, 9:00
> > > 117, Monday, 2, 9:03
> > > 117, Monday, 3, 9:09
> > > 117, Monday, 4, 9:12
> > > 117, Monday, 5, 9:15
> > > ..
> > > .
> > > 117, Monday, 1, 9:30
> > > 117, Monday, 2, 9:33
> > > ..
> > > .
> > > 117, Monday, 1, 10:50
> > > 117, Monday, 2, 10:53
> > > ..
> > > .
> > > If i have the timetable data as a property field for each node, can i
> use
> > > this data in the astar algorithm?
> > > Any help would be great
> > > Thanks
> > > _______________________________________________
> > > Neo4j mailing list
> > > User@lists.neo4j.org
> > > https://lists.neo4j.org/mailman/listinfo/user
> > >
> >
> >
> >
> > --
> > Mattias Persson, [matt...@neotechnology.com]
> > Hacker, Neo Technology
> > www.neotechnology.com
> > _______________________________________________
> > Neo4j mailing list
> > User@lists.neo4j.org
> > https://lists.neo4j.org/mailman/listinfo/user
> >
> _______________________________________________
> Neo4j mailing list
> User@lists.neo4j.org
> https://lists.neo4j.org/mailman/listinfo/user
>
_______________________________________________
Neo4j mailing list
User@lists.neo4j.org
https://lists.neo4j.org/mailman/listinfo/user
