[FLINK-1526] Add Minimum Spanning Tree library method and example

• Type: New Feature
• Status: Closed
• Priority: Not a Priority
• Resolution: Won't Fix
• Component/s: Library / Graph Processing
• Labels: algorithm auto-deprioritized-major auto-deprioritized-minor auto-unassigned
• Assignee: Unassigned
• Reporter: Vasia Kalavri
• Created: 11/Feb/15 14:57
• Updated: 19/Oct/22 11:28
• Resolved: 19/Oct/22 11:28

Description

This issue proposes the addition of a library method and an example for distributed minimum spanning tree in Gelly.

The DMST algorithm is very interesting because it is quite different from PageRank-like iterative graph algorithms. It consists of distinct phases inside the same iteration and requires a mechanism to detect convergence of one phase to proceed to the next one. Current implementations in vertex-centric models are quite long (>1000 lines) and hard to understand.
You can find a description of the algorithm here and here .

Issue Links

• links to: GitHub Pull Request #3284