[Neo4j] Generating a directed acyclic graph
peter.neubauer at neotechnology.com
Tue Oct 19 19:04:57 CEST 2010
are you planning to implement the paper fully? Sounds like a good
match for my case too, modeling only the train network in Sweden right
now. However, I would like to expand it later to more transport
options. Well, seems everyone gets down the routing rabbit hole :)
VP Product Development, Neo Technology
Phone +46 704 106975
http://www.neo4j.org - Your high performance graph database.
http://www.thoughtmade.com - Scandinavia's coolest Bring-a-Thing party.
On Sun, Oct 17, 2010 at 9:55 PM, Paddy <paddyfitz at gmail.com> wrote:
> Hi Peter,
> I've been trying to implement this paper:
> It's being used by google transit. I'm representing the network as a time
> expanded graph with each departure time
> at each stop as a stoptime node. Each stoptime node is connected to the
> parent stop node.
> Each route is connected at the stoptime level and walking connections are
> determined by using neo4j-spatial to
> find available transfers nearby. Time is represented in minutes 0-1440.
> The paper describes creating a time query graph lookup table, I was thinking
> of using lucene for the lookups.
> Then to find all transfer patterns, find all shortest paths from each
> stoptime node to all stops using a Dijkstra.
> Convert each path to a transfer pattern. Then to create a directed ascynic
> graph with these transfer patterns for every stop.
> Use a time dependent dijskra where costs are determined on the fly by a
> CostEvaluator using the time query lookup table.
> This will enable fast queries and also multiple paths. I'm not sure the best
> way to create these directed acyclic graph's from the transfer patterns.
> Most of the info I see has been about converting directed acyclic graph to
> tables, Not sure if there an algorigthm to construct a directed acyclic
> On Sat, Oct 16, 2010 at 10:57 PM, Peter Neubauer <
> peter.neubauer at neotechnology.com> wrote:
>> I am experimenting with connecting train routes to stations. Would
>> your case be something similar? My approach right now is to first
>> insert the stations and index them, then in a second pass insert the
>> routes that reference the station names. Not super pretty but that is
>> the data I have. Is yours something similar?
>> On Sunday, October 17, 2010, Paddy <paddyfitz at gmail.com> wrote:
>> > Hi,
>> > I would like to generate a directed acylic graph from a large list of
>> > Each path begins from one single source node to multiple end nodes.
>> > Would this be a good use case for the pattern matching component? I
>> > find this functionality implemented, I'm not sure of the best way to
>> > approach this.
>> > Thanks
>> > Paddy
>> > _______________________________________________
>> > Neo4j mailing list
>> > User at lists.neo4j.org
>> > https://lists.neo4j.org/mailman/listinfo/user
>> Neo4j mailing list
>> User at lists.neo4j.org
> Neo4j mailing list
> User at lists.neo4j.org
More information about the User