Skip to content

GSoC 2020 Lengauer Tarjan dominator tree and Bipartite

Jump to bottom Edit New page
Prakash Tiwari edited this page Aug 31, 2020 · 16 revisions

Table of Contents

Proposal

Brief Project Description

The project consists of the implementation of two algorithms:

  • Lengauer Tarjan Dominator Tree

  • Bipartite
    The algorithms are going to be taken from Boost Graph Library (BGL). ​ The first part of this project is ​ to provide support for Lengauer Tarjan Dominator Tree in pgRouting. Lengauer Tarjan Dominator Tree ​ is applied in many routing applications, such as if the user wants to go from city A to city B and there are multiple routes but all the routes are diverting from city X then the user can find out city X by using this algorithm. And the second part of this project is to provide support for check any given graph is bipartite or not. If the graph is bipartite then function returns the node along with two colors 0 and 1 which represents two different sets. If graph is not bipartite then algorithm returns an empty set. The algorithms are going to be taken from the Boost Graph Library (BGL).

  • Lengauer Tarjan dominator tree
    In a directed graph G = ( V , E , r ) where V is set of vertices, E is set of edges and r is starting vertex, a vertex v is dominated by vertex w if every possible path from starting vertex r to the vertex v goes through the vertex w . Vertex ​ w is the immediate dominator of v, denoted as idom(v) = w if w dominates v and other dominators of v dominate w. By making every idom ​ of each vertex as its parent, the dominator tree can be built.

    • Boost implemented the Lengauer-Tarjan algorithm whose time complexity is O ((V + E )log(V + E )).
    • Lengauer-Tarjan algorithm utilizes two techniques:
      • Find a semi dominator.
      • Path Compression.

  • Bipartite graph
    A bipartite graph is a graph with two sets of vertices which are connected to each other,but not within themselves. A bipartite graph G = (U, V, E), consists of a set of vertices U a disjoint set of vertices V and a set of edges E ⊂ U × V. A bipartite graph is possible if the graph coloring is possible using two colors such that vertices in a set are colored with the same color.​

    • The time complexity for the algorithm is O (V + E).
  • Two graphs common spanning trees

(This idea was dropped due to bug in boost algorithm. Instead of that implemented Bipartite graph algorithm with the permission of mentors.)
A spanning tree is a subset of Graph G, which has all the vertices covered with the minimum possible number of edges. Hence, a spanning tree does not have cycles and it cannot be disconnected.Now, imagine there are two graphs that are represented as lists of edges. A common spanning tree is a set of indices that identifies a spanning tree for both the first and for the second of the two graphs. Both graphs can have multiple common spanning trees.

  • The algorithm, based on an academic article of ​ Mint​ , ​ Read and ​ Tarjan​ , called ​ MRT, is an efficient algorithm for the common spanning tree problem.

State of the Project Before GSoC

pgRouting currently does not have these algorithms implemented.

  • Current state of pgRouting ​ doesn’t support any algorithm for finding a dominator tree. A single standard function does not exist​ .
  • pgRouting has the algorithms to find the minimum cost spanning tree using Prim’s and Kruskal’s algorithm but ​ doesn’t support any algorithm for ​ Two Graphs Common Spanning Trees.
  • And also a single standard function does not exist to check whether any graph is Bi-partite or not.

Deliverables

  1. Implementation of ​ Lengauer tarjan dominator tree for pgRouting : I need to construct a function pgr_lengauerTarjanDominatorTree() and it will return ​ the dominator tree where parents are each child's immediate dominator. Create all helper functions and header files. ​ Create documentation and tests. Prepare a report for Evaluation. ​ And ​ finalize all documentation and tests.

2​. Implementation of Bipartite graph ​for pgRouting : I need to construct a function ​ pgr_bipartite() ​ and it will return a vector which contains color of each node such that the color of two adjacent vertices are not same,if the graph is bipartite. Else it will return an empty set which shows the graph is not bipartite. Create all helper functions and header files. ​ Create documentation and tests. Prepare a report for Evaluation. ​ And ​ finalize all documentation and tests.

Detailed Proposal

Detailed Proposal in PDF format

Participants

Title GitHub Handle Name
1st Mentor cvvergara Vicky Vergara
2nd Mentor AasheeshT Aasheesh Tiwari
Student Developer prakashupes Prakash Tiwari

Timeline

Community Bonding Period (May 4th - May 17th)

  • Initial research and analysis of algorithms and requirements.
  • Set up the development environment.
  • Interact with mentors, introduce myself to the community, and actively get involved in the discussion.
  • Get familiar with pgRouting’s development style. Understand expected coding, documentation, and testing standards set by pgRouting.
  • Set up a wiki page to keep track of weekly progress.
  • 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.

(Note: After discussing with mentors I have planned to complete the work of the official coding period in the community bonding period and get 2-weeks buffer for the end semester examination. The tentative week for the examination is Week-6 and Week-7)

Week 1 (May 18th - May 25th)

  • Developing pgr_​lengauerTarjanDominatorTree().
  • Create a basic skeleton for C, C++, SQL code, and for documentation and tests.

Week 2 (May 25th - June 1st)

  • Read data from PostgreSQL.
  • Transform data to C++ containers suitable for using with Boost.

First Coding Period (June 1st - June 29th)

Week 1 (June 1st - June 8th)

  • Create the necessary class wrappers for the Boost function.
  • Process the data with the Boost function.
  • Transform results to C containers suitable for passing to PostgreSQL.

Week 2 (June 8th - June 15th)

  • Prepare user documentation.
  • Create suitable queries using the sample data of the pgRouting documentation.
  • Create the first term report.

Week 3 (June 15th - June 22nd)

  • Create the necessary class wrappers for the Boost function.
  • Process the data with the Boost function.
  • Transform results to C containers suitable for passing to PostgreSQL.

Week 4 (June 22nd - June 29th)

  • Prepare user documentation.
  • Create suitable queries using the sample data of the pgRouting documentation.
  • Create the first term report.

Second Coding Period (June 29th - July 27th)

Week 5 (June 29th - July 6th)

  • Work on feedback provided from the first evaluation.
  • Developing pgr_bipartite() starts.
  • Create a basic skeleton for C, C++, SQL code, and for documentation and tests.

Week 6 (July 6th - July 13th)

  • Read data from PostgreSQL.
  • Transform data to C++ containers suitable for using with Boost.

Week 7 (July 13th - July 20th)

  • Create the necessary class wrappers for the Boost function.
  • Process the data with the Boost function.
  • Transform results to C containers suitable for passing to PostgreSQL.

Week 8 (July 20th - July 27th)

  • Prepare user documentation.
  • Create suitable queries using the sample data of the pgRouting documentation.
  • Create the first term report.

Third Coding Period (July 27th - August 24th)

Week 9 (July 27th - August 3rd)

  • Work on feedback provided from the second evaluation.
  • Tests for function pgr_​lengauerTarjanDominatorTree().
    • create pgTap tests to check no server crash.
    • create pgTap unit tests for expected results for different small graphs:
      • one vertex graph
      • one edge graph
      • two edge graph
      • cycle graph with 3 edges

Week 10 (August 3rd - August 10th)

  • Tests for function pgr_bipartite().
    • create pgTap tests to check no server crash.
    • create pgTap unit tests for expected results for different small graphs:
      • one vertex graph
      • one edge graph
      • two edge graph
      • cycle graph with 3 edges

Week 11 (August 10th - August 17th)

Week 12 (August 17th - August 24th)

  • Preparation of final report.

Log of Pull Requests

Pull Request Description Date Status
#35 Rebase to 3.0.0 and some basic dummy function 20th May Merged
#37 [Official coding week 0] 25th May-June 1st Merged
#40 Coding of week [1] June 1st-June 7th Merged
#44 Coding of week [2] June 7th-June 14th Merged
#48 Coding of week [3] June 14th-Jun 21st Merged
#51 Coding of week[4] June 21-June 28th Merged
#55 Coding of week[5] June 29- Jul 6th Merged
#60 Coding of week[6] Jul 7th- Jul 13th Merged
#64 Coding of week[7] Jul 13th-Jul 19th Merged
#80 Coding of week[8] Jul 19th-Jul 26th Merged
#112 Coding of week[9] Jul 27th- Aug 2nd Merged
#130 Coding of week[10] Aug 3rd- Aug 10th Merged
#134 Coding of week[11] Aug 10th- Aug 16th Merged
#135 Coding of week[12] Aug 16th- Aug 23rd Merged
#1608 Final pull request August 23rd Merged
#1609 removing links from linkcheck_ignore August 24th Merged

Slides

https://docs.google.com/presentation/d/1uvQc4GUUYr1pzRH4KfwOg5YoRZ6TFC8bMQw81QUjnfA/edit?usp=drivesdk

Final Report

Hello everyone,

With GSoC coming to an end, I present to you the final report of my work over the past three months! It has been a great experience and great learning. This report is in accordance with the guidelines set by Google and OSGeo GSoC Admins.

Title - Implement Lengauer Tarjan Dominator Tree and Bipartite algorithm for pgRouting

Organisation - pgRouting under OSGeo

Abstract - This GSoC project dealt with implementing two new graph algorithms in pgRouting. The algorithms are described as follows:

  • Boost::lengauer_tarjan_dominator_tree The algorithm calculates the immediate dominator (The immediate dominator or idom of a node n is the unique node that strictly dominates n but does not strictly dominate any other node that strictly dominates n) of each vertex called idom, once idom of each vertex is calculated then by making every idom of each vertex as its parent, the dominator tree can be built.This algorithm is only applicable for directed graphs. It has a linear time complexity of O((V+E)log(V+E)).

  • Boost::is_bipartite A bipartite graph is a graph with two sets of vertices which are connected to each other, but not within themselves. A bipartite graph is possible if the graph coloring is possible using two colors such that vertices in a set are colored with the same color. This algorithm is only applicable for undirected graphs. It has a linear time complexity of O(|V| + |E|).

State of the Project Before GSoC - pgRouting currently does not have these algorithms implemented. Current state of pgRouting doesn’t support any algorithm for finding a dominator tree. And also a single standard function does not exist to check whether any graph is Bi-partite or not.

The addition that my project brought to pgRouting: The deliverables are code, documentation, documentation tests, and the pgTAP tests of the two functions.

  • Lengauer Tarjan Dominator Tree (pgr_lengauerTarjanDominatorTree) can be used to find the dominator tree of any graph or immediate dominator of any vertex. It returns the immediate dominator of each vertex. This function is applicable only for directed graphs.

  • Bipartite (pgr_bipartite) can be used to check whether a given graph is bipartite or not. If the graph is bipartite then the function returns the vertex and color. If the graph is not bipartite then the function returns an empty row. This function is applicable only for undirected graphs.

Potential Future Work

  • Edge Coloring algorithm can be implemented, which assigns the color to the edges of a graph, unlike the Bipartite graph algorithm, that assigns the colors to the vortices if the graph is bipartite.

  • The third function pgr_twoGraphsCommonSpanningTrees, can't be implemented because there was some problem in the boost algorithm itself. The algorithm was not returning the output as expected. In future if it will be fixed in boost algorithm then it can also be implemented in the pgRouting.

Links

Slide Demonstration https://docs.google.com/presentation/d/1uvQc4GUUYr1pzRH4KfwOg5YoRZ6TFC8bMQw81QUjnfA/edit?usp=drivesdk

I am so glad to have such an interesting and exciting adventure with all of you. Thanks for all your support! I will be happy if my code proves beneficial to the community.

Thanks and Regards,

Prakash Tiwari

Weekly Reports

Third Evaluation Period (July 27th - August 24th)

Week 12 (August 17th - August 24th)

What did I get done this week?

  • Created the pull request in which my weekly progress can be reviewed. Completed work for the final submission of code and made the changes suggested by the mentor.
  • Completed the user documentation for pgr_bipartite and pgr_lengaueeTarjanDominatorTree with a lot of suggations and changes these can be reviewed in week 12 PR.
  • Rebased my working branch before making PR to pgrouting/develop.
  • Created a pull request to pgrouting-develop from my working branch gsoc-prakash for final integration of the code.
  • Made the presentation for the two functions which I implemented during the program.
  • Created a tag named 2020-prakashupes-lengauerTarjanDominatorTree-bipartite.

What do I plan on doing next week?

  • Merge the final pull request which is created to the pgrouting/develop branch.
  • Submit the final report of GSoC work.
  • Complete the mentor evaluation.

Blocking Issues

It is not blocking of pgRouting. But I found the problem in boost::two_graph_common_spanning_trees it was not returning the output as they were expected, So I mailed the issue to the boost mailing list regarding this. As they will response I will continue with my rest of the coding part. Till then I started working in my next function (After discussing with mentors)that is bipartite it was an additional idea.

Meetings attended in this week

No meeting was scheduled.

Week 11 (August 10th - August 17th)

What did I get done this week?

  • Created the pull request in which my weekly progress can be reviewed. [2]
  • Fixed the rebase from the main repository.
  • Started work on the final submission of work.
  • Prepare user documentation for pgr_bipartite with an additional example of odd length cycle.
  • Created more pgTap tests for  pgr_bipartite that includes tests for odd length cycle and even length cycle.
  • Modified docquaries and output column for bipartite.

What do I plan on doing next week?

  • Refine and review the code of implemented algorithms.Add more pgTap tests of pgr_bipartite and pgr_lengauerTarjanDominatorTree Prepare user documentation with additional example of pgr_bipartite and pgr_lengauerTarjanDominatorTree.
  • Work on suggestions given by mentors.

Blocking Issues

It is not blocking of pgRouting. But I found the problem in boost::two_graph_common_spanning_trees it was not returning the output as they were expected, So I mailed the issue to the boost mailing list regarding this. As they will response I will continue with my rest of the coding part. Till then I started working in my next function (After discussing with mentors)that is bipartite it was an additional idea.

Meetings attended in this week

An individual meeting was scheduled for rebasing the branch.

Week 10 (August 3rd - August 10th)

What did I get done this week?

  • Created the pull request in which my weekly progress can be reviewed.
  • Fixed the rebase from the main repository.
  • Started work on the final submission of work.
  • Prepare user documentation with an additional example of pgr_bipartite.
  • Renamed the directory of the function Lengauer Tarjan dominator Tree from  LTDTRee to lengauerTarjanDominatorTree.
  • Fixed the coding style according to code checker. What do I plan on doing next week?
  • Refine and review the code of implemented algorithms.
  • Add more pgTap tests of pgr_bipartite and pgr_lengauerTarjanDominatorTree Prepare user documentation with additional example of pgr_bipartite and pgr_lengauerTarjanDominatorTree.
  • Work on suggestions given by mentors.

Blocking Issues

It is not blocking of pgRouting. But I found the problem in boost::two_graph_common_spanning_trees it was not returning the output as they were expected, So I mailed the issue to the boost mailing list regarding this. As they will response I will continue with my rest of the coding part. Till then I started working in my next function (After discussing with mentors)that is bipartite it was an additional idea.

Meetings attended in this week

No meeting was scheduled.

Week 9 (July 27th - August 3rd)

What did I get done this week?

  • Created the pull request in which my weekly progress can be reviewed.
  • Completed the GSoC second evaluation.
  • Complete the pgTap tests of pgr_bipartite which includes
    • no_crash_test-bipartite.sql
    • bipartite-inner-query.sql
    • bipartite-types-check.sql
    • bipartite-edges-sql.sql
  • Prepare user documentation with additional example of pgr_bipartite.
  • Renamed files of pgTap tests according to mentor suggationa.
  • Refined the code of c++ files.
  • Rebase my working branch gsoc-prakash with upstream/develop where upstream is remote of pgRouting main repository.
  • Merged the pull request of this week.

What do I plan on doing next week?

  • Refine and review the code of implemented algorithms.

  • Add more pgTap tests of pgr_bipartite and pgr_lengauerTarjanDominatorTree

  • Prepare user documentation with additional example of pgr_bipartite and pgr_lengauerTarjanDominatorTree.

Blocking Issues

It is not a blocking of pgRouting. But I found the problem in boost::two_graph_common_spanning_trees it was not returning the output as they were expected, So I mailed the issue to the boost mailing list regarding this. As they will response I will continue with my rest of coding part. Till then I started working in my next function (After discussing with mentors)that is bipartite it was an additional idea.

Meetings attended in this week

No meeting was scheduled.

Second Evaluation Period (June 29th - July 27th)

Week 8 (July 20th - July 27th)

What did I get done this week?

  • Created the pull request in which my weekly progress can be reviewed.
  • Found the problem in boost::two_graph_common_spanning_trees it was not returning the output as they were expected, So mailed the issue to the boost mailing list regarding this.
  • Created an issue in pgRouting to discuss the signature of new function that is pgr_bipartite.
  • Improved the c++ containers of pgr_lengauerTarjanDominatorTree by removing manual mapping and made suitable containers that can work with Base Graph.
  • Rebase my working branch gsoc-prakash with upstream/develop where upstream is remote of pgRouting main repository.
  • Started coding of new function boost::is_bipartite() in the pgr_bipartite for that made following files:
  • SQL files (the main signature)
    • bipartite.sql
    • _bipartite.sql
  • C/C++ Headers and files:
    • bipartite.c
    • bipartite_driver.cpp
    • bipartite_driver.h
    • pgr_bipartite_driver.hpp
    • pgr_bipartite_rt.h
  • pgTap Test files:
    • no_crash_test-bipartite.sql
    • bipartite-inner-query.sql
    • bipartite-types-check.sql
    • bipartite-edges-sql.sql
  • Doc and Docqueries:
    • pgr_bipartite.rst
    • doc-bipartite.result
    • doc-bipartite.test.sql
    • test.bipartite
  • Started and completed the coding of bipartite.sql and _bipartite.sql with the signature of pgr_bipartite(edge_sql) which returns set of (vid,color).
  • Started and completed the coding of bipartite.cfile by making and including suitable headers and functions.
  • Started and completed the coding of bipartite_driver.cpp file. Which converted the data_edge into undirected graph and also it includes all the necessary exceptions and headers.
  • Started and completed the coding of pgr_bipartite_driver.hpp. In which created proper c++ containers that can work with boost and base graph. Also called the boost::is_bipartite() algorithm. And converted the result into a vector.
  • Merged the pull request of this week.

What do I plan on doing next week?

  • Complete the GSoC evaluation.
  • Complete the pgTap tests of pgr_bipartite which includes
    • no_crash_test-bipartite.sql
    • bipartite-inner-query.sql
    • bipartite-types-check.sql
    • bipartite-edges-sql.sql
  • Prepare user documentation with additional example of pgr_bipartite.

Blocking Issues

It is not a blocking of pgRouting. But I found the problem in boost::two_graph_common_spanning_trees it was not returning the output as they were expected, So I mailed the issue to the boost mailing list regarding this. As they will response I will continue with my rest of coding part. Till then I started working in my next function (After discussing with mentors)that is bipartite it was an additional idea.

Meetings attended in this week

No meeting was scheduled.

Week 7 (July 13th - July 20th)

What did I get done this week?

  • Created the pull request in which my weekly progress can be reviewed.
  • Completed the user documentation of lengauerTarjanDominatorTree.
  • Fix the errors of Lengauer Tarjan dominator Tree docqueries.
  • Changed the signature of Two Graphs Common Spanning Trees from pgr_mrt to pgr_two_graphs_common_spanning_trees and changed all the files related to this that are mrt.c and pgrouting--3.0.0.sig.
  • Made the c++ containers and added boost::two_graphs_common_spanning_trees algorithm for undirected graph.But till now it gives a lot of errors.
  • Added docqueries files inside the doc/spanningTree folder containing doc-mrt.test.sql and doc-mrt.result.
  • Completed the user documentation of pgr_two_graphs_common_spanning_trees up till work.

What do I plan on doing next week?

  • Complete coding of c++ containers and add boost::lengauer_tarjan_dominator_tree for both undirected graph and directed graph and fix all errors.
  • Write some tests for no_crash_test-mrt.sql and mrt-edge-cases.sql
  • Prepare user documentation for two graph common spanning tree.

Meetings attended in this week

No meetings attended.

Week 6 (July 6th - July 13th)

What did I get done this week?

  • Created the pull request in which my weekly progress can be reviewed.
  • Completed the coding of SQL functions that are pgr_mrt.sql and _pgr_mrt.sql.
  • Fix the signature of Lengauer Tarjan dominator Tree. (Rename from LTDTree to lengauer_tarjan_dominator_tree).
    • Changed the name of the function in LTDTree.c file to solve the errors.
    • Changed the name of functions in pgTap tests to proper testing.
    • Changed the signature of function in pgrouting--3.0.0.sig file.
  • Able to read data from postgreSql for pgr_mrt().
  • Made the c++ containers and added boost::lengauer_tarjan_dominator_tree algorithm for undirected graph.But till now it returns 0 rows.
  • Added pgTap tests files with zero tests in spanningTree/mrt directory that contains:
  • mrt-edge-cases.sql
  • mrt-innerQuery.sql
  • no_crash_test-mrt.sql
  • pgr_mrt_types_check.sql

What do I plan on doing next week?

  • Complete coding of c++ containers and add boost::lengauer_tarjan_dominator_tree for both undirected graph and directed graph.
  • Write some tests for no_crash_test-mrt.sql and mrt-edge-cases.sql
  • Prepare user documentation for two graph common spanning tree.

Meetings attended in this week

No meeting was scheduled.

Week 5 (June 29th - July 6th)

What did I get done this week?

  • Created the pull request in which my weekly progress can be reviewed.
  • Completed the mentor evaluation in Google Summer Of Code official website.
  • Read and understand the requirements of two graph common spanning trees.
  • Started coding my SQL function pgr_mrt and _pgr_mrt.
  • Added all the required files for the implementation of pgr_mrt and _pgr_mrt function ie:
  • sql/mrt/ - CMakeLists.txt, _mrt.sql, mrt.sql
  • Added the directory in configuration.conf and Added the function signatures in sql/sigs/pgrouting--3.0.0.sig
  • Created all files of c,c++,headers, The files are:
  • SQL files:
    • mrt.sql
    • _mrt.sql
  • C/C++ Headers and files:
    • mrt.c
    • mrt_driver.cpp
    • mrt_driver.h
    • pgr_mrt_driver.hpp

What do I plan on doing next week?

  • Complete the coding of sql functions.
  • Read data from postgreSql.
  • Transform data into c++ containers suitable for using Boost C++.

Meetings attended in this week

These meetings were a part of the Bolsena Online Code Sprint 2020:

June 30th: Discussed and presented all the work I had done so far, for the GSoC '20 program, with the mentor, who reviewed the work and suggested some modifications.

July 2nd: Attended and reviewed the workshop of the MobilityDB team with pgRouting and PostGIS.

First Evaluation Period (June 1st - June 29th)

Week 4 (June 22nd - June 29th)

What did I get done this week?

  • Created the pull request in which my weekly progress can be reviewed.
  • Fixed the server got crashed when user entered any query.
  • Created function is_valid_root to handle negative vertex and vertex that are not present in the graph. Also raised exception in LTDTree.sql file.
  • Written ltdtree-edges-cases pgTap tests. Which includes:
    • 0 edge 0 vertex tests
    • Root not present tests
    • Negative root tests
    • Id constrained tests
  • Add docqueries for the documentation using the pgRouting Sample Data.
  • Completed user documentaion with suitable example.

What do I plan on doing next week?

  • Create more pgTap tests.
  • Add more suitable example in documentation.
  • Complete first term evaluation and work on feedback provided from the mentors.
  • Open an issue to discuss about the signature of next function Two Graph Common Spannig Trees.
  • Add initial sql and c\c++ files to be required to develop the function.

Am I blocked on anything?

No blocking issues.

Meetings attended in this week

No meetings are scheduled.

Week 3 (June 15th - June 22nd)

What did I get done this week?

  • Created the pull request in which my weekly progress can be reviewed.
  • Created the necessary containers for boost functions in pgr_ltdtree_driver.hpp file. And return the results vector which is type of pgr_ltdtree_rt and contains vid (vertex id) and idom (immediate dominator)
  • Created pgTap test which includes :
    • no_crash_test-ltdtree.sql
    • ltdtree-inner-query.sql
    • ltdtree-edges-cases.sql
  • Competed user documentation of up till work.

What do I plan on doing next week?

  • I have completed the boost work but server got crashed when user entered any query so fix the issue in next week.
  • Create more pgTap tests.
  • Add docqueries for the documentation using the pgRouting Sample Data.

Am I blocked on anything?

No blocking issues.

Meetings attended in this week

No meetings are scheduled.

Week 2 (June 8th - June 15th)

What did I get done this week?

  • Created the pull request in which my weekly progress can be reviewed.
  • Start coding of pgr_ltdtree_driver.hpp file. In which function template function name pgr_ltdree is defined which will return the vector of result which will further proceed in ltdtree_driver.cpp file.
  • Understand the parameters of boost::lengauer_tarjan_dominator_tree. And I planned to used the boost version in which it takes three parameters:
    • const graph: The graph object on which the algorithm will be applied.
    • vertex_descriptor entry : The dominator tree will be rooted at this vertex.
    • DomTreePredMap: The predecessor map where parents are each children's immediate dominator.
  • Extracted vertices of pgr_base_graph to make use in boost algorithm.
  • Completed documentation of uptil work.

What do I plan on doing next week?

  • Complete the requirements of boost::lengauer_tarjan_dominator_tree and make the The predecessor map.
  • Create basic tests and complete the user documentation.

Am I blocked on anything?

No blocking issues.

Meetings attended in this week

No meetings are scheduled.

Week 1 (June 1st - June 8th)

What did I get done this week?

  • Created the pull request in which my weekly progress can be reviewed.
  • Completed the code of sql function and make it capable to read data from postgres.
  • Transform the data of sql function into c++ container.
  • Created the structure name pgr_ltdtree_rt of the result tuples to store the result and transform back into sql.
  • Completed the coding of ltdtree_driver.h file in which do_pgr_ltdtree function is defined.
  • Created function template and exceptions handling inside the ltdtree_driver.cpp file.

What do I plan on doing next week?

  • Start coding of pgr_ltdtree_driver.hpp file.
  • Till now I haven't started the coding for boost::lengauer_tarjan_dominator_tree so in this week make suitable c++ containers to provide parameter for boost algorithm.

Am I blocked on anything?

No blocking issues.

Meetings attended in this week

June 2nd: Discussions regarding contraction algorithms and techniques.

June 5th: More Discussion regarding contraction, particularly area contraction. Also, learned how to use the run.sh file effectively for building and testing the files locally.

Week 0 (May 25th - May 31st)

What did I get done this week?

  • Created the pull request in which my weekly progress can be reviewed.
  • Read and understand the coding style and required files of pgRouting library.
  • Started coding my SQL function pgr_LTDTree and _pgr_LTDTree.
  • Added all the required files for the implementation of pgr_LTDTree and _pgr_LTDTree function ie:
  • sql/ltdtree/ - CMakeLists.txt, _LTDTree.sql, LTDTree.sql
  • Added the directory in configuration.conf and Added the function signatures in sql/sigs/pgrouting--3.0.0.sig
  • Created all files of c,c++,headers, doc,docqueries,pgTap. The files are:
  • C/C++ Headers and files:
    • ltdtree.c
    • ltdtree_driver.cpp
    • ltdtree_driver.h
    • pgr_ltdtree_driver.hpp
  • pgTap Test files:
    • no_crash_test-ltdtree.sql
    • ltdtree-inner-query.sql
    • ltdtree-types-check.sql
    • ltdtree-edges-sql.sql
  • Doc and Docqueries:
    • pgr_ltdtree.rst
    • doc-ltdtree.result
    • doc-ltdtree.test.sql
    • test.config

What do I plan on doing next week?

  • Complete the coding of sql functions.
  • Read data from postgreSql.
  • Transform data into c++ containers suitable for using Boost C++.

Am I blocked on anything?

No blocking issues.

Meetings attended in this week

May 26th: More discussions regarding the functionality request of the pgr_dijkstra with the combinations SQL.

May 28th: Discussion regarding Contraction Techniques in pgRouting.

Community Bonding Period (May 4th - May 25th)

  • Initial research and analysis of algorithms and requirements.
  • 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 student's 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.

Pre-Bonding Period (February 25th - March 31st)

References

[1]. Thomas Lengauer and Robert Endre Tarjan​ , A fast algorithm for finding dominators flowgraph ​ ACM Transactions on Programming Language and Systems, 1(1):121-141,1979.

[2]. Lengauer Tarjan Dominator Tree , Boost C++ Libraries Official Documentation.

[3]. ​Schach, S. R. (1983), Efficient algorithm for common spanning tree problem,Electronics Letters, 19(9), 346.

[4]. Boost: is_bipartite algorithm documentation

[5]. Wikipedia: bipartite graph

[6]. Sample Data network.

Contact: https://discourse.osgeo.org/c/pgrouting/pgrouting-dev

pgRouting Project

pgRouting Project

Quick Links

Clone this wiki locally