[
https://issues.apache.org/jira/browse/MADLIB-1071?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16006997#comment-16006997
]
Frank McQuillan edited comment on MADLIB-1071 at 5/11/17 8:04 PM:
------------------------------------------------------------------
[[email protected]]
could you kindly post the interface you are thinking about for this module?
Other questions that come to mind:
1) Do we know time complexity yet?
2) Are there any traversal algos that we can break out as separate module in
the course of doing this implementation? e.g., BFS?
3) Are there any helper functions that we should provide once we have a
connected components table? I opened a separate JIRAs
https://issues.apache.org/jira/browse/MADLIB-1101 but here are examples:
* Set of all nodes which can be reached (have a path) from a specified vertex
* Are 2 specified vertices connected or not
* Count of connected components clusters
* Histogram of connected component sizes
* Get biggest component
* others?
was (Author: fmcquillan):
[[email protected]]
could you kindly post the interface you are thinking about for this module?
Other questions that come to mind:
1) Do we know time complexity yet?
2) Are there any traversal algos that we can break out as separate module in
the course of doing this implementation? e.g., BFS?
3) Are there any helper functions that we should provide once we have a
connected components table? I guess these would be separate JIRAs but here are
a cpl examples:
* Set of all nodes which can be reached (have a path) from a specified vertex
* Are 2 specified vertices connected or not
* Count of connected components clusters
* Histogram of connected component sizes
* Get biggest component
* others?
> Graph - weakly connect components
> ---------------------------------
>
> Key: MADLIB-1071
> URL: https://issues.apache.org/jira/browse/MADLIB-1071
> Project: Apache MADlib
> Issue Type: New Feature
> Components: Module: Graph
> Reporter: Frank McQuillan
> Assignee: Rashmi Raghu
> Fix For: v1.12
>
>
> 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)
--
This message was sent by Atlassian JIRA
(v6.3.15#6346)
