/* ----------------------------------------------------------------------- *//**
 *
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 *
 *
 * @file graph.sql_in
 *
 * @brief SQL functions for graph analytics
 * @date June 2017
 *
 * @sa Provides various graph algorithms.
 *
 *//* ----------------------------------------------------------------------- */
m4_include(`SQLCommon.m4')


/**
@addtogroup grp_wcc

<div class="toc"><b>Contents</b>
<ul>
<li><a href="#wcc">Weakly Connected Components</a></li>
<li><a href="#rlcc">Retrieve Largest Connected Component</a></li>
<li><a href="#hist">Build Histogram</a></li>
<li><a href="#samecpt">Check Vertices in Same Connected Component</a></li>
<li><a href="#reach">Retrieve Reachable Vertices</a></li>
<li><a href="#count">Count Connected Components</a></li>
<li><a href="#examples">Examples</a></li>
</ul>
</div>

@brief Find all weakly connected components of a graph.

Given a directed graph, a weakly connected component (WCC) is a subgraph of
the original graph where all vertices are connected to each other by some path,
ignoring the direction of edges. In case of an undirected graph, a weakly
connected component is also a strongly connected component.  This module also
includes a number of helper functions that operate on the WCC output.

@anchor wcc
@par Weakly Connected Components
<pre class="syntax">
weakly_connected_components( vertex_table,
            vertex_id,
            edge_table,
            edge_args,
            out_table,
            grouping_cols
          )
</pre>

\b Arguments
<dl class="arglist">
<dt>vertex_table</dt>
<dd>TEXT. Name of the table containing the vertex data for the graph. Must contain the
column specified in the 'vertex_id' parameter below.</dd>

<dt>vertex_id</dt>
<dd>TEXT, default = 'id'. Name of the column in 'vertex_table' containing
vertex ids.  The vertex ids are of type INTEGER with no duplicates.
They do not need to be contiguous.</dd>

<dt>edge_table</dt>
<dd>TEXT. Name of the table containing the edge data. The edge table must
contain columns for source vertex and destination vertex.</dd>

<dt>edge_args</dt>
<dd>TEXT. A comma-delimited string containing multiple named arguments of
the form "name=value". The following parameters are supported for
this string argument:
  - src (INTEGER): Name of the column containing the source vertex ids in the edge table.
                   Default column name is 'src'.
  - dest (INTEGER): Name of the column containing the destination vertex ids in the edge table.
                    Default column name is 'dest'.</dd>

<dt>out_table</dt>
<dd>TEXT. Name of the table to store the component ID associated with each vertex.
It will contain a row for every vertex from 'vertex_table' with
the following columns:
  - vertex_id : The id of a vertex. Will use the input parameter 'vertex_id' for column naming.
  - component_id : Component that the vertex belongs to.
  We use the convention where 'component_id' is the id of
  the first vertex in a particular group.  It means that component ids
  are generally not contiguous.
  - grouping_cols : Grouping column (if any) values associated with the vertex_id.

A summary table named <out_table>_summary is also created. This is an internal
table that keeps a record of some of the input parameters and is used by the
weakly connected component helper functions.
</dd>

<dt>grouping_cols (optional)</dt>
<dd>TEXT, default: NULL. A single column or a list of comma-separated
columns that divides the input data into discrete groups, which are
treated independently as separate graphs.
When this value is NULL, no grouping is used and
weakly connected components are generated for all data
(single graph).
@note Expressions are not currently supported for 'grouping_cols'.</dd>

</dl>

@note On a Greenplum cluster, the edge table should be distributed
by the source vertex id column for better performance.
In addition, the user should note that this
function creates a duplicate of the edge table (on Greenplum cluster) for
better performance.

@anchor rlcc
@par Retrieve Largest Connected Component

The largest connected component retrieval function finds the largest weakly
connected component(s) in a graph. If weakly connected components was run with
grouping, the largest connected components are computed for each group.

<pre class="syntax">
graph_wcc_largest_cpt( wcc_table,
                      largest_cpt_table
                     )
</pre>

\b Arguments
<dl class="arglist">
<dt>wcc_table</dt>
<dd>TEXT. Name of the table that contains the output of weakly connected
components.</dd>

<dt>largest_cpt_table</dt>
<dd>TEXT. Name of the output table that contains the largest component's
information. It contains one or more rows for every group and has the following
columns:
  - grouping_cols: The grouping columns given in the creation of wcc_table.
  If there are no grouping columns, this column is not created.
  - component_id: The ID of the largest component.  Recall that we use the
  convention where 'component_id' is the id of the first vertex in a
  particular group. It means that component ids are generally not contiguous.
  If there are multiple components of the same size, a row is created for each
  component. If grouping_cols is specified, the largest
  component is computed for each group.
  - num_vertices: Number of vertices in the largest component.
</dd>
</dl>

@anchor hist
@par Retrieve Histogram of Vertices Per Connected Component

This function creates a histogram of the number of vertices
per connected component.

<pre class="syntax">
graph_wcc_histogram( wcc_table,
                    histogram_table
                   )
</pre>

\b Arguments
<dl class="arglist">
<dt>wcc_table</dt>
<dd>TEXT. Name of the table that contains the output of weakly connected
components.</dd>

<dt>histogram_table</dt>
<dd>TEXT. Name of the output table that contains the number of vertices per
component. A row is created for every comoponent in every group
if grouping_cols was specified when running weakly connected components.
The output table has the following columns:
  - grouping_cols: The grouping columns given during the creation of the
wcc_table. If there are no grouping columns, this column
is not created.
  - component_id: The ID of the component.
  - num_vertices: Number of vertices in the component specified by the
component_id column.

</dd>
</dl>

@anchor samecpt
@par Check if Two Vertices Belong to the Same Component

This function determines if two vertices belong to the same component.

<pre class="syntax">
graph_wcc_vertex_check( wcc_table,
                       vertex_pair,
                       pair_table
                      )
</pre>

\b Arguments
<dl class="arglist">
<dt>wcc_table</dt>
<dd>TEXT. Name of the table that contains the output of weakly connected
components.</dd>

<dt>vertex_pair</dt>
<dd>TEXT. A pair of vertex IDs separated by a comma.</dd>

<dt>pair_table</dt>
<dd>TEXT. Name of the output table that specifies if the two vertices in
vertex_pair belong to the same component. If wcc_table was generated using
grouping_cols, all the components in all groups are considered. The output
table has the following columns:
  - component_id: Component ID that contains both the vertices in vertex_pair.
  - grouping_cols: The grouping columns given in the creation of wcc_table. If
                    there are no grouping columns, this column is not created.

</dd>
</dl>

@anchor reach
@par Retrieve All Vertices Reachable from a Vertex

This function finds all the vertices that can be reached from a given vertex
via weakly connected paths.

<pre class="syntax">
graph_wcc_reachable_vertices( wcc_table,
                             src,
                             reachable_vertices_table
                            )
</pre>

\b Arguments
<dl class="arglist">
<dt>wcc_table</dt>
<dd>TEXT. Name of the table that contains the output of weakly connected
components.</dd>

<dt>src</dt>
<dd>TEXT. The vertex ID from which all reachable vertices have to be found.</dd>

<dt>reachable_vertices_table</dt>
<dd>TEXT. Name of the output table that contains the list of vertices that are
reachable from the src vertex. The output table has the following columns:
  - grouping_cols : The grouping columns given in the creation of wcc_table. If
                    there are no grouping columns, this column is not created.
  - component_id  : The ID of the component that both the src and dest vertices
                    belong to.
  - dest          : Vertex ID that is reachable from the src vertex.
                    Reachability is computed with regard to a component.

</dd>
</dl>

@anchor count
@par Count of Connected Components

This function finds the total number of components in the input graph.

<pre class="syntax">
graph_wcc_num_cpts( wcc_table,
                   count_table
                  )
</pre>

\b Arguments
<dl class="arglist">
<dt>wcc_table</dt>
<dd>TEXT. Name of the table that contains the output of weakly connected
components.</dd>

<dt>count_table</dt>
<dd>TEXT. Name of the output table that contains the total number of components
per group in the graph, if there are any grouping_cols in wcc_table. The output
table has the following columns:
  - grouping_cols : The grouping columns given in the creation of wcc_table.
                    If there are no grouping columns, this column is not created,
                    and count is with regard to the entire graph.
  - num_components : Count of weakly connected components in a graph, or the
                     number of components within a group if grouping_cols is defined.
</dd>

</dl>

@anchor examples
@examp

-# Create vertex and edge tables to represent the graph:
<pre class="syntax">
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);
</pre>

-# Find all the weakly connected components in the graph:
<pre class="syntax">
DROP TABLE IF EXISTS wcc_out, wcc_out_summary;
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;
</pre>
<pre class="result">
 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)
</pre>

-# Now get the weakly connected components associated with each 'user_id'
using the grouping feature:
<pre class="syntax">
DROP TABLE IF EXISTS wcc_out, wcc_out_summary;
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
                         'user_id');           -- Grouping column name
SELECT * FROM wcc_out ORDER BY user_id, component_id, id;
</pre>
<pre class="result">
 id | component_id | user_id
----+--------------+---------
  0 |            0 |       1
  1 |            0 |       1
  2 |            0 |       1
  3 |            0 |       1
  5 |            0 |       1
  6 |            0 |       1
 10 |           10 |       2
 11 |           10 |       2
 12 |           10 |       2
 13 |           10 |       2
 14 |           14 |       2
 15 |           14 |       2
 16 |           14 |       2
(13 rows)
</pre>
Note that vertex 4 is not identified as a separate component
above. This is because there is no entry in the
edge table for vertex 4 indicating which group it belongs to
(though you could do that if you wanted to).

-# Retrieve the largest connected component:
<pre class="syntax">
DROP TABLE IF EXISTS largest_cpt_table;
SELECT madlib.graph_wcc_largest_cpt(
                         'wcc_out',             -- WCC output table
                         'largest_cpt_table');  -- output table containing largest component ID
SELECT * FROM largest_cpt_table ORDER BY component_id;
</pre>
<pre class="result">
 user_id | component_id | num_vertices
---------+--------------+--------------
       1 |            0 |            6
       2 |           10 |            4
(2 rows)
</pre>

-# Retrieve histogram of the number of vertices per
connected component:
<pre class="syntax">
DROP TABLE IF EXISTS histogram_table;
SELECT madlib.graph_wcc_histogram(
                         'wcc_out',           -- WCC output table
                         'histogram_table');  -- output table containing the histogram of vertices
SELECT * FROM histogram_table ORDER BY component_id;
</pre>
<pre class="result">
 user_id | component_id | num_vertices
---------+--------------+--------------
       1 |            0 |            6
       2 |           10 |            4
       2 |           14 |            3
(3 rows)
</pre>

-# Check if two vertices belong to the same component:
<pre class="syntax">
DROP TABLE IF EXISTS vc_table;
SELECT madlib.graph_wcc_vertex_check(
                         'wcc_out',    -- WCC output table
                         '14,15',      -- Pair of vertex IDs
                         'vc_table');  -- output table containing components that contain the two vertices
SELECT * FROM vc_table ORDER BY component_id;
</pre>
<pre class="result">
 user_id | component_id
---------+--------------
       2 |           14
(1 row)
</pre>

-# Retrieve all vertices reachable from a vertex
<pre class="syntax">
DROP TABLE IF EXISTS reach_table;
SELECT madlib.graph_wcc_reachable_vertices(
                         'wcc_out',         -- WCC output table
                         '0',               -- source vertex
                         'reach_table');    -- output table containing all vertices reachable from source vertex
SELECT * FROM reach_table ORDER BY component_id, dest;
</pre>
<pre class="result">
 user_id | component_id | dest
---------+--------------+------
       1 |            0 |    1
       1 |            0 |    2
       1 |            0 |    3
       1 |            0 |    5
       1 |            0 |    6
(5 rows)
</pre>

-# Count of connected components:
<pre class="syntax">
DROP TABLE IF EXISTS count_table;
SELECT madlib.graph_wcc_num_cpts(
                         'wcc_out',       -- WCC output table
                         'count_table');  -- output table containing number of components per group
SELECT * FROM count_table;
</pre>
<pre class="result">
 user_id | num_components
---------+----------------
       1 |              1
       2 |              2
(2 rows)
</pre>

*/

-------------------------------------------------------------------------

CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.weakly_connected_components(
    vertex_table            TEXT,
    vertex_id               TEXT,
    edge_table              TEXT,
    edge_args               TEXT,
    out_table               TEXT,
    grouping_cols           TEXT

) RETURNS VOID AS $$
    PythonFunction(graph, wcc, wcc)
$$ LANGUAGE plpythonu VOLATILE
m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `MODIFIES SQL DATA', `');
-------------------------------------------------------------------------
CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.weakly_connected_components(
    vertex_table            TEXT,
    vertex_id               TEXT,
    edge_table              TEXT,
    edge_args               TEXT,
    out_table               TEXT

) RETURNS VOID AS $$
     SELECT MADLIB_SCHEMA.weakly_connected_components($1, $2, $3, $4, $5, NULL);
$$ LANGUAGE sql VOLATILE
m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `MODIFIES SQL DATA', `');
-------------------------------------------------------------------------
-- HELPER functions
-------------------------------------------------------------------------
CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.graph_wcc_largest_cpt(
    wcc_table             TEXT,
    largest_cpt_table     TEXT

) RETURNS VOID AS $$
    PythonFunction(graph, wcc, graph_wcc_largest_cpt)
$$ LANGUAGE plpythonu VOLATILE
m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `MODIFIES SQL DATA', `');
-------------------------------------------------------------------------

CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.graph_wcc_histogram(
    wcc_table           TEXT,
    histogram_table     TEXT

) RETURNS VOID AS $$
    PythonFunction(graph, wcc, graph_wcc_histogram)
$$ LANGUAGE plpythonu VOLATILE
m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `MODIFIES SQL DATA', `');
-------------------------------------------------------------------------

CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.graph_wcc_vertex_check(
    wcc_table           TEXT,
    vertex_pair         TEXT,
    pair_table          TEXT

) RETURNS VOID AS $$
    PythonFunction(graph, wcc, graph_wcc_vertex_check)
$$ LANGUAGE plpythonu VOLATILE
m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `MODIFIES SQL DATA', `');
-------------------------------------------------------------------------

CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.graph_wcc_reachable_vertices(
    wcc_table                    TEXT,
    src                          TEXT,
    reachable_vertices_table     TEXT

) RETURNS VOID AS $$
    PythonFunction(graph, wcc, graph_wcc_reachable_vertices)
$$ LANGUAGE plpythonu VOLATILE
m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `MODIFIES SQL DATA', `');
-------------------------------------------------------------------------

CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.graph_wcc_num_cpts(
    wcc_table           TEXT,
    count_table         TEXT

) RETURNS VOID AS $$
    PythonFunction(graph, wcc, graph_wcc_num_cpts)
$$ LANGUAGE plpythonu VOLATILE
m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `MODIFIES SQL DATA', `');
-------------------------------------------------------------------------

-------------------------------------------------------------------------

-- Online help
CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.weakly_connected_components(
    message VARCHAR
) RETURNS VARCHAR AS $$
    PythonFunction(graph, wcc, wcc_help)
$$ LANGUAGE plpythonu IMMUTABLE
m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `CONTAINS SQL', `');

-------------------------------------------------------------------------------

CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.weakly_connected_components()
RETURNS VARCHAR AS $$
    SELECT MADLIB_SCHEMA.weakly_connected_components('');
$$ LANGUAGE sql IMMUTABLE
m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `CONTAINS SQL', `');
-------------------------------------------------------------------------------