[pgrouting-dev] GSoC 2020 - Lengauer Tarjan dominator Tree and Two graphs common Spanning Trees for pgRouting - Weekly Report [Week 8]

pgRouting pgrouting-dev
1

Hello Everyone,

This is my weekly report for week [8] (Jul 19th -Jul 26th). The report can also be found in the project wiki [1].

What did I get done this week?

  • Created the pull request in which my weekly progress can be reviewed. [2]
  • 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 a new function that is pgr_bipartite. [3]
  • Improved the c++ containers of pgr_lengauer_tarjan_dominator_tree 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 in my working branch gsoc-prakash
  • 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 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.

Thanks,

Prakash Tiwari

links:


[1]. [https://github.com/pgRouting/pgrouting/wiki/GSoC-2020-Lengauer-Tarjan-dominator-tree-and-Two-graphs-common-Spanning-Trees](https://github.com/pgRouting/pgrouting/wiki/GSoC-2020-Lengauer-Tarjan-dominator-tree-and-Two-graphs-common-Spanning-Trees)

[2].[https://github.com/pgRouting/GSoC-pgRouting/pull/80](https://github.com/pgRouting/GSoC-pgRouting/pull/80)

[3]. [https://github.com/pgRouting/pgrouting/issues/1498](https://github.com/pgRouting/pgrouting/issues/1498)

[4]. [https://github.com/pgRouting/pgrouting/wiki/GSoC-2020-Lengauer-Tarjan-dominator-tree-and-Two-graphs-common-Spanning-Trees#week-8-july-20th---july-27th-1](https://github.com/pgRouting/pgrouting/wiki/GSoC-2020-Lengauer-Tarjan-dominator-tree-and-Two-graphs-common-Spanning-Trees#week-8-july-20th---july-27th-1)