Github user orhankislal commented on a diff in the pull request:
https://github.com/apache/incubator-madlib/pull/152#discussion_r129095148
--- Diff: src/ports/postgres/modules/graph/measures.sql_in ---
@@ -0,0 +1,820 @@
+/* -----------------------------------------------------------------------
*//**
+ *
+ * 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 closeness.sql_in
+ *
+ * @brief SQL functions for graph analytics
+ * @date Jun 2017
+ *
+ * @sa Provides analytical measures for graphs
+ *
+ *//*
----------------------------------------------------------------------- */
+m4_include(`SQLCommon.m4')
+
+/**
+@addtogroup grp_graph_closeness
+@brief Computes the closeness centrality value of each node in the graph.
+
+<div class="toc"><b>Contents</b>
+<ul>
+<li><a href="#closeness">Closeness</a></li>
+<li><a href="#examples">Examples</a></li>
+</ul>
+</div>
+
+The Closeness function returns various closeness centrality measures and
the
+k-degree for given subset of vertices. The closeness measures are the
inverse of
+the sum, the inverse of the average, and the sum of inverses of the
shortest
+distances to all reachable target vertices (excluding the source vertex).
+
+@note The closeness measures require a valid output from a prior APSP run
- both
+the APSP table and the associated output summary table. APSP is a
+computationally expensive algorithm because it finds the shortest path
between
+all nodes in the graph. The worst case run-time for this implementation is
O(V^2
+* E) where V is the number of vertices and E is the number of edges. In
+practice, run-time will be generally be much less than this, depending on
the
+graph.
+
+@anchor closeness
+@par Closeness
+<pre class="syntax">
+graph_closeness( apsp_table,
+ output_table,
+ vertex_filter_expr
+ )
+</pre>
+
+\b Arguments
+<dl class="arglist">
+<dt>apsp_table</dt>
+<dd>TEXT. Name of the output table generated by a prior run of all pairs
shortest path (APSP).
+</dd>
+
+<dt>out_table</dt>
+<dd>TEXT. Name of the table to store the closeness measures.
+It contains a row for every vertex of every group and have
+the following columns (in addition to the grouping columns):
+ - inverse_sum_dist: Inverse of the sum of shortest distances to all
reachable
+ vertices.
+ - inverse_average_dist: Inverse of the average of shortest distances to
all
+ reachable vertices.
+ - sum_inverse_dist: Sum of the inverse of shortest distances to all
reachable
+ vertices.
+ - k_degree: Total number of reachable vertices.
+</dd>
+
+<dt>vertex_filter_expr (optional)</dt>
+
+<dd>TEXT, default = NULL. Valid PostgreSQL expression that describes the
+ vertices to generate closeness measures for. If this parameter is not
+specified, closeness measures are generated for all vertices in the apsp
table.
+This input should be treated like a WHERE clause.
+
+Some example inputs:
+- If you want a short list of vertices, say 1, 2 and 3:
+<pre>vertex_id IN (1, 2, 3)</pre>
+- If you want a range of vertices between 1000 and 2000:
+<pre>vertix_id BETWEEN 1000 AND 2000</pre>
+- If you want a set of vertices from a separate table satisfying to a
condition
+<pre>EXISTS (SELECT vertex_id FROM vertices_of_interest
+ WHERE vertex_id > 5000 AND condition = 'xyz')
+</pre>
+
+</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,
+ name TEXT
+ );
+CREATE TABLE edge(
+ src_id INTEGER,
+ dest_id INTEGER,
+ edge_weight FLOAT8
+ );
+INSERT INTO vertex VALUES
+(0, 'A'),
+(1, 'B'),
+(2, 'C'),
+(3, 'D'),
+(4, 'E'),
+(5, 'F'),
+(6, 'G'),
+(7, 'H');
+INSERT INTO edge VALUES
+(0, 1, 1.0),
+(0, 2, 1.0),
+(0, 4, 10.0),
+(1, 2, 2.0),
+(1, 3, 10.0),
+(2, 3, 1.0),
+(2, 5, 1.0),
+(2, 6, 3.0),
+(3, 0, 1.0),
+(4, 0, -2.0),
+(5, 6, 1.0),
+(6, 7, 1.0);
+</pre>
+
+-# Calculate the all-pair shortest paths:
+<pre class="syntax">
+DROP TABLE IF EXISTS out_apsp, out_apsp_summary;
+SELECT madlib.graph_apsp('vertex', -- Vertex table
+ 'id', -- Vertix id column (NULL means
use default naming)
+ 'edge', -- Edge table
+ 'src=src_id, dest=dest_id, weight=edge_weight',
+ -- Edge arguments (NULL means use
default naming)
+ 'out_apsp'); -- Output table of shortest
paths
+</pre>
+
+-# Compute the closeness measure for all nodes:
+<pre class="syntax">
+DROP TABLE IF EXISTS out_closeness;
+SELECT madlib.graph_closeness('out_apsp', 'out_closeness');
+SELECT * FROM out_closeness;
+</pre>
+<pre class="result">
+ src_id | inverse_sum_dist | inverse_avg_dist | sum_inverse_dist |
k_degree
+--------+--------------------+-------------------+------------------+----------
+ 1 | 0.0285714285714286 | 0.2 | 1.93809523809524 |
7
+ 3 | 0.0357142857142857 | 0.25 | 2.87424242424242 |
7
+ 4 | -1 | -7 | -1 |
7
+ 0 | 0.0434782608695652 | 0.304347826086957 | 3.68333333333333 |
7
+ 6 | 1 | 1 | 1 |
1
+ 2 | 0.0416666666666667 | 0.291666666666667 | 3.75 |
7
+ 5 | 0.333333333333333 | 0.666666666666667 | 1.5 |
2
+ 7 | [NULL] | [NULL] | 0 |
0
+(8 rows)
+</pre>
+
+-# Create a graph with 2 groups and find APSP for each group:
+<pre class="syntax">
+DROP TABLE IF EXISTS edge_gr;
+CREATE TABLE edge_gr AS
+(
+ SELECT *, 0 AS grp FROM edge
+ UNION
+ SELECT *, 1 AS grp FROM edge WHERE src_id < 6 AND dest_id < 6
+);
+INSERT INTO edge_gr VALUES
+(4,5,-20,1);
+</pre>
+
+-# Find APSP for all groups:
+<pre class="syntax">
+DROP TABLE IF EXISTS out_gr, out_gr_summary;
+SELECT madlib.graph_apsp(
+ 'vertex', -- Vertex table
+ NULL, -- Vertex id column (NULL means
use default naming)
+ 'edge_gr', -- Edge table
+ 'src=src_id, dest=dest_id, weight=edge_weight',
+ 'out_gr', -- Output table of shortest paths
+ 'grp' -- Grouping columns
+);
+</pre>
+
+-# Compute closeness measure for vertex 0 to vertex 5 in every group
+<pre class="syntax">
+DROP TABLE IF EXISTS out_gr_path;
+SELECT madlib.graph_closeness('out_gr', 'out_gr_closeness', 'src_id >= 0
and src_id <=5');
+SELECT * FROM out_gr_closeness ORDER BY grp;
+</pre>
+<pre class="result">
+ grp | src_id | inverse_sum_dist | inverse_avg_dist |
sum_inverse_dist | k_degree
+-----+--------+---------------------+--------------------+-------------------+----------
+ 0 | 0 | 0.0434782608695652 | 0.304347826086957 |
3.68333333333333 | 7
+ 0 | 5 | 0.333333333333333 | 0.666666666666667 |
1.5 | 2
+ 0 | 4 | -1 | -7 |
-1 | 7
+ 0 | 3 | 0.0357142857142857 | 0.25 |
2.87424242424242 | 7
+ 0 | 1 | 0.0285714285714286 | 0.2 |
1.93809523809524 | 7
+ 0 | 2 | 0.0416666666666667 | 0.291666666666667 |
3.75 | 7
+ 1 | 3 | 0.142857142857143 | 0.714285714285714 |
1.97979797979798 | 5
+ 1 | 5 | [NULL] | [NULL] |
0 | 0
+ 1 | 0 | 0.25 | 1.25 |
2.5 | 5
+ 1 | 1 | 0.0588235294117647 | 0.294117647058824 |
0.988095238095238 | 5
+ 1 | 2 | 0.1 | 0.5 |
1.79166666666667 | 5
+ 1 | 4 | -0.0416666666666667 | -0.208333333333333 |
-2.55 | 5
+(12 rows)
+</pre>
+
+*/
+-------------------------------------------------------------------------
+
+
+CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.graph_closeness(
+ apsp_table TEXT,
+ out_table TEXT,
+ vertex_filter_expr TEXT
+) RETURNS VOID AS $$
+ PythonFunction(graph, measures, graph_closeness)
+$$ LANGUAGE plpythonu VOLATILE
+m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `MODIFIES SQL DATA', `');
+-------------------------------------------------------------------------------
+
+CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.graph_closeness(
+ apsp_table TEXT,
+ out_table TEXT
+) RETURNS VOID AS $$
+ SELECT MADLIB_SCHEMA.graph_closeness($1, $2, NULL);
+$$ LANGUAGE SQL VOLATILE
+m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `MODIFIES SQL DATA', `');
+-------------------------------------------------------------------------------
+
+-- Online help
+CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.graph_closeness(
+ message VARCHAR
+) RETURNS VARCHAR AS $$
+ PythonFunction(graph, measures, graph_closeness_help)
+$$ LANGUAGE plpythonu IMMUTABLE
+m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `CONTAINS SQL', `');
+
+--------------------------------------------------------------------------------
+
+CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.graph_closeness()
+RETURNS VARCHAR AS $$
+ SELECT MADLIB_SCHEMA.graph_apsp('');
+$$ LANGUAGE sql IMMUTABLE
+m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `CONTAINS SQL', `');
+--------------------------------------------------------------------------------
+
+/**
+@addtogroup grp_graph_diameter
+@brief Computes the diameter of a graph.
+
+<div class="toc"><b>Contents</b>
+<ul>
+<li><a href="#diameter">Diameter</a></li>
+<li><a href="#examples">Examples</a></li>
+</ul>
+</div>
+
+Diameter is defined as the longest of all shortest paths in a graph.
+
+@note This function assumes a valid output from a prior APSP run - both
the APSP
+table and the associated output summary table. APSP is a computationally
+expensive algorithm because it finds the shortest path between all nodes
in the
+graph. The worst case run-time for this implementation is O(V^2 * E) where
V is
+the number of vertices and E is the number of edges. In practice,
run-time will
+be generally be much less than this, depending on the graph.
+
+@anchor diameter
+@par Diameter
+<pre class="syntax">
+graph_diameter( apsp_table,
+ output_table
+ )
+</pre>
+
+\b Arguments
+<dl class="arglist">
+<dt>apsp_table</dt>
+<dd>TEXT. Name of the output table generated by a prior run of all pairs
shortest path (APSP).
+</dd>
+
+<dt>out_table</dt>
+<dd>TEXT. Name of the table to store the diameter. It contains a row for
every group, the diameter value and the two vertices that are the farthest
apart.
+</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,
+ name TEXT
+ );
+CREATE TABLE edge(
+ src_id INTEGER,
+ dest_id INTEGER,
+ edge_weight FLOAT8
+ );
+INSERT INTO vertex VALUES
+(0, 'A'),
+(1, 'B'),
+(2, 'C'),
+(3, 'D'),
+(4, 'E'),
+(5, 'F'),
+(6, 'G'),
+(7, 'H');
+INSERT INTO edge VALUES
+(0, 1, 1.0),
+(0, 2, 1.0),
+(0, 4, 10.0),
+(1, 2, 2.0),
+(1, 3, 10.0),
+(2, 3, 1.0),
+(2, 5, 1.0),
+(2, 6, 3.0),
+(3, 0, 1.0),
+(4, 0, -2.0),
+(5, 6, 1.0),
+(6, 7, 1.0);
+</pre>
+
+-# Calculate the all-pair shortest paths:
+<pre class="syntax">
+DROP TABLE IF EXISTS out_apsp, out_apsp_summary;
+SELECT madlib.graph_apsp('vertex', -- Vertex table
+ 'id', -- Vertix id column (NULL means
use default naming)
+ 'edge', -- Edge table
+ 'src=src_id, dest=dest_id, weight=edge_weight',
+ -- Edge arguments (NULL means use
default naming)
+ 'out_apsp'); -- Output table of shortest
paths
+</pre>
+
+-# Compute the diameter measure for the graph:
+<pre class="syntax">
+DROP TABLE IF EXISTS out_diameter;
+SELECT madlib.graph_diameter('out_apsp', 'out_diameter');
--- End diff --
Fails on PG9.4:
```
SELECT graph_diameter('out_apsp', 'out_diameter');
psql:/tmp/madlib.pw7L2w/graph/test/measures.sql_in.tmp:87: ERROR:
spiexceptions.UndefinedObject: could not find array type for data type integer[]
CONTEXT: Traceback (most recent call last):
PL/Python function "graph_diameter", line 23, in <module>
return measures.graph_diameter(**globals())
PL/Python function "graph_diameter", line 310, in graph_apsp_measures
PL/Python function "graph_diameter", line 273, in diameter
PL/Python function "graph_diameter"
```
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastruct...@apache.org or file a JIRA ticket
with INFRA.
---
