fbpx

CL LAB

HOME > CL LAB > Neo4j > 祝Pokémon GOリリース!Neo4jでレアポケモンゲットだぜ! #neo4j

Pokémon GO has been released! Get rare Pokémons by visiting around their habitats efficiently with Neo4j! #neo4j

 ★ 2

    neo4j_logo

    Kiuchi here.  Let me start with the apology for using a fishing title.  (I just wanted to draw your attention….)

    So, everyone around the world is excited about Pokémon GO.  Are you part of the worldwide phenomenon too?  I’m on level 11, and have not visited the gym because I’m too scared….  
    As advanced my level by the collecting the ordinary Pokémons near my house and office, I started to search for more excitement.  … and as I get useful information, such as Pikachu can be found in Shinjuku Gyoen Park, I start to think ‘OK, let’s go find rare Pokémons this weekend.’

    It also seems like everyone in charge of the marketing in the IT world wants to jump on this occasion to draw everyone’s attention. I have to admit, I am one of them....and this article has a double meaning…
    Enough for the prologue.  Let’s get to it the serious as Creationline way.

    What are rare Pokémons?

    Those Pokemons that cannot be collected just by playing Pokémons Go regularly are called rare Pokemons, such as follows:

    • Pikachu
    • Eevee
    • Growlithe
    • Farfetch’d
    • Sand
    • Diglett
    • Seel
    • Magnemite
    • Voltorb
    • Jynx
    • Electabuzz
    • Polygon
    • Laplace

    There are quite a lot…  Children can spend their whole summer vacation for it, but time is very limited for moms and dads.  

    It seems that there are certain places for certain rare Pokemons.   As far as I understand, the following places are said to be the habitats for the rare Pokémons.  

    • Pikachu: Shinjuku Gyoen Park
    • Eevee: Setagaya Park
    • Growlithe: Shinjuku Gyoen Park
    • Farfetch’d: Yoyogi Park
    • Sandshrew: Yoyogi Park
    • Diglett: Hibiya Park
    • Seel: Mizumoto Park
    • Magnemite: Odaiba Kaihin Park
    • Voltorb: Inokashira Park
    • Jynx: Oomiya Park
    • Electabuzz: Ueno Park
    • Polygon: Shibuya
    • Laplace: Enoshima

    It seems like they are widely scattered, as I mapped them in a Google map.

    https://drive.google.com/open?id=1Ktf_tYgJ9GaiaGvR7TPCidy_y_8&usp=sharing

    Collecting all of those rare Pokemons together with your family can be a nice memory of the summer, and of course you can brag about it to your co-workers.  However, collecting all of them seems very difficult since they are dotted in a wide map.  Your kids cannot go on his or her own, and holidays are very limited for the adults.  Is there a way for us to visit those places effectively?     

    Root search Algorithm

    This proposition is related to the graph root search problem called ‘traveling salesman problem’ or ‘Hamiltonian path problem.’  Yes, I’m aware that I have just steamrollered you into a serious math world.  Let’s move on.  It’s a theory to draw an answer to ‘what is the shortest possible route that starts from a certain point, visits each check-point and returns to the starting point?

    This ‘traveling salesman problem’ belongs to the class of “NP-hard” problems, that means it is computationally difficult to solve.   The definition of NP-hard itself is difficult, but I think it can be interpreted as ‘The issue may not be solved even if we use computers since it has computational complexity (too many calculations.).’
    When we limit some conditions of ‘traveling salesman problem’, the problem is called ‘Hamiltonian path problem’ with less complexity.  It is a “NP-complete” problem, meaning it is possible to solve it, it is just matter of time.      

    I’d love to search for the Pokemon route using ‘Hamiltonian path problem’ but unfortunately, Neo4j is not equipped with the library for it.  Python NetworkX has in its library called ‘Hamiltonian path’ for the exact purpose, but it needs to have the graph data in its own form, and cannot be solved when linked with Neo4j.    
    Therefore, we’ve decided to implement the search algorithm on our own and search for the shortest route by brute force. We will search for all possible routes, but how many there are?  

    I have listed 11 rare Pokemon spots. When calculating the visiting orders by permutations and combinations, it goes like this;
    : 11! = 11 x 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 39,916,800.  
    There are about 40 million routes!  It will take your whole summer to calculate the shortest route among them. The real goal is to become a rare Pokémon hunter or make fun memories of the summer with your family, not spending the whole time searching for a route. So, let’s leave the difficult task to the computer.

    Let’s begin the calculation.

    Convert the route into graph data with Neo4j

    We know where to visit for rare Pokemons as mentioned above.  Let’s assume we will use trains to visit the sites, and create the graph data that includes the train routes.  Paste the following URL of Neo4j graph data definition on the query window.

    https://raw.githubusercontent.com/m-kiuchi/neo4j-pokemongo/master/pokemongo.neo4j

    Now we have the graph like the following.  Nearest station for each Pokemon habitat and route between those stations are defined. The relationship also shows how long it takes from one station to another.

    pokemongo-1

    Route search and Transportation cost calculation

    Neo4j has the function to calculate the shortest route between any 2 apexes.
    Example:

    MATCH path=allShortestPaths((a)--(b))
    WHERE a.someProperty = 'hogehoge' AND b.someProperty = 'fugafuga'
    RETURN path

    Now we can select the shortest route when moving from one rare Pokemon spot to another, within one route.  Please note that when the graph includes circulating route, the query cannot be completed with the simple search command, in case of graph data route search.   
    When summing the transportation cost for each searched relation, we use the following query.

    MATCH path=allShortestPaths((a)-[r*]-(b))
    WHERE a.someProperty = 'hogehoge' AND b.someProperty = 'fugafuga'
    WITH path,reduce(s = 0, rel IN r | s + rel.cost) AS totalCost
    RETURN path

    Programming and execution result

    Here’s the route search program, integrating the above mentioned queries.

    https://github.com/m-kiuchi/neo4j-pokemongo/blob/master/pokemongo.py

    Here’s also the program execution results.  It took 18 minutes for all the route searching.   

    OOOOO.O.OO..O.....O.....O.....O.OO.....
    (omitted)
    Num of traversal route: 39916800
    All route has traversalled
    -----
    calculated fastest path to Rare-Pokemon-master !!
    (401, 372, 378, 379, 374, 373, 381, 382, 377, 375, 376, 380, 401)
    estimated duration: 15.00 hours
    Good luck !!

    The recommended route calculated by the route search

    The following is the shortest route for rare Pokemon hunt, calculated by the Neo4j route search!  Surely it’s the shortest route, but it still takes 15 hours just for the transportation, and it increases to 18 hours when including the Pokemon hunting itself at each park.  Also it does not include the time to take a break.  

    I don’t think anyone would want to take this very harsh journey…

    • 06:00AM: Depart Creationline office, heading for Akihabara station.
    • 06:16AM: Take JR Soubu line to Shinjuku station.
    • 06:31AM: Get off at Shinjuku station, heading for Shinjuku Gyoen on foot.
    • 07:00AM: Arrive at Shinjuku Gyoen.  Get Pikachu and Growlithe!
    • 07:15AM: Leave Shinjuku Gyoen. Walk to Shinjuku station.
    • 07:45AM: Take the JR Chou line from Shinjuku to Kichijoji
    • 08:05AM: Arrive at Kichijoji station. Walk to Inokashira Park.
    • 08:15AM: Arrive at Inokashira Park. Get Voltorb!
    • 08:25AM: Leave Inokashira Park. Walk to Kichijoji station.
    • 08:35AM: Take the JR Chou line from Kichijoji to Shinjuku.
    • 08:55AM: Arrive at Shinjuku. Transfer to the JR Saikyo line and head to Omiya station.
    • 09:35AM: Arrive at Omiya station. Transfer to the Tobu Noda line and head to the Tobu Omiya Koen station.
    • 10:00AM: Arrive at Tobu Omiya Koen station. Walk to Omiya Park.
    • 10:10AM: Arrive at Omiya Park. Get Jynx!
    • 10:25AM: Leave Omiya Park. Walk to Tobu Omiya Koen station.
    • 10:35AM: Take the Tobu Noda line from Tobu Omiya Koen station to Omiya station.
    • 10:50AM: Arrive at Omiya station. Take the JR Saikyo line to Shinjuku.
    • 11:30PM: Arrive at Shinjuku station. Transfer to the JR Yamanote line and head to Harajuku station.
    • 11:45PM: Arrive at Harajuku station. Walk to Yoyogi Park.
    • 11:55PM: Arrive at Yoyogi Park. Get Farfetch’d and Sandshrew!
    • 12:15PM: Leave Yoyogi Park. Walk to Harajuku station.
    • 12:25PM: Take the JR Yamanote line from Harajuku station to Shibuya station.
    • 12:40PM: Arrive at Shibuya station. Transfer to the Denentoshi line and head to Sangenjaya station.
    • 12:50PM: Arrive at Sangenjaya station. Walk to Setagaya Park.
    • 13:05PM: Arrive at Setagaya Park. Get Eevee!
    • 13:15PM: Leave Setagaya Park. Walk to Sangenjaya station.
    • 13:25PM: Take the Denentoshi line from Sangenjaya station to Shibuya station.
    • 13:40PM: Arrive at Shibuya station. Walk out of the station and get Porygon.
    • 14:00PM: Go back to Shibuya station and take the JR Shonan Shinjuku line to Yokohama station.
    • 14:35PM: Arrive at Yokohama station. Transfer to the JR Tokaido line and head to Fujisawa station.
    • 15:05PM: Arrive at Fujisawa station. Transfer to the Enoshima Electric Railway and head to Enoshima station.
    • 15:25PM: Arrive at Enoshima station. Walk to Enoshima.
    • 15:45PM: Arrive at Enoshima. Get Lapras!
    • 15:55PM: Leave Enoshima. Walk to Enoshima station.
    • 16:05PM: Take the Enoshima Electric Railway to Fujisawa station.
    • 16:25PM: Arrive at Fujisawa station. Transfer to the JR Tokaido line and head to Yokohama station.
    • 16:55PM: Arrive at Yokohama station. Continue taking the JR Tokaido line to Shinagawa station.
    • 17:25PM: Arrive at Shinagawa station. Continue taking the JR Tokaido line to Shimbashi station.
    • 17:40PM: Arrive at Shimbashi station. Transfer to the Yurikamome line and head to Daiba station.
    • 18:05PM: Arrive at Daiba station. Walk to Odaiba Seaside Park.
    • 18:15PM: Arrive at Odaiba Seaside Park. Get Magnemite!
    • 18:25PM: Leave Odaiba Seaside Park. Head to Daiba station.
    • 18:35PM: Take the Yurikamome line from Daiba station to Shimbashi station.
    • 19:00PM: Arrive at Shimbashi station. Transfer to the JR Yamanote line and head to Yurakucho station.
    • 19:15PM: Arrive at Yurakucho station. Walk to Hibiya Park.
    • 19:25PM: Arrive at Hibiya Park. Get Diglett!
    • 19:35PM: Leave Hibiya Park. Walk to Yurakucho station.
    • 19:45PM: Arrive at Yurakucho station. Take the JR Yamanote line to Ueno station.
    • 20:15PM: Arrive at Ueno station. Transfer to the JR Joban line and head to Kita-Senju station.
    • 20:35PM: Arrive at Kita-Senju station. Transfer to the Tokyo Metro Chiyoda line and head to Kanamachi station.
    • 20:55PM: Arrive at Kanamachi station. Walk to Mizumoto Park.
    • 21:25PM: Arrive at Mizumoto Park. Get Seel!
    • 21:35PM: Leave Mizumoto Park. Walk to Kanamachi station.
    • 22:05PM: Take the Tokyo Metro Chiyoda line from Kanamachi station to Kita-Senju station.
    • 22:25PM: Arrive at Kita-Senju. Transfer to the JR Joban line and head to Ueno station.
    • 22:45PM: Arrive at Ueno station. Walk to Ueno Park.
    • 22:55PM: Arrive at Ueno Park. Get Electabuzz!
    • 23:05PM: Leave Ueno Park. Walk to Ueno station.
    • 23:15PM: Arrive at Ueno station. Take the JR Yamanote line to Akihabara station.
    • 23:30PM: Arrive at Akihabara station. Walk to Creationline, the finish line.
    • 23:40PM: Arrive at Creationline. GOAL!

    Lastly

    I have to admit, I started out writing this article with different intentions but it turned out pretty well. For now, I'm guessing the title is just about getting by. Just as anyone would expect, the calculated route is too hard to go around in a day. It is more realistic to divide it into 2 days and and go around while enjoying the scenery.

    Other than what we introduced in this article, I believe that the route search using Neo4j can be applied to many cases. I am more than happy if I was able to get anyone interested through this article.

    See you next time!

CL LAB Mail Magazine

CL LABの情報を逃さずチェックしよう!

メールアドレスを登録すると記事が投稿されるとメールで通知します。

メールアドレス: 登録

※登録後メールに記載しているリンクをクリックして認証してください。

Related post