You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@madlib.apache.org by fm...@apache.org on 2017/01/18 22:48:44 UTC
incubator-madlib-site git commit: python notebook for graph - sssp
Repository: incubator-madlib-site
Updated Branches:
refs/heads/asf-site 90eed6ac0 -> 3c445f783
python notebook for graph - sssp
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/3c445f78
Tree: http://git-wip-us.apache.org/repos/asf/incubator-madlib-site/tree/3c445f78
Diff: http://git-wip-us.apache.org/repos/asf/incubator-madlib-site/diff/3c445f78
Branch: refs/heads/asf-site
Commit: 3c445f7830bea34440d16b4c74779b6b07037641
Parents: 90eed6a
Author: Frank McQuillan <fm...@pivotal.io>
Authored: Wed Jan 18 14:48:10 2017 -0800
Committer: Frank McQuillan <fm...@pivotal.io>
Committed: Wed Jan 18 14:48:10 2017 -0800
----------------------------------------------------------------------
community-artifacts/SSSP-v1.ipynb | 573 +++++++++++++++++++++++++++++++++
1 file changed, 573 insertions(+)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-madlib-site/blob/3c445f78/community-artifacts/SSSP-v1.ipynb
----------------------------------------------------------------------
diff --git a/community-artifacts/SSSP-v1.ipynb b/community-artifacts/SSSP-v1.ipynb
new file mode 100644
index 0000000..6258ed0
--- /dev/null
+++ b/community-artifacts/SSSP-v1.ipynb
@@ -0,0 +1,573 @@
+{
+ "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
+}