GSoC 2019 GRAPH C Boost graph algorithms for pgRouting
- Proposal
- Log of Pull Requests
- Weekly Reports
- References
My project will focus on implementing:
- topological sort. Topological sort is a sorting algorithm. It is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.[1]
- transitive closure. The concept of transitive closure can be thought of as constructing a data structure that makes it possible to answer reachability questions. That is, can one get from node a to node d in one or more hops? A binary relation tells you only that node a is connected to node b, and that node b is connected to node c, etc.[2] lengauer tarjan dominator tree
- dominator tree. A dominator tree is a tree where each node's children are those nodes it immediately dominates. Because the immediate dominator is unique, it is a tree. The start node is the root of the tree.[3]
I propose to add the above 3 algorithms into pgRouting during the GSoC period.
pgRouting currently does not have these algorithms implemented.
Topological sort is a common sorting algorithm of graph. However, a single standard function does not exist.
Floyd’s algorithm implemented in pgRouting can also answer reachability question. However, it has a higher run-time complexity. Transitive closure is required
Also lengauer tarjan dominator tree is not implemented before in pgRouting. So far, a single standard function does not exist.
- Implementation of topological sort to pgRouting.
- Implementation of transitive closure for pgRouting.
- Implementation of lengauer tarjan dominator tree for pgRouting.
Each implemented function will include relevant documentation and tests.
- Design pgr_topological_sort() function
- Create a basic skeleton for documentation and tests.
- Implement pgr_topological_sort() function along its helper files.
- Basic testing.
- Prepare a report for First Evaluation.
- Work on feedback provided from the first evaluation.
- Prepare documentation for pgr_topological_sort() function.
- Complete testing along with writing pgTap tests for pgr_topological_sort() function.
- Design pgr_transitive_closure() function.
- Create a basic skeleton for documentation and tests.
- Begin implementation of pgr_transitive_closure() function.
- Create a basic skeleton for documentation and tests.
- Design pgr_lengauer_tarjan_dominator_tree() function.
- Prepare a report for Second Evaluation.
- Work on feedback provided from the second evaluation.
- Complete the implementation of pgr_transitive_closure() function.Each implemented function will be delivered with the relevant documentation and tests included.
- Begin implementation of pgr_lengauer_tarjan_dominator_tree() function.
- Complete testing along with writing pgTap tests for pgr_transitive_closure() function and pgr_lengauer_tarjan_dominator_tree() function.
- Review, complete and finalize all documentation and tests. = Create a detailed final report.
Original Proposal Submitted to Google
| Pull Request | Description | Date | Status |
|---|
- Set up the development environment.
- Interact with mentors, introduce myself to the community and actively get involved in the discussion.
- Set up a wiki page to keep track of weekly progress.
- Add a wiki link to OSGeo's accepted students wiki page.
- Introduce myself and my project on OSGeo's SOC mailing list.
- Get familiar with pgRouting’s development style. Understand expected coding, documentation and testing standards set by pgRouting.
- Develop a better understanding of PostgreSQL, PostGIS, Pl/pgSQL and how they interact with pgRouting.
- Learn to create unit tests using pgTap.
- Implement simple dummy functions to better understand pgRouting.
-
"Topological sorting From Wikipedia, the free encyclopedia", https://en.wikipedia.org/wiki/Topological_sorting
-
"transitive closure From Wikipedia, the free encyclopedia", https://en.wikipedia.org/wiki/Transitive_closure
-
"Dominator_(graph_theory)#Algorithms From Wikipedia, the free encyclopedia.", https://en.wikipedia.org/wiki/Dominator_(graph_theory)#Algorithms
-
"DAG From th7.com", https://m.baidu.com/tc?from=bd_graph_mm_tc&srd=1&dict=20&src=http%3A%2F%2Fwww.th7.cn%2Fweb%2Fjs%2F201608%2F179332.shtml&sec=1554819720&di=302233a63ff9bbd4
-
"lengtarj Persudo code & implement figuresa", https://www.cl.cam.ac.uk/~mr10/lengtarj.pdf
-
"pgr_bdDijkstra Documentation", https://docs.pgrouting.org/dev/en/pgr_bdDijkstra.html
-
"pgRouting Sample Data", https://docs.pgrouting.org/dev/en/sampledata.html
