GSoC 2012 Jinfu Leng
- Name: Jinfu Leng
- School: I am doing my master degree in Computer Science and Geography at University of Nebraska - Lincoln, USA.
- Proposal http://www.google-melange.com/gsoc/proposal/review/google/gsoc2012/jinfu/1
- Source Code https://github.com/pgRouting/pgrouting/tree/gsoc-two_q
- Report 1, 2012-05-25
- Report 2, 2012-06-01
- Report 3, 2012-06-08
- Report 4, 2012-06-15
- Report 5, 2012-06-22
- Report 6, 2012-06-29
- Report 7, 2012-07-06
- Report 8, 2012-07-13
- Report 9, 2012-07-20
- Report 10, 2012-07-27
- Report 11, 2012-08-03
- Report 12, 2012-08-10
- Report 13, 2012-08-17
Integrate a new shortest path algorithm (mild_two_q) to pgRouting.
No significant modification.
Integrated the mild_two_q algorithm to pgRouting, and developed a tester for evaluating the performance.
-
Mild_Two_Q Algorithm https://github.com/pgRouting/pgrouting/tree/gsoc-two_q
The mild_two_q algorithm is integrated to pgRouting, and it will come with the installation of pgRouting.
- Function with parameters
mild_two_q_shortest_path( sql text, source_id integer, target_id integer, directed boolean, has_reverse_cost boolean )
- Example
SELECT * FROM mild_two_q_shortest_path(' SELECT gid as id, source::integer, target::integer, length::double precision as cost FROM ways', 5700, 6733, false, false);
The tester is working.
- How to compile?
Open your terminal, go into the folder of the project, and then execute "make".
- How to use?
RoutingTester argument1[string] argument2[int] argument3[int]
argument1: the name of the database (you have to import the road network to your postgreSQL firstly)
argument2: the number of the randomly generated pairs
argument3: the number of executions for each pair
No, at present.
Do a complete evaluation.
Finished the basic plan, and had very good communication with the mentors.
Should also participate the discussion on other issues in the community.
- do the experiments with the tester
- write the report
- did the experiments with the tester
- Start experiments based on the generated source-target pairs and figure out the best way to record the results
- Implemented the auto tester, which can generate random source-target pairs and then call the shortest path algorithms. Source code of the tester: https://github.com/jinfu-leng/RoutingTester
- Cleaned and commented the source code.
- The comparison of the algorithms are based on the execution time of the SQL command. I am not sure if this is appropriate.
- Start experiments based on the generated source-target pairs and figure out the best way to record the results
- I did not get many progresses this week. This week I flied from China to US, and was involved in another academic project immediately once I arrived in US. I will try to catch up in the next week.
- Start experiments based on the generated source-target pairs and figure out the best way to record the results
- Read a series of related papers on evaluating the performance of shortest path algorithms. Especially, I am looking into the code from the paper "shortest paths algorithms - theory and experimental evaluation". I am trying to understand the code and adjust it to match our PgRouting project.
- Start experiments based on the generated source-target pairs and figure out the best way to record the results
- Did not get many progress, still coding for recording the experiment results
- Start experiments based on the generated source-target pairs and figure out the best way to record the results
- comment to my code
- load a few road networks to the database for future testing
- implement the function to generate random source-target pairs basd on the network
- Start experiments based on the generated source-target pairs and figure out the best way to record the results
- optimized the logic of the mild_two_q algorithm
- cleaned the source code (the code was implemented based on an existing algorithm, and so there were some unnecessary staff for my algorithm)
- I was planning to start to comprehensively compare the performance of these algorithms this week, but I have some problems on implementing the automatic testing tool. I will continue my work on it this week.
- implemented the origin two_q algorithm and the revised mild_two_q algorithm
- manually tested the mild_two_q algorithm, and the output is identical with the output of the embedded dijkstra algorithm
- optimize the performance of the mild_two_q algorithm
- clean the code
- start to comprehensively compare the performance of dijkstra, two_q and mild_two_q algorithm
- implemented the interfaces of the algorithm. The framework is completely done, and right now users can call the function by executing SQL commands.
- translating the algorithm to fit the data structure of the C++ library "boost". It is kind of not easy, since I did not access this library before and C++ templates are widely used in the library. I am trying to use the basic queue as the temporary buffer in the algorithm, and I would like to implement the template of the two_queue later.
- continue translating the algorithm
- Learned to use "cmake" to integrate my new source code
- Based on the source code of "shooting_star" algorithm, implemented the framework of the new algorithm.
- Learned to use the library "boost/graph" to manage the road network.
- Implement the core computing process of the algorithm
- Road network of London was fetched from OpenStreetMap, and the network data was transformed and imported to PostgreSQL database.
- The data structure of Node and Edge was designed
- The exporting of road network from database and the constructing of road network in memory were implemented
- Continue to transform the existing code of two_q algorithm to fit the data structure in pgRouting
- Prerequisites were installed, source code was successfully compiled and installed
- Git branch was created, wiki page was created
- Source code was went through
- Network database was created
- Transform the existing code of two_q algorithm to fit the data structure in pgRouting
