[
https://issues.apache.org/jira/browse/MADLIB-1071?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16008493#comment-16008493
]
Rashmi Raghu commented on MADLIB-1071:
--------------------------------------
Here is the proposed interface for this module:
-- Interface suggestion
SELECT madlib.graph_connected_components(
vertex_table, -- Vertex table
vertex_id, -- Vertix id column (NULL means use default naming)
edge_table, -- Edge table
edge_args, -- Edge arguments (NULL means use default naming)
out_table); -- Output table of connected components
out_table: TEXT. Name of the table to store the result of Connected Components.
It will contain a row for every vertex from 'vertex_table' and have the
following columns:
- vertex_id : id of the vertex
- component_id : id of the component that the vertex belongs to
Regarding the other questions:
1) Complexity of this algorithm will be related to the complexity of BFS
(breadth first search) which is O(|V|+|E|)
2) Yes, BFS can be broken out into a separate module which I highly recommend
doing. I will create a separate JIRA for that
3) All of the helper functions listed above and in the JIRA MADLIB-1101 will be
useful
> 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)
