[pgrouting-dev] pgRouting's GSoC project

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

[pgrouting-dev] pgRouting's GSoC project

Cong Ding
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 sorttransitive 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
[hidden email]
https://lists.osgeo.org/mailman/listinfo/pgrouting-dev
Reply | Threaded
Open this post in threaded view
|

Re: [pgrouting-dev] pgRouting's GSoC project

Maoguang Wang
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].


Best regards,
Maoguang Wang


Cong Ding <[hidden email]> 于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 sorttransitive 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
[hidden email]
https://lists.osgeo.org/mailman/listinfo/pgrouting-dev

_______________________________________________
pgrouting-dev mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/pgrouting-dev
Reply | Threaded
Open this post in threaded view
|

Re: [pgrouting-dev] pgRouting's GSoC project

Vicky Vergara-2
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
Read pgRouting documentation of develop branch:
and decide in which functions you could add to pgRouting.
Regards
Vicky



On Thu, Feb 7, 2019 at 7:11 AM Maoguang Wang <[hidden email]> wrote:
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].


Best regards,
Maoguang Wang


Cong Ding <[hidden email]> 于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 sorttransitive 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
[hidden email]
https://lists.osgeo.org/mailman/listinfo/pgrouting-dev
_______________________________________________
pgrouting-dev mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/pgrouting-dev


--
Georepublic UG (haftungsbeschränkt)
Salzmannstraße 44, 
81739 München, Germany

Vicky Vergara
Operations Research

eMail: vicky@georepublic.de
Web: 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


_______________________________________________
pgrouting-dev mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/pgrouting-dev