You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@madlib.apache.org by iyerr3 <gi...@git.apache.org> on 2017/07/17 07:44:21 UTC
[GitHub] incubator-madlib pull request #152: Feature/graph measures 1
GitHub user iyerr3 opened a pull request:
https://github.com/apache/incubator-madlib/pull/152
Feature/graph measures 1
Note: This PR will have to be rebased after #148 is merged.
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/iyerr3/incubator-madlib feature/graph_measures_1
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/incubator-madlib/pull/152.patch
To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:
This closes #152
----
commit 6461061cfe0b161e0e19eef0d9e7e62c470136a1
Author: Rahul Iyer <ri...@apache.org>
Date: 2017-07-08T05:23:18Z
Graph: Update Python code to follow PEP-8
- Changed indentation to use spaces instead of tabs
- Updated to PEP-8 guidelines
- Updated to follow style guide convention
- Refactored few functions to clean code and design
commit 60b0774b71bce90f88f1ddb1573295e6adf0706a
Author: Rahul Iyer <ri...@apache.org>
Date: 2017-06-29T20:31:55Z
Graph: Add initial set of centrality measures
JIRA: MADLIB-1073
This commit adds the following measures:
- Closeness (uses APSP)
- Graph diameter (uses APSP)
- Average path length (uses APSP)
- In/out degrees
----
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-madlib issue #152: Feature/graph measures 1
Posted by iyerr3 <gi...@git.apache.org>.
Github user iyerr3 commented on the issue:
https://github.com/apache/incubator-madlib/pull/152
Merged with 06788cc
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-madlib issue #152: Feature/graph measures 1
Posted by asfgit <gi...@git.apache.org>.
Github user asfgit commented on the issue:
https://github.com/apache/incubator-madlib/pull/152
Refer to this link for build results (access rights to CI server needed):
https://builds.apache.org/job/madlib-pr-build/125/
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-madlib issue #152: Feature/graph measures 1
Posted by asfgit <gi...@git.apache.org>.
Github user asfgit commented on the issue:
https://github.com/apache/incubator-madlib/pull/152
Refer to this link for build results (access rights to CI server needed):
https://builds.apache.org/job/madlib-pr-build/114/
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-madlib pull request #152: Feature/graph measures 1
Posted by orhankislal <gi...@git.apache.org>.
Github user orhankislal commented on a diff in the pull request:
https://github.com/apache/incubator-madlib/pull/152#discussion_r129096107
--- Diff: src/ports/postgres/modules/graph/test/measures.sql_in ---
@@ -0,0 +1,150 @@
+/* ----------------------------------------------------------------------- *//**
+ *
+ * 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.
+ *
+ */
+/* ----------------------------------------------------------------------- */
+
+-- Create vertex and edge tables to represent the graph:
+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);
+
+-- Calculate the all-pair shortest paths:
+DROP TABLE IF EXISTS out_apsp, out_apsp_summary;
+SELECT 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
+
+-- Compute the closeness measure for all nodes:
+DROP TABLE IF EXISTS out_closeness;
+SELECT graph_closeness('out_apsp', 'out_closeness');
+SELECT * FROM out_closeness;
+
+SELECT assert(relative_error(inverse_sum_dist, 0.04347) < 1e-2 and
+ relative_error(inverse_avg_dist, 0.3043) < 1e-2 and
+ relative_error(sum_inverse_dist, 3.6833) < 1e-2 and
+ k_degree = 7,
+ 'Incorrect value for closeness')
+FROM out_closeness
+WHERE src_id = 0;
+
+-- Compute the diameter measure for graph
+DROP TABLE IF EXISTS out_diameter;
+SELECT 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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-madlib pull request #152: Feature/graph measures 1
Posted by iyerr3 <gi...@git.apache.org>.
Github user iyerr3 closed the pull request at:
https://github.com/apache/incubator-madlib/pull/152
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-madlib issue #152: Feature/graph measures 1
Posted by asfgit <gi...@git.apache.org>.
Github user asfgit commented on the issue:
https://github.com/apache/incubator-madlib/pull/152
Refer to this link for build results (access rights to CI server needed):
https://builds.apache.org/job/madlib-pr-build/115/
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-madlib issue #152: Feature/graph measures 1
Posted by iyerr3 <gi...@git.apache.org>.
Github user iyerr3 commented on the issue:
https://github.com/apache/incubator-madlib/pull/152
Push-forced after rebasing to master.
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-madlib issue #152: Feature/graph measures 1
Posted by asfgit <gi...@git.apache.org>.
Github user asfgit commented on the issue:
https://github.com/apache/incubator-madlib/pull/152
Refer to this link for build results (access rights to CI server needed):
https://builds.apache.org/job/madlib-pr-build/121/
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-madlib issue #152: Feature/graph measures 1
Posted by asfgit <gi...@git.apache.org>.
Github user asfgit commented on the issue:
https://github.com/apache/incubator-madlib/pull/152
Refer to this link for build results (access rights to CI server needed):
https://builds.apache.org/job/madlib-pr-build/128/
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-madlib pull request #152: Feature/graph measures 1
Posted by orhankislal <gi...@git.apache.org>.
Github user orhankislal commented on a diff in the pull request:
https://github.com/apache/incubator-madlib/pull/152#discussion_r129121134
--- 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');
+SELECT * FROM out_diameter;
+</pre>
+<pre class="result">
+ diameter | diameter_end_vertices
+----------+-----------------------
+ 14 | {{1,4}}
+(1 row)
+</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>
+
+-# Find the diameter of graph in every group
+<pre class="syntax">
+DROP TABLE IF EXISTS out_gr_path;
+SELECT madlib.graph_diameter('out_gr', 'out_gr_diameter');
+SELECT * FROM out_gr_diameter ORDER BY grp;
+</pre>
+<pre class="result">
+ grp | diameter | diameter_end_vertices
+-----+----------+-----------------------
+ 0 | 14 | {{1,4}}
+ 1 | 14 | {{1,4}}
+(2 rows)
+</pre>
+
+*/
+
+
+CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.graph_diameter(
+ apsp_table TEXT,
+ out_table TEXT
+) RETURNS VOID AS $$
+ PythonFunction(graph, measures, graph_diameter)
+$$ LANGUAGE plpythonu VOLATILE
+m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `MODIFIES SQL DATA', `');
+-------------------------------------------------------------------------------
+
+-- Online help
+CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.graph_diameter(
+ message VARCHAR
+) RETURNS VARCHAR AS $$
+ PythonFunction(graph, measures, graph_diameter)
+$$ LANGUAGE plpythonu IMMUTABLE
+m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `CONTAINS SQL', `');
+
+--------------------------------------------------------------------------------
+
+CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.graph_diameter()
+RETURNS VARCHAR AS $$
+ SELECT MADLIB_SCHEMA.graph_diameter('');
+$$ LANGUAGE sql IMMUTABLE
+m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `CONTAINS SQL', `');
+--------------------------------------------------------------------------------
+
+/**
+@addtogroup grp_graph_avg_path_length
+@brief Computes the average shortest-path length of a graph.
+
+<div class="toc"><b>Contents</b>
+<ul>
+<li><a href="#avg_path_length">Average Path Length</a></li>
+<li><a href="#examples">Examples</a></li>
+</ul>
+</div>
+
+This function computes the average of the shortest paths between each pair of
+vertices. Average path length is based on "reachable target vertices", so it
+ignores infinite-length paths between vertices that are not connected.
+
+@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 avg_path_length
+@par Average Path Length
+<pre class="syntax">
+graph_avg_path_length( 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 average path length. It contains a row
+for every group, and the average path value.
+</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 average path length measure:
+<pre class="syntax">
+DROP TABLE IF EXISTS out_avg_path_length;
+SELECT madlib.graph_avg_path_length('out_apsp', 'out_avg_path_length');
+SELECT * FROM out_avg_path_length;
+</pre>
+<pre class="result">
+ avg_path_length
+------------------
--- End diff --
This causes the result block separated into two halves. I tried `\------------------` and that seems to fix the issue. It does not happen with any other result blocks
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-madlib issue #152: Feature/graph measures 1
Posted by asfgit <gi...@git.apache.org>.
Github user asfgit commented on the issue:
https://github.com/apache/incubator-madlib/pull/152
Refer to this link for build results (access rights to CI server needed):
https://builds.apache.org/job/madlib-pr-build/124/
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-madlib issue #152: Feature/graph measures 1
Posted by asfgit <gi...@git.apache.org>.
Github user asfgit commented on the issue:
https://github.com/apache/incubator-madlib/pull/152
Refer to this link for build results (access rights to CI server needed):
https://builds.apache.org/job/madlib-pr-build/123/
---
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] incubator-madlib pull request #152: Feature/graph measures 1
Posted by orhankislal <gi...@git.apache.org>.
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 infrastructure@apache.org or file a JIRA ticket
with INFRA.
---