[Neo4j] Generating a directed acyclic graph

Peter Neubauer 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 :)


/peter neubauer

VP Product Development, 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, Oct 17, 2010 at 9:55 PM, Paddy <paddyfitz at gmail.com> wrote:
> Hi Peter,
> I've been trying to implement this paper:
> http://ad.informatik.uni-freiburg.de/papers/transferpatterns.pdf
> 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
> graph?
> Paddy
> On Sat, Oct 16, 2010 at 10:57 PM, Peter Neubauer <
> peter.neubauer at neotechnology.com> wrote:
>> Paddy,
>> 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?
>> /Peter
>> 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
>> paths.
>> > 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
>> couldn't
>> > 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
>> 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