Hello everyone,

I’m Aditya Pratap Singh and this is my final report.

I am very happy to work with you all and learned a lot from my mentors.

**Title:**

Implement Minimum Spanning Tree and Min-Cut for pgRouting by the Boost Graph Library

**Abstract:**

A Minimum Spanning Tree in an undirected connected weighted graph is a spanning tree of minimum weight. For this I had implemented two functions that are Prim Algorithm and Kruskal Algorithm.

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. I had implemented Min-Cut by Stoer Wagner function.

**Implemented function:**

- pgr_prim()

Returns the minimum spanning tree of graph using Prim algorithm. Ideally graph should be undirected and connected but I made signature which can work on unconnected graph also.

- pgr_kruskal()

Returns the minimum spanning tree of graph using Kruskal algorithm on undirected graph.

- pgr_stoerWagner()

Returns the weight of the min-cut of graph using Stoer Wagner algorithm. Function determines a min-cut and the min-cut weight of a connected, undirected graph.

**The state before my GSoC**

pgRouting didn’t have the functionality of minimum spanning tree and min-cut. So, I implemented these function in my GSoC period.

**The addition that my project brought to pgRouting**

The deliverable are code, full documentation, documentation tests and pgTAP of those three functions.

**Pending Work:**

After implementing these function I went for implementation of Random Spanning Tree. It’s C++ code is working but it is not working in pgRouting architecture.

**Future Directions:**

- Implement full functionality of random spanning tree in pgRouting architecture and its documentation and test and pgTAP.
- Implement algorithm for Common Spanning Trees of Two Graphs using boost graph library.

**Links:**

Wiki:

https://github.com/pgRouting/pgrouting/wiki/GSoC-2018-MST-and-Mincut

Pull request with all the commits:

https://github.com/pgRouting/pgrouting/pull/1079

Tag:

https://github.com/pgRouting/pgrouting/releases/tag/gsoc2018-apslight-lw

Repository:

https://github.com/apslight/Sample-Code

Best regard,

Aditya Pratap Singh

IIT BBS, India