Google Git
Sign in
apache / madlib-site / 5455828f6b559fc1057ac4019a665185cc458fce / . / community-artifacts / Graph / APSP-v1.ipynb
blob: 05b20b327e14524afc4e35bcf62000fd2971b076 [file] [log] [blame]
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# All pairs shortest path\n",
"The all pairs shortest paths (APSP) algorithm finds the lengths (summed weights) of the shortest paths between all pairs of vertices such that the sum of the weights of the path edges is minimized.\n",
"\n",
"APSP was added in MADlib 1.12."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"name": "stderr",
"output_type": "stream",
"text": [
"/Users/fmcquillan/anaconda/lib/python2.7/site-packages/IPython/config.py:13: ShimWarning: The `IPython.config` package has been deprecated. You should import from traitlets.config instead.\n",
" \"You should import from traitlets.config instead.\", ShimWarning)\n",
"/Users/fmcquillan/anaconda/lib/python2.7/site-packages/IPython/utils/traitlets.py:5: UserWarning: IPython.utils.traitlets has moved to a top-level traitlets package.\n",
" warn(\"IPython.utils.traitlets has moved to a top-level traitlets package.\")\n"
]
}
],
"source": [
"%load_ext sql"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"u'Connected: gpdbchina@madlib'"
]
},
"execution_count": 2,
"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": 3,
"metadata": {},
"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.12-dev, git revision: rel/v1.11-16-gf50f76d, cmake configuration time: Mon Jun 12 20:12:42 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.12-dev, git revision: rel/v1.11-16-gf50f76d, cmake configuration time: Mon Jun 12 20:12:42 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": 3,
"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": 4,
"metadata": {},
"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": 4,
"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"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Done.\n",
"1 rows affected.\n",
"64 rows affected.\n"
]
},
{
"data": {
"text/html": [
"<table>\n",
" <tr>\n",
" <th>src</th>\n",
" <th>dest</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>1</td>\n",
" </tr>\n",
" <tr>\n",
" <td>0</td>\n",
" <td>2</td>\n",
" <td>1.0</td>\n",
" <td>2</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>4</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>4.0</td>\n",
" <td>3</td>\n",
" </tr>\n",
" <tr>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>0.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>2</td>\n",
" </tr>\n",
" <tr>\n",
" <td>1</td>\n",
" <td>3</td>\n",
" <td>3.0</td>\n",
" <td>2</td>\n",
" </tr>\n",
" <tr>\n",
" <td>1</td>\n",
" <td>4</td>\n",
" <td>14.0</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <td>1</td>\n",
" <td>5</td>\n",
" <td>3.0</td>\n",
" <td>2</td>\n",
" </tr>\n",
" <tr>\n",
" <td>1</td>\n",
" <td>6</td>\n",
" <td>4.0</td>\n",
" <td>5</td>\n",
" </tr>\n",
" <tr>\n",
" <td>1</td>\n",
" <td>7</td>\n",
" <td>5.0</td>\n",
" <td>6</td>\n",
" </tr>\n",
" <tr>\n",
" <td>2</td>\n",
" <td>0</td>\n",
" <td>2.0</td>\n",
" <td>3</td>\n",
" </tr>\n",
" <tr>\n",
" <td>2</td>\n",
" <td>1</td>\n",
" <td>3.0</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <td>2</td>\n",
" <td>2</td>\n",
" <td>0.0</td>\n",
" <td>2</td>\n",
" </tr>\n",
" <tr>\n",
" <td>2</td>\n",
" <td>3</td>\n",
" <td>1.0</td>\n",
" <td>3</td>\n",
" </tr>\n",
" <tr>\n",
" <td>2</td>\n",
" <td>4</td>\n",
" <td>12.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>5</td>\n",
" </tr>\n",
" <tr>\n",
" <td>2</td>\n",
" <td>6</td>\n",
" <td>2.0</td>\n",
" <td>5</td>\n",
" </tr>\n",
" <tr>\n",
" <td>2</td>\n",
" <td>7</td>\n",
" <td>3.0</td>\n",
" <td>6</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>3</td>\n",
" <td>1</td>\n",
" <td>2.0</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <td>3</td>\n",
" <td>2</td>\n",
" <td>2.0</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <td>3</td>\n",
" <td>3</td>\n",
" <td>0.0</td>\n",
" <td>3</td>\n",
" </tr>\n",
" <tr>\n",
" <td>3</td>\n",
" <td>4</td>\n",
" <td>11.0</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <td>3</td>\n",
" <td>5</td>\n",
" <td>3.0</td>\n",
" <td>2</td>\n",
" </tr>\n",
" <tr>\n",
" <td>3</td>\n",
" <td>6</td>\n",
" <td>4.0</td>\n",
" <td>5</td>\n",
" </tr>\n",
" <tr>\n",
" <td>3</td>\n",
" <td>7</td>\n",
" <td>5.0</td>\n",
" <td>6</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>4</td>\n",
" <td>1</td>\n",
" <td>-1.0</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <td>4</td>\n",
" <td>2</td>\n",
" <td>-1.0</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <td>4</td>\n",
" <td>3</td>\n",
" <td>0.0</td>\n",
" <td>2</td>\n",
" </tr>\n",
" <tr>\n",
" <td>4</td>\n",
" <td>4</td>\n",
" <td>0.0</td>\n",
" <td>4</td>\n",
" </tr>\n",
" <tr>\n",
" <td>4</td>\n",
" <td>5</td>\n",
" <td>0.0</td>\n",
" <td>2</td>\n",
" </tr>\n",
" <tr>\n",
" <td>4</td>\n",
" <td>6</td>\n",
" <td>1.0</td>\n",
" <td>5</td>\n",
" </tr>\n",
" <tr>\n",
" <td>4</td>\n",
" <td>7</td>\n",
" <td>2.0</td>\n",
" <td>6</td>\n",
" </tr>\n",
" <tr>\n",
" <td>5</td>\n",
" <td>0</td>\n",
" <td>inf</td>\n",
" <td>None</td>\n",
" </tr>\n",
" <tr>\n",
" <td>5</td>\n",
" <td>1</td>\n",
" <td>inf</td>\n",
" <td>None</td>\n",
" </tr>\n",
" <tr>\n",
" <td>5</td>\n",
" <td>2</td>\n",
" <td>inf</td>\n",
" <td>None</td>\n",
" </tr>\n",
" <tr>\n",
" <td>5</td>\n",
" <td>3</td>\n",
" <td>inf</td>\n",
" <td>None</td>\n",
" </tr>\n",
" <tr>\n",
" <td>5</td>\n",
" <td>4</td>\n",
" <td>inf</td>\n",
" <td>None</td>\n",
" </tr>\n",
" <tr>\n",
" <td>5</td>\n",
" <td>5</td>\n",
" <td>0.0</td>\n",
" <td>5</td>\n",
" </tr>\n",
" <tr>\n",
" <td>5</td>\n",
" <td>6</td>\n",
" <td>1.0</td>\n",
" <td>6</td>\n",
" </tr>\n",
" <tr>\n",
" <td>5</td>\n",
" <td>7</td>\n",
" <td>2.0</td>\n",
" <td>6</td>\n",
" </tr>\n",
" <tr>\n",
" <td>6</td>\n",
" <td>0</td>\n",
" <td>inf</td>\n",
" <td>None</td>\n",
" </tr>\n",
" <tr>\n",
" <td>6</td>\n",
" <td>1</td>\n",
" <td>inf</td>\n",
" <td>None</td>\n",
" </tr>\n",
" <tr>\n",
" <td>6</td>\n",
" <td>2</td>\n",
" <td>inf</td>\n",
" <td>None</td>\n",
" </tr>\n",
" <tr>\n",
" <td>6</td>\n",
" <td>3</td>\n",
" <td>inf</td>\n",
" <td>None</td>\n",
" </tr>\n",
" <tr>\n",
" <td>6</td>\n",
" <td>4</td>\n",
" <td>inf</td>\n",
" <td>None</td>\n",
" </tr>\n",
" <tr>\n",
" <td>6</td>\n",
" <td>5</td>\n",
" <td>inf</td>\n",
" <td>None</td>\n",
" </tr>\n",
" <tr>\n",
" <td>6</td>\n",
" <td>6</td>\n",
" <td>0.0</td>\n",
" <td>6</td>\n",
" </tr>\n",
" <tr>\n",
" <td>6</td>\n",
" <td>7</td>\n",
" <td>1.0</td>\n",
" <td>7</td>\n",
" </tr>\n",
" <tr>\n",
" <td>7</td>\n",
" <td>0</td>\n",
" <td>inf</td>\n",
" <td>None</td>\n",
" </tr>\n",
" <tr>\n",
" <td>7</td>\n",
" <td>1</td>\n",
" <td>inf</td>\n",
" <td>None</td>\n",
" </tr>\n",
" <tr>\n",
" <td>7</td>\n",
" <td>2</td>\n",
" <td>inf</td>\n",
" <td>None</td>\n",
" </tr>\n",
" <tr>\n",
" <td>7</td>\n",
" <td>3</td>\n",
" <td>inf</td>\n",
" <td>None</td>\n",
" </tr>\n",
" <tr>\n",
" <td>7</td>\n",
" <td>4</td>\n",
" <td>inf</td>\n",
" <td>None</td>\n",
" </tr>\n",
" <tr>\n",
" <td>7</td>\n",
" <td>5</td>\n",
" <td>inf</td>\n",
" <td>None</td>\n",
" </tr>\n",
" <tr>\n",
" <td>7</td>\n",
" <td>6</td>\n",
" <td>inf</td>\n",
" <td>None</td>\n",
" </tr>\n",
" <tr>\n",
" <td>7</td>\n",
" <td>7</td>\n",
" <td>0.0</td>\n",
" <td>7</td>\n",
" </tr>\n",
"</table>"
],
"text/plain": [
"[(0, 0, 0.0, 0),\n",
" (0, 1, 1.0, 1),\n",
" (0, 2, 1.0, 2),\n",
" (0, 3, 2.0, 2),\n",
" (0, 4, 10.0, 4),\n",
" (0, 5, 2.0, 2),\n",
" (0, 6, 3.0, 5),\n",
" (0, 7, 4.0, 6),\n",
" (1, 0, 4.0, 3),\n",
" (1, 1, 0.0, 1),\n",
" (1, 2, 2.0, 2),\n",
" (1, 3, 3.0, 2),\n",
" (1, 4, 14.0, 0),\n",
" (1, 5, 3.0, 2),\n",
" (1, 6, 4.0, 5),\n",
" (1, 7, 5.0, 6),\n",
" (2, 0, 2.0, 3),\n",
" (2, 1, 3.0, 0),\n",
" (2, 2, 0.0, 2),\n",
" (2, 3, 1.0, 3),\n",
" (2, 4, 12.0, 0),\n",
" (2, 5, 1.0, 5),\n",
" (2, 6, 2.0, 5),\n",
" (2, 7, 3.0, 6),\n",
" (3, 0, 1.0, 0),\n",
" (3, 1, 2.0, 0),\n",
" (3, 2, 2.0, 0),\n",
" (3, 3, 0.0, 3),\n",
" (3, 4, 11.0, 0),\n",
" (3, 5, 3.0, 2),\n",
" (3, 6, 4.0, 5),\n",
" (3, 7, 5.0, 6),\n",
" (4, 0, -2.0, 0),\n",
" (4, 1, -1.0, 0),\n",
" (4, 2, -1.0, 0),\n",
" (4, 3, 0.0, 2),\n",
" (4, 4, 0.0, 4),\n",
" (4, 5, 0.0, 2),\n",
" (4, 6, 1.0, 5),\n",
" (4, 7, 2.0, 6),\n",
" (5, 0, inf, None),\n",
" (5, 1, inf, None),\n",
" (5, 2, inf, None),\n",
" (5, 3, inf, None),\n",
" (5, 4, inf, None),\n",
" (5, 5, 0.0, 5),\n",
" (5, 6, 1.0, 6),\n",
" (5, 7, 2.0, 6),\n",
" (6, 0, inf, None),\n",
" (6, 1, inf, None),\n",
" (6, 2, inf, None),\n",
" (6, 3, inf, None),\n",
" (6, 4, inf, None),\n",
" (6, 5, inf, None),\n",
" (6, 6, 0.0, 6),\n",
" (6, 7, 1.0, 7),\n",
" (7, 0, inf, None),\n",
" (7, 1, inf, None),\n",
" (7, 2, inf, None),\n",
" (7, 3, inf, None),\n",
" (7, 4, inf, None),\n",
" (7, 5, inf, None),\n",
" (7, 6, inf, None),\n",
" (7, 7, 0.0, 7)]"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"%%sql\n",
"DROP TABLE IF EXISTS out, out_summary;\n",
"\n",
"SELECT madlib.graph_apsp(\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",
" 'out'); -- Output table of shortest paths\n",
"\n",
"SELECT * FROM out ORDER BY src,dest;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# 3. Get the shortest path from vertex 0 to vertex 5"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"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": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"%%sql\n",
"DROP TABLE IF EXISTS out_path;\n",
"SELECT madlib.graph_apsp_get_path('out',0,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": 12,
"metadata": {},
"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": 12,
"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. Calculate the shortest paths"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Done.\n",
"1 rows affected.\n",
"64 rows affected.\n"
]
},
{
"data": {
"text/html": [
"<table>\n",
" <tr>\n",
" <th>e_src</th>\n",
" <th>dest</th>\n",
" <th>e_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>1</td>\n",
" </tr>\n",
" <tr>\n",
" <td>0</td>\n",
" <td>2</td>\n",
" <td>1.0</td>\n",
" <td>2</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>4</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>4.0</td>\n",
" <td>3</td>\n",
" </tr>\n",
" <tr>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>0.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>2</td>\n",
" </tr>\n",
" <tr>\n",
" <td>1</td>\n",
" <td>3</td>\n",
" <td>3.0</td>\n",
" <td>2</td>\n",
" </tr>\n",
" <tr>\n",
" <td>1</td>\n",
" <td>4</td>\n",
" <td>14.0</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <td>1</td>\n",
" <td>5</td>\n",
" <td>3.0</td>\n",
" <td>2</td>\n",
" </tr>\n",
" <tr>\n",
" <td>1</td>\n",
" <td>6</td>\n",
" <td>4.0</td>\n",
" <td>5</td>\n",
" </tr>\n",
" <tr>\n",
" <td>1</td>\n",
" <td>7</td>\n",
" <td>5.0</td>\n",
" <td>6</td>\n",
" </tr>\n",
" <tr>\n",
" <td>2</td>\n",
" <td>0</td>\n",
" <td>2.0</td>\n",
" <td>3</td>\n",
" </tr>\n",
" <tr>\n",
" <td>2</td>\n",
" <td>1</td>\n",
" <td>3.0</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <td>2</td>\n",
" <td>2</td>\n",
" <td>0.0</td>\n",
" <td>2</td>\n",
" </tr>\n",
" <tr>\n",
" <td>2</td>\n",
" <td>3</td>\n",
" <td>1.0</td>\n",
" <td>3</td>\n",
" </tr>\n",
" <tr>\n",
" <td>2</td>\n",
" <td>4</td>\n",
" <td>12.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>5</td>\n",
" </tr>\n",
" <tr>\n",
" <td>2</td>\n",
" <td>6</td>\n",
" <td>2.0</td>\n",
" <td>5</td>\n",
" </tr>\n",
" <tr>\n",
" <td>2</td>\n",
" <td>7</td>\n",
" <td>3.0</td>\n",
" <td>6</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>3</td>\n",
" <td>1</td>\n",
" <td>2.0</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <td>3</td>\n",
" <td>2</td>\n",
" <td>2.0</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <td>3</td>\n",
" <td>3</td>\n",
" <td>0.0</td>\n",
" <td>3</td>\n",
" </tr>\n",
" <tr>\n",
" <td>3</td>\n",
" <td>4</td>\n",
" <td>11.0</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <td>3</td>\n",
" <td>5</td>\n",
" <td>3.0</td>\n",
" <td>2</td>\n",
" </tr>\n",
" <tr>\n",
" <td>3</td>\n",
" <td>6</td>\n",
" <td>4.0</td>\n",
" <td>5</td>\n",
" </tr>\n",
" <tr>\n",
" <td>3</td>\n",
" <td>7</td>\n",
" <td>5.0</td>\n",
" <td>6</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>4</td>\n",
" <td>1</td>\n",
" <td>-1.0</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <td>4</td>\n",
" <td>2</td>\n",
" <td>-1.0</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <td>4</td>\n",
" <td>3</td>\n",
" <td>0.0</td>\n",
" <td>2</td>\n",
" </tr>\n",
" <tr>\n",
" <td>4</td>\n",
" <td>4</td>\n",
" <td>0.0</td>\n",
" <td>4</td>\n",
" </tr>\n",
" <tr>\n",
" <td>4</td>\n",
" <td>5</td>\n",
" <td>0.0</td>\n",
" <td>2</td>\n",
" </tr>\n",
" <tr>\n",
" <td>4</td>\n",
" <td>6</td>\n",
" <td>1.0</td>\n",
" <td>5</td>\n",
" </tr>\n",
" <tr>\n",
" <td>4</td>\n",
" <td>7</td>\n",
" <td>2.0</td>\n",
" <td>6</td>\n",
" </tr>\n",
" <tr>\n",
" <td>5</td>\n",
" <td>0</td>\n",
" <td>inf</td>\n",
" <td>None</td>\n",
" </tr>\n",
" <tr>\n",
" <td>5</td>\n",
" <td>1</td>\n",
" <td>inf</td>\n",
" <td>None</td>\n",
" </tr>\n",
" <tr>\n",
" <td>5</td>\n",
" <td>2</td>\n",
" <td>inf</td>\n",
" <td>None</td>\n",
" </tr>\n",
" <tr>\n",
" <td>5</td>\n",
" <td>3</td>\n",
" <td>inf</td>\n",
" <td>None</td>\n",
" </tr>\n",
" <tr>\n",
" <td>5</td>\n",
" <td>4</td>\n",
" <td>inf</td>\n",
" <td>None</td>\n",
" </tr>\n",
" <tr>\n",
" <td>5</td>\n",
" <td>5</td>\n",
" <td>0.0</td>\n",
" <td>5</td>\n",
" </tr>\n",
" <tr>\n",
" <td>5</td>\n",
" <td>6</td>\n",
" <td>1.0</td>\n",
" <td>6</td>\n",
" </tr>\n",
" <tr>\n",
" <td>5</td>\n",
" <td>7</td>\n",
" <td>2.0</td>\n",
" <td>6</td>\n",
" </tr>\n",
" <tr>\n",
" <td>6</td>\n",
" <td>0</td>\n",
" <td>inf</td>\n",
" <td>None</td>\n",
" </tr>\n",
" <tr>\n",
" <td>6</td>\n",
" <td>1</td>\n",
" <td>inf</td>\n",
" <td>None</td>\n",
" </tr>\n",
" <tr>\n",
" <td>6</td>\n",
" <td>2</td>\n",
" <td>inf</td>\n",
" <td>None</td>\n",
" </tr>\n",
" <tr>\n",
" <td>6</td>\n",
" <td>3</td>\n",
" <td>inf</td>\n",
" <td>None</td>\n",
" </tr>\n",
" <tr>\n",
" <td>6</td>\n",
" <td>4</td>\n",
" <td>inf</td>\n",
" <td>None</td>\n",
" </tr>\n",
" <tr>\n",
" <td>6</td>\n",
" <td>5</td>\n",
" <td>inf</td>\n",
" <td>None</td>\n",
" </tr>\n",
" <tr>\n",
" <td>6</td>\n",
" <td>6</td>\n",
" <td>0.0</td>\n",
" <td>6</td>\n",
" </tr>\n",
" <tr>\n",
" <td>6</td>\n",
" <td>7</td>\n",
" <td>1.0</td>\n",
" <td>7</td>\n",
" </tr>\n",
" <tr>\n",
" <td>7</td>\n",
" <td>0</td>\n",
" <td>inf</td>\n",
" <td>None</td>\n",
" </tr>\n",
" <tr>\n",
" <td>7</td>\n",
" <td>1</td>\n",
" <td>inf</td>\n",
" <td>None</td>\n",
" </tr>\n",
" <tr>\n",
" <td>7</td>\n",
" <td>2</td>\n",
" <td>inf</td>\n",
" <td>None</td>\n",
" </tr>\n",
" <tr>\n",
" <td>7</td>\n",
" <td>3</td>\n",
" <td>inf</td>\n",
" <td>None</td>\n",
" </tr>\n",
" <tr>\n",
" <td>7</td>\n",
" <td>4</td>\n",
" <td>inf</td>\n",
" <td>None</td>\n",
" </tr>\n",
" <tr>\n",
" <td>7</td>\n",
" <td>5</td>\n",
" <td>inf</td>\n",
" <td>None</td>\n",
" </tr>\n",
" <tr>\n",
" <td>7</td>\n",
" <td>6</td>\n",
" <td>inf</td>\n",
" <td>None</td>\n",
" </tr>\n",
" <tr>\n",
" <td>7</td>\n",
" <td>7</td>\n",
" <td>0.0</td>\n",
" <td>7</td>\n",
" </tr>\n",
"</table>"
],
"text/plain": [
"[(0, 0, 0.0, 0),\n",
" (0, 1, 1.0, 1),\n",
" (0, 2, 1.0, 2),\n",
" (0, 3, 2.0, 2),\n",
" (0, 4, 10.0, 4),\n",
" (0, 5, 2.0, 2),\n",
" (0, 6, 3.0, 5),\n",
" (0, 7, 4.0, 6),\n",
" (1, 0, 4.0, 3),\n",
" (1, 1, 0.0, 1),\n",
" (1, 2, 2.0, 2),\n",
" (1, 3, 3.0, 2),\n",
" (1, 4, 14.0, 0),\n",
" (1, 5, 3.0, 2),\n",
" (1, 6, 4.0, 5),\n",
" (1, 7, 5.0, 6),\n",
" (2, 0, 2.0, 3),\n",
" (2, 1, 3.0, 0),\n",
" (2, 2, 0.0, 2),\n",
" (2, 3, 1.0, 3),\n",
" (2, 4, 12.0, 0),\n",
" (2, 5, 1.0, 5),\n",
" (2, 6, 2.0, 5),\n",
" (2, 7, 3.0, 6),\n",
" (3, 0, 1.0, 0),\n",
" (3, 1, 2.0, 0),\n",
" (3, 2, 2.0, 0),\n",
" (3, 3, 0.0, 3),\n",
" (3, 4, 11.0, 0),\n",
" (3, 5, 3.0, 2),\n",
" (3, 6, 4.0, 5),\n",
" (3, 7, 5.0, 6),\n",
" (4, 0, -2.0, 0),\n",
" (4, 1, -1.0, 0),\n",
" (4, 2, -1.0, 0),\n",
" (4, 3, 0.0, 2),\n",
" (4, 4, 0.0, 4),\n",
" (4, 5, 0.0, 2),\n",
" (4, 6, 1.0, 5),\n",
" (4, 7, 2.0, 6),\n",
" (5, 0, inf, None),\n",
" (5, 1, inf, None),\n",
" (5, 2, inf, None),\n",
" (5, 3, inf, None),\n",
" (5, 4, inf, None),\n",
" (5, 5, 0.0, 5),\n",
" (5, 6, 1.0, 6),\n",
" (5, 7, 2.0, 6),\n",
" (6, 0, inf, None),\n",
" (6, 1, inf, None),\n",
" (6, 2, inf, None),\n",
" (6, 3, inf, None),\n",
" (6, 4, inf, None),\n",
" (6, 5, inf, None),\n",
" (6, 6, 0.0, 6),\n",
" (6, 7, 1.0, 7),\n",
" (7, 0, inf, None),\n",
" (7, 1, inf, None),\n",
" (7, 2, inf, None),\n",
" (7, 3, inf, None),\n",
" (7, 4, inf, None),\n",
" (7, 5, inf, None),\n",
" (7, 6, inf, None),\n",
" (7, 7, 0.0, 7)]"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"%%sql\n",
"DROP TABLE IF EXISTS out_alt, out_alt_summary;\n",
"\n",
"SELECT madlib.graph_apsp(\n",
" 'vertex_alt', -- Vertex table\n",
" 'v_id', -- Vertex 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",
" 'out_alt'); -- Output table of shortest paths\n",
"\n",
"SELECT * FROM out_alt ORDER BY e_src, dest;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# 6. Grouping\n",
"Create a graph with 2 groups and find APSP for each group:"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"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": 17,
"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": "markdown",
"metadata": {},
"source": [
"# 7. Find APSP for all groups"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Done.\n",
"1 rows affected.\n",
"28 rows affected.\n"
]
},
{
"data": {
"text/html": [
"<table>\n",
" <tr>\n",
" <th>grp</th>\n",
" <th>src</th>\n",
" <th>dest</th>\n",
" <th>weight</th>\n",
" <th>parent</th>\n",
" </tr>\n",
" <tr>\n",
" <td>0</td>\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>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>0</td>\n",
" <td>2</td>\n",
" <td>1.0</td>\n",
" <td>2</td>\n",
" </tr>\n",
" <tr>\n",
" <td>0</td>\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>0</td>\n",
" <td>4</td>\n",
" <td>10.0</td>\n",
" <td>4</td>\n",
" </tr>\n",
" <tr>\n",
" <td>0</td>\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>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>0</td>\n",
" <td>7</td>\n",
" <td>4.0</td>\n",
" <td>6</td>\n",
" </tr>\n",
" <tr>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>0</td>\n",
" <td>4.0</td>\n",
" <td>3</td>\n",
" </tr>\n",
" <tr>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>0.0</td>\n",
" <td>1</td>\n",
" </tr>\n",
" <tr>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>2</td>\n",
" <td>2.0</td>\n",
" <td>2</td>\n",
" </tr>\n",
" <tr>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>3</td>\n",
" <td>3.0</td>\n",
" <td>2</td>\n",
" </tr>\n",
" <tr>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>4</td>\n",
" <td>14.0</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>5</td>\n",
" <td>3.0</td>\n",
" <td>2</td>\n",
" </tr>\n",
" <tr>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>6</td>\n",
" <td>4.0</td>\n",
" <td>5</td>\n",
" </tr>\n",
" <tr>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>7</td>\n",
" <td>5.0</td>\n",
" <td>6</td>\n",
" </tr>\n",
" <tr>\n",
" <td>1</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0.0</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <td>1</td>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>1.0</td>\n",
" <td>1</td>\n",
" </tr>\n",
" <tr>\n",
" <td>1</td>\n",
" <td>0</td>\n",
" <td>2</td>\n",
" <td>1.0</td>\n",
" <td>2</td>\n",
" </tr>\n",
" <tr>\n",
" <td>1</td>\n",
" <td>0</td>\n",
" <td>3</td>\n",
" <td>2.0</td>\n",
" <td>2</td>\n",
" </tr>\n",
" <tr>\n",
" <td>1</td>\n",
" <td>0</td>\n",
" <td>4</td>\n",
" <td>10.0</td>\n",
" <td>4</td>\n",
" </tr>\n",
" <tr>\n",
" <td>1</td>\n",
" <td>0</td>\n",
" <td>5</td>\n",
" <td>-10.0</td>\n",
" <td>4</td>\n",
" </tr>\n",
" <tr>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>0</td>\n",
" <td>4.0</td>\n",
" <td>3</td>\n",
" </tr>\n",
" <tr>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>0.0</td>\n",
" <td>1</td>\n",
" </tr>\n",
" <tr>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>2</td>\n",
" <td>2.0</td>\n",
" <td>2</td>\n",
" </tr>\n",
" <tr>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>3</td>\n",
" <td>3.0</td>\n",
" <td>2</td>\n",
" </tr>\n",
" <tr>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>4</td>\n",
" <td>14.0</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>5</td>\n",
" <td>-6.0</td>\n",
" <td>4</td>\n",
" </tr>\n",
"</table>"
],
"text/plain": [
"[(0, 0, 0, 0.0, 0),\n",
" (0, 0, 1, 1.0, 1),\n",
" (0, 0, 2, 1.0, 2),\n",
" (0, 0, 3, 2.0, 2),\n",
" (0, 0, 4, 10.0, 4),\n",
" (0, 0, 5, 2.0, 2),\n",
" (0, 0, 6, 3.0, 5),\n",
" (0, 0, 7, 4.0, 6),\n",
" (0, 1, 0, 4.0, 3),\n",
" (0, 1, 1, 0.0, 1),\n",
" (0, 1, 2, 2.0, 2),\n",
" (0, 1, 3, 3.0, 2),\n",
" (0, 1, 4, 14.0, 0),\n",
" (0, 1, 5, 3.0, 2),\n",
" (0, 1, 6, 4.0, 5),\n",
" (0, 1, 7, 5.0, 6),\n",
" (1, 0, 0, 0.0, 0),\n",
" (1, 0, 1, 1.0, 1),\n",
" (1, 0, 2, 1.0, 2),\n",
" (1, 0, 3, 2.0, 2),\n",
" (1, 0, 4, 10.0, 4),\n",
" (1, 0, 5, -10.0, 4),\n",
" (1, 1, 0, 4.0, 3),\n",
" (1, 1, 1, 0.0, 1),\n",
" (1, 1, 2, 2.0, 2),\n",
" (1, 1, 3, 3.0, 2),\n",
" (1, 1, 4, 14.0, 0),\n",
" (1, 1, 5, -6.0, 4)]"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"%%sql\n",
"DROP TABLE IF EXISTS out_gr, out_gr_summary;\n",
"\n",
"SELECT madlib.graph_apsp(\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",
" 'out_gr', -- Output table of shortest paths\n",
" 'grp' -- Grouping columns\n",
");\n",
"\n",
"SELECT * FROM out_gr WHERE src < 2 ORDER BY grp,src,dest;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# 8. Find the path from vertex 0 to vertex 5 in every group"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"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": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"%%sql\n",
"DROP TABLE IF EXISTS out_gr_path;\n",
"SELECT madlib.graph_apsp_get_path('out_gr',0,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": 1
}