Skip to content

GSoC 2022 Implementing hawick_circuits algorithm from Boost Graph Library to pgRouting

Jump to bottom Edit New page
Nitish Chauhan edited this page Jul 31, 2022 · 27 revisions

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 and hawick_circuit_unique 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 , Boost::hawick_unique_circuits function
  • 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

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

Blocked on anything?

  • Nothing, major.

Week 2 (June 20th - June 26th)

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

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

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

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

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

Work done this week?

  • This week I have worked majorly on resolving errors in the function pipeline to get the results.

Blocked on anything?

  • Nothing Major

Week 5 (July 11th - July 17th)

  • Implementing pgr_hawick_circuit() & pgr_hawick_unique_circuit()
  • Helper Functions

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

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

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

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

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

Blocked on anything?

  • Nothing

Week 8 (August 01st - August 07th)

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

Week 9 (August 08th - August 14th)

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

Week 10 (August 15th - August 21st)

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

Week 11 (August 22nd - August 28th)

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

Week 12 (August 29th - September 04th)

  • Preparation of the final report

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-1: pgr_hawickCircuits June 19th, 2022 Merged
#218 GSoC-2022 Week-2: pgr_hawickCircuits June 26th, 2022 Merged
#223 GSoC-2022 Week-3: pgr_hawickCircuits July 3rd, 2022 Merged
#228 GSoC-2022 Week-4: pgr_hawickCircuits July 10th, 2022 Merged
#231 GSoC-2022 Week-5: pgr_hawickCircuits July 17th, 2022 Merged
#235 GSoC-2022 Week-6: pgr_hawickCircuits July 24th, 2022 Merged
#242 GSoC-2022 Week-7: pgr_hawickCircuits July 31st, 2022 Merged

Final Report

To be added.

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

To be added.

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

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

pgRouting Project

pgRouting Project

Quick Links

Clone this wiki locally