[
https://issues.apache.org/jira/browse/MADLIB-1071?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16070760#comment-16070760
]
Frank McQuillan commented on MADLIB-1071:
-----------------------------------------
have been testing this and it seems to work OK (without grouping yet)
Load some data
{code}
DROP TABLE IF EXISTS vertex, edge;
CREATE TABLE vertex(
id INTEGER
);
CREATE TABLE edge(
src INTEGER,
dest INTEGER,
user_id INTEGER
);
INSERT INTO vertex VALUES
(0),
(1),
(2),
(3),
(4),
(5),
(6),
(10),
(11),
(12),
(13),
(14),
(15),
(16);
INSERT INTO edge VALUES
(0, 1, 1),
(0, 2, 1),
(1, 2, 1),
(1, 3, 1),
(2, 3, 1),
(2, 5, 1),
(2, 6, 1),
(3, 0, 1),
(5, 6, 1),
(6, 3, 1),
(10, 11, 2),
(10, 12, 2),
(11, 12, 2),
(11, 13, 2),
(12, 13, 2),
(13, 10, 2),
(15, 16, 2),
(15, 14, 2);
{code}
Run WCC
{code}
DROP TABLE IF EXISTS wcc_out;
SELECT madlib.weakly_connected_components(
'vertex', -- Vertex table
'id', -- Vertix id column
'edge', -- Edge table
'src=src, dest=dest', -- Comma delimted string of edge
arguments
'wcc_out'); -- Output table of weakly connected
components
SELECT * FROM wcc_out ORDER BY component_id, id;
{code}
produces
{code}
id | component_id
----+--------------
0 | 0
1 | 0
2 | 0
3 | 0
5 | 0
6 | 0
4 | 4
10 | 10
11 | 10
12 | 10
13 | 10
14 | 14
15 | 14
16 | 14
(14 rows)
{code}
> 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: Nandish Jayaram
> 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.4.14#64029)
