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 May 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

Timeline

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

  • Setting up the Development Environment
  • Implementing dummy functions for better understanding.
  • Introduce myself to the community and active involvement in healthy discussions
  • Learning pgTap, BGL, and understanding the standard process in developing pgRouting.
  • Wiki page for tracking the progress of the project.

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 2 (June 20th - June 26th)

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

Week 3 (June 27th - July 03rd)

  • Reading data from user
  • SQL query

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 5 (July 11th - July 17th)

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

Week 6 (July 18th - July 24th)

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

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 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

To be added.

Slides

To be added.

Final Report

To be added.

Weekly Reports

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 [to be made] 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