Google Git
Sign in
apache / madlib-site / 5455828f6b559fc1057ac4019a665185cc458fce / . / community-artifacts / Graph / SSSP-v2.ipynb
blob: 3a84d5ad6a129a354976ebf13b748d2211ca23fa [file] [log] [blame]
{
"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
}