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

[Prakash Tiwari]

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

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

[3]. 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/soc/attachments/20200726/f1868c95/attachment-0001.html>