[MADLIB-1071] Graph - weakly connect components

• Type: New Feature
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Fix Version/s: v1.12
• Component/s: Module: Graph
• Assignee: Nandish Jayaram
• Reporter: Frank McQuillan
• Created: 15/Feb/17 18:24
• Updated: 30/Jun/17 21:37
• Resolved: 29/Jun/17 00:22

Description

Story

As a MADlib developer, I want to implement weakly connected components (ref [0]) in an efficient and scaleable way.

Acceptance

1) Interface defined
2) Design document updated
3) Documentation and on-line help
4) IC and functional tests
5) Scale tests

References

[0] https://en.wikipedia.org/wiki/Connectivity_(graph_theory)
"A directed graph is called weakly connected if replacing all of its directed edges with undirected edges produces a connected (undirected) graph."

[1] Grails paper
http://pages.cs.wisc.edu/~jignesh/publ/Grail.pdf

[2] Grails deck
http://pages.cs.wisc.edu/~jignesh/publ/Grail-slides.pdf

[3] Grails repo with page rank example
https://github.com/UWQuickstep/Grail
https://github.com/UWQuickstep/Grail/blob/master/analytics/wcc.sql
(weakly connected components implementation)

Issue Links

• links to: GitHub Pull Request #144