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 Jun 19, 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

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)

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

Plan for next week?

  • structuring include files
  • linking src, sql, include files to run the function

Blocked on anything?

  • Nothing, major.

Week 2 (June 20th - June 26th)

--

Week 3 (June 27th - July 03rd)

--

Week 4 (July 04th - July 10th)

--

Week 5 (July 11th - July 17th)

--

Week 6 (July 18th - July 24th)

--

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

Week 7 (July 25th - July 31st)

--

Week 8 (August 01st - August 07th)

--

Week 9 (August 08th - August 14th)

--

Week 10 (August 15th - August 21st)

--

Week 11 (August 22nd - August 28th)

--

Week 12 (August 29th - September 04th)

--

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 Week1: pgr_hawickCircuits June 19th, 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