GSoC 2022 Implementing hawick_circuits algorithm from Boost Graph Library to pgRouting - pgRouting/pgrouting GitHub Wiki

Table of Contents

Proposal

Brief Description

The project aims at implementing Boost Graph Library Algorithm Hawick_circuits in pgRouting. Hawick circuit is an algorithm used for searching circuits in a graph. It can be used to enumerate all the circuits in a directed multigraph. Specifically, it can also enumerate self-loops and redundant circuits caused by parallel edges which is not detected by other available algorithm for circuits.It enumerates the circuits in linear order of vertex.This algorithm is an extension of johnson’s algorithm for circuits and presents a memory efficient and high-performance implementation.

State of the Project Before GSoC

Currently, there is 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.

Benefits to the Community

  • Hawick_circuit function can help solve various real-world problems. Circuits occur as a natural data-mining pattern in several real-world applications. They appear naturally in food webs, where circuits highlight cyclic dependencies, often revealing the fragile parts of an ecosystem. In financial transaction data, a circuit could be an indication of a money-laundering scheme. In biological and complex networks, a circuit is an indication of a feedback mechanism. Despite the wide range of use cases, circuits, although not extensively studied, is thus a problem of considerable importance.

  • So, depending on different domains, suitable interesting properties can be extracted from the circuits. For Example: For a Road network domain the connectivity of nodes in the graph is an important feature that can be extracted using vertex contribution to the circuit. Similarly for a Delivery agency knowing all the circuits can help them manage their resources more efficiently. They can select a good warehouse location on knowing how much that location contributes to the overall network of circuits.

  • Different functionality using hawick_circuit function such as counting the total no. of circuits, vertex popularity in circuits, or vertex contribution to the connectivity of the graph , length of the available longest circuit, distribution of circuits length,maximum mean weight cycle, etc can be implemented.

  • These properties are important for analyzing various networks. If you want to know more about how these properties are useful. Please refer to the publication Node Importance Ranking and Scaling Properties of some Complex Road Networks. This publication consists of the analysis of trunk road networks for Scotland and the North and South New Zealand islands.

  • There are various other applications such as social graphs, workflow tasks, Kauffman networks, trade networks etc where circuits represent important properties.

  • Also implementing Boost::hawick_circuits in pgRouting will add more functionality to pgRouting. It will help future users and developers to use it and integrate it with other pgRouting algorithms.

Deliverables

The deliverables for the proposal would be:

  • Implementation of Boost::hawick_circuits
  • SQL Queries to run the implemented function with self-documentation
  • Users' Documentation of the function
  • pgTap test cases
  • Wiki page of the function

Detailed Proposal

Detailed Proposal in PDF format

Participants

Title GitHub Handle Name
1st Mentor @Veenits123 Veenit Kumar
2nd Mentor @dkastl Daniel Kastl
Student Developer @nitishchauhan0022 Nitish Chauhan

Weekly Report And Plan

Community Bonding Period (May 20th - June 12th)

  • Introduced myself and my project to the community mailing lists.
  • Created a wiki page, where I will update my weekly work and report.
  • Updated the OSGeo Accepted Students wiki page.
  • Created a public repository, where I will be contributing this GSoC period.
  • Studied GSoC students guide and the OSGeo's specific recommendation for students
  • Participated in an introduction meeting with the mentors where I got to know how to create the branch in which I will be working on the coding period, the file structure and QGIS.
  • Get familiar with pgRouting’s development style. Understand expected coding, documentation, and testing standards set by pgRouting.
  • Set up the development environment.

First Coding Period (June 13th - July 24th)

Week 1 (June 13th - June 19th)

  • Basic Skeleton for documentation and tests
  • Code skeleton Of SQL, C, and C++ code

Week 1 Report

Work done this week?

Structuring of the following files :

  • src/circuits/CMakeLists.txt

  • src/circuits/hawickCircuits.c

  • src/circuits/hawickCircuits_driver.cpp

  • sql/circuits/CMakeLists.txt

  • sql/circuits/hawickCircuits.sql

  • sql/circuits/_hawickCircuits.sql

  • Pr with this week work #211

Blocked on anything?

  • Nothing, major.

Week 2 (June 20th - June 26th)

  • Design pgr_hawick_circuit( ) function
  • Necessary class wrappers for the Boost function

Week 2 Report

Work done this week?

  • Added the CMakeLists.txt for doc directory
  • Created c_type circuits_rt for outputting the circuit result
  • Modified the hawickCircuit.c for outputting the circuit array
  • Did some requested changes
  • Pr with this week work #218

Blocked on anything?

  • For some time, on how to output the array but solved it myself by referencing other functions.

Week 3 (June 27th - July 03rd)

  • Reading data from user
  • SQL query

Week 3 Report

Work done this week?

  • created the function logic header file
  • fixed some linting errors
  • uncommenting the CMake lists and adding the circuit to the configuration file
  • Pr with this week work #223

Blocked on anything?

  • Nothing Major

Week 4 (July 04th - July 10th)

  • Pipeline to process data from SQL query to C function
  • C driver to use the c++ boost function

Week 4 Report

Work done this week?

  • This week I have worked majorly on resolving errors in the function pipeline to get the results.
  • Pr with this week work #228

Blocked on anything?

  • Nothing Major

Week 5 (July 11th - July 17th)

  • Implementing pgr_hawick_circuit()
  • Helper Functions

Week 5 Report

Work done this week?

  • change of outputting circuit design from array to path with the help of dijakstraVia
  • Solving error to get query output
  • Creating the documentation
  • Pr with this week work #231

Blocked on anything?

  • Got stucked for sometime in outputting the queries, solved in the twitch stream
  • Unable to locate linkcheck error in documentation

Week 6 (July 18th - July 24th)

  • Finalizing the proposed function to get the solution
  • Preparing the First coding report

Week 6 Report

Work done this week?

  • work on hawickCircuit.hpp
  • documentation changes to the pgRouitng standard
  • types_check pgtap test
  • change of output design to include end_vid
  • Pr with this week work #235

Blocked on anything?

  • Nothing Major

Second Coding Period (July 25th - September 04th)

Week 7 (July 25th - July 31st)

  • Work on the feedback as provided from the First Evaluation
  • Bug fixing
  • Preparing second coding period Synopsis

Week 7 Report

Work done this week?

  • Improving circuit driver implementation
  • changing the visitor and function logic from struct to class (pgRouitng standard)
  • making the visitor ready to output to the circuit container
  • improved the error handling in function logic
  • running the function with output up to the node, will be continuing next week with the remaining columns to be filled
  • pushed the example function for reference
  • Pr with this week work #242

Blocked on anything?

  • Nothing

Week 8 (August 01st - August 07th)

  • Internal tests for pgr_hawick_circuits
  • No server crash test
  • pgTap Unit tests.

Week 8 Report

Work done this week?

  • pgtap edge_case
  • characteristic of the documentation
  • vector to deque datatype
  • fixing errors and improving the structure
  • Pr with this week work #248

Blocked on anything?

  • Having diffculties in converting the circuit output of vertex descriptors to path (edge descriptor) and using edge properties to fill up the remaining return columns.

Week 9 (August 08th - August 14th)

  • Developer and User’s Documentation
  • Suitable Query using sample data on pgRouting documentation.

Week 9 Report

Work done this week?

  • pgtap edge_case
  • characteristic of the documentation
  • vector to deque datatype
  • fixing errors and improving the structure
  • Pr with this week work #251

Blocked on anything?

  • Nothing Major

Week 10 (August 15th - August 21st)

  • Fixing remaining bugs, tests and documentation details
  • Wiki page

Week 10 Report

Work done this week?

  • improving pgtap test edge_cases
  • improved the structure of circuit visitor
  • output result correction
  • Pr with this week work #253

Blocked on anything?

  • nothing major, got some errors in edge_cases, will be resolving them next week

Week 11 (August 22nd - August 28th)

  • Preparing for Final Delivery
  • Integrating to develop branch in the main repository

Week 11 Report

Work done this week?

  • FOSS4G presentation
  • Changing pgtap edge cases to previous version sample data
  • Pr with this week work #256

Blocked on anything?

  • Nothing

Week 12 (August 29th - September 04th)

  • Preparation of the final report

Week 12 Report

Work done this week?

  • Developer Documentation
  • Improved User's Documentation
  • Preparation of the final report
  • Pr with this week work #259

Log of Pull Requests

Link to all the Pull Requests made in GSoC-pgRouting repository nitish-2022 branch

Pull Request Description Date Status
#211 GSoC-2022 Week-01: pgr_hawickCircuits June 19th, 2022 Merged
#218 GSoC-2022 Week-02: pgr_hawickCircuits June 26th, 2022 Merged
#223 GSoC-2022 Week-03: pgr_hawickCircuits July 3rd, 2022 Merged
#228 GSoC-2022 Week-04: pgr_hawickCircuits July 10th, 2022 Merged
#231 GSoC-2022 Week-05: pgr_hawickCircuits July 17th, 2022 Merged
#235 GSoC-2022 Week-06: pgr_hawickCircuits July 24th, 2022 Merged
#242 GSoC-2022 Week-07: pgr_hawickCircuits July 31st, 2022 Merged
#248 GSoC-2022 Week-08: pgr_hawickCircuits Aug 07th, 2022 Merged
#251 GSoC-2022 Week-09: pgr_hawickCircuits Aug 14th, 2022 Merged
#253 GSoC-2022 Week-10: pgr_hawickCircuits Aug 21st, 2022 Merged
#256 GSoC-2022 Week-11: pgr_hawickCircuits Aug 28th, 2022 Merged
#259 GSoC-2022 Week-12: pgr_hawickCircuits Sep 02nd, 2022 Merged

FOSS4G presentation Slides

Slides

Final Report

(The below report was sent to the GSoC mailing list of OSGeo which can be found here) [SoC] (https://lists.osgeo.org/pipermail/soc/2022-September/004966.html) [pgRouting-Dev] (https://lists.osgeo.org/pipermail/pgrouting-dev/2022-September/002323.html)

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:

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

Community Bonding Period (May 20th - June 12th)

Tasks

  • Request writing access to the OSGeo wiki, for editing all info related to my project.
  • 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.
  • Studied GSoC students guide and the OSGeo recommendations for students.
  • Introduce myself and my project on OSGeo's SOC and pgrouting-dev 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.
  • Created a public repository GSoC-pgRouting where all my works are reflected in the GSoC period.
  • Learned how and where to create Pull Request, merge and how to commit, etc.
  • Created a new branch named nitish-2022 in the GSoC-pgRouting repository, where I will be merging all the Pull Requests.

Meeting Discussions

  1. June 3rd

    • First official introductory meeting with the mentors.
    • Repository preparation of GSoc pgRouting.
    • Understood the files and structures of functions.

  2. June 22nd

    • Learned about code structures.
    • Learned about the workflow of different directories

  3. July 1st

    • Review of the PR.
    • Learned about the docqueries.

  4. July 6th

    • Learned various developer techniques.
    • Learned about the output result datatype

  5. July 20th

    • Review of the PR.
    • Task assignment for further session

Pre-Bonding Period (March 07th - April 19th)

References

  1. https://www.boost.org/doc/libs/1_78_0/libs/graph/doc/hawick_circuits.html
  2. https://www.boost.org/doc/libs/1_61_0/boost/graph/hawick_circuits.hpp
  3. https://www.researchgate.net/publication/221440635_Enumerating_Circuits_and_Loops_in_Graphs_with_Self-Arcs_and_Multiple-Arcs
  4. DOI:10.1137/0204007 Finding All the Elementary Circuits of a Directed Graph - Donald B. Johnson
  5. https://www.baeldung.com/cs/path-vs-cycle-vs-circuit
  6. Enumeration of the Elementary Circuits of a Directed Graph (cornell.edu)
  7. Node importance ranking and scaling properties of some complex road networks
  8. DOI:10.1145/362814.362819 An efficient search algorithm to find the elementary circuits of a graph
  9. https://docs.pgrouting.org/2.4/en/sampledata.html
  10. https://github.com/pgRouting/pgrouting