GSoC 2018 MST and Mincut - pgRouting/pgrouting GitHub Wiki

PgRouting wiki page for MST and Mincut

Contents of the Wiki

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

Log of Pull Requests

Pull Request Description Date Status
#1079 GSoC'18 MST and Mincut 01 August 2018 Merged
#1075 Compile my work with gcc7 31 July 2018 Merged
#1071 [WIP] Implementation of random spanning tree 29 July 2018 Merged
#1069 [WIP] Basic code for pgr_randomSpanningTree 22 July 2018 Merged
#1063 Documentation, test, pgTAP for pgr_stoerWagner 15 July 2018 Merged
#1056 pgTAP for pgr_kruskal and Implementation of pgr_stoerWagner 8 July 2018 Merged
#1054 [WIP]Documentation of pgr_kruskal 1 July 2018 Merged
#1051 C++ implementation of pgr_kruskal 24 June 2018 Merged
#1047 [WIP] Basic code of pgr_kruskal 17 June 2018 Merged
#1044 Implementation of pgr_prim with refined signature 14 June 2018 Merged
#1041 [WIP] PgTap Tests for pgr_prim 10 June 2018 Merged
#1038 [WIP] Documentation and Implementation of pgr_prim 3 June 2018 Merged
#1035 [WIP] Full Implementation of pgr_prim(c/c++) 27 May 2018 Merged
#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

Weekly Report

Final evaluation period

Week 12

Tag: https://github.com/pgRouting/pgrouting/releases/tag/gsoc2018-apslight-lw
Goole presentation : https://docs.google.com/presentation/d/1g46CsdTEdZLpsAKNOWfI7R6A2QX6_3ycjFf1fUzMri0/edit?usp=sharing

  1. What did you get done this week?

    • Compile my project code with gcc7
    • Make a google presentation of my project.
      Detailed can be found here [1][2].

  2. What am I going to achieve for next week?
    Make final report and complete the final evaluation.

  3. Is there any blocking issue?
    No, at the moment I’m not blocked.

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

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

[2] https://github.com/pgRouting/pgrouting/pull/1079

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

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

Week 11

  1. What did you get done this week? I implemented c++ code of random_Span_Tree [1] and implemented in pgRouting for undirectred graph only. To run this function graph must be connected so I used connectedComponent function in sql code. Detailed can be found here [2].

  2. What am I going to achieve for next week?

    • I'll clean unused code.
    • Is to make the code compatible with some changes in develop branch.
    • Do small presentation of implemented function.

  3. Is there any blocking issue?
    No, at the moment I’m not blocked.

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

[1] https://github.com/apslight/Sample-Code/blob/master/randomSpanningTree/randomSpanTree.cpp

[2] https://github.com/pgRouting/pgrouting/pull/1071

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

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

Week 10

  1. What did you get done this week? Read about RandomSpanningTree

    RandomSpanningTree

    The random_spanning_tree() function generates a random spanning tree on a directed or undirected graph. The algorithm used is Wilson's algorithm. There must be a path from every non-root vertex of the graph to the root; the algorithm typically enters an infinite loop when given a graph that does not satisfy this property, but may also throw the exception loop_erased_random_walk_stuck if the search reaches a vertex with no outgoing edges. Both weighted and unweighted versions of random_spanning_tree() are implemented. In the unweighted version, all spanning trees are equally likely. In the weighted version, the probability of a particular spanning tree being selected is the product of its edge weights.

    References:

    Prepare Basic code of randomSpanningTree(). Detailed can be found here [1].

  2. What am I going to achieve for next week?

    • I'll implement random_spanning_tree() and write documentation.

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

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

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

Week 9

  1. What did you get done this week? Use connenctedComponent function for pgr_stoerWagner query because it only works on connected graph and create documentation, tests, pgTAP for pgr_stoerWagner. Detailed can be found here [1].

    • Tests Dir
      • doc-stoerWagner.result
      • doc-stoerWagner.test.sql
      • test.conf
    • Documentation
      • doc-pgr_stoerWagner.queries
      • pgr_stoerWagner.rst
    • pgTAP
      • compare.test.sql
      • stoerWagner-innerQuery.sql
      • stoerWagner-types-check.sql

  2. What am I going to achieve for next week?

    • I'll study about random_spanning_tree( ) and implement basic code.

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

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

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

Second evaluation period

Week 8

  1. What did you get done this week? Create pgTAP for pgr_kruskal and prepare basic code and implement pgr_stoerWagner. Detailed can be found here [1].

    • PgTap Directory of mst
      • Create kruskal-innerQuery.sql
      • Create kruskal-types-check.sql
      • Modified compare.test.sql

    Signature of stoerWagner algorithm:

    seq | edge | cost | mincut

  2. What am I going to achieve for next week?

    • Refine signature of pgr_stoerWagner and then implement test, pgTAP, documentation.

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

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

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

Week 7

  1. What did you get done this week? Refine signature and implemented test and documentation of pgr_kruskal and changed prim directory to mst directory. Detailed can be found here [1].

    Refined Signature of kruskal algorithm:

    seq | component | edge | cost | tree_cost
    • Test Directory
      • Create doc-kruskal.result
      • Create doc-kruskal.test.sql
    • Doc Directory
      • Modified CMakeLists.txt
      • Create doc-pgr_kruskal.queries
      • Create pgr_kruskal.rst

  2. What am I going to achieve for next week?

    • Create pgTAP of pgr_kruskal function and then start with min-cut algorithm.

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

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

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

Week 6

  1. What did you get done this week? Implemented the kruskal algorithm and then add the connected component to get the minimum spanning tree of each subgraph. Detailed can be found here [1].
    Current Signature of kruskal algorithm: 
    seq | sub_graph | edge | cost | tree_cost
  2. What am I going to achieve for next week?
    • Refine signature and add test, documentation and pgTAP.
  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/1051

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

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

Week 5

  1. What did you get done this week? I refined the signature of pgr_prim and add new documentation and it's pgTap [1]. Create basic code of kruskal algorithm [2].

    • Src Directory
      • Create prim.c & prim_driver.cpp
    • Include Directory
      • Create prim_driver.h & pgr_kruskal.hpp
    • Sql Directory
      • Create prim.sql

  2. What am I going to achieve for next week?

    • I'll implement pgr_kruskal and if time permit then add documentation.

  3. Is there any blocking issue?
    No, at the moment I’m not blocked.

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

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

[2] https://github.com/pgRouting/pgrouting/pull/1047

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

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

First evaluation period

Week 4

  1. What did you get done this week? I added pgTAP for pgr_prim and refining signature, column names and output results. Detailed can be found here [1].
    • pgTAP Directory
      • Create 'compare.test.sql'
      • Create 'prim-innerQuery.sql'
      • Create 'prim-types-check.sql'
    • Refining Signatures
      Old Signature: 
      seq | prim_tree | start_node | end_node | edge | cost | agg_cost
      New Signature: 
      seq | root_vertex | node | edge | cost | agg_cost | tree_cost
  2. What am I going to achieve for next week?
    • I'll add the functionality of multiple root_vertex and then start with kruskal algorithm.
  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/1041

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

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

Week 3

  1. What did you get done this week? I uses connected component for disconnected graph to get minimum spanning tree of all sub-graph. I added the functionality of choosing root vertex. Detailed can be found here [1].
    • Include Directory
      • Fix pgr_prim.hpp
    • Test Directory
      • Create 'test.conf'
      • Create 'doc-prim.result'
      • Create 'doc-prim.test.sql'
    • Doc Directory
      • Create 'CMakeLists.txt'
      • Create 'doc-pgr_prim.queries'
      • Create 'pgr_prim.rst'
  2. What am I going to achieve for next week?
    • Create pgTAP of pgr_prim function and if time permit then start with kruskal algorithm.
  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/1038

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

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

Week 2

  1. What did you get done this week? Get more familiar with pgRouting architecture and implemented pgr_prim function. I tested with pgRouting sample data and with other data and now it is working. Detailed can be found here [1].
    • Include Directory
      • Create pgr_prim.hpp
      • Create pgr_prim_t.h
      • Deleted pgr_primGraph.hpp
      • Fix pgr_prim.hpp
  2. What am I going to achieve for next week?
    • Fix some bug of pgr_prim if found
    • Create test, documentation and pgTAP of pgr_prim function.
  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/1035

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

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

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

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