GSoC 2012 Jinfu Leng - pgRouting/pgrouting GitHub Wiki

Biography

  • Name: Jinfu Leng
  • School: I am doing my master degree in Computer Science and Geography at University of Nebraska - Lincoln, USA.

GSoC project

My Status Reports

Report 13

Initial Plan for project

Integrate a new shortest path algorithm (mild_two_q) to pgRouting.

Plan as modified with Mentor

No significant modification.

Actual accomplishments

Integrated the mild_two_q algorithm to pgRouting, and developed a tester for evaluating the performance.

Where the source code is?

How to install it?

The mild_two_q algorithm is integrated to pgRouting, and it will come with the installation of pgRouting.

How to use it?

  • 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);

How to compile and run your tester, state if it is working or not.

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

Known issues

No, at present.

Future ideas for this code if someone had time to work on it more

Do a complete evaluation.

What worked well and not so well for you during GSoC

Finished the basic plan, and had very good communication with the mentors.

Should also participate the discussion on other issues in the community.

Report 12

The plan

  • do the experiments with the tester
  • write the report

What have been done?

  • did the experiments with the tester

Report 11

The plan

  • Start experiments based on the generated source-target pairs and figure out the best way to record the results

What have been done?

  • 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 problems

  • The comparison of the algorithms are based on the execution time of the SQL command. I am not sure if this is appropriate.

Report 10

The plan

  • Start experiments based on the generated source-target pairs and figure out the best way to record the results

What have been done?

  • 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.

Report 9

The plan

  • Start experiments based on the generated source-target pairs and figure out the best way to record the results

What have been done?

  • 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.

Report 8

The plan

  • Start experiments based on the generated source-target pairs and figure out the best way to record the results

What have been done?

  • Did not get many progress, still coding for recording the experiment results

Next week:

  • Start experiments based on the generated source-target pairs and figure out the best way to record the results

Report 7

What have been done?

  • 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

Next week:

  • Start experiments based on the generated source-target pairs and figure out the best way to record the results

Report 6

What have been done?

  • 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)

Next week:

  • 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.

Report 5

What have been done?

  • 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

Next week:

  • 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

Report 4

What have been done?

  • implemented the interfaces of the algorithm. The framework is completely done, and right now users can call the function by executing SQL commands.

What am I doing?

  • 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.

Next week:

  • continue translating the algorithm

Report 3

What have been done?

  • 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.

Next week:

  • Implement the core computing process of the algorithm

Report 2

What have been done?

Road network data

  • Road network of London was fetched from OpenStreetMap, and the network data was transformed and imported to PostgreSQL database.

Coding

  • 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

Next week:

  • Continue to transform the existing code of two_q algorithm to fit the data structure in pgRouting

Report 1

What have been done?

Get used to development environment

  • Prerequisites were installed, source code was successfully compiled and installed
  • Git branch was created, wiki page was created

Be familiar with the architecture of pgRouting

  • Source code was went through

Learned to use pgrouting:

  • Network database was created

Next week:

  • Transform the existing code of two_q algorithm to fit the data structure in pgRouting