[pgrouting-dev] GSoC 2022 - Final Report: Implementing hawick_circuits algorithm from Boost Graph Library to pgRouting

[Nitish Chauhan]

Hello everyone,

With GSoC coming to an end, This mail serves as the final report of my work
over the past three months! It has been an incredible experience! This
report is in accordance with the guidelines set by Google [1] and OSGeo
GSoC Admins [2].

*Title:* GSoC 2022 Implementing hawick_circuits algorithm from Boost Graph
Library to pgRouting

*Organization:* pgRouting under OSGeo

*Abstract:* The GSoC project has implemented the Boost Graph Library
Algorithm Hawick_circuits in pgRouting. Hawick circuit is an algorithm used
for searching for circuits in a graph. It can be used to enumerate all the
circuits in a directed multigraph, it can also enumerate self-loops and
redundant circuits. It enumerates the circuits in the linear order of
vertex. This algorithm is an extension of johnson’s algorithm for circuits
and presents a memory-efficient and high-performance implementation. It has
a time complexity of the order of `O((v+e)(c+1))` where c represents the
circuit count.

*State of the Project Before GSoC:* Previously, there was no algorithm
implemented in pgRouting for searching or enumerating circuits in
pgRouting. Detecting and enumerating circuits in graphs is of fundamental
importance for analyzing graphs. This project has added this functionality
to pgRouting.

*The addition that my project brought to pgRouting:* The deliverables are
code, documentation, documentation tests, and the pgTAP tests of the
function.
Hawick Circuit (pgr_hawickcircuit) can be used to get all the distinct
circuits present in a graph. End users can view all of the circuits in a
single go with properties such as the cost and length of these circuits.
These circuits can be used to get a deep analysis of the respective graph.

*Potential Future Work:*

   - In the near future, we can implement the other variation of the
   algorithm, which can help us count and show the parallel circuits as well.
   - General metric function can be developed over the top of a circuit
   which can expose metrics such as median circuit length, node importance
   over its occurrence in a circuit, and various other of these kinds.


*Links:*

   - *Tags:*
      - *Hawick Circuits
      (2022-nitish-hawickcircuit-function):
https://github.com/pgRouting/GSoC-pgRouting/releases/tag/2022-nitish-hawickcircuit-function
      <https://github.com/pgRouting/GSoC-pgRouting/releases/tag/2022-nitish-hawickcircuit-function>*
   - *Pull Requests:*
      - *Final Pull Request: *(#2363) Experimental Function -
      pgr_hawickCircuits
* (https://github.com/pgRouting/pgrouting/pull/2363
      <https://github.com/pgRouting/pgrouting/pull/2363>) *
      - *Intermediate pull requests:*
      https://github.com/pgRouting/pgrouting/wiki/GSoC-2022-Implementing-hawick_circuits-algorithm-from-Boost-Graph-Library-to-pgRouting#log-of-pull-requests
   - *Project Documentation (Wiki Page): *
   https://github.com/pgRouting/pgrouting/wiki/GSoC-2022-Implementing-hawick_circuits-algorithm-from-Boost-Graph-Library-to-pgRouting
   - *Example Image:*
      - *pgr_hawickCircuits:*
      https://drive.google.com/file/d/1WtcR8tBdBi7d9o4CeukFhC0FB-yfBeu2/view?usp=sharing
   - *FOSS4g Work Presentation:*
      - *Slide Demonstration:*
      https://docs.google.com/presentation/d/1SnS1JBCrSF-earc5u3f0fux87qJFpxq-p343x1ZHiko/edit?usp=sharing

I am thrilled to be a part of the incredible GSoC community. There have
been many ups and downs, and I have learned a lot from them, which I am
confident will benefit me in my future development journey. I would be
delighted if my code is useful to the community. Finally, thanks to all of
you for your encouragement and this wonderful opportunity! Looking forward
to contributing more and growing with the community.
Thanks and regards,
Nitish Chauhan

[1] https://developers.google.com/open-source/gsoc/help/work-product
[2] https://lists.osgeo.org/pipermail/soc/2022-September/004962.html
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20220911/7dc970f0/attachment-0001.htm>