Neo4j kShortestPaths Algorithm apply to City Map
May 18: Museum Night, One Month Graph Challenge
Welcome word
In this series of small posts I do one simple graph daily. Domain model of graph somehow related to day’s history, some historical event, celebration or person. I do this challenge to learn Neo4j Data Modeling and Cypher. Every day. One month. Follow me. Maybe you will be inspired and next month would be yours One Month Graph Challenge. #OMGChallenge
Domain model
Today is an International Museum Day and numerous museums around the world open their doors for everyone absolutely free, prepare new expositions, thematic lectures, tours, scientific readings. Currently, more than 20,000 museums around the world celebrate this holiday.
The most famous event of this day is the Museum Night, during which you can see the museum expositions at night. So today I plan to build a small graph of museums and build a query, that helps me to visit in this one night some of the museums.
Graph
I need a map of museums with names and locations. Wikipedia? Yes, of course.
I need somehow connect them to each other, but I don’t really want to do this task manually. Better to apply some automatic rule. What if I connect museum with 3 other most nearest museums? Seems like good idea.
Museums map looks cool, is not it. Now it is time to plan my museum night walking trip. Let’s assume I want to start at 18:00 and finish at 23:00. So, I have only 5 hours to visit as much museums as I can. I plan to spend 20 minutes in each museum I visit. For sure, I can’t see a lot of stuff for just 20 minutes, but I care about amount of visits, rather than quality of visits. And my average speed between museums is 4 km/h. I can start from any museum, and end in any, this is doesn’t matter for me. Time to analyse and plan a trip.
Most probably, my approach is not good. I used kShortestPaths with only first result path returns. Also, it takes long time to compute result. Any advice, guys? Maybe you can suggest me how to improve it?
Anyway, results ready to use. Seems like I can visit just 6 places and spend around 3 and a half hours. Thank you Neo4j for good advice. This is why I will walk less to see more. Without using of “short” path, I can find something to spend all 5h and visit much more museums, but I need to write different query for it. Maybe you want to try this one? Also, if we change 20 minutes of visit to for example 1 hour, results would be totally different. That is also interesting to play with.
Resume
Interesting to play with pathes, again and again. Balance of visiting time against time spend in walk. This is hot topic, for sure. Also, I want to see here how to apply some faster approach, actually. Maybe someone of you can suggest me. And finally, I like to try Duration, it is awesome type.
Similar topics
Neo4j PageRank Algorithm and Path Pattern Matching on Flights Domain Model
Unusual use of Neo4j Common Neighbors Algorithm on people community graph
Neo4j Betweenness Centrality Algorithm detailed and fun example
Neo4j Cosine Similarity Algorithm example
Analyse Neo4j Graph of Books domain model with Jaccard Similarity Algorithm
