GSoC 2018 MST and Mincut

PgRouting wiki page for MST and Mincut

Contents of the Wiki

• Brief Description
• State of the project before GSOC
• Project
• Log of Pull Requests
• Biography
• Weekly Report
• Community Bonding Period
  • Pre-Bonding Period
  • Timeline
• References

Brief Description

Graph connectivity is one of the classical subjects in graph theory and has many practical applications. A Minimum Spanning Tree in an undirected connected weighted graph is a spanning tree of minimum weight. For this I will implement two Functions that are Prim Algorithms and Kruskal Algorithms.

Finding the minimum cut of an edge weighted graph is a fundamental algorithmic problem. Stoer–Wagner algorithm is a recursive algorithm to solve the minimum cut problem in undirected weighted graphs with non-negative weights. The essential idea of this algorithm is to shrink the graph by merging the most intensive vertices, until the graph only contains two combined vertex sets. I will implement Min-Cut by Stoer Wagner function.

State of the project before GSOC

Current state of PgRouting do not support Minimum Spanning Tree And MinCut. My project goal is to implement Prim algotithm, Kruskal algorithms and mincut by Stoer Wagner.

Project

• Proposal
• Slides
  • Kruskal's MST
  • Prim's MST
  • Mincut
• Github Branch

Log of Pull Requests

Pull Request	Description	Date	Status
#1031	[WIP]Implementation of PRIM Algorithm	19 May 2018	Merged
#997	Doxygen documentation of get_check_data	3 Feb 2018	Merged
#975	Improve code of Class Pgr_allpairs	15 Dec 2017	Merged

Biography

• Name : Aditya Pratap Singh
• Country : India
• School : IIT Bhubaneswar
  • Degree : B.Tech in Electronics & Communication Engineering
• Email : [email protected]

Weekly Report

Week 2

Week 1

1. What did you get done this week? I generated the initial code for pgr_prim using the template pgr_dijkstra code and fix these files. And detailed can be found here [1].
   • Src Directory
     • Create CMakeLists.txt & prim.c & prim_driver.cpp
   • Include Directory
     • Create prim_driver.h
   • Sql Directory
     • Create CMakeLists.txt & prim.sql
2. What am I going to achieve for next week?
   • Full Implementation of pgr_prim
   • Create pgr_prim.hpp & pgr_prim_t.h
3. Is there any blocking issue?
   No, at the moment I’m not blocked.

• The wiki page can be found in [2]
• The repository can be found in [3]

[1] https://github.com/pgRouting/pgrouting/pull/1031

[2] https://github.com/pgRouting/pgrouting/wiki/GSoC-2018-MST-and-Mincut#week-1

[3] https://github.com/pgRouting/pgrouting/tree/gsoc/mincut

Community Bonding Period

• Set up Wiki Page
• Edit all info related to your project in OSGeo wiki.
• Get to know your mentors
• Introduce yourself and your project in SOC mailing list and your software mailing list
• Familiarize with the community practices and processes.
• Hand-Written copy of OSGeo mail (Issue #6)
• Team Work
  • Detailed explanation how PostgreSQL is connected to C function.
  • Working of C/C++ Driver
• Become familiar with the developer manuals.
• Practice pgTAP

Pre-Bonding Period

• Watch C++ video for better understanding (Issue #5)

  • https://www.youtube.com/watch?v=eidEEmGLQcU
  • https://www.youtube.com/watch?v=u5senBJUkPc
  • https://www.youtube.com/watch?v=YnWhqhNdYyk
  • https://www.youtube.com/watch?v=1OEu9C51K2A
  • https://www.youtube.com/watch?v=xnqTKD8uD64
  • https://www.youtube.com/watch?v=86xWVb4XIyE
  • Make Report

• Create demo function pgr_naziiDijkstra (Issue #4)

  • Edit the create.sh (in tools/template directory) according to need
  • Create file in src, pgtap, sql, doc, include, test of my function

• Study git branching model & commands (Issue #2)

  • Study

    • http://nvie.com/posts/a-successful-git-branching-model/
    • https://git-scm.com/doc

• Initial Tasks

  • Fork PgRouting
  • Install Dependencies
  • Build and Compile pgRouting
  • Create account on Travis and AppVeyor
  • Read https://summerofcode.withgoogle.com/terms/student
  • Read https://wiki.osgeo.org/wiki/Google_Summer_of_Code_Recommendations_for_Students
  • Write Proposal

Timeline

Community Bonding Period (April 23 - May 13 )

• Create a wiki page for TODO tasks and weekly reports.
• Learn more about fork.
• Getting familiar with the community, the BGL docs.
• Get familiar with the PgRouting architecture.
• Develop a better understanding of postGIS, postgreSQL and PL/pgsql. Get familiar with postgreSQL procedural language.
• Watch C++ videos for better understanding of C++ and STL.
• Go through pgTap for creating unit tests for PostgreSQL.

Official Coding Period ( May 14 - August 14 )

Official Coding Period Phase 1 ( May 14 - June 10 )

---

• Week 1 ( May 14 to May 21 )

  • Learn and create initial documentation of implementing functions.
  • Learn more about Boost C++ graph library using in this project.

• Week 2 ( May 22 to May 28 )

  • Learn how to implement functions for pgRouting by the BGL.
  • Go through boost related work in pgRouting for a better understanding and skills on the implementation.

• Week 3 to 4 ( May 29 to June 11 )

  • Implement pgr_prim() function.
  • Create documentation and test of pgr_prim() function.
  • Create pgTap unit test for pgr_prim() function.

First evaluation period (June 11 to June 15, 2018)

• Mentors evaluate me and I evaluate mentors of officially coding period phase 1.
• Deliver pgr_prim() function and its documentation, test and pgTap.

---

Official Coding Period Phase 2 (June 11 to July 8, 2018 )

---

• Week 5 to 7 ( June 11 to July 1 )

  • Work on the feedback as provided after the first evaluation.
  • Implement pgr_kruskal() function.
  • Create documentation and test of pgr_kruskal() function.
  • Create pgTap unit test for pgr_kruskal() function.

• Week 8 ( July 2 to July 8 )

  • Implement pgr_stoerWagnerMinCut().

Second evaluation period ( July 9 to July 13, 2018 )

• Mentors evaluate me and I evaluate the mentors of coding period phase 2.
• Deliver pgr_kruskal function and its documentation, test, pgTap and pgr_stoerWagnerMinCut() functions.

---

Official Coding Period Phase 3 ( July 9 to August 5, 2018 )

---

• Week 9 to 10 ( July 9 to July 23 )

  • Work on the feedback as provided after the second evaluation.
  • Create documentation of pgr_stoerWagnerMinCut() function.
  • Create test for the pgr_stoerWagnerMinCut() function.
  • Create pgTAp for the pgr_stoerWagnerMinCut() function.

• Week 11 to 12 ( July 24 to August 5 )

  • Work on the final submission report.
  • Rigorous bug fixes and improve documentation.
  • Prepare for the final delivery.

Final evaluation period ( August 6 to August 14, 2018 )

• Wrap up the project and submit final evaluation of my mentors of Coding Period Phase 3.
• Deliver pgr_stoerWagnerMinCut() documentation, test, pgTap.

---

References

1. ICS 161: Design and Analysis of Algorithms Lecture notes for February 6, 1996 https://www.ics.uci.edu/~eppstein/161/960206.html
2. Mechtild Stoer and Frank Wagner, A Simple Min Cut Algorithm
3. Minimum Spanning Trees and Prim's Algorithm
4. https://algs4.cs.princeton.edu/43mst/
5. Minimum Spanning Tree, https://www.scribd.com/presentation/368401579/19PrimKruskal-ppt
6. Min_cut, www.cse.iitd.ernet.in/~naveen/courses/CSL758/mfmc.ppt