You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@madlib.apache.org by ok...@apache.org on 2017/01/19 21:26:01 UTC
incubator-madlib git commit: Graph: SSSP
Repository: incubator-madlib
Updated Branches:
refs/heads/master 02a7ef453 -> 498c55906
Graph: SSSP
JIRA: MADLIB-992
- Introduces a new module: Graph.
- Implements the single source shortest path algorithm (Bellman-Ford).
Closes #78
Project: http://git-wip-us.apache.org/repos/asf/incubator-madlib/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-madlib/commit/498c5590
Tree: http://git-wip-us.apache.org/repos/asf/incubator-madlib/tree/498c5590
Diff: http://git-wip-us.apache.org/repos/asf/incubator-madlib/diff/498c5590
Branch: refs/heads/master
Commit: 498c55906a56e4c6d3d561a088d9c113994368cf
Parents: 02a7ef4
Author: Orhan Kislal <ok...@pivotal.io>
Authored: Thu Jan 19 11:51:05 2017 -0800
Committer: Orhan Kislal <ok...@pivotal.io>
Committed: Thu Jan 19 13:25:08 2017 -0800
----------------------------------------------------------------------
doc/design/design.tex | 1 +
doc/design/modules/graph.tex | 71 +++
doc/literature.bib | 15 +
doc/mainpage.dox.in | 4 +
src/config/Modules.yml | 1 +
src/ports/postgres/modules/graph/__init__.py_in | 0
src/ports/postgres/modules/graph/sssp.py_in | 432 +++++++++++++++++++
src/ports/postgres/modules/graph/sssp.sql_in | 289 +++++++++++++
.../postgres/modules/graph/test/sssp.sql_in | 78 ++++
.../postgres/modules/utilities/pivot.sql_in | 84 ++--
10 files changed, 933 insertions(+), 42 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-madlib/blob/498c5590/doc/design/design.tex
----------------------------------------------------------------------
diff --git a/doc/design/design.tex b/doc/design/design.tex
index 516a23a..30e0ef7 100644
--- a/doc/design/design.tex
+++ b/doc/design/design.tex
@@ -229,6 +229,7 @@
\input{modules/decision-trees}
\input{modules/random-forests}
\input{modules/SVM}
+\input{modules/graph}
\printbibliography
\end{document}
http://git-wip-us.apache.org/repos/asf/incubator-madlib/blob/498c5590/doc/design/modules/graph.tex
----------------------------------------------------------------------
diff --git a/doc/design/modules/graph.tex b/doc/design/modules/graph.tex
new file mode 100644
index 0000000..223d8b5
--- /dev/null
+++ b/doc/design/modules/graph.tex
@@ -0,0 +1,71 @@
+% When using TeXShop on the Mac, let it know the root document. The following must be one of the first 20 lines.
+% !TEX root = ../design.tex
+
+\chapter[Graph]{Graph}
+
+\begin{moduleinfo}
+\item[Author] \href{mailto:okislal@pivotal.io}{Orhan Kislal}
+\item[History]
+ \begin{modulehistory}
+ \item[v0.1] Initial version, SSSP only.
+ \end{modulehistory}
+\end{moduleinfo}
+
+
+% Abstract. What is the problem we want to solve?
+
+This module implements various graph algorithms that are used in a number of applications such as social networks, telecommunications and road networks.
+
+% \section{Graph Representation} \label{sec:graph:rep}
+
+% Our graph representation depends on two structures, a \emph{vertex} table and an \emph{edge} table.
+
+\section{Single Source Shortest Path} \label{sec:graph:sssp}
+
+Given a graph and a source vertex, single source shortest path (SSSP) algorithm finds a path for every vertex such that the sum of the weights of its constituent edges is minimized.
+
+Shortest path is defined as follows. Let $e_{i,j}$ be the edge from vertex $i$ to vertex $j$ and $w_{i,j}$ be its weight. Given a graph G, the shortest path from $s$ to $d$ is $P = (v_1, v_2 \dots, v_n)$ (where $v_1=s$ and $v_n=d$) that over all possible $n$ minimizes the sum $ \sum _{i=1}^{n-1}f(e_{i,i+1})$.
+
+% \subsection{Bellman Ford Algorithm}
+
+Bellman-Ford Algorithm \cite{bellman1958routing,ford1956network} is based on the following idea: We start with a naive approximation for the cost of reaching every vertex. At each iteration, these values are refined based on the edge list and the existing approximations. If there are no refinements at any given step, the algorithm returns the calculated results. If the algorithm does not converge in $|V|-1$ iterations, this indicates the existence of a negative cycle in the graph.
+
+
+\begin{algorithm}[SSSP$(V,E,start)$] \label{alg:sssp}
+\alginput{Vertex set $V$, edge set $E$, starting vertex $start$}
+\algoutput{Distance and parent set for every vertex $cur$}
+\begin{algorithmic}[1]
+ \State $toupdate(0) \set (start,0,start)$
+ \For{every $i \in 0\dots|V|-1$}
+ \For{every tuple $t \in toupdate(i)$} \label{alg:sssp:update}
+ \For{every edge $e \mid e.src = t.id$}
+ \State $local \set e.val + t.val$
+ \If{$local < toupdate(i+1,e.dest).val$} \label{alg:sssp:single}
+ \State $toupdate(i+1,dest) \set (local,e.src)$
+ \EndIf
+ \EndFor
+ \EndFor
+ \For{every tuple $t \in toupdate(i+1)$}
+ \If{$t.val < cur(t.id).val$}
+ \State $cur(t.id) \set (t.val,t.parent)$
+ \EndIf
+ \EndFor
+ \EndFor
+\end{algorithmic}
+\end{algorithm}
+
+\begin{description}
+\item edge: (src,dest,val). The edges of the graph.
+\item cur: id -> (val,parent). The intermediate SSSP results.
+\item toupdate: iter -> (id -> (val,parent)). The set of updates.
+\end{description}
+
+Changes from the standard Bellman-Ford algorithm:
+
+\begin{description}
+\item Line~\ref{alg:sssp:update}: We only check the vertices that have been updated in the last iteration.
+\item Line~\ref{alg:sssp:single}: At each iteration, we update a given vertex only one time. This means the toupdate set cannot contain multiple records for the same vertex which requires the comparison with the existing value.
+\end{description}
+
+This is not a 1-to-1 pseudocode for the implementation since we don't compare the `toupdate` table records one by one but calculate the overall minimum. In addition, the comparison with `cur` values take place earlier to reduce the number of tuples in the `toupdate` table.
+
http://git-wip-us.apache.org/repos/asf/incubator-madlib/blob/498c5590/doc/literature.bib
----------------------------------------------------------------------
diff --git a/doc/literature.bib b/doc/literature.bib
index 64f5b0d..0353c23 100644
--- a/doc/literature.bib
+++ b/doc/literature.bib
@@ -892,3 +892,18 @@ Applied Survival Analysis},
pages = {1443--1471},
}
+@article{bellman1958routing,
+ title={On a routing problem},
+ author={Bellman, Richard},
+ journal={Quarterly of applied mathematics},
+ pages={87--90},
+ year={1958},
+ publisher={JSTOR}
+}
+
+@techreport{ford1956network,
+ title={Network flow theory},
+ author={Ford Jr, Lester R},
+ year={1956},
+ institution={DTIC Document}
+}
http://git-wip-us.apache.org/repos/asf/incubator-madlib/blob/498c5590/doc/mainpage.dox.in
----------------------------------------------------------------------
diff --git a/doc/mainpage.dox.in b/doc/mainpage.dox.in
index b85ef15..0e846e1 100644
--- a/doc/mainpage.dox.in
+++ b/doc/mainpage.dox.in
@@ -119,6 +119,10 @@ complete matrix stored as a distributed table.
@defgroup grp_stemmer Stemming
@ingroup grp_datatrans
+@defgroup grp_graph Graph
+@{Contains graph algorithms. @}
+ @defgroup grp_sssp Single Source Shortest Path
+ @ingroup grp_graph
@defgroup grp_mdl Model Evaluation
@{Contains functions for evaluating accuracy and validation of predictive methods. @}
http://git-wip-us.apache.org/repos/asf/incubator-madlib/blob/498c5590/src/config/Modules.yml
----------------------------------------------------------------------
diff --git a/src/config/Modules.yml b/src/config/Modules.yml
index fd3c5e6..c3315b6 100644
--- a/src/config/Modules.yml
+++ b/src/config/Modules.yml
@@ -14,6 +14,7 @@ modules:
- name: elastic_net
- name: glm
depends: ['utilities']
+ - name: graph
- name: kmeans
depends: ['array_ops', 'svec_util', 'sample']
- name: lda
http://git-wip-us.apache.org/repos/asf/incubator-madlib/blob/498c5590/src/ports/postgres/modules/graph/__init__.py_in
----------------------------------------------------------------------
diff --git a/src/ports/postgres/modules/graph/__init__.py_in b/src/ports/postgres/modules/graph/__init__.py_in
new file mode 100644
index 0000000..e69de29
http://git-wip-us.apache.org/repos/asf/incubator-madlib/blob/498c5590/src/ports/postgres/modules/graph/sssp.py_in
----------------------------------------------------------------------
diff --git a/src/ports/postgres/modules/graph/sssp.py_in b/src/ports/postgres/modules/graph/sssp.py_in
new file mode 100644
index 0000000..558ec3d
--- /dev/null
+++ b/src/ports/postgres/modules/graph/sssp.py_in
@@ -0,0 +1,432 @@
+# coding=utf-8
+#
+# 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.
+
+# Single Source Shortest Path
+
+# Please refer to the sssp.sql_in file for the documentation
+
+"""
+@file sssp.py_in
+
+@namespace graph
+"""
+
+import plpy
+from utilities.control import MinWarning
+from utilities.utilities import _assert
+from utilities.utilities import extract_keyvalue_params
+from utilities.utilities import unique_string
+from utilities.validate_args import get_cols
+from utilities.validate_args import unquote_ident
+from utilities.validate_args import table_exists
+from utilities.validate_args import columns_exist_in_table
+from utilities.validate_args import table_is_empty
+
+m4_changequote(`<!', `!>')
+
+def graph_sssp(schema_madlib, vertex_table, vertex_id, edge_table,
+ edge_args, source_vertex, out_table, **kwargs):
+ """
+ Single source shortest path function for graphs using the Bellman-Ford
+ algorhtm [1].
+ Args:
+ @param vertex_table Name of the table that contains the vertex data.
+ @param vertex_id Name of the column containing the vertex ids.
+ @param edge_table Name of the table that contains the edge data.
+ @param edge_args A comma-delimited string containing multiple
+ named arguments of the form "name=value".
+ @param source_vertex The source vertex id for the algorithm to start.
+ @param out_table Name of the table to store the result of SSSP.
+
+ [1] https://en.wikipedia.org/wiki/Bellman-Ford_algorithm
+ """
+
+ with MinWarning("warning"):
+
+ INT_MAX = 2147483647
+ EPSILON = 0.000001
+
+ message = unique_string(desp='message')
+
+ oldupdate = unique_string(desp='oldupdate')
+ newupdate = unique_string(desp='newupdate')
+
+ params_types = {'src': str, 'dest': str, 'weight': str}
+ default_args = {'src': 'src', 'dest': 'dest', 'weight': 'weight'}
+ edge_params = extract_keyvalue_params(edge_args,
+ params_types,
+ default_args)
+ if vertex_id is None:
+ vertex_id = "id"
+
+ src = edge_params["src"]
+ dest = edge_params["dest"]
+ weight = edge_params["weight"]
+
+ distribution = m4_ifdef(<!__POSTGRESQL__!>, <!''!>,
+ <!"DISTRIBUTED BY ({0})".format(vertex_id)!>)
+ local_distribution = m4_ifdef(<!__POSTGRESQL__!>, <!''!>,
+ <!"DISTRIBUTED BY (id)"!>)
+
+ validate_graph_coding(vertex_table, vertex_id, edge_table,
+ edge_params, source_vertex, out_table)
+
+ plpy.execute(" DROP TABLE IF EXISTS {0},{1},{2}".format(
+ message,oldupdate,newupdate))
+
+ # We keep a table of every vertex, the minimum cost to that destination
+ # seen so far and the parent to this vertex in the associated shortest
+ # path. This table will be updated throughtout the execution.
+ plpy.execute(
+ """ CREATE TABLE {out_table} AS
+ SELECT {vertex_id} AS {vertex_id},
+ CAST('Infinity' AS DOUBLE PRECISION) AS {weight},
+ NULL::INT AS parent
+ FROM {vertex_table}
+ WHERE {vertex_id} IS NOT NULL
+ {distribution} """.format(**locals()))
+
+ # We keep 2 update tables and alternate them during the execution.
+ # This is necessary since we need to know which vertices are updated in
+ # the previous iteration to calculate the next set of updates.
+ plpy.execute(
+ """ CREATE TEMP TABLE {oldupdate}(
+ id INT, val DOUBLE PRECISION, parent INT)
+ {local_distribution}
+ """.format(**locals()))
+ plpy.execute(
+ """ CREATE TEMP TABLE {newupdate}(
+ id INT, val DOUBLE PRECISION, parent INT)
+ {local_distribution}
+ """.format(**locals()))
+
+ # Since HAWQ does not allow us to update, we create a new table and
+ # rename at every iteration
+ temp_table = unique_string(desp='temp')
+ sql = m4_ifdef(<!__HAWQ__!>,
+ """ CREATE TABLE {temp_table} (
+ {vertex_id} INT, {weight} DOUBLE PRECISION, parent INT)
+ {distribution};
+ """, <!''!>)
+ plpy.execute(sql.format(**locals()))
+
+ # GPDB and HAWQ have distributed by clauses to help them with indexing.
+ # For Postgres we add the indices manually.
+ sql_index = m4_ifdef(<!__POSTGRESQL__!>,
+ <!""" CREATE INDEX ON {out_table} ({vertex_id});
+ CREATE INDEX ON {oldupdate} (id);
+ CREATE INDEX ON {newupdate} (id);
+ """.format(**locals())!>,
+ <!''!>)
+ plpy.execute(sql_index)
+
+ # The source can be reached with 0 cost and it has itself as the parent.
+ plpy.execute(
+ """ INSERT INTO {oldupdate}
+ VALUES({source_vertex},0,{source_vertex})
+ """.format(**locals()))
+
+ v_cnt = plpy.execute(
+ """SELECT count(*) FROM {vertex_table}
+ WHERE {vertex_id} IS NOT NULL""".format(**locals()))[0]['count']
+ for i in range(0,v_cnt+1):
+
+ # Apply the updates calculated in the last iteration
+ sql = m4_ifdef(<!__HAWQ__!>,
+ <!"""
+ TRUNCATE TABLE {temp_table};
+ INSERT INTO {temp_table}
+ SELECT *
+ FROM {out_table}
+ WHERE {out_table}.{vertex_id} NOT IN (
+ SELECT {oldupdate}.id FROM {oldupdate})
+ UNION
+ SELECT * FROM {oldupdate};
+ DROP TABLE {out_table};
+ ALTER TABLE {temp_table} RENAME TO {out_table};
+ CREATE TABLE {temp_table} (
+ {vertex_id} INT, {weight} DOUBLE PRECISION, parent INT)
+ {distribution};
+ """!>,
+ <!"""
+ UPDATE {out_table} SET
+ {weight}=oldupdate.val,
+ parent=oldupdate.parent
+ FROM
+ {oldupdate} AS oldupdate
+ WHERE
+ {out_table}.{vertex_id}=oldupdate.id
+ """!>)
+ plpy.execute(sql.format(**locals()))
+
+
+ plpy.execute("TRUNCATE TABLE {0}".format(newupdate))
+
+ # 'oldupdate' table has the update info from the last iteration
+
+ # Consider every edge that has an updated source
+ # From these edges:
+ # For every destination vertex, find the min total cost to reach.
+ # Note that, just calling an aggregate function with group by won't
+ # let us store the src field of the edge (needed for the parent).
+ # This is why we need the 'x'; it gives a list of destinations and
+ # associated min values. Using these values, we identify which edge
+ # is selected.
+
+ # Since using '='' with floats is dangerous we use an epsilon value
+ # for comparison.
+
+ # Once we have a list of edges and values (stores as 'message'),
+ # we check if these values are lower than the existing shortest path
+ # values.
+
+ sql = (""" INSERT INTO {newupdate}
+ SELECT DISTINCT ON (message.id) message.id AS id,
+ message.val AS val,
+ message.parent AS parent
+ FROM {out_table} AS out_table INNER JOIN
+ (
+ SELECT edge_table.{dest} AS id, x.val AS val,
+ oldupdate.id AS parent
+ FROM {oldupdate} AS oldupdate INNER JOIN
+ {edge_table} AS edge_table ON
+ (edge_table.{src} = oldupdate.id) INNER JOIN
+ (
+ SELECT edge_table.{dest} AS id,
+ min(oldupdate.val + edge_table.{weight})
+ AS val
+ FROM {oldupdate} AS oldupdate INNER JOIN
+ {edge_table} AS edge_table ON
+ (edge_table.{src}=oldupdate.id)
+ GROUP BY edge_table.{dest}
+ ) x ON (edge_table.{dest} = x.id)
+ WHERE ABS(oldupdate.val + edge_table.{weight} - x.val)
+ < {EPSILON}
+ ) AS message ON (message.id = out_table.{vertex_id})
+ WHERE message.val<out_table.{weight}
+ """.format(**locals()))
+
+ # If there are no updates, SSSP is finalized
+ ret = plpy.execute(sql)
+ if ret.nrows() == 0:
+ break
+
+ # Swap the update tables for the next iteration
+ tmp = oldupdate
+ oldupdate = newupdate
+ newupdate = tmp
+
+ # Bellman-Ford should converge in |V|-1 iterations.
+ if i == v_cnt:
+ plpy.execute("DROP TABLE IF EXISTS {out_table}".format(**locals()))
+ plpy.error("Graph SSSP: Detected a negative cycle in the graph.")
+
+ m4_ifdef(<!__HAWQ__!>,
+ plpy.execute("DROP TABLE {temp_table} ".format(**locals())), <!''!>)
+
+ return None
+
+def graph_sssp_get_path(schema_madlib, sssp_table, dest_vertex, **kwargs):
+ """
+ Helper function that can be used to get the shortest path for a vertex
+ Args:
+ @param source_table Name of the table that contains the SSSP output.
+ @param out_table The vertex that will be the destination of the
+ desired path.
+ """
+
+ validate_get_path(sssp_table, dest_vertex)
+ cur = dest_vertex
+ cols = get_cols(sssp_table)
+ id = cols[0]
+ ret = [dest_vertex]
+ plan_name = unique_string(desp='plan')
+
+ # Follow the 'parent' chain until you reach the source.
+ # We don't need to know what the source is since it is the only vertex with
+ # itself as its parent
+ plpy.execute(""" PREPARE {plan_name} (int) AS
+ SELECT parent FROM {sssp_table} WHERE {id} = $1 LIMIT 1
+ """.format(**locals()))
+ sql = "EXECUTE {plan_name} ({cur})"
+ parent = plpy.execute(sql.format(**locals()))
+
+ if parent.nrows() == 0:
+ plpy.error(
+ "Graph SSSP: Vertex {0} is not present in the sssp table {1}".
+ format(dest_vertex,sssp_table))
+
+ while 1:
+ parent = parent[0]['parent']
+ if parent == cur:
+ ret.reverse()
+ return ret
+ else:
+ ret.append(parent)
+ cur = parent
+ parent = plpy.execute(sql.format(**locals()))
+
+ return None
+
+def validate_graph_coding(vertex_table, vertex_id, edge_table, edge_params,
+ source_vertex, out_table, **kwargs):
+
+ _assert(out_table and out_table.strip().lower() not in ('null', ''),
+ "Graph SSSP: Invalid output table name!")
+ _assert(not table_exists(out_table),
+ "Graph SSSP: Output table already exists!")
+
+ _assert(vertex_table and vertex_table.strip().lower() not in ('null', ''),
+ "Graph SSSP: Invalid vertex table name!")
+ _assert(table_exists(vertex_table),
+ "Graph SSSP: Vertex table ({0}) is missing!".format(vertex_table))
+ _assert(not table_is_empty(vertex_table),
+ "Graph SSSP: Vertex table ({0}) is empty!".format(vertex_table))
+
+ _assert(edge_table and edge_table.strip().lower() not in ('null', ''),
+ "Graph SSSP: Invalid edge table name!")
+ _assert(table_exists(edge_table),
+ "Graph SSSP: Edge table ({0}) is missing!".format(edge_table))
+ _assert(not table_is_empty(edge_table),
+ "Graph SSSP: Edge table ({0}) is empty!".format(edge_table))
+
+ existing_cols = set(unquote_ident(i) for i in get_cols(vertex_table))
+ _assert(vertex_id in existing_cols,
+ """Graph SSSP: The vertex column {vertex_id} is not present in vertex
+ table ({vertex_table}) """.format(**locals()))
+ _assert(columns_exist_in_table(edge_table, edge_params.values()),
+ "Graph SSSP: Not all columns from {0} present in edge table ({1})".
+ format(edge_params.values(), edge_table))
+
+ _assert(isinstance(source_vertex,int),
+ """Graph SSSP: Source vertex {source_vertex} has to be an integer """.
+ format(**locals()))
+ src_exists = plpy.execute("""
+ SELECT * FROM {vertex_table} WHERE {vertex_id}={source_vertex}
+ """.format(**locals()))
+
+ if src_exists.nrows() == 0:
+ plpy.error(
+ """Graph SSSP: Source vertex {source_vertex} is not present in the
+ vertex table {vertex_table} """.format(**locals()))
+
+ vt_error = plpy.execute(
+ """ SELECT {vertex_id}
+ FROM {vertex_table}
+ WHERE {vertex_id} IS NOT NULL
+ GROUP BY {vertex_id}
+ HAVING count(*) > 1 """.format(**locals()))
+
+ if vt_error.nrows() != 0:
+ plpy.error(
+ """Graph SSSP: Source vertex table {vertex_table}
+ contains duplicate vertex id's """.format(**locals()))
+
+ return None
+
+def validate_get_path(sssp_table, dest_vertex, **kwargs):
+
+ _assert(sssp_table and sssp_table.strip().lower() not in ('null', ''),
+ "Graph SSSP: Invalid SSSP table name!")
+ _assert(table_exists(sssp_table),
+ "Graph SSSP: SSSP table ({0}) is missing!".format(sssp_table))
+ _assert(not table_is_empty(sssp_table),
+ "Graph SSSP: SSSP table ({0}) is empty!".format(sssp_table))
+
+
+def graph_sssp_help(schema_madlib, message, **kwargs):
+ """
+ Help function for graph_sssp and graph_sssp_get_path
+
+ Args:
+ @param schema_madlib
+ @param message: string, Help message string
+ @param kwargs
+
+ Returns:
+ String. Help/usage information
+ """
+ if not message:
+ help_string = """
+-----------------------------------------------------------------------
+ SUMMARY
+-----------------------------------------------------------------------
+
+Given a graph and a source vertex, single source shortest path (SSSP)
+algorithm finds a path for every vertex such that the the sum of the
+weights of its constituent edges is minimized.
+
+For more details on function usage:
+ SELECT {schema_madlib}.graph_sssp('usage')
+ """
+ elif message in ['usage', 'help', '?']:
+ help_string = """
+----------------------------------------------------------------------------
+ USAGE
+----------------------------------------------------------------------------
+ SELECT {schema_madlib}.graph_sssp(
+ vertex_table TEXT, -- Name of the table that contains the vertex data.
+ vertex_id TEXT, -- Name of the column containing the vertex ids.
+ edge_table TEXT, -- Name of the table that contains the edge data.
+ edge_args TEXT, -- A comma-delimited string containing multiple
+ -- named arguments of the form "name=value".
+ source_vertex INT, -- The source vertex id for the algorithm to start.
+ out_table TEXT -- Name of the table to store the result of SSSP.
+);
+
+The following parameters are supported for edge table arguments ('edge_args'
+ above):
+
+src (default = 'src') : Name of the column containing the source
+ vertex ids in the edge table.
+dest (default = 'dest') : Name of the column containing the destination
+ vertex ids in the edge table.
+weight (default = 'weight') : Name of the column containing the weight of
+ edges in the edge table.
+
+To retrieve the path for a specific vertex:
+
+ SELECT {schema_madlib}.graph_sssp_get_path(
+ sssp_table TEXT, -- Name of the table that contains the SSSP output.
+ dest_vertex INT -- The vertex that will be the destination of the
+ -- desired path.
+);
+
+----------------------------------------------------------------------------
+ OUTPUT
+----------------------------------------------------------------------------
+The output table ('out_table' above) will contain a row for every vertex from
+vertex_table and have the following columns:
+
+vertex_id : The id for the destination. Will use the input parameter
+ (vertex_id) for column naming.
+weight : The total weight of the shortest path from the source vertex
+ to this particular vertex. Will use the input parameter (weight)
+ for column naming.
+parent : The parent of this vertex in the shortest path from source.
+ Will use "parent" for column naming.
+
+The graph_sssp_get_path function will return an INT array that contains the
+shortest path from the initial source vertex to the desired destination vertex.
+"""
+ else:
+ help_string = "No such option. Use {schema_madlib}.graph_sssp()"
+
+ return help_string.format(schema_madlib=schema_madlib)
+# ---------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-madlib/blob/498c5590/src/ports/postgres/modules/graph/sssp.sql_in
----------------------------------------------------------------------
diff --git a/src/ports/postgres/modules/graph/sssp.sql_in b/src/ports/postgres/modules/graph/sssp.sql_in
new file mode 100644
index 0000000..7534a75
--- /dev/null
+++ b/src/ports/postgres/modules/graph/sssp.sql_in
@@ -0,0 +1,289 @@
+/* ----------------------------------------------------------------------- *//**
+ *
+ * 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 Nov 2016
+ *
+ * @sa Provides various graph algorithms.
+ *
+ *//* ----------------------------------------------------------------------- */
+m4_include(`SQLCommon.m4')
+
+
+/**
+@addtogroup grp_sssp
+
+<div class="toc"><b>Contents</b>
+<ul>
+<li><a href="#sssp">SSSP</a></li>
+<li><a href="#notes">Notes</a></li>
+<li><a href="#examples">Examples</a></li>
+<li><a href="#literature">Literature</a></li>
+</ul>
+</div>
+
+@brief Finds the shortest path from a single source vertex to every other vertex in a given graph.
+
+Given a graph and a source vertex, the single source shortest path (SSSP) algorithm
+finds a path from the source vertex to every other vertex in the graph,
+such that the sum of the weights of the path edges is minimized.
+
+@anchor sssp
+@par SSSP
+<pre class="syntax">
+graph_sssp( vertex_table,
+ vertex_id,
+ edge_table,
+ edge_args,
+ source_vertex,
+ out_table
+ )
+</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, destination vertex and edge weight.
+Column naming convention is described below in the 'edge_args' parameter.</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'.
+ - weight (FLOAT8): Name of the column containing the edge weights in the edge table. Default column name is 'weight'.</dd>
+
+<dt>source_vertex</dt>
+<dd>INTEGER. The source vertex id for the algorithm to start. This vertex id must
+exist in the 'vertex_id' column of 'vertex_table'.</dd>
+
+<dt>out_table</dt>
+<dd>TEXT. Name of the table to store the result of SSSP.
+It will contain a row for every vertex from 'vertex_table' and have
+the following columns:
+ - vertex_id : The id for the destination. Will use the input parameter 'vertex_id' for column naming.
+ - weight : The total weight of the shortest path from the source vertex to this particular vertex.
+ Will use the input parameter (weight) for column naming.
+ - parent : The parent of this vertex in the shortest path from source. Will use 'parent' for column naming.</dd>
+</dl>
+
+@par Path Retrieval
+
+The path retrieval function returns the shortest path from the
+source vertex to a specified desination vertex.
+
+<pre class="syntax">
+graph_sssp( sssp_table,
+ dest_vertex
+ )
+</pre>
+
+\b Arguments
+<dl class="arglist">
+<dt>sssp_table</dt>
+<dd>TEXT. Name of the table that contains the SSSP output.</dd>
+
+<dt>dest_vertex</dt>
+<dd>INTEGER. The vertex that will be the destination of the desired path.</dd>
+</dl>
+
+@anchor notes
+@par Notes
+
+The Bellman-Ford algorithm [1] is used to implement SSSP. This algorithm allows
+negative edges but not negative cycles. In the case of graphs with
+negative cycles, an error will be given and no output table will be generated.
+
+Also see the Grail project [2] for more background on graph analytics processing
+in relational databases.
+
+@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,
+ weight FLOAT8
+ );
+INSERT INTO vertex VALUES
+(0),
+(1),
+(2),
+(3),
+(4),
+(5),
+(6),
+(7);
+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 shortest paths from vertex 0:
+<pre class="syntax">
+DROP TABLE IF EXISTS out;
+SELECT madlib.graph_sssp(
+ 'vertex', -- Vertex table
+ NULL, -- Vertix id column (NULL means use default naming)
+ 'edge', -- Edge table
+ NULL, -- Edge arguments (NULL means use default naming)
+ 0, -- Source vertex for path calculation
+ 'out'); -- Output table of shortest paths
+SELECT * FROM out ORDER BY id;
+</pre>
+<pre class="result">
+ id | weight | parent
+----+--------+--------
+ 0 | 0 | 0
+ 1 | 1 | 0
+ 2 | 1 | 0
+ 3 | 2 | 2
+ 4 | 10 | 0
+ 5 | 2 | 2
+ 6 | 3 | 5
+ 7 | 4 | 6
+(8 rows)
+</pre>
+
+-# Get the shortest path to vertex 6:
+<pre class="syntax">
+SELECT madlib.graph_sssp_get_path('out',6) AS spath;
+</pre>
+<pre class="result">
+ spath
+\-----------
+ {0,2,5,6}
+</pre>
+
+-# Now let's do a similar example except using
+different column names in the tables (i.e., not the defaults).
+Create the vertex and edge tables:
+<pre class="syntax">
+DROP TABLE IF EXISTS vertex_alt, edge_alt;
+CREATE TABLE vertex_alt AS SELECT id AS v_id FROM vertex;
+CREATE TABLE edge_alt AS SELECT src AS e_src, dest, weight AS e_weight FROM edge;
+</pre>
+
+-# Get the shortest path from vertex 1:
+<pre class="syntax">
+DROP TABLE IF EXISTS out_alt;
+SELECT madlib.graph_sssp(
+ 'vertex_alt', -- Vertex table
+ 'v_id', -- Vertix id column (NULL means use default naming)
+ 'edge_alt', -- Edge table
+ 'src=e_src, weight=e_weight', -- Edge arguments (NULL means use default naming)
+ 1, -- Source vertex for path calculation
+ 'out_alt'); -- Output table of shortest paths
+SELECT * FROM out_alt ORDER BY v_id;
+</pre>
+<pre class="result">
+ v_id | e_weight | parent
+------+----------+--------
+ 0 | 4 | 3
+ 1 | 0 | 1
+ 2 | 2 | 1
+ 3 | 3 | 2
+ 4 | 14 | 0
+ 5 | 3 | 2
+ 6 | 4 | 5
+ 7 | 5 | 6
+(8 rows)
+</pre>
+
+@anchor literature
+@par Literature
+
+[1] Bellman\u2013Ford algorithm. https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
+
+[2] The case against specialized graph analytics engines, J. Fan, G. Soosai Raj,
+and J. M. Patel. CIDR 2015. http://cidrdb.org/cidr2015/Papers/CIDR15_Paper20.pdf
+*/
+
+-------------------------------------------------------------------------
+
+CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.graph_sssp(
+ vertex_table TEXT,
+ vertex_id TEXT,
+ edge_table TEXT,
+ edge_args TEXT,
+ source_vertex INT,
+ out_table TEXT
+
+) RETURNS VOID AS $$
+ PythonFunction(graph, sssp, graph_sssp)
+$$ LANGUAGE plpythonu VOLATILE
+m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `MODIFIES SQL DATA', `');
+-------------------------------------------------------------------------
+CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.graph_sssp_get_path(
+ sssp_table TEXT,
+ dest_vertex INT
+
+) RETURNS INT[] AS $$
+ PythonFunction(graph, sssp, graph_sssp_get_path)
+$$ LANGUAGE plpythonu VOLATILE
+m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `CONTAINS SQL', `');
+-------------------------------------------------------------------------
+
+-- Online help
+CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.graph_sssp(
+ message VARCHAR
+) RETURNS VARCHAR AS $$
+ PythonFunction(graph, sssp, graph_sssp_help)
+$$ LANGUAGE plpythonu IMMUTABLE
+m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `CONTAINS SQL', `');
+
+--------------------------------------------------------------------------------
+
+CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.graph_sssp()
+RETURNS VARCHAR AS $$
+ SELECT MADLIB_SCHEMA.graph_sssp('');
+$$ LANGUAGE sql IMMUTABLE
+m4_ifdef(`\_\_HAS_FUNCTION_PROPERTIES\_\_', `CONTAINS SQL', `');
+--------------------------------------------------------------------------------
+
http://git-wip-us.apache.org/repos/asf/incubator-madlib/blob/498c5590/src/ports/postgres/modules/graph/test/sssp.sql_in
----------------------------------------------------------------------
diff --git a/src/ports/postgres/modules/graph/test/sssp.sql_in b/src/ports/postgres/modules/graph/test/sssp.sql_in
new file mode 100644
index 0000000..e2342c5
--- /dev/null
+++ b/src/ports/postgres/modules/graph/test/sssp.sql_in
@@ -0,0 +1,78 @@
+/* ----------------------------------------------------------------------- *//**
+ *
+ * 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.
+ *
+ *//* ----------------------------------------------------------------------- */
+
+
+DROP TABLE IF EXISTS vertex,edge,out,vertex_alt,edge_alt,out_alt;
+
+
+CREATE TABLE vertex(
+ id INTEGER
+ );
+
+CREATE TABLE edge(
+ src INTEGER,
+ dest INTEGER,
+ weight INTEGER
+ );
+
+INSERT INTO vertex VALUES
+(0),
+(1),
+(2),
+(3),
+(4),
+(5),
+(6),
+(7)
+;
+INSERT INTO edge VALUES
+(0, 1, 1),
+(0, 2, 1),
+(0, 4, 10),
+(1, 2, 2),
+(1, 3, 10),
+(2, 3, 1),
+(2, 5, 1),
+(2, 6, 3),
+(3, 0, 1),
+(4, 0, -2),
+(5, 6, 1),
+(6, 7, 1)
+;
+
+SELECT graph_sssp('vertex',NULL,'edge',NULL,0,'out');
+
+SELECT * FROM out;
+
+SELECT assert(weight = 3, 'Wrong output in graph (SSSP)') FROM out WHERE id = 6;
+SELECT assert(parent = 5, 'Wrong parent in graph (SSSP)') FROM out WHERE id = 6;
+
+SELECT graph_sssp_get_path('out',6);
+
+CREATE TABLE vertex_alt AS SELECT id AS v_id FROM vertex;
+CREATE TABLE edge_alt AS SELECT src AS e_src, dest, weight AS e_weight FROM edge;
+
+SELECT graph_sssp('vertex_alt','v_id','edge_alt','src=e_src, weight=e_weight',1,'out_alt');
+
+SELECT * FROM out_alt;
+
+SELECT assert(e_weight = 4, 'Wrong output in graph (SSSP)') FROM out_alt WHERE v_id = 6;
+SELECT assert(parent = 5, 'Wrong parent in graph (SSSP)') FROM out_alt WHERE v_id = 6;
http://git-wip-us.apache.org/repos/asf/incubator-madlib/blob/498c5590/src/ports/postgres/modules/utilities/pivot.sql_in
----------------------------------------------------------------------
diff --git a/src/ports/postgres/modules/utilities/pivot.sql_in b/src/ports/postgres/modules/utilities/pivot.sql_in
index 2cadab0..1c36cef 100644
--- a/src/ports/postgres/modules/utilities/pivot.sql_in
+++ b/src/ports/postgres/modules/utilities/pivot.sql_in
@@ -21,7 +21,7 @@
* @file pivot.sql_in
*
* @brief SQL functions for pivoting
- * @date June 2014
+ * @date June 2016
*
* @sa Creates a pivot table for data summarization.
*
@@ -34,7 +34,7 @@ m4_include(`SQLCommon.m4')
<div class="toc"><b>Contents</b>
<ul>
-<li><a href="#categorical">Pivoting</a></li>
+<li><a href="#pivoting">Pivoting</a></li>
<li><a href="#notes">Notes</a></li>
<li><a href="#examples">Examples</a></li>
<li><a href="#literature">Literature</a></li>
@@ -43,7 +43,7 @@ m4_include(`SQLCommon.m4')
@brief Provides pivoting functions helpful for data preparation before modeling
-@anchor categorical
+@anchor pivoting
The goal of the MADlib pivot function is to provide a data summarization tool
that can do basic OLAP type operations on data stored in one table and output
the summarized data to a second table.
@@ -70,22 +70,22 @@ pivot(
<dt>output_table</dt>
<dd>VARCHAR. Name of output table that contains the pivoted data.
The output table contains all the columns present in
- the <em>'index'</em> column list, plus additional columns for each
- distinct value in <em>'pivot_cols'</em>.
+ the <em>'index'</em> column list, plus additional columns for each
+ distinct value in <em>'pivot_cols'</em>.
@note The names of the columns in the output table are auto-generated.
Please see the examples section below to see how this works in practice.
- The convention used is to concatenate the following strings and separate
+ The convention used is to concatenate the following strings and separate
each by an underscore '_' :
- name of the value column <em>'pivot_values'</em>
- aggregate function
- name of the pivot column <em>'pivot_cols'</em>
- values in the pivot column
-
+
</dd>
<dt>index </dt>
<dd>VARCHAR. Comma-separated columns that will form the index of the output
- pivot table. By index we mean the values to group by; these are the rows
+ pivot table. By index we mean the values to group by; these are the rows
in the output pivot table.</dd>
<dt>pivot_cols </dt>
<dd>VARCHAR. Comma-separated columns that will form the columns of the
@@ -99,13 +99,13 @@ pivot(
possible to assign a set of aggregates per value column. Please refer to the
examples 12\-14 below for syntax details.</dd>
- @note Only aggregates with
+ @note Only aggregates with
strict transition functions are permitted here.
- A strict transition function means rows with null values are ignored;
- the function is not called and the previous state value is retained.
+ A strict transition function means rows with null values are ignored;
+ the function is not called and the previous state value is retained.
If you need some other behavior for null inputs, this should
be done prior to calling the pivot function.
- Aggregates with strict transition
+ Aggregates with strict transition
functions are described in [2,3].
<dt>fill_value (optional)</dt>
@@ -133,7 +133,7 @@ pivot(
@note
- NULLs in the index column are treated like any other value.
- NULLs in the pivot column are ignored unless keep_null is TRUE.
-- Only strict transition functions are
+- Only strict transition functions are
allowed so NULLs are ignored.
- It is not allowed to set the fill_value parameter without setting the
aggregate_func parameter due to possible ambiguity. Set
@@ -199,7 +199,7 @@ SELECT id,id2,piv,piv2,val,val2 FROM pivset_ext
ORDER BY id,id2,piv,piv2,val,val2;
</pre>
<pre class="result">
- id | id2 | piv | piv2 | val | val2
+ id | id2 | piv | piv2 | val | val2
----+-----+-----+------+-----+------
0 | 0 | 10 | 0 | 1 | 11
0 | 1 | 10 | 100 | 2 | 12
@@ -240,14 +240,14 @@ DROP AGGREGATE IF EXISTS array_accum1 (anyelement);
CREATE AGGREGATE array_accum1 (anyelement) (
sfunc = array_add1,
stype = anyarray,
- initcond = '{}'
+ initcond = '{}'
);
DROP TABLE IF EXISTS pivout;
SELECT madlib.pivot('pivset_ext', 'pivout', 'id', 'piv', 'val', 'array_accum1');
SELECT * FROM pivout ORDER BY id;
</pre>
<pre class="result">
- id | val_array_accum1_piv_10 | val_array_accum1_piv_20 | val_array_accum1_piv_30
+ id | val_array_accum1_piv_10 | val_array_accum1_piv_20 | val_array_accum1_piv_30
----+-------------------------+-------------------------+-------------------------
0 | {1,2} | {3} | {}
1 | {7} | {4} | {5,6}
@@ -316,30 +316,30 @@ SELECT * FROM pivout ORDER BY id;
id | 0
val_avg_piv_10_piv2_0 | 1
val_avg_piv_10_piv2_100 | 2
-val_avg_piv_10_piv2_200 |
-val_avg_piv_10_piv2_300 |
-val_avg_piv_20_piv2_0 |
+val_avg_piv_10_piv2_200 |
+val_avg_piv_10_piv2_300 |
+val_avg_piv_20_piv2_0 |
val_avg_piv_20_piv2_100 | 3
-val_avg_piv_20_piv2_200 |
-val_avg_piv_20_piv2_300 |
-val_avg_piv_30_piv2_0 |
-val_avg_piv_30_piv2_100 |
-val_avg_piv_30_piv2_200 |
-val_avg_piv_30_piv2_300 |
+val_avg_piv_20_piv2_200 |
+val_avg_piv_20_piv2_300 |
+val_avg_piv_30_piv2_0 |
+val_avg_piv_30_piv2_100 |
+val_avg_piv_30_piv2_200 |
+val_avg_piv_30_piv2_300 |
-[ RECORD 2 ]-----------+----
id | 1
-val_avg_piv_10_piv2_0 |
-val_avg_piv_10_piv2_100 |
+val_avg_piv_10_piv2_0 |
+val_avg_piv_10_piv2_100 |
val_avg_piv_10_piv2_200 | 7
-val_avg_piv_10_piv2_300 |
-val_avg_piv_20_piv2_0 |
+val_avg_piv_10_piv2_300 |
+val_avg_piv_20_piv2_0 |
val_avg_piv_20_piv2_100 | 4
-val_avg_piv_20_piv2_200 |
-val_avg_piv_20_piv2_300 |
-val_avg_piv_30_piv2_0 |
-val_avg_piv_30_piv2_100 |
+val_avg_piv_20_piv2_200 |
+val_avg_piv_20_piv2_300 |
+val_avg_piv_30_piv2_0 |
+val_avg_piv_30_piv2_100 |
val_avg_piv_30_piv2_200 | 5.5
-val_avg_piv_30_piv2_300 |
+val_avg_piv_30_piv2_300 |
...
</pre>
@@ -354,10 +354,10 @@ SELECT * FROM pivout ORDER BY id;
id | 0
val_avg_piv_10 | 1.5
val_avg_piv_20 | 3
-val_avg_piv_30 |
+val_avg_piv_30 |
val2_avg_piv_10 | 11.5
val2_avg_piv_20 | 13
-val2_avg_piv_30 |
+val2_avg_piv_30 |
-[ RECORD 2 ]---+-----
id | 1
val_avg_piv_10 | 7
@@ -381,10 +381,10 @@ SELECT * FROM pivout ORDER BY id;
id | 0
val_avg_piv_10 | 1.5
val_avg_piv_20 | 3
-val_avg_piv_30 |
+val_avg_piv_30 |
val_sum_piv_10 | 3
val_sum_piv_20 | 3
-val_sum_piv_30 |
+val_sum_piv_30 |
-[ RECORD 2 ]--+----
id | 1
val_avg_piv_10 | 7
@@ -435,13 +435,13 @@ SELECT * FROM pivout ORDER BY id;
id | 0
val_avg_piv_10 | 1.5
val_avg_piv_20 | 3
-val_avg_piv_30 |
+val_avg_piv_30 |
val2_avg_piv_10 | 11.5
val2_avg_piv_20 | 13
-val2_avg_piv_30 |
+val2_avg_piv_30 |
val2_sum_piv_10 | 23
val2_sum_piv_20 | 13
-val2_sum_piv_30 |
+val2_sum_piv_30 |
-[ RECORD 2 ]---+-----
id | 1
val_avg_piv_10 | 7
@@ -577,7 +577,7 @@ SELECT madlib.pivot('pivset_ext', 'pivout', 'id, id2', 'piv, piv2', 'val, val2',
SELECT * FROM pivout_dictionary;
</pre>
<pre class="result">
- __pivot_cid__ | pval | agg | piv | piv2 | col_name
+ __pivot_cid__ | pval | agg | piv | piv2 | col_name
---------------+------+-----+-----+------+------------------------------
__p_1__ | val | avg | | 100 | "val_avg_piv_null_piv2_100"
__p_5__ | val | avg | 10 | 100 | "val_avg_piv_10_piv2_100"