Repository: incubator-madlib-site Updated Branches: refs/heads/asf-site a7df2267a -> d7cb76fa4
add grouping example to SSSP notebook Project: http://git-wip-us.apache.org/repos/asf/incubator-madlib-site/repo Commit: http://git-wip-us.apache.org/repos/asf/incubator-madlib-site/commit/d7cb76fa Tree: http://git-wip-us.apache.org/repos/asf/incubator-madlib-site/tree/d7cb76fa Diff: http://git-wip-us.apache.org/repos/asf/incubator-madlib-site/diff/d7cb76fa Branch: refs/heads/asf-site Commit: d7cb76fa479648f3b90b47b1d310883ec21300f4 Parents: a7df226 Author: Frank McQuillan <fmcquil...@pivotal.io> Authored: Mon Apr 17 11:13:20 2017 -0700 Committer: Frank McQuillan <fmcquil...@pivotal.io> Committed: Mon Apr 17 11:13:20 2017 -0700 ---------------------------------------------------------------------- community-artifacts/SSSP-v1.ipynb | 573 ----------------- community-artifacts/SSSP-v2.ipynb | 1090 ++++++++++++++++++++++++++++++++ 2 files changed, 1090 insertions(+), 573 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/incubator-madlib-site/blob/d7cb76fa/community-artifacts/SSSP-v1.ipynb ---------------------------------------------------------------------- diff --git a/community-artifacts/SSSP-v1.ipynb b/community-artifacts/SSSP-v1.ipynb deleted file mode 100644 index 6258ed0..0000000 --- a/community-artifacts/SSSP-v1.ipynb +++ /dev/null @@ -1,573 +0,0 @@ -{ - "cells": [ - { - "cell_type": "markdown", - "metadata": {}, - "source": [ - "# Single source shortest path (MADlib v1.10+)\n", - "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's edges is minimized." - ] - }, - { - "cell_type": "code", - "execution_count": 9, - "metadata": { - "collapsed": false - }, - "outputs": [ - { - "name": "stdout", - "output_type": "stream", - "text": [ - "The sql extension is already loaded. To reload it, use:\n", - " %reload_ext sql\n" - ] - } - ], - "source": [ - "%load_ext sql" - ] - }, - { - "cell_type": "code", - "execution_count": 10, - "metadata": { - "collapsed": false - }, - "outputs": [ - { - "data": { - "text/plain": [ - "u'Connected: gpdbchina@madlib'" - ] - }, - "execution_count": 10, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "%sql postgresql://gpdbchina@10.194.10.68:55000/madlib\n", - "#%sql postgresql://fmcquillan@localhost:5432/madlib\n", - "#%sql postgresql://gpadmin@54.197.30.46:10432/gpadmin" - ] - }, - { - "cell_type": "code", - "execution_count": 11, - "metadata": { - "collapsed": false - }, - "outputs": [ - { - "name": "stdout", - "output_type": "stream", - "text": [ - "1 rows affected.\n" - ] - }, - { - "data": { - "text/html": [ - "<table>\n", - " <tr>\n", - " <th>version</th>\n", - " </tr>\n", - " <tr>\n", - " <td>MADlib version: 1.10.0-dev, git revision: v1.7.1-206-g7907a6b, cmake configuration time: Wed Jan 18 18:26:02 UTC 2017, build type: Release, build system: Linux-2.6.18-238.27.1.el5.hotfix.bz516490, C compiler: gcc 4.4.0, C++ compiler: g++ 4.4.0</td>\n", - " </tr>\n", - "</table>" - ], - "text/plain": [ - "[(u'MADlib version: 1.10.0-dev, git revision: v1.7.1-206-g7907a6b, cmake configuration time: Wed Jan 18 18:26:02 UTC 2017, build type: Release, build system: Linux-2.6.18-238.27.1.el5.hotfix.bz516490, C compiler: gcc 4.4.0, C++ compiler: g++ 4.4.0',)]" - ] - }, - "execution_count": 11, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "%sql select madlib.version();\n", - "#%sql select version();" - ] - }, - { - "cell_type": "markdown", - "metadata": {}, - "source": [ - "# 1. Create vertex and edge tables" - ] - }, - { - "cell_type": "code", - "execution_count": 84, - "metadata": { - "collapsed": false - }, - "outputs": [ - { - "name": "stdout", - "output_type": "stream", - "text": [ - "Done.\n", - "Done.\n", - "Done.\n", - "8 rows affected.\n", - "12 rows affected.\n" - ] - }, - { - "data": { - "text/plain": [ - "[]" - ] - }, - "execution_count": 84, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "%%sql \n", - "DROP TABLE IF EXISTS vertex, edge;\n", - "\n", - "CREATE TABLE vertex(\n", - " id INTEGER\n", - " );\n", - "\n", - "CREATE TABLE edge(\n", - " src INTEGER,\n", - " dest INTEGER,\n", - " weight FLOAT8\n", - " );\n", - "\n", - "INSERT INTO vertex VALUES\n", - "(0),\n", - "(1),\n", - "(2),\n", - "(3),\n", - "(4),\n", - "(5),\n", - "(6),\n", - "(7);\n", - "\n", - "INSERT INTO edge VALUES\n", - "(0, 1, 1.0),\n", - "(0, 2, 1.0),\n", - "(0, 4, 10.0),\n", - "(1, 2, 2.0),\n", - "(1, 3, 10.0),\n", - "(2, 3, 1.0),\n", - "(2, 5, 1.0),\n", - "(2, 6, 3.0),\n", - "(3, 0, 1.0),\n", - "(4, 0, -2.0),\n", - "(5, 6, 1.0),\n", - "(6, 7, 1.0);" - ] - }, - { - "cell_type": "markdown", - "metadata": {}, - "source": [ - "# 2. Calculate the shortest paths from vertex 0" - ] - }, - { - "cell_type": "code", - "execution_count": 85, - "metadata": { - "collapsed": false - }, - "outputs": [ - { - "name": "stdout", - "output_type": "stream", - "text": [ - "Done.\n", - "1 rows affected.\n", - "8 rows affected.\n" - ] - }, - { - "data": { - "text/html": [ - "<table>\n", - " <tr>\n", - " <th>id</th>\n", - " <th>weight</th>\n", - " <th>parent</th>\n", - " </tr>\n", - " <tr>\n", - " <td>0</td>\n", - " <td>0.0</td>\n", - " <td>0</td>\n", - " </tr>\n", - " <tr>\n", - " <td>1</td>\n", - " <td>1.0</td>\n", - " <td>0</td>\n", - " </tr>\n", - " <tr>\n", - " <td>2</td>\n", - " <td>1.0</td>\n", - " <td>0</td>\n", - " </tr>\n", - " <tr>\n", - " <td>3</td>\n", - " <td>2.0</td>\n", - " <td>2</td>\n", - " </tr>\n", - " <tr>\n", - " <td>4</td>\n", - " <td>10.0</td>\n", - " <td>0</td>\n", - " </tr>\n", - " <tr>\n", - " <td>5</td>\n", - " <td>2.0</td>\n", - " <td>2</td>\n", - " </tr>\n", - " <tr>\n", - " <td>6</td>\n", - " <td>3.0</td>\n", - " <td>5</td>\n", - " </tr>\n", - " <tr>\n", - " <td>7</td>\n", - " <td>4.0</td>\n", - " <td>6</td>\n", - " </tr>\n", - "</table>" - ], - "text/plain": [ - "[(0, 0.0, 0),\n", - " (1, 1.0, 0),\n", - " (2, 1.0, 0),\n", - " (3, 2.0, 2),\n", - " (4, 10.0, 0),\n", - " (5, 2.0, 2),\n", - " (6, 3.0, 5),\n", - " (7, 4.0, 6)]" - ] - }, - "execution_count": 85, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "%%sql\n", - "DROP TABLE IF EXISTS out;\n", - "\n", - "SELECT madlib.graph_sssp(\n", - " 'vertex', -- Vertex table\n", - " NULL, -- Vertix id column (NULL means use default naming)\n", - " 'edge', -- Edge table\n", - " NULL, -- Edge arguments (NULL means use default naming)\n", - " 0, -- Source vertex for path calculation\n", - " 'out'); -- Output table of shortest paths\n", - "\n", - "SELECT * FROM out ORDER BY id;" - ] - }, - { - "cell_type": "markdown", - "metadata": {}, - "source": [ - "# 3. Get the shortest path to vertex 6" - ] - }, - { - "cell_type": "code", - "execution_count": 50, - "metadata": { - "collapsed": false - }, - "outputs": [ - { - "name": "stdout", - "output_type": "stream", - "text": [ - "1 rows affected.\n" - ] - }, - { - "data": { - "text/html": [ - "<table>\n", - " <tr>\n", - " <th>spath</th>\n", - " </tr>\n", - " <tr>\n", - " <td>[0, 2, 5, 6]</td>\n", - " </tr>\n", - "</table>" - ], - "text/plain": [ - "[([0, 2, 5, 6],)]" - ] - }, - "execution_count": 50, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "%%sql\n", - "SELECT madlib.graph_sssp_get_path('out',6) AS spath;" - ] - }, - { - "cell_type": "markdown", - "metadata": {}, - "source": [ - "# 4. Custom column names\n", - "i.e., not using defaults. Create the vertex and edge tables:" - ] - }, - { - "cell_type": "code", - "execution_count": 86, - "metadata": { - "collapsed": false - }, - "outputs": [ - { - "name": "stdout", - "output_type": "stream", - "text": [ - "Done.\n", - "8 rows affected.\n", - "12 rows affected.\n", - "12 rows affected.\n" - ] - }, - { - "data": { - "text/html": [ - "<table>\n", - " <tr>\n", - " <th>e_src</th>\n", - " <th>dest</th>\n", - " <th>e_weight</th>\n", - " </tr>\n", - " <tr>\n", - " <td>0</td>\n", - " <td>1</td>\n", - " <td>1.0</td>\n", - " </tr>\n", - " <tr>\n", - " <td>0</td>\n", - " <td>2</td>\n", - " <td>1.0</td>\n", - " </tr>\n", - " <tr>\n", - " <td>0</td>\n", - " <td>4</td>\n", - " <td>10.0</td>\n", - " </tr>\n", - " <tr>\n", - " <td>4</td>\n", - " <td>0</td>\n", - " <td>-2.0</td>\n", - " </tr>\n", - " <tr>\n", - " <td>2</td>\n", - " <td>3</td>\n", - " <td>1.0</td>\n", - " </tr>\n", - " <tr>\n", - " <td>2</td>\n", - " <td>5</td>\n", - " <td>1.0</td>\n", - " </tr>\n", - " <tr>\n", - " <td>2</td>\n", - " <td>6</td>\n", - " <td>3.0</td>\n", - " </tr>\n", - " <tr>\n", - " <td>6</td>\n", - " <td>7</td>\n", - " <td>1.0</td>\n", - " </tr>\n", - " <tr>\n", - " <td>3</td>\n", - " <td>0</td>\n", - " <td>1.0</td>\n", - " </tr>\n", - " <tr>\n", - " <td>1</td>\n", - " <td>2</td>\n", - " <td>2.0</td>\n", - " </tr>\n", - " <tr>\n", - " <td>1</td>\n", - " <td>3</td>\n", - " <td>10.0</td>\n", - " </tr>\n", - " <tr>\n", - " <td>5</td>\n", - " <td>6</td>\n", - " <td>1.0</td>\n", - " </tr>\n", - "</table>" - ], - "text/plain": [ - "[(0, 1, 1.0),\n", - " (0, 2, 1.0),\n", - " (0, 4, 10.0),\n", - " (4, 0, -2.0),\n", - " (2, 3, 1.0),\n", - " (2, 5, 1.0),\n", - " (2, 6, 3.0),\n", - " (6, 7, 1.0),\n", - " (3, 0, 1.0),\n", - " (1, 2, 2.0),\n", - " (1, 3, 10.0),\n", - " (5, 6, 1.0)]" - ] - }, - "execution_count": 86, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "%%sql \n", - "DROP TABLE IF EXISTS vertex_alt,edge_alt;\n", - "CREATE TABLE vertex_alt AS SELECT id AS v_id FROM vertex;\n", - "CREATE TABLE edge_alt AS SELECT src AS e_src, dest, weight AS e_weight FROM edge;\n", - "SELECT * FROM edge_alt;" - ] - }, - { - "cell_type": "markdown", - "metadata": {}, - "source": [ - "# 5.0 Get the shortest path from vertex 1" - ] - }, - { - "cell_type": "code", - "execution_count": 87, - "metadata": { - "collapsed": false - }, - "outputs": [ - { - "name": "stdout", - "output_type": "stream", - "text": [ - "Done.\n", - "1 rows affected.\n", - "8 rows affected.\n" - ] - }, - { - "data": { - "text/html": [ - "<table>\n", - " <tr>\n", - " <th>v_id</th>\n", - " <th>e_weight</th>\n", - " <th>parent</th>\n", - " </tr>\n", - " <tr>\n", - " <td>0</td>\n", - " <td>4.0</td>\n", - " <td>3</td>\n", - " </tr>\n", - " <tr>\n", - " <td>1</td>\n", - " <td>0.0</td>\n", - " <td>1</td>\n", - " </tr>\n", - " <tr>\n", - " <td>2</td>\n", - " <td>2.0</td>\n", - " <td>1</td>\n", - " </tr>\n", - " <tr>\n", - " <td>3</td>\n", - " <td>3.0</td>\n", - " <td>2</td>\n", - " </tr>\n", - " <tr>\n", - " <td>4</td>\n", - " <td>14.0</td>\n", - " <td>0</td>\n", - " </tr>\n", - " <tr>\n", - " <td>5</td>\n", - " <td>3.0</td>\n", - " <td>2</td>\n", - " </tr>\n", - " <tr>\n", - " <td>6</td>\n", - " <td>4.0</td>\n", - " <td>5</td>\n", - " </tr>\n", - " <tr>\n", - " <td>7</td>\n", - " <td>5.0</td>\n", - " <td>6</td>\n", - " </tr>\n", - "</table>" - ], - "text/plain": [ - "[(0, 4.0, 3),\n", - " (1, 0.0, 1),\n", - " (2, 2.0, 1),\n", - " (3, 3.0, 2),\n", - " (4, 14.0, 0),\n", - " (5, 3.0, 2),\n", - " (6, 4.0, 5),\n", - " (7, 5.0, 6)]" - ] - }, - "execution_count": 87, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "%%sql\n", - "DROP TABLE IF EXISTS out_alt;\n", - "\n", - "SELECT madlib.graph_sssp(\n", - " 'vertex_alt', -- Vertex table\n", - " 'v_id', -- Vertix id column (NULL means use default naming)\n", - " 'edge_alt', -- Edge table\n", - " 'src=e_src, weight=e_weight', -- Edge arguments (NULL means use default naming)\n", - " 1, -- Source vertex for path calculation\n", - " 'out_alt'); -- Output table of shortest paths\n", - "\n", - "SELECT * FROM out_alt ORDER BY v_id;" - ] - } - ], - "metadata": { - "kernelspec": { - "display_name": "Python 2", - "language": "python", - "name": "python2" - }, - "language_info": { - "codemirror_mode": { - "name": "ipython", - "version": 2 - }, - "file_extension": ".py", - "mimetype": "text/x-python", - "name": "python", - "nbconvert_exporter": "python", - "pygments_lexer": "ipython2", - "version": "2.7.12" - } - }, - "nbformat": 4, - "nbformat_minor": 0 -} http://git-wip-us.apache.org/repos/asf/incubator-madlib-site/blob/d7cb76fa/community-artifacts/SSSP-v2.ipynb ---------------------------------------------------------------------- diff --git a/community-artifacts/SSSP-v2.ipynb b/community-artifacts/SSSP-v2.ipynb new file mode 100644 index 0000000..3a84d5a --- /dev/null +++ b/community-artifacts/SSSP-v2.ipynb @@ -0,0 +1,1090 @@ +{ + "cells": [ + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "# Single source shortest path\n", + "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's edges is minimized.\n", + "\n", + "SSSP was added in MADlib 1.10 and grouping was added in 1.11." + ] + }, + { + "cell_type": "code", + "execution_count": 3, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "The sql extension is already loaded. To reload it, use:\n", + " %reload_ext sql\n" + ] + } + ], + "source": [ + "%load_ext sql" + ] + }, + { + "cell_type": "code", + "execution_count": 4, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "data": { + "text/plain": [ + "u'Connected: gpdbchina@madlib'" + ] + }, + "execution_count": 4, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "# Greenplum 4.3.10.0\n", + "%sql postgresql://gpdbchina@10.194.10.68:61000/madlib\n", + " \n", + "# PostgreSQL local\n", + "#%sql postgresql://fmcquillan@localhost:5432/madlib\n", + "\n", + "# Greenplum 4.2.3.0\n", + "#%sql postgresql://gpdbchina@10.194.10.68:55000/madlib" + ] + }, + { + "cell_type": "code", + "execution_count": 5, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "1 rows affected.\n" + ] + }, + { + "data": { + "text/html": [ + "<table>\n", + " <tr>\n", + " <th>version</th>\n", + " </tr>\n", + " <tr>\n", + " <td>MADlib version: 1.11-dev, git revision: rel/v1.9.1-74-g1cc0efc, cmake configuration time: Fri Apr 14 23:56:52 UTC 2017, build type: Release, build system: Linux-2.6.18-238.27.1.el5.hotfix.bz516490, C compiler: gcc 4.4.0, C++ compiler: g++ 4.4.0</td>\n", + " </tr>\n", + "</table>" + ], + "text/plain": [ + "[(u'MADlib version: 1.11-dev, git revision: rel/v1.9.1-74-g1cc0efc, cmake configuration time: Fri Apr 14 23:56:52 UTC 2017, build type: Release, build system: Linux-2.6.18-238.27.1.el5.hotfix.bz516490, C compiler: gcc 4.4.0, C++ compiler: g++ 4.4.0',)]" + ] + }, + "execution_count": 5, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "%sql select madlib.version();\n", + "#%sql select version();" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "# 1. Create vertex and edge tables" + ] + }, + { + "cell_type": "code", + "execution_count": 6, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "Done.\n", + "Done.\n", + "Done.\n", + "8 rows affected.\n", + "12 rows affected.\n", + "12 rows affected.\n" + ] + }, + { + "data": { + "text/html": [ + "<table>\n", + " <tr>\n", + " <th>src</th>\n", + " <th>dest</th>\n", + " <th>weight</th>\n", + " </tr>\n", + " <tr>\n", + " <td>0</td>\n", + " <td>1</td>\n", + " <td>1.0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>0</td>\n", + " <td>2</td>\n", + " <td>1.0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>0</td>\n", + " <td>4</td>\n", + " <td>10.0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>1</td>\n", + " <td>2</td>\n", + " <td>2.0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>1</td>\n", + " <td>3</td>\n", + " <td>10.0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>2</td>\n", + " <td>3</td>\n", + " <td>1.0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>2</td>\n", + " <td>5</td>\n", + " <td>1.0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>2</td>\n", + " <td>6</td>\n", + " <td>3.0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>3</td>\n", + " <td>0</td>\n", + " <td>1.0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>4</td>\n", + " <td>0</td>\n", + " <td>-2.0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>5</td>\n", + " <td>6</td>\n", + " <td>1.0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>6</td>\n", + " <td>7</td>\n", + " <td>1.0</td>\n", + " </tr>\n", + "</table>" + ], + "text/plain": [ + "[(0, 1, 1.0),\n", + " (0, 2, 1.0),\n", + " (0, 4, 10.0),\n", + " (1, 2, 2.0),\n", + " (1, 3, 10.0),\n", + " (2, 3, 1.0),\n", + " (2, 5, 1.0),\n", + " (2, 6, 3.0),\n", + " (3, 0, 1.0),\n", + " (4, 0, -2.0),\n", + " (5, 6, 1.0),\n", + " (6, 7, 1.0)]" + ] + }, + "execution_count": 6, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "%%sql \n", + "DROP TABLE IF EXISTS vertex, edge;\n", + "\n", + "CREATE TABLE vertex(\n", + " id INTEGER\n", + " );\n", + "\n", + "CREATE TABLE edge(\n", + " src INTEGER,\n", + " dest INTEGER,\n", + " weight FLOAT8\n", + " );\n", + "\n", + "INSERT INTO vertex VALUES\n", + "(0),\n", + "(1),\n", + "(2),\n", + "(3),\n", + "(4),\n", + "(5),\n", + "(6),\n", + "(7);\n", + "\n", + "INSERT INTO edge VALUES\n", + "(0, 1, 1.0),\n", + "(0, 2, 1.0),\n", + "(0, 4, 10.0),\n", + "(1, 2, 2.0),\n", + "(1, 3, 10.0),\n", + "(2, 3, 1.0),\n", + "(2, 5, 1.0),\n", + "(2, 6, 3.0),\n", + "(3, 0, 1.0),\n", + "(4, 0, -2.0),\n", + "(5, 6, 1.0),\n", + "(6, 7, 1.0);\n", + "\n", + "SELECT * FROM edge ORDER BY src, dest;" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "# 2. Calculate the shortest paths from vertex 0" + ] + }, + { + "cell_type": "code", + "execution_count": 7, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "Done.\n", + "1 rows affected.\n", + "8 rows affected.\n" + ] + }, + { + "data": { + "text/html": [ + "<table>\n", + " <tr>\n", + " <th>id</th>\n", + " <th>weight</th>\n", + " <th>parent</th>\n", + " </tr>\n", + " <tr>\n", + " <td>0</td>\n", + " <td>0.0</td>\n", + " <td>0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>1</td>\n", + " <td>1.0</td>\n", + " <td>0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>2</td>\n", + " <td>1.0</td>\n", + " <td>0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>3</td>\n", + " <td>2.0</td>\n", + " <td>2</td>\n", + " </tr>\n", + " <tr>\n", + " <td>4</td>\n", + " <td>10.0</td>\n", + " <td>0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>5</td>\n", + " <td>2.0</td>\n", + " <td>2</td>\n", + " </tr>\n", + " <tr>\n", + " <td>6</td>\n", + " <td>3.0</td>\n", + " <td>5</td>\n", + " </tr>\n", + " <tr>\n", + " <td>7</td>\n", + " <td>4.0</td>\n", + " <td>6</td>\n", + " </tr>\n", + "</table>" + ], + "text/plain": [ + "[(0, 0.0, 0),\n", + " (1, 1.0, 0),\n", + " (2, 1.0, 0),\n", + " (3, 2.0, 2),\n", + " (4, 10.0, 0),\n", + " (5, 2.0, 2),\n", + " (6, 3.0, 5),\n", + " (7, 4.0, 6)]" + ] + }, + "execution_count": 7, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "%%sql\n", + "DROP TABLE IF EXISTS out, out_summary;\n", + "\n", + "SELECT madlib.graph_sssp(\n", + " 'vertex', -- Vertex table\n", + " NULL, -- Vertex id column (NULL means use default naming)\n", + " 'edge', -- Edge table\n", + " NULL, -- Edge arguments (NULL means use default naming)\n", + " 0, -- Source vertex for path calculation\n", + " 'out'); -- Output table of shortest paths\n", + "\n", + "SELECT * FROM out ORDER BY id;" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "# 3. Get the shortest path to vertex 5" + ] + }, + { + "cell_type": "code", + "execution_count": 9, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "Done.\n", + "1 rows affected.\n", + "1 rows affected.\n" + ] + }, + { + "data": { + "text/html": [ + "<table>\n", + " <tr>\n", + " <th>path</th>\n", + " </tr>\n", + " <tr>\n", + " <td>[0, 2, 5]</td>\n", + " </tr>\n", + "</table>" + ], + "text/plain": [ + "[([0, 2, 5],)]" + ] + }, + "execution_count": 9, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "%%sql\n", + "DROP TABLE IF EXISTS out_path;\n", + "SELECT madlib.graph_sssp_get_path('out',5, 'out_path');\n", + "SELECT * FROM out_path;" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "# 4. Custom column names\n", + "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:" + ] + }, + { + "cell_type": "code", + "execution_count": 10, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "Done.\n", + "8 rows affected.\n", + "12 rows affected.\n", + "12 rows affected.\n" + ] + }, + { + "data": { + "text/html": [ + "<table>\n", + " <tr>\n", + " <th>e_src</th>\n", + " <th>dest</th>\n", + " <th>e_weight</th>\n", + " </tr>\n", + " <tr>\n", + " <td>0</td>\n", + " <td>1</td>\n", + " <td>1.0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>0</td>\n", + " <td>2</td>\n", + " <td>1.0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>0</td>\n", + " <td>4</td>\n", + " <td>10.0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>1</td>\n", + " <td>2</td>\n", + " <td>2.0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>1</td>\n", + " <td>3</td>\n", + " <td>10.0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>2</td>\n", + " <td>3</td>\n", + " <td>1.0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>2</td>\n", + " <td>5</td>\n", + " <td>1.0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>2</td>\n", + " <td>6</td>\n", + " <td>3.0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>3</td>\n", + " <td>0</td>\n", + " <td>1.0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>4</td>\n", + " <td>0</td>\n", + " <td>-2.0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>5</td>\n", + " <td>6</td>\n", + " <td>1.0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>6</td>\n", + " <td>7</td>\n", + " <td>1.0</td>\n", + " </tr>\n", + "</table>" + ], + "text/plain": [ + "[(0, 1, 1.0),\n", + " (0, 2, 1.0),\n", + " (0, 4, 10.0),\n", + " (1, 2, 2.0),\n", + " (1, 3, 10.0),\n", + " (2, 3, 1.0),\n", + " (2, 5, 1.0),\n", + " (2, 6, 3.0),\n", + " (3, 0, 1.0),\n", + " (4, 0, -2.0),\n", + " (5, 6, 1.0),\n", + " (6, 7, 1.0)]" + ] + }, + "execution_count": 10, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "%%sql \n", + "DROP TABLE IF EXISTS vertex_alt, edge_alt;\n", + "CREATE TABLE vertex_alt AS SELECT id AS v_id FROM vertex;\n", + "CREATE TABLE edge_alt AS SELECT src AS e_src, dest, weight AS e_weight FROM edge;\n", + "SELECT * FROM edge_alt ORDER BY e_src, dest;" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "# 5.0 Get the shortest path from vertex 1" + ] + }, + { + "cell_type": "code", + "execution_count": 12, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "Done.\n", + "1 rows affected.\n", + "8 rows affected.\n" + ] + }, + { + "data": { + "text/html": [ + "<table>\n", + " <tr>\n", + " <th>v_id</th>\n", + " <th>e_weight</th>\n", + " <th>parent</th>\n", + " </tr>\n", + " <tr>\n", + " <td>0</td>\n", + " <td>4.0</td>\n", + " <td>3</td>\n", + " </tr>\n", + " <tr>\n", + " <td>1</td>\n", + " <td>0.0</td>\n", + " <td>1</td>\n", + " </tr>\n", + " <tr>\n", + " <td>2</td>\n", + " <td>2.0</td>\n", + " <td>1</td>\n", + " </tr>\n", + " <tr>\n", + " <td>3</td>\n", + " <td>3.0</td>\n", + " <td>2</td>\n", + " </tr>\n", + " <tr>\n", + " <td>4</td>\n", + " <td>14.0</td>\n", + " <td>0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>5</td>\n", + " <td>3.0</td>\n", + " <td>2</td>\n", + " </tr>\n", + " <tr>\n", + " <td>6</td>\n", + " <td>4.0</td>\n", + " <td>5</td>\n", + " </tr>\n", + " <tr>\n", + " <td>7</td>\n", + " <td>5.0</td>\n", + " <td>6</td>\n", + " </tr>\n", + "</table>" + ], + "text/plain": [ + "[(0, 4.0, 3),\n", + " (1, 0.0, 1),\n", + " (2, 2.0, 1),\n", + " (3, 3.0, 2),\n", + " (4, 14.0, 0),\n", + " (5, 3.0, 2),\n", + " (6, 4.0, 5),\n", + " (7, 5.0, 6)]" + ] + }, + "execution_count": 12, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "%%sql\n", + "DROP TABLE IF EXISTS out_alt, out_alt_summary;\n", + "\n", + "SELECT madlib.graph_sssp(\n", + " 'vertex_alt', -- Vertex table\n", + " 'v_id', -- Vertix id column (NULL means use default naming)\n", + " 'edge_alt', -- Edge table\n", + " 'src=e_src, weight=e_weight', -- Edge arguments (NULL means use default naming)\n", + " 1, -- Source vertex for path calculation\n", + " 'out_alt'); -- Output table of shortest paths\n", + "\n", + "SELECT * FROM out_alt ORDER BY v_id;" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "# 6.0 Grouping\n", + "Create a graph with 2 groups and find SSSP for each group:" + ] + }, + { + "cell_type": "code", + "execution_count": 13, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "Done.\n", + "21 rows affected.\n", + "1 rows affected.\n", + "22 rows affected.\n" + ] + }, + { + "data": { + "text/html": [ + "<table>\n", + " <tr>\n", + " <th>src</th>\n", + " <th>dest</th>\n", + " <th>weight</th>\n", + " <th>grp</th>\n", + " </tr>\n", + " <tr>\n", + " <td>0</td>\n", + " <td>1</td>\n", + " <td>1.0</td>\n", + " <td>0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>0</td>\n", + " <td>2</td>\n", + " <td>1.0</td>\n", + " <td>0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>0</td>\n", + " <td>4</td>\n", + " <td>10.0</td>\n", + " <td>0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>1</td>\n", + " <td>2</td>\n", + " <td>2.0</td>\n", + " <td>0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>1</td>\n", + " <td>3</td>\n", + " <td>10.0</td>\n", + " <td>0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>2</td>\n", + " <td>3</td>\n", + " <td>1.0</td>\n", + " <td>0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>2</td>\n", + " <td>5</td>\n", + " <td>1.0</td>\n", + " <td>0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>2</td>\n", + " <td>6</td>\n", + " <td>3.0</td>\n", + " <td>0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>3</td>\n", + " <td>0</td>\n", + " <td>1.0</td>\n", + " <td>0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>4</td>\n", + " <td>0</td>\n", + " <td>-2.0</td>\n", + " <td>0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>5</td>\n", + " <td>6</td>\n", + " <td>1.0</td>\n", + " <td>0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>6</td>\n", + " <td>7</td>\n", + " <td>1.0</td>\n", + " <td>0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>0</td>\n", + " <td>1</td>\n", + " <td>1.0</td>\n", + " <td>1</td>\n", + " </tr>\n", + " <tr>\n", + " <td>0</td>\n", + " <td>2</td>\n", + " <td>1.0</td>\n", + " <td>1</td>\n", + " </tr>\n", + " <tr>\n", + " <td>0</td>\n", + " <td>4</td>\n", + " <td>10.0</td>\n", + " <td>1</td>\n", + " </tr>\n", + " <tr>\n", + " <td>1</td>\n", + " <td>2</td>\n", + " <td>2.0</td>\n", + " <td>1</td>\n", + " </tr>\n", + " <tr>\n", + " <td>1</td>\n", + " <td>3</td>\n", + " <td>10.0</td>\n", + " <td>1</td>\n", + " </tr>\n", + " <tr>\n", + " <td>2</td>\n", + " <td>3</td>\n", + " <td>1.0</td>\n", + " <td>1</td>\n", + " </tr>\n", + " <tr>\n", + " <td>2</td>\n", + " <td>5</td>\n", + " <td>1.0</td>\n", + " <td>1</td>\n", + " </tr>\n", + " <tr>\n", + " <td>3</td>\n", + " <td>0</td>\n", + " <td>1.0</td>\n", + " <td>1</td>\n", + " </tr>\n", + " <tr>\n", + " <td>4</td>\n", + " <td>0</td>\n", + " <td>-2.0</td>\n", + " <td>1</td>\n", + " </tr>\n", + " <tr>\n", + " <td>4</td>\n", + " <td>5</td>\n", + " <td>-20.0</td>\n", + " <td>1</td>\n", + " </tr>\n", + "</table>" + ], + "text/plain": [ + "[(0, 1, 1.0, 0),\n", + " (0, 2, 1.0, 0),\n", + " (0, 4, 10.0, 0),\n", + " (1, 2, 2.0, 0),\n", + " (1, 3, 10.0, 0),\n", + " (2, 3, 1.0, 0),\n", + " (2, 5, 1.0, 0),\n", + " (2, 6, 3.0, 0),\n", + " (3, 0, 1.0, 0),\n", + " (4, 0, -2.0, 0),\n", + " (5, 6, 1.0, 0),\n", + " (6, 7, 1.0, 0),\n", + " (0, 1, 1.0, 1),\n", + " (0, 2, 1.0, 1),\n", + " (0, 4, 10.0, 1),\n", + " (1, 2, 2.0, 1),\n", + " (1, 3, 10.0, 1),\n", + " (2, 3, 1.0, 1),\n", + " (2, 5, 1.0, 1),\n", + " (3, 0, 1.0, 1),\n", + " (4, 0, -2.0, 1),\n", + " (4, 5, -20.0, 1)]" + ] + }, + "execution_count": 13, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "%%sql\n", + "DROP TABLE IF EXISTS edge_gr;\n", + "\n", + "CREATE TABLE edge_gr AS\n", + "(\n", + " SELECT *, 0 AS grp FROM edge\n", + " UNION\n", + " SELECT *, 1 AS grp FROM edge WHERE src < 6 AND dest < 6\n", + ");\n", + "\n", + "INSERT INTO edge_gr VALUES\n", + "(4,5,-20,1);\n", + "\n", + "SELECT * FROM edge_gr ORDER BY grp, src, dest;" + ] + }, + { + "cell_type": "code", + "execution_count": 14, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "Done.\n", + "1 rows affected.\n", + "14 rows affected.\n" + ] + }, + { + "data": { + "text/html": [ + "<table>\n", + " <tr>\n", + " <th>grp</th>\n", + " <th>id</th>\n", + " <th>weight</th>\n", + " <th>parent</th>\n", + " </tr>\n", + " <tr>\n", + " <td>0</td>\n", + " <td>0</td>\n", + " <td>0.0</td>\n", + " <td>0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>0</td>\n", + " <td>1</td>\n", + " <td>1.0</td>\n", + " <td>0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>0</td>\n", + " <td>2</td>\n", + " <td>1.0</td>\n", + " <td>0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>0</td>\n", + " <td>3</td>\n", + " <td>2.0</td>\n", + " <td>2</td>\n", + " </tr>\n", + " <tr>\n", + " <td>0</td>\n", + " <td>4</td>\n", + " <td>10.0</td>\n", + " <td>0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>0</td>\n", + " <td>5</td>\n", + " <td>2.0</td>\n", + " <td>2</td>\n", + " </tr>\n", + " <tr>\n", + " <td>0</td>\n", + " <td>6</td>\n", + " <td>3.0</td>\n", + " <td>5</td>\n", + " </tr>\n", + " <tr>\n", + " <td>0</td>\n", + " <td>7</td>\n", + " <td>4.0</td>\n", + " <td>6</td>\n", + " </tr>\n", + " <tr>\n", + " <td>1</td>\n", + " <td>0</td>\n", + " <td>0.0</td>\n", + " <td>0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>1</td>\n", + " <td>1</td>\n", + " <td>1.0</td>\n", + " <td>0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>1</td>\n", + " <td>2</td>\n", + " <td>1.0</td>\n", + " <td>0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>1</td>\n", + " <td>3</td>\n", + " <td>2.0</td>\n", + " <td>2</td>\n", + " </tr>\n", + " <tr>\n", + " <td>1</td>\n", + " <td>4</td>\n", + " <td>10.0</td>\n", + " <td>0</td>\n", + " </tr>\n", + " <tr>\n", + " <td>1</td>\n", + " <td>5</td>\n", + " <td>-10.0</td>\n", + " <td>4</td>\n", + " </tr>\n", + "</table>" + ], + "text/plain": [ + "[(0, 0, 0.0, 0),\n", + " (0, 1, 1.0, 0),\n", + " (0, 2, 1.0, 0),\n", + " (0, 3, 2.0, 2),\n", + " (0, 4, 10.0, 0),\n", + " (0, 5, 2.0, 2),\n", + " (0, 6, 3.0, 5),\n", + " (0, 7, 4.0, 6),\n", + " (1, 0, 0.0, 0),\n", + " (1, 1, 1.0, 0),\n", + " (1, 2, 1.0, 0),\n", + " (1, 3, 2.0, 2),\n", + " (1, 4, 10.0, 0),\n", + " (1, 5, -10.0, 4)]" + ] + }, + "execution_count": 14, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "%%sql\n", + "DROP TABLE IF EXISTS out_gr, out_gr_summary;\n", + "SELECT madlib.graph_sssp(\n", + " 'vertex', -- Vertex table\n", + " NULL, -- Vertex id column (NULL means use default naming)\n", + " 'edge_gr', -- Edge table\n", + " NULL, -- Edge arguments (NULL means use default naming)\n", + " 0, -- Source vertex for path calculation\n", + " 'out_gr', -- Output table of shortest paths\n", + " 'grp' -- Grouping columns\n", + ");\n", + "\n", + "SELECT * FROM out_gr ORDER BY grp, id;" + ] + }, + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "Find the path to vertex 5 for every group:" + ] + }, + { + "cell_type": "code", + "execution_count": 15, + "metadata": { + "collapsed": false + }, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "Done.\n", + "1 rows affected.\n", + "2 rows affected.\n" + ] + }, + { + "data": { + "text/html": [ + "<table>\n", + " <tr>\n", + " <th>grp</th>\n", + " <th>path</th>\n", + " </tr>\n", + " <tr>\n", + " <td>0</td>\n", + " <td>[0, 2, 5]</td>\n", + " </tr>\n", + " <tr>\n", + " <td>1</td>\n", + " <td>[0, 4, 5]</td>\n", + " </tr>\n", + "</table>" + ], + "text/plain": [ + "[(0, [0, 2, 5]), (1, [0, 4, 5])]" + ] + }, + "execution_count": 15, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "%%sql\n", + "DROP TABLE IF EXISTS out_gr_path;\n", + "SELECT madlib.graph_sssp_get_path('out_gr',5,'out_gr_path');\n", + "SELECT * FROM out_gr_path ORDER BY grp;" + ] + } + ], + "metadata": { + "kernelspec": { + "display_name": "Python 2", + "language": "python", + "name": "python2" + }, + "language_info": { + "codemirror_mode": { + "name": "ipython", + "version": 2 + }, + "file_extension": ".py", + "mimetype": "text/x-python", + "name": "python", + "nbconvert_exporter": "python", + "pygments_lexer": "ipython2", + "version": "2.7.12" + } + }, + "nbformat": 4, + "nbformat_minor": 0 +}
