[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
<https://drive.google.com/file/d/12achE9jQ56bALO4-T2Xwcrnu_jf8zDxK/view?usp=sharing>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 <https://github.com/drenchding/Algorithm-templates> is the GitHub page
of the algorithm I implemented. in particular, topological sort
<https://github.com/drenchding/Algorithm-templates/blob/master/Graph%20Theory/Topological%20sort.cpp>
, transitive closure
<https://github.com/drenchding/Algorithm-templates/blob/master/Graph%20Theory/Transitive%20closure.cpp>
 and dominator tree
<https://github.com/drenchding/Algorithm-templates/blob/master/Graph%20Theory/Dominator%20tree.cpp>
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20190207/1179168c/attachment.html>