Dear pgRouting developers,
I am a junior from Xi’an Jiaotong University who are interested in your GSoC project. I want to be able to participate in it and I’d like to introduce myself and my thoughts on this project.
I‘m good at algorithms and data structures. In 2018, I participated in the International Collegiate Programming Contest World Finals and got the 56th place from among 140 teams of three chosen from a field of 49,935 contestants from 3,098 universities in 111 countries on six continents. You can get more details in https://icpc.baylor.edu/ about this contest. I also advance to the World Finals 2019 which will be held in May. If you want to get more information about me, here is my resume.
Because of the experience in the algorithmic competition. I am particularly interested in your idea 12 which to implement some algorithms. I have lots of ideas about doing it. For example, the algorithm for obtaining a transitive closure is generally implemented by using a recursive algorithm, but this recursive algorithm can be optimized by using a bitset. Besides, The algorithm for finding the dominator tree of a directed graph to can be optimized according to the characteristics of the graph: if the graph is a tree or a directed acyclic graph, the problem will be simpler.
In addition to the four algorithms given in idea 12, I also have some ideas for other algorithm implementations. For example, the Tarjan algorithm for finding strongly connected components of directed graphs, as well as the Tarjan algorithm for finding undirected graph cuts and bridges, is also important.
Here is the GitHub page of the algorithm I implemented. in particular, topological sort, transitive closure and dominator tree are inside. Since this repo is for personal use by now, the comments are not complete, and I will gradually complete it in the future.
Looking forward to your reply!
Best regards,
Cong Ding
Hi Cong,
Very glad to hear you have interests in pgRouting development. You have much experience in algorithms field and I’m sure it will help you a lot.
Idea 12 means that you will implement some algorithms for pgRouting from Boost Graph library. In other word, your “mission” is gluing BGL features to pgRouting.
In addition, components algorithms are good in master branch. Refer to [1].
[1] https://github.com/pgRouting/pgrouting/tree/master/include/components
Best regards,
Maoguang Wang
Cong Ding <dingcong1998@gmail.com> 于2019年2月7日周四 下午7:47写道：
Dear pgRouting developers,
I am a junior from Xi’an Jiaotong University who are interested in your GSoC project. I want to be able to participate in it and I’d like to introduce myself and my thoughts on this project.
I‘m good at algorithms and data structures. In 2018, I participated in the International Collegiate Programming Contest World Finals and got the 56th place from among 140 teams of three chosen from a field of 49,935 contestants from 3,098 universities in 111 countries on six continents. You can get more details in https://icpc.baylor.edu/ about this contest. I also advance to the World Finals 2019 which will be held in May. If you want to get more information about me, here is my resume.
Because of the experience in the algorithmic competition. I am particularly interested in your idea 12 which to implement some algorithms. I have lots of ideas about doing it. For example, the algorithm for obtaining a transitive closure is generally implemented by using a recursive algorithm, but this recursive algorithm can be optimized by using a bitset. Besides, The algorithm for finding the dominator tree of a directed graph to can be optimized according to the characteristics of the graph: if the graph is a tree or a directed acyclic graph, the problem will be simpler.
In addition to the four algorithms given in idea 12, I also have some ideas for other algorithm implementations. For example, the Tarjan algorithm for finding strongly connected components of directed graphs, as well as the Tarjan algorithm for finding undirected graph cuts and bridges, is also important.
Here is the GitHub page of the algorithm I implemented. in particular, topological sort, transitive closure and dominator tree are inside. Since this repo is for personal use by now, the comments are not complete, and I will gradually complete it in the future.
Looking forward to your reply!
Best regards,
Cong Ding
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
https://lists.osgeo.org/mailman/listinfo/pgrouting-dev
Hello Cong Ding
As Maoguang mentions, task #16 is about gluing an algorithm of the C++ library into postgres
I recommend that you see the boost graph library documentation
https://www.boost.org/doc/libs/1_53_0/libs/graph/doc/table_of_contents.html
Read pgRouting documentation of develop branch:
https://docs.pgrouting.org/dev/en/index.html
and decide in which functions you could add to pgRouting.
Regards
Vicky
···
Georepublic UG (haftungsbeschränkt)
Salzmannstraße 44,
81739 München, Germany
Vicky Vergara
Operations Research
eMail: vicky@[georepublic.de](http://georepublic.de)
Web: [https://georepublic.info](https://georepublic.info)
Tel: +49 (089) 4161 7698-1
Fax: +49 (089) 4161 7698-9
Commercial register: Amtsgericht München, HRB 181428
CEO: Daniel Kastl