{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Tutorial" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This is a brief tutorial of basic Metagraph usage.\n", "\n", "First, we import Metagraph:" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "execution": { "iopub.execute_input": "2020-12-08T20:14:50.455572Z", "iopub.status.busy": "2020-12-08T20:14:50.446284Z", "iopub.status.idle": "2020-12-08T20:14:50.689190Z", "shell.execute_reply": "2020-12-08T20:14:50.690460Z" } }, "outputs": [], "source": [ "import metagraph as mg" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Inspecting Types and Available Algorithms\n", "\n", "The default resolver automatically pulls in all registered Metagraph plugins." ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "execution": { "iopub.execute_input": "2020-12-08T20:14:50.696027Z", "iopub.status.busy": "2020-12-08T20:14:50.694423Z", "iopub.status.idle": "2020-12-08T20:14:53.956765Z", "shell.execute_reply": "2020-12-08T20:14:53.957376Z" } }, "outputs": [], "source": [ "res = mg.resolver" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "A hierarchy of available types is automatically added as properties on `res`." ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "execution": { "iopub.execute_input": "2020-12-08T20:14:53.962001Z", "iopub.status.busy": "2020-12-08T20:14:53.960348Z", "iopub.status.idle": "2020-12-08T20:14:53.981939Z", "shell.execute_reply": "2020-12-08T20:14:53.983027Z" } }, "outputs": [ { "data": { "text/plain": [ "['BipartiteGraph',\n", " 'DataFrame',\n", " 'EdgeMap',\n", " 'EdgeSet',\n", " 'Graph',\n", " 'Matrix',\n", " 'NodeMap',\n", " 'NodeSet',\n", " 'Vector']" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "dir(res.types)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Two important concepts in Metagraph are abstract types and concrete types. \n", "\n", "Abstract types describe a generic kind of data container with potentially many equivalent representations.\n", "\n", "Concrete types describe a specific data object which fits under the abstract type category.\n", "\n", "One can think of abstract types as data container specifications and concrete types as implementations of those specifications.\n", "\n", "For each abstract type, there are several concrete types.\n", "\n", "Within a single abstract type, all concrete types are able to represent equivalent data, but in a different format or data structure.\n", "\n", "Here we show the concrete types which represent `Graphs`:" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "execution": { "iopub.execute_input": "2020-12-08T20:14:53.988165Z", "iopub.status.busy": "2020-12-08T20:14:53.986647Z", "iopub.status.idle": "2020-12-08T20:14:53.995486Z", "shell.execute_reply": "2020-12-08T20:14:53.996513Z" } }, "outputs": [ { "data": { "text/plain": [ "['GrblasGraphType', 'NetworkXGraphType', 'ScipyGraphType']" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "dir(res.types.Graph)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Algorithms are also listed under `res.algos` and grouped by categories." ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "execution": { "iopub.execute_input": "2020-12-08T20:14:54.001579Z", "iopub.status.busy": "2020-12-08T20:14:54.000063Z", "iopub.status.idle": "2020-12-08T20:14:54.008968Z", "shell.execute_reply": "2020-12-08T20:14:54.010070Z" } }, "outputs": [ { "data": { "text/plain": [ "['bipartite',\n", " 'centrality',\n", " 'clustering',\n", " 'embedding',\n", " 'flow',\n", " 'subgraph',\n", " 'traversal',\n", " 'util']" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "dir(res.algos)" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "execution": { "iopub.execute_input": "2020-12-08T20:14:54.016609Z", "iopub.status.busy": "2020-12-08T20:14:54.013111Z", "iopub.status.idle": "2020-12-08T20:14:54.022531Z", "shell.execute_reply": "2020-12-08T20:14:54.023262Z" } }, "outputs": [ { "data": { "text/plain": [ "['all_pairs_shortest_paths',\n", " 'astar_search',\n", " 'bellman_ford',\n", " 'bfs_iter',\n", " 'bfs_tree',\n", " 'dfs_iter',\n", " 'dfs_tree',\n", " 'dijkstra',\n", " 'minimum_spanning_tree']" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "dir(res.algos.traversal)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Example Usage\n", "\n", "Let's see how to use Metagraph by first constructing a graph from an edge list.\n", "\n", "Begin with an input csv file representing an edge list and weights." ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "execution": { "iopub.execute_input": "2020-12-08T20:14:54.029513Z", "iopub.status.busy": "2020-12-08T20:14:54.028621Z", "iopub.status.idle": "2020-12-08T20:14:54.033217Z", "shell.execute_reply": "2020-12-08T20:14:54.033945Z" } }, "outputs": [], "source": [ "data = \"\"\"\n", "Source,Destination,Weight\n", "0,1,4\n", "0,3,2\n", "0,4,7\n", "1,3,3\n", "1,4,5\n", "2,4,5\n", "2,5,2\n", "2,6,8\n", "3,4,1\n", "4,7,4\n", "5,6,4\n", "5,7,6\n", "\"\"\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Read in the csv file and convert to a Pandas `DataFrame`." ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "execution": { "iopub.execute_input": "2020-12-08T20:14:54.044336Z", "iopub.status.busy": "2020-12-08T20:14:54.043162Z", "iopub.status.idle": "2020-12-08T20:14:54.047558Z", "shell.execute_reply": "2020-12-08T20:14:54.048659Z" } }, "outputs": [], "source": [ "import pandas as pd\n", "import io\n", "csv_file = io.StringIO(data)\n", "df = pd.read_csv(csv_file)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This `DataFrame` represents a graph’s edges, but Metagraph doesn’t know that yet. To use the `DataFrame` within Metagraph, we first need to convert it into an `EdgeMap`.\n", "\n", "A `PandasEdgeMap` takes a `DataFrame` plus the labels of the columns representing source, destination, and weight. With these, Metagraph will know how to interpret the `DataFrame` as an `EdgeMap`." ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "execution": { "iopub.execute_input": "2020-12-08T20:14:54.053529Z", "iopub.status.busy": "2020-12-08T20:14:54.051978Z", "iopub.status.idle": "2020-12-08T20:14:54.077310Z", "shell.execute_reply": "2020-12-08T20:14:54.078380Z" } }, "outputs": [ { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
SourceDestinationWeight
0014
1032
2047
3133
4145
5245
6252
7268
8341
9474
10564
11576
\n", "
" ], "text/plain": [ " Source Destination Weight\n", "0 0 1 4\n", "1 0 3 2\n", "2 0 4 7\n", "3 1 3 3\n", "4 1 4 5\n", "5 2 4 5\n", "6 2 5 2\n", "7 2 6 8\n", "8 3 4 1\n", "9 4 7 4\n", "10 5 6 4\n", "11 5 7 6" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "em = res.wrappers.EdgeMap.PandasEdgeMap(df, 'Source', 'Destination', 'Weight', is_directed=False)\n", "em.value" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Convert EdgeMap to a Graph\n", "\n", "`Graphs` and `EdgeMaps` have many similarities, but `Graphs` are more powerful. `Graphs` can have weights on the nodes, not just on the edges. `Graphs` can also have isolate nodes (nodes with no edges), which `EdgeMaps` cannot have.\n", "\n", "Most Metagraph algorithms take a `Graph` as input, so we will convert our `PandasEdgeMap` into a `Graph`. In this case, it will become a `NetworkXGraph`." ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "execution": { "iopub.execute_input": "2020-12-08T20:14:54.083168Z", "iopub.status.busy": "2020-12-08T20:14:54.081673Z", "iopub.status.idle": "2020-12-08T20:14:54.094540Z", "shell.execute_reply": "2020-12-08T20:14:54.095636Z" } }, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "g = res.algos.util.graph.build(em)\n", "g" ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "execution": { "iopub.execute_input": "2020-12-08T20:14:54.100382Z", "iopub.status.busy": "2020-12-08T20:14:54.098792Z", "iopub.status.idle": "2020-12-08T20:14:54.107890Z", "shell.execute_reply": "2020-12-08T20:14:54.108996Z" } }, "outputs": [ { "data": { "text/plain": [ "EdgeDataView([(0, 1, {'weight': 4}), (0, 3, {'weight': 2}), (0, 4, {'weight': 7}), (1, 3, {'weight': 3}), (1, 4, {'weight': 5}), (3, 4, {'weight': 1}), (4, 2, {'weight': 5}), (4, 7, {'weight': 4}), (2, 5, {'weight': 2}), (2, 6, {'weight': 8}), (5, 6, {'weight': 4}), (5, 7, {'weight': 6})])" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "g.value.edges(data=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Translate to other Graph formats\n", "\n", "Because Metagraph knows how to interpret `g` as a `Graph`, we can easily convert it other `Graph` formats.\n", "\n", "Let's convert it to a `ScipyGraph`. This format stores the edges and weights in a scipy.sparse matrix along with a numpy array mapping the position to a NodeId (in case the nodes are not sequential from 0..n). Any node weights are stored in a separate numpy array." ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "execution": { "iopub.execute_input": "2020-12-08T20:14:54.113573Z", "iopub.status.busy": "2020-12-08T20:14:54.112146Z", "iopub.status.idle": "2020-12-08T20:14:54.122871Z", "shell.execute_reply": "2020-12-08T20:14:54.123969Z" } }, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "g2 = res.translate(g, res.wrappers.Graph.ScipyGraph)\n", "g2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The matrix is accessed using `g2.value`. The node list is accessed using `.node_list`.\n", "\n", "We can verify the weighs and edges by inspecting the sparse adjacency matrix directly." ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "execution": { "iopub.execute_input": "2020-12-08T20:14:54.128798Z", "iopub.status.busy": "2020-12-08T20:14:54.127300Z", "iopub.status.idle": "2020-12-08T20:14:54.136404Z", "shell.execute_reply": "2020-12-08T20:14:54.137456Z" } }, "outputs": [ { "data": { "text/plain": [ "array([[0, 4, 0, 2, 7, 0, 0, 0],\n", " [4, 0, 0, 3, 5, 0, 0, 0],\n", " [0, 0, 0, 0, 5, 2, 8, 0],\n", " [2, 3, 0, 0, 1, 0, 0, 0],\n", " [7, 5, 5, 1, 0, 0, 0, 4],\n", " [0, 0, 2, 0, 0, 0, 4, 6],\n", " [0, 0, 8, 0, 0, 4, 0, 0],\n", " [0, 0, 0, 0, 4, 6, 0, 0]])" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "g2.value.toarray()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can also convert `g` into an adjacency matrix representation using a `GrblasGraph`. This also stores the edges and node weights separately." ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "execution": { "iopub.execute_input": "2020-12-08T20:14:54.142279Z", "iopub.status.busy": "2020-12-08T20:14:54.140829Z", "iopub.status.idle": "2020-12-08T20:14:54.151325Z", "shell.execute_reply": "2020-12-08T20:14:54.152349Z" } }, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "g3 = res.translate(g, res.types.Graph.GrblasGraphType)\n", "g3" ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "execution": { "iopub.execute_input": "2020-12-08T20:14:54.157126Z", "iopub.status.busy": "2020-12-08T20:14:54.155553Z", "iopub.status.idle": "2020-12-08T20:14:54.187485Z", "shell.execute_reply": "2020-12-08T20:14:54.188608Z" } }, "outputs": [ { "data": { "text/html": [ "
\n", "\n", "
M0
\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
grblas.Matrix
nvals
nrows
ncols
dtype
2488INT64
\n", "
\n", "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
01234567
0427
1435
2528
3231
475514
5246
684
746
\n", "
" ], "text/plain": [ "\"M_0\" nvals nrows ncols dtype\n", "grblas.Matrix 24 8 8 INT64\n", "-----------------------------------------\n", " 0 1 2 3 4 5 6 7\n", "0 4 2 7 \n", "1 4 3 5 \n", "2 5 2 8 \n", "3 2 3 1 \n", "4 7 5 5 1 4\n", "5 2 4 6\n", "6 8 4 \n", "7 4 6 " ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "g3.value" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can also visualize the graph." ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "execution": { "iopub.execute_input": "2020-12-08T20:14:54.193746Z", "iopub.status.busy": "2020-12-08T20:14:54.192160Z", "iopub.status.idle": "2020-12-08T20:14:57.945522Z", "shell.execute_reply": "2020-12-08T20:14:57.946652Z" } }, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAV0AAADnCAYAAAC9roUQAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8vihELAAAACXBIWXMAAAsTAAALEwEAmpwYAAA59UlEQVR4nO3dd3hUZfbA8e9kkslkhhq6gRADQQKolIjs0kmQbkMQBUTQRZQiZdH9CUpZyy4uCBZ26YggKihgQyQKKKwQCSAQWgIkgVACyVLTpry/Py6JgMlMypSU83meebLO3PveM6webt77vufolFIIIYTwDB9vByCEEBWJJF0hhPAgSbpCCOFBknSFEMKDJOkKIYQH+Tr6sGbNmiokJMRDoQghRPkQGxt7USlVK7/PHCbdkJAQdu/e7Z6ohBCinNLpdEkFfSbTC0II4UGSdIUQwoMk6QohhAdJ0hVCCA+SpCuEEB7kcPWCEEKUWVYrJCZCVhYYjRASAr7eT3nej0AIIVwlLQ2WLoVly+D4cfDzA70ebDbIyYHGjWH4cHjmGQgM9EqIMr0ghCj7cnJgyhSoXx+mTYPDh7X3rl+HK1e0nxaL9v60aRAUpB2fk+PxUCXpCiHKtuRkaNEC5s7VphIyMx0fn5mpHTd3rnZecrInoswjSVcIUXYlJ0NEBJw4ARkZRTs3I0M7LyLCo4lXkq4QomzKyYGoKEhP1+Zsi8Nm086PitKmHzxAkq4QomyaMQNSUoqfcHPZbNo4M2a4Ji4nJOkKIcqetDSYM6foUwoFyciA2bO1u143k6QrhCh7li4Fnc7hIUOAekAVoAmw2NmYOh0sWeKS8ByRpCuEKHuWLXO6SuH/gETgCvAlMBWIdXRCZiYsX+6a+ByQpCuEKFusVm3jgxPNAf8b/1t34+X0rIQEbXw3kqQrhChbEhO1nWaF8AJgApqiTTX0dnaCn582vhtJ0hVClC1ZWdrW3kKYD1wFfgYe5fc73wLp9dr4biRJVwhRthiNRVompgc6AKeBfzs72GbTxncjKXgjhCi1tmzZwpkzZ2jRogVNmzbF398fQkJQFguO1y78kZVCzOlaLFo1MjeSpCuEKLWWLl3Kp59+ir+/PxkZGej1ekwmE4fNZuo5KFaTCvwI9AUCgGhgNfCxsws2buz28o+SdIUQpdKZM2e4evUqVqsVy01bdF955RXqKKXtICtg2ZgObSphFGAHGgJzgYccXTAgQCv76GaSdIUQpcaOHTuYO3cuW7ZsIS0tjcDAQHQ6HUopqlWrxrZt27jnnnu0nWPTpxc4Ti1gW1EvrhSMGFGC6AtHHqQJIbzGarWybNkyOnToQEBAAB07dmTv3r0MHz6clJQU0tLS6NChAzVr1mTXrl20aNGC06dP89aCBSytVg17QIBrAjGZYNIkjxQ2lztdIYRHXbx4kXfeeYe1a9eSkJCAr68vrVq1Ys6cOTzzzDMYDIZbjl+8eDGjR48mKiqKc+fOYbVaUUrx8oQJ+Hz9tVaesSRFb/R6raj5tGkl/GaFI0lXCFFs27dv55NPPqFmzZo88cQT3HXXXfket2fPHubMmcPmzZtJTU2lWrVqdO7cmfnz5xMZGenwGo0bN+bSpUucPn0apRQAbdu25R9z5sD48Vo93OKWd9Trtbvb6OhCb7goKZleEEIUy7x585g0aRIhISEopRg7diyXL1/O+1wpxRdffIHZbCYiIoLt27czcOBATp48yf/+9z/Wr1/vNOEC2Gw2atasmZdwjUYjK1as0D4MDobdu8msVw/rbXfITplMEBoKu3dr43iKUqrAV5s2bZQQQuTnyJEjKjU1VSmlVFZWlurbt6/au3fvLcekpqaqOXPmqOvXrxfrGjExMSowMFCZzWY1fvx4pdPp1IgRI2455vvvv1cBer2Kf/xxpYxGpQIClNIei+X/Mpm046ZMUSonp1hxOQPsVgXkVUm6QohisdvtSikt4Sql1L333qt27drlkrFtNpt6/vnnlU6nU926dVOZmZnKbrerWbNm5SX6y5cvq2effVbpdDoFKJvNplRamlKzZinVrJlSBoNSZrNSVapoPw0G7f2339aOcyNHSVenbtyy5yciIkLt3r3bUzfdQoj8WK1aEZasLG2LakiI2xfwF5ZSCp1Ox4YNG1ixYgWrVq3CWMJttPHx8XTr1o3U1FSWLFnCkCFD/nDM999/z6BBg7h27RoWiwWz2cy1a9duPciLf246nS5WKRWR32cypytEaZSWBm+/Dc2agdkMLVtC+/baT5NJe//ttz3S6eDatWvMmjWL77//nttv0nQ3ComvW7eOXr16lTjhzpw5k6ZNm1K7dm3Onj2bb8IFOHjwINevX8/bNFGrVq0/HuTrq+0wa9HCIzvNCq2gW2Al0wtCeF52tlKvvFK4ucmAAO24V17RznOhhIQE9fzzz6sGDRoonU6nzGazGjt2bN6Uws3i4+PV4MGDld1uV4mJiSomJibf4xw5e/asCg8PV3q9Xs2ZM6dQ5wwdOlTpdDrl6+urSluuQuZ0hSgDkpKUCgvTHvQ4Srb5PRgKC9POL4HvvvtO9e3bV1WtWlUBqm7duuqpp55S+/btc3jekCFDVK1atVRkZKQKDw9XixYtUhaLpdDX/c9//qN8fX1Vo0aNVFIhv8Pp06eVj4+Pev/999Xy5cvVwoULC309T5CkK0Rpl5SkVK1aSun1RUu4uS+9Xjs/n6SVnp6utm/f/of3MzMz1bvvvqsiIiKUn5+f8vHxUU2bNlWvvfaaSivkgyabzaamT5+uXnnlFXXkyJEifeWrV6+qdu3aKR8fH/XSSy8V6dzWrVursLCwIp3jSZJ0hSjNsrO1O9XiJtybE29Y2C3LoM6dO6caNWqkKleurKxWq0pOTlbjx49Xd955p9LpdCogIEB16tRJrVixokh3pyW1du1aZTQaVZ06ddSBAweKdO5nn32mdDqdOnTokJuiKzlJukKUZq+8UvQpBUdTDVOmKKWUSkpKUkFBQUqv1ytfX19VuXJlBaiaNWuqQYMGqZ07d3r8q2ZnZ6vevXsrnU6nhg8fri3zKgKLxaIqV66sBg8e7KYIXUOSrhCl1cWL2sMwB4k0DdTDoEyggkGtcpJ47Uaj+mjePOXr66uAvFdERIQ6e/as177qtm3bVJUqVVTVqlXVTz/9VKwxhg8frsxms0fvyovDUdKVJWNCeNPSpaBz3ANhNGAAzgOrgOeBOAfH2+x2Tkydir+/P0ajEYPBQEBAAOnp6dStW9dloReW3W7n6aefpkuXLnTq1IkLFy7QsWPHIo8THx/Phx9+yIIFC/AtLcu/ikE2RwjhTc2aweHDBX58HagOHASa3HhvKBAE/MPZuHFaar5w4QJxcXFkZWXRs2dPV0RdaAcOHKB79+5cuXKFVatW8cgjjxR7rPDwcAwGA7/99psLI3QPR5sjyu5fF0KUdVYrHHfctesYWmPFJje9dy+FKNCdkKCN7+tLrVq16NKlS0kiLZaXXnqJ2bNn065dOzZt2kSlSpWKPdbixYs5duwYJ0+edGGE3iHTC0J4S2Ki03KC14Cqt71XFa2tuEN+ftr4XpCcnEyjRo2YO3cu//73v9mxY0eJEm5OTg7jxo1j1KhRBHuyGpibyJ2uEN6SlaXVc3WgEnDltveuAJWdja3Xa+N72OzZs3n55Zdp2rQpp06dok6dOiUe08/Pj7179xIWFuaCCL1P7nSF8Baj0Wnh7SZorcPjb3rvN6C5s7FtNm18D0lPT6dVq1a89NJLTJ8+nYMHD7ok4YJW36FJkyb4+JSPdFU+voUQZVFICNzU5TY/ZuBR4DW0h2o7gA1oD9Mcsli08T3go48+ol69eqSlpXH06FGmTp3q8mvonKzwKEsk6QrhLb6+0KiR08PmA5lAbeAJtNbiTu90PVBVKyMjg27dujFs2DBGjhxJcnIyjRs3LtZY+/fvZ9WqVURHR5OTk+PiSEsXSbpCeNPw4eCko20gsB7tTjcZeNLZmAEB2rhutHHjRmrXrs3+/fuJiYnhvffeK/ZYWVlZDB8+nB07dvDCCy/w9ddfA9r63vJI1ukK4U3p6VonWlc+9DIaISXFLe3ErVYrTzzxBJ9//jkDBw7k448/LvFc65gxY/D19WXu3LmsX78+rxB606ZN6du3L/fee6+LovccKWIuRGkVGAgTJ2qFyV1AmUwwaZJbEm5MTAx16tRh48aNbNy4kU8++aTECffq1atcuHCBKVOmAPDOO+9Qu3Zthg8fjtVq5V//+he2krRXL40K2h+spPaCEJ7hoipjVp1OHQP17LBhaseOHSrHRU0Xb+5XFhkZqTIzM10ybq7cguc2m00tWbLkls969+6tYmNjXXo9T0BqLwhRihkMEB0NgYHYi3vnqNejr1mTx6pVY/GHHxIZGUmVKlXo1KkTJ06cKHZo8fHxNGzYkKVLl/LRRx8RHR1d4pY8t8tdmeDj48OIESPy3t+7dy+nTp3innvucen1vE2SrhClQXAwa//2N47b7diKmtRMJggNhd27mbl8OQaDgaysLLKysoiLiyv2etnp06fTtGlT6tSpw7lz5xg8eHCxximO7OxsnnvuOf7v//6vTBe3yY8kXSG8LCEhgZ49ezJg0iTuCwhAP3Gi9jDMyaoGTCbtuAkTtOI2wcH06dMnb8tto0aNiI+Px2w2Fymec+fOER4ezuuvv87s2bPZvXs31apVK+a3Kzq73c6pU6cYOnQoTzzxhMeu6ynl668QIcoQpRTjx49n0aJFZN1YvdC5e3d44w3tYdiSJbB8uVa8xs9P29prs2kbHxo31paFjRhxy0MzX19fxowZQ2xsLF999VWxYvLz86NKlSqcOHHCY7UO9u/fT9OmTfHz88PHx4fGjRszZswYj1zb0yTpCuElSini4uKw2+0opdDpdLRu3Vr7MDAQJk/WXlarVrwmK0u7sw0Jcbjx4a9//StmsznfXVxWqxVfX19sNhv6fOo+6HQ6AgMD2bVrl4u+pXN2u50uXboQFRXFZ599dkss5ZEkXSG8xMfHh40bN1KtWjV8fHzQ6/X57+jy9dXubAupcuX8y+FMnjyZs2fPsnLlSvR6fV6iv52nk92LL75IZmYmK1as8Oh1vUXmdIXwoqFDh6LT6Th06BC9e/emXbt2Lr+GUorJkyeza9cukpKSmDNnTt773pacnMz8+fOZN2+ey1dFlFayI00IL/nhhx/o3r07X3/9Nb1793brtVJSUrDb7aSlpTF06FBWr15NixYtCpxm8JSWLVuSlZXFkSNHvBaDO0jnCCFKmZycHB555BEeeughtydcgKCgIAAaNGjA0KFDGT9+PNHR0V5NuKtXr2b//v0cPXrUazF4g0wvCOEFjz76KD4+PqxZs8bj1x47diwmk4mZM2cCkJaW5vGpBqvVysiRI3nqqafKTXHywpI7XSE8bMOGDXz77bds3brVKwv/AwIC+OCDD3jkkUeIi4vD39+ff/3rX9SuXdtjMeTuPFu8eLHHrllaSNIVwoMyMjJ48sknGTJkCJ06dfJaHD4+Ppw5c4YqVarw4YcfejThHjlyhJUrV/LJJ5+Uu91mhSHTC0J4UJ8+fTCZTCxfvtzt1ypoykApxT/+8Q8mTpzIjz/+SIMGDdwei8ViYfz48cTHx/PQQw/RsmVLBg4c6PbrlkayekEID1m5ciVPPfUUMTExRETk+2DbJdLT04mMjGTBggXcd999+a67LWjVQm4+cPVa3cTERMLCwtDpdFgsFo4dO1au53Klnq4QXqaUolu3bkyZMsWtCXfFihV5/cpq1KhRYPIsaNWCUoq2bdsyb948l8aVmpqKyWTCYrHg6+tLp06dOH78uEuvUVZI0hXCA3Q6HfXq1ctbMeBqGRkZdO3alaeffprnnnuO5ORkGhWi/9rtfHx8GDhwIBMmTGD06NGkp6dz//3389tvv5UovgsXLpCRkQGAv78/YWFhHi2iU5pI0hXChbZu3cqpU6fy/Uyn07lli21uv7IDBw4QExPDu+++W6LxJk+ezOeff86CBQsICQnh119/5Z///KfzE61WrTjPwYPaT6s176Ndu3ZhtVoxm80sWrSIbdu2UaNGjRLFWWYVVN1cSecIIYokPj5eValSRf3lL3/xyPUsFovq37+/0ul0atCgQcpms7lsbJvNpjp37qwABSh/f3+Vnp7+xwMvXlRq1iylwsOVMhiUMpuVqlJF++nnp70/a5bqfPfdqn79+vmPUQ4hnSOEcL/Jkyczfvx4Tpw4wUsvvUR2drbbrrVr1y7q1KnDd999x6ZNm1i9enWJ+5Xd7JtvvmHbtm15c7/Z2dm33kHn5MCUKVC/PkybBocPa+9dvw5Xrmg/LRbt/WnT2HzoECeeeILqRaztWy4VlI2V3OkKUWh///vfVd++fZVSSsXGxqphw4apgwcPKqV+7wHmCjabTY0aNUrpdDoVFRXl8n5luaxWq/rll1/UzJkzVevWrRWgfHx81OnTp5VKStJ6uplMRevjZjJp5yUluSXm0gS50xXCfWw2GzVq1GDhwoUAhIeHU7t2bfr378/Ro0ddNo977NgxgoODWbZsGatWrWLz5s1uq8yl1+tp164dr776KrGxsVy/fp2xY8ey4vXXISICTpyAGw/GCi0jQzsvIgKSk90Sd1kg63SFcAF1ozbtzetfX331VTIyMnjjjTdKnBynT5/O3//+d1q1akV0dLR3nvzn5ECLFlriLElbdL1e6+kWF6d1xCiHZJ2uEG6Wezer1+ux3UhIAwYMYP/+/axatarY43q7X9ktZsyAlJSSJVzQzk9J0cargCTpCuFiuXe699xzD88//zyXL18u1jjz58+nQYMG2Gw2EhMTGT9+vAujLKK0NJgzp8AphfeBCMAfeLow42VkwOzZkJ7ushDLiopXbUIIN8qdZsj16KOPFnmMK1eu0KNHD2JiYnj55Zd58803XRli8SxdCg7mpu8ApgKbgMzCjqnTac03J08ueXxliNzpCuEi77//PpmZmSWqTbt27Vrq1KlDYmIi+/fvLx0JF2DZMsgsOJ0+CjwMFGm7Q2am1u24gpGkK4QL7Nu3j3HjxrFmzZpirVbIycmhd+/eDBw4kMGDB5OSkkLz5s3dEGkxWK3grjoJt+1cqwhkekGIErLb7fTo0YP27dszbNiwIp+/detWHnroIXQ6HT/99BMdOnRwQ5QlkJiorTLIyXH92H5+2vhF6HZc1smdrhAl9Oyzz3L16lU2btxYpPPsdjtPPfUU3bp1o0uXLly8eLH0JVyArCxtmZc76PXa+BWI3OkKUQI7duxg+fLlrFmzhkqVKhX6vP3799O9e3euXr3KunXreOihh9wYZeFYLBamT59OeHg4999/P40bN9amSozGki8TK4jNpo1fgUjSFaKYrFYr/fr144EHHqB///6FPm/y5MnMmTOHP/3pT3z33XdFStbuZLfbefvtt/Hz88Nut2O1WjEYDATVqcORnByHvxZbb7xsN15ZaMnFaYKxWCAkxBXhlxkyvSBEMT355JNYLBbWr19fqOOTkpIIDQ1l3rx5LFiwgO3bt5eahJuUlMSMGTPw8/MjIyODrKwsrFYrRqORpStWoHMy5/o6EAD8A1h543+/XpgLN24MFaxPmiRdIYph8+bNrF27lrVr1xZqi+/bb79No0aNMJvNnD59mmeffdYDURYsNTWVN954g/vvvx+z2UxISAgLFy4kKCgIvV6PyWRi8ODBnDt3jg4dOqAbPhwCAgocbzo3akDe9JruLIiAABg+3DVfqCwpqBKOkipjQtwiPj5ejR07VqWmpqpKlSqp/v37Oz0nLS1NtWzZUvn4+KjXX3/dA1Hm7/Lly2ru3LmqU6dOqkqVKgpQVatWVV26dFHvvfeeunz5slJKqZiYGAWoadOm3VodLS1NKaOxaFXFnL2MRm3ccggHVcYk6QpRSIsWLVK+vr7Kz89Pmc1mZbFYHB6/fPlyZTAYVHBwsEpISCjRtePj49XChQtVv3791JgxY5wen5mZqRYvXqweeOABFRgYqABlNptVu3bt1FtvvaUuXLiQ73l2u10dPnw4/0FfeaXo5RwdlXmcMqUkfySlmiRdIVzgr3/9a95vzwaDQY0aNSrf465fv646d+6sdDqdGjt2bImve/r0aeXr66tGjhypVq9erS5evPiHY+x2u/rkk0/Ugw8+qGrXrq0AZTQaVatWrdTUqVNVkitq2GZna/Vw9fqSJVy9XhsnJ6fkMZVSjpJuxZrBFsIRq1VbqJ+VpS1jCgm55SHPzc0Z9Xo9GRkZ2O32Wzo2fPvttwwYMICAgAB2795N69atSxxWUFAQTZo04Z133sFkMhV43Jo1a0hISGDIkCE8++yzhIeHl/jatzAYIDpaq4ebnl68ZWR6PQQGauOU07KOzkg9XVGxpaVpxVyWLdO2uvr5aYnBZtN2YDVurD3seeYZAoKCyMrK4r777mPhwoW0bNmSv/zlL/j4+PDBBx8waNAgvvjiCx5//HFWrVrl0vY5jz/+OD4+PtSuXRt/f38GDx7Mvffem/e5uq3QjlslJ0NUlFaesSiFzE0mCArSEm5wsPviKwUc1dOV6QVRMWVna3OURqNSAQGOfx0OCFA2g0G9qdOpeW+/nfeA6eDBgyogIED5+/urSpUqqUqVKqnvv//eLeGuW7dOPfDAA2rhwoVq3rx5qn379urQoUNuuVahFOXPz2TSjpsypVxPKdwMB9MLcqcrKp5i3qlZ/f3xDQ7Ou1Pr3LkzP/30EwC+vr4kJiYSFBRU7LDi4+NZtGgR3333HXv37s2rywv8YRpj+vTpVK1alQkTJhT7ei6Rnq6VZ1y+XCtec/NvChbL778pjBihTStUEI7udGVOV1QsycnFnpP0zc7O6/H1+f/9X17CzTVt2jQWL15c6PHOnDnDokWL+Oqrrzh06BCZmZnUqlWLtm3bkpGRQeXKlfOOvX2q4tChQ/Tq1atI8btFYKBWD3fyZKdz4kIjfyKi4sjJ0e5wi/sQCMBmw56Wxj0TJ2Ly8yPiT3+iTZs2hIeH0759e6xWK74FJJr09HSWLFnC+vXr2b9/P9euXaNatWq0adOGd955h6FDhxb4oMxms3H48GHWr1/Pnj17yM7OpnPnzsX7Du7i61uhqoUVlyRdUXG4qMeXj91OqNHI9UmT4HVts+vp06fp2rUrAwcO5I033gDg+vXrrFixgrVr17Jnzx4uXbpE5cqVueeee5g+fTojRoygevXqhbqmXq/n4MGDnDp1ihEjRtC1a1fMZnOJvofwDpnTFRVDWhrUr+/aMoJGI6SksP/0abp160Z6ejr16tWjZcuWxMTEcPHiRQICAmjevDn9+vXj2Wef5Y477nDd9UWpJXO6Qjjp8ZUrHrgbeAytcIsjSqfjhyefpGd0dF4H4DNnzlC9enVGjBjByJEjadSoUUkjF+WMJF1RMTjp8ZVrNHBfIYfUZWZSb9MmbICfnx9KKXx8fPjnP/9Jnz59ShKtKMck6Yryr5A9vj4BqgF/BhIKOXRzg4FrqanE/vYbO3fuZMuWLRgMhuLHKso9mdMV5V9CArRsCdevF3jIFSAC+AFYgpZ0nU0vAGA2w7598tRe3MLRnK7U0xXlhlKKM2fO/LEFeiF6fL0KPAM0KOpFK2CPL1EyknRFuXHy5EmCgoKoV68eo0aN4vvvvycrK4urFovDZWL7gGigWHu7KmCPL1EyMr0gyo3z589zxx13YLfbb3m/Xq1apFy6hM5iyfe8ucAUIHf/1zW0Pl/hwB5nFzUYtGkL2XklbiLTC6Jcsdvt/PLLL7z22ms88MADBAcH4+/vT926dfMSrk6nw9/fn/nz55Ny/rzDHl8jgeNod7z7gFFAH2BTYYKpgD2+RMnIvy2iVEtNTeWrr75i27Zt7Nu3j6SkJK5cuYKPjw/Vq1cnNDSUPn36EBkZSc+ePRk2bBgbNmygVatWbNiw4ffNCMOHw7Rp+S4bM9145aoEGIFazoKrqD2+RInI9IIokZycHH777TcOHDjA1q1b+ctf/kLHjh2LPI7VamX79u1s2rSJnTt3cuzYMS5cuIDFYiEgIICgoCCaN29O+/bt6dOnD82aNct3nK+//pqYmBhee+21W2sgpKdrtVzdsCOtIlXPEoUjO9JKszJemWn27Nm8+eabPPfcc7Rs2ZKQkBCn55w+fZovv/ySn376if3793Pq1CmuXbuGXq+nRo0aNGrUiP79+9O9e3e6d+9eqG67ufr27Uvfvn3/+EFgIEycCHPnFq3wdkFMJpgwQRKuKDK50/WGInQrKO3/Ua9du5bVq1fz+eefF3hMWloaDz/8MAkJCVy8eBGr1YrZbKZ+/frcfffddOzYkX79+nHnnXe6N9icHGjRQivPWJKiN3o9hIZCXFyFbTkjHHN0pytJ15NycrRKV3PmaHUAHG1LDQjQ6u5PnKjNRZbSXU4nTpygc+fOvPnmmyQkJNC7d2/uv//+W47JyckhKiqKtm3b0qNHDzp37uy9XVslqKcL/N7ja/fuct9yRhSfJN3SoJz0lbq9gwFAt27duPPOOwkNDWXjxo3MmDGDyMhIL0VYCDf+v1ApKejK8P8XovSSOV1vK8ndVUZGXrcCT99dxcXF8c0337Bjxw7i4uI4c+YMq1ev5sEHH7ylCeK3336bN+8aEBDA5s2b6dChA/7+/h6LtUiCg0nZtIlPmzVjgtGofRdHv3WYTGC3a3O406bJlIIoEUm67uaibgWkp2vjuGEe8erVq2zcuJEff/yR2NhYTp48yf/+9z+UUlSpUoWGDRvSvn17unbtSrdu3f7QdfbmB12VK1fm8OHDLo3P1Y4dO8a9995L5cqVmXjkiPT4Eh4lSdfdXNStAJtNG2fGjLxuBaDVG7BarfgVIhHb7Xb27dvHN998wy+//MLhw4c5e/Ys2dnZGAwG6tatS9OmTenTpw+9e/cmIiLCaRvx3HoHv/zyC8nJyURHRzN06NBSe5e7YsUKRo0aRVZWFl27dpUeX8Lj5N8od0pL0x6auWptaEYGzJ6tPVwLDOTKlSsMGTKElJQUYmNjbzk0PT2db775hi1btrB3714SExO5fPkyANWqVePOO+8kMjKSbt260atXr0K3jbmdTqdj//79LFq0iPvuu48XXniBqKioEn9Vdxg2bBhr1qwh88ZUQp06dW49QHp8CQ+QpOtOTroVZAMvoBVbSQcaA28CDnu86nSwZAl7o6Lo27cvFy9exG63M2XKFGJiYjh69Cjnz58nJycHo9FIvXr1aNasGQMGDKBPnz7cfffdTu9ei6pXr16lozOtEzVq1LilLoOr/xyEKAxZveBOzZqBg/nN68DbwNNAMPAt8ARwAAhxMGyi2cydt9WGrV69OmFhYbRu3ZqoqCh69OhBpUqVShZ/ORQeHs6FCxf43//+x8iRI/n3v//t7ZBEOSSrF7yhEN0KzMD0m/65L3AnEIvjpHvH9euY/f3JttnQ36gTu2DBAgYMGFCSiMu9X375haNHjxIXF0elSpXy/uyE8CRJuu6SmKg9Cc/JKfQp54FjQHMnxxnMZq7t28cJHx++/vprPvvss1L74Ko0GTFiBO3atSM8PNzboYgKTJKuuxSiW8HNLMBgYBjQ1NnBN7oVhLZowbhx4xg3blzx46wgtm7dytGjRzl69Ki3QxEVnDxJcBejsdDLxOzAUMAAvF+YE6RbQZHlVj8LCwvzdiiigpM7XXcJCdEW1zuh0HpznUd7kFaobQ8Wiza+KJTNmzdz/PhxoqOjvR2KEHKn6za+vtCokdPDngcOA18BAYUdW7oVFMnIkSPp1q0bDRs29HYoQsidritMnjyZ9evXU716dWrWrMn58+e5du0ab9euzYMBAQXu608CFgD+QN2b3l+ANr+bL+lWUCRffvklSUlJ7Nixw9uhCAFI0nWJoKAgkpKSSEhIyHuvS5cuRK5YAU2aFHheQ7TphSJRSqsDIAplzJgx9OzZ8/e2PUJ4mUwvlNBHH33Ee++9h+XG/K3BYGDUqFFs2bIFc4MG2pZdk8nJKIVkMsGkSVJ4pZDWrl1LSkoKy5cv93YoQuSRpFsM6enpPPvss1SqVInhw4fTpEkT+vXrh16vp2vXrrz//k1rEKZN02qwlnQhvl6vjTNtWsnGqUDGjRtHv379qF27trdDESKPTC8UwY8//sjLL79MbGwsNWvWZOLEiUydOhWDwcChQ4dQSvHpp5/eutPJYNCKXruiW0F0tNRyLaSVK1dy/vx5li5d6u1QhLhFhb/TPXPmDBMmTCAyMpL58+dz5syZWz5XSvHaa69Rq1YtoqKi0Ol0REdHk5qaysyZM/PazjRr1oyvvvoKU35TCcHBWgHy0NCiTzWYTNp50h6mSCZNmsSjjz5KoEzFiFKmQifd9PR0Jk+ejMlkYurUqXz33Xds3779D8f9+uuvPPLII1y8eJGYmBi6detW9IsFB8PBgzB+PBiNqAAnC8RMJm0DxIQJWuFySbiFtnjxYtLS0liyZIm3QxHiDyp0lbGzZ8/Svn17Tpw4AcDTTz/NsGHDtOLWNyil/tApocTS0/lxyBCa/Pe/1M/MlG4FLlazZk169uzJypUrvR2KqKCkylgB6tWrR3h4OCNGjGDfvn1cv36dmjVrUqNGDe655x4A1ydc4IqvLz02b6Zp06Yc2LtXuhW40Pz587l8+TL/+c9/vB2KEPmq0NMLoC35qlWrFoMGDSIuLg6j0cgHH3xAcnKyW65nt9vp378/VquVS5cu/d6toEUL2WnmAlOmTGHo0KFSS1iUWqUn6VqtWmPAgwe1n1arWy6jlOLmKZXAwECOHj1KVFQUvr6+PPHEE2RnZ3P+/Hm3XH/KlCl5u6POnz/P9duKkYvimz17NtevX2f+/PneDkWIAnk36aalwdtvax0WzGZo2RLat9d+mkza+2+/rS21KqE9e/bQtWtXpk6desv7WVlZNGvWjE8//RTQVjOkpaVx7733lviat4uJieEf//hHXo8uf39/2Z7qIna7nRkzZvDMM8/c0p1YiNLGO0k3JwemTIH69bXF/ocPa+9dvw5Xrmg/LRbt/dzNBVOmFKkgOGj/Ib7zzjs0aNCAiIgIUlNTad269S3ztEajkUcffZSdO3fSsWNHXnrpJR5//HH8/Pxw9JCxOO69914+/vhj6tWrh9FoJDMzk3379rn0GhXVW2+9RXZ2NvPmzfN2KEI4lvvrdn6vNm3aKJdLSlIqLEwpk0kprZJA4V4mk3ZeUtIfhjxx4oRq27atunDhwo1LJKnHHntMGQwG5e/vrwYOHKhOnTrlMKyTJ0+q3bt3u/775qNGjRrqlVdeUZmZmcpqtXrkmuWZzWZTZrNZvfjii94ORQillFLAblVAXvVs0k1KUqpWLaX0+qIl3NyXXq+df1PiTUtLU/Xr11e+vr7qiSeeUOHh4Uqn06kGDRqoefPmKZvN5trvUEIWi0XpdDp14MABb4dSbrz66qvKaDQqi8Xi7VCEUEo5Trqem17IyYGoqOJvhQXtvPR0bRyLhezsbCIjIzlz5gxWq5XVq1dTt25d9uzZQ3JyMuPGjSt1bbY3bdqEXq+nRYsW3g6lXLDb7fzrX/9i3Lhx+MrKD1EGeO7f0hkzICWl+Ak3l80GKSlcnjSJpmvWcO7cubyP/Pz8mDx5Mi1btizZNdzo888/JygoyNthlBs6nY6UlBSqVq3q7VCEKBTPJN20NJgzR9sA4MAnwAwgGa2o93KgY34HZmQQ8MEH3NW8Oe3atcPf35/U1FTS0tJIS0tzcfCu9csvvxARke9GFVEMOp2OatWquWUTixDu4Jmku3QpOPmPYjPwMvAp0BY462RIg78/W4cOhcmTXROjhyQmJvK3v/3N22GUWSqfbdmScEVZ4pkJz2XLCmxZk2sa8BrQDi2ooBuvAmVmQhkrTn3mzBmysrLo37+/t0Mpc2JjY4HfE6ytpNNUQniJ+5Ou1QrHjzs8xAbsBi4AjYH6wBjAcZrGrTvX3GH16tVUrlxZtqgW0bZt2+jZsyfDhw9n/fr1AOj1epevoxbCE9yfdBMTnRbePg9YgLXAz8A+YC/wurOx/fy08cuITZs20cRBzzTxR0opAgMDadu2Lc2aNWPDhg2MGDGCBQsWMHbsWG+HJ0SRuT/pZmU5bVWTW1l2LFAPqAlMBL51NrZe7/ThXGmyf/9+Onfu7O0wyhSdTsfdd99Nly5dOH78OBMmTKBz585MmzaN2NhY2UYtyhz3J12j0ekysepoUwpFfhxis2njlwF2u53U1FQGDRrk7VDKpL/+9a9UqVKFsLAwWrVqhdlsZvDgwbz11lukpKR4OzwhCs39qxdCQrQ6Ck4MB94DegJ+wFygr7OTLBZt/DJg69at6HQ67rvvPm+HUubkrlgIDQ3lb3/7G9u2bWP8+PGMGTOGPn36yLpnUaa4/07X1xcaNXJ62KvAfUATIBxoBUxxdlIZqj+7du1a6tWr5+0wyqTcFQujRo3ijjvuoG7dunnzuXfeeac3QxOiyDyzZGz4cHDSE8wPmA9cAs4B7wIOJw4CArRxy4jt27fTqlUrb4dR5k2cODGvw6+1DK1cESKXZ5LuM89oJWtcSSmth1gZcfz4cXr37u3tMMqs3GIhfn5+3HHHHQBSa0GUSZ5JuoGBMHFi0duPF8RkgkmTykzTxrS0NDIyMnj88ce9HUqZ9fDDDzNz5kxvhyFEiXmuBFduMXIny8ec0uu1caZNc01cHvDpp59iNpsJLCN/SZQ2qampfP311zRv3tzboQhRYp77/cxggOhoiIgodnlHm06HT2AguuhopxsuSpNevXpRuXJlb4dRZg0bNoygoCAee+wxb4ciRIl5tthscDDs3g2hoUWealAmEyeUonlGBt8cOFCmtoCGhIQwZMgQb4dRJp0+fZpNmzbxwQcfeDsUIVzC8xW+g4O1jr/jx2sbG5ysasBkAqMR3YQJTB8wgMPXr/Poo4/SpEkT1qxZUyaSr06nk0pYxfT000/TsGFD+vXr5+1QhHAJ77RVMBjgjTe0ouYzZmhdfw0GrSNwlSraT4NBez+3+Pnrr/Ng//4YDAZycnJISEhg0KBBxMfHe+UrCPdLSkrixx9/ZOHChd4ORQiX0Tm6U4yIiFC7d+/2TCRWq1a8JitLuwMOCfnDxof4+HhatmxJZmYmSik2b95MVFSUZ+ITHtepUyfOnj0rf7GKMken08UqpfLtVlB6Fjr6+mo7zBxodGNnW6tWrUhMTGTKlCmlNuna7fZS15+tLImPj2f79u1s2bLF26EI4VJlKiv4+PgQExPDrl272LlzJ7GxsaWuC0NsbCwTJkzgzTffJPe3hNzfJsrC/HNp8dRTT3HXXXdJVTZR7pSppAvQvHlzfH19CQsLY8mSJcyaNYvo6GhvhwVo3QwmTpxI5cqVuXbtGgMGDODLL7/Me4i2ZMkSrl696uUoS7+4uDh27dqVt91XiHKloN7sSinatGnjqTbxxTZo0CBlNBrVhQsXvB2K+vXXX1WHDh3y/vngwYOqVatWav/+/Uoppe666y5vhVamtGnTRt19993eDkOIYgN2qwLyaumZ0y2mVatW0ahRI9q1a8exY8e8Oo+6b98+goODAcjKyqJ58+aMHj2ad999l+7duxMeHu612MqKffv2sWfPHn799VdvhyKEW5S56YXb+fj4sGvXLk6fPs3TTz/t1Vi6d+/Oc889R1ZWFkajEZvNxvDhw6lbty5jxoyRWrqFMGzYMFq2bEmbNm28HYoQblHmky5A7dq1WbduHStXrmTlypVei6Nhw4Z07NgR441uFnq9Hh8fH55++mmCg4Ml6Trx66+/cuDAAVasWOHtUIRwm9KzTtcFJk2axLvvvsuRI0fylpd5i7rR7SDXtWvXMJlMsozMgebNm1OpUiV27drl7VCEKBFH63TLVQaYPXs299xzD3/605+8XuD6+PHjXL58Oe+fK1WqJAnXge3bt3P48GG5yxXlXrnLAj///DNPPvmk1xPckCFDePjhh70aQ1nyzDPP8Oc//5m77rrL26EI4VblLumaTCbeeecdryfdI0eO0L17d6/GUFb88MMPxMfHy12uqBDKXdIFnFb0shWjlm9RZGVlcfnyZZ588km3Xqe8GDlyJJ07dyY0NNTboQjhdmV+nW5x6EvavcKJDRs2YDAYCCkj7eG96dtvv+XkyZNSY0FUGBUi6R49epTk5GQOHjyIUoqrV68SFxdH165def75511+vfXr19OwYUOXj1sePf/883Tv3j1vU4kQ5V25nF64WXx8PCNGjODrr7+mRYsWgLae9tixY+zYsYOsrCyXXzMmJoa2bdu6fNzyZt26dZw6dYoPP/zQ26EI4THl/k43LCyM1q1bc+rUKbp3747NZuOLL76gV69evPrqq3kbGVzp1KlTzJo1y+XjlhddunShVatWfPLJJ/Tu3Zu6det6OyQhPKZcJ93cmrbvvfce999/Pw8++CB+fn5ERkbywgsv3HKMq8THx2OxWKS9jAN79+5lx44dWK1WQkNDuXTpEtWqVfN2WEJ4RLmeXvDx8SEnJ4fk5GTuu+8+tm7dSlRUVF7CVUq5fGnZxx9/TPXq1TEYDC4dtzxRSuVtXnn//ff55z//6eWIhPCccn2nC2AwGFi+fDmZmZksW7YMvxut293V2eGHH36QamJO5OTkAGA0GnnxxRf5+9//7uWIhPCccp90QavJYDab8/45907LHXejcXFxjB492uXjljkOet5lZ2fj5+fHN998Q7du3bwaphCeViGSbm7Czb27PXXqFE2aNGHv3r0uvSu1Wq2kp6czaNAgl41ZpqSlwdKlsGwZHD8Ofn6g14PNBjk50LgxSd260cBsZstvv3m9KJEQ3lAhkm6u3OmE4OBgWrVqRYcOHTh79qzL7ni//fZbfH19adasmUvGKzNycmDGDJgzB3Q6yMz8/f2bHT5Mg5MnOWm3o1+6FKZNA5n7FhVMuX6Q5siWLVuw2+1ERka6bMwvvviC+vXru2y8MiE5GVq0gLlztamE3IRbAJ+sLPQ5OdrxLVpo5wtRgVTYpGs0Gvn555/573//y/Tp010y5s6dOytWofLkZIiIgBMnICOjaOdmZGjnRURI4hUVSoVNugAtWrTg/fffZ+bMmWzfvr3E4yUmJlac9bk5ORAVBenp2pxtcdhs2vlRUWCxuDY+IUqpCp10Qdv7/+CDD9KjRw8uXbpU7HFOnTpFdnY2/fv3d11wpdmMGZCSUvyEm8tm08aZMcM1cQlRylX4pAvaXGz16tX585//XORz9+zZQ8OGDenRowdGo5FDhw55vWuF26WlaQ/NCphSqHTbSw+MdTReRgbMnq3d9QpRzknSRVvVsHPnThISEhg5cmSRzq1Tpw4pKSkcPnyY7Oxs7r//fubMmeOmSEuJpUu1VQoFuHbT6zwQAAxwNqZOB0uWuCpCIUotSbo31K9fn08//ZTFixezdu1atmzZUqiiNUFBQdSuXRvQNl0EBwe7pVxkqbJsmdNVCrnWArWBjs4OzMyE5ctLFpcQZYAk3Zs88sgjPPfcczz++OP06tWL119/HUfdknPlLjsLCAhg8+bNVK5c2d2heo/Vqm18KKQPgacAx708bkhI0MYXohyTpHuTK1eukJCQgFKK7OxsLBYLZ86ccXpebgHudevW0bhxY3eH6V2JidpOs0JIBrYBwwo7tp+fNr4Q5Zgk3ZscPXqUHTt24O/vD2jbemNjY/M/2GrV7swOHqS5vz/3tWpFjx49PBit+/Xv358xY8awbdu23x8OZmVpW3sLYQXQAbizsBfU67XxhSjPlFIFvtq0aaMqmkuXLqkZM2Yok8mkAPXAAw/8/uHFi0rNmqVUeLhSBoNSZrNSVaoom8mkbL6+2vuzZimVlubxuK9cuaLWrFmjRo8erebMmaOuXbtW4jFDQ0MVoEwmk/Lz81P16tVTLzzwgLIGBCgFTl9hoJYU4ri8l9msVHy8C/40hPAuYLcqIK/Kne5tqlatymuvvUZqaiq9e/dm+/btXDxzBqZMgfr1tXoBhw9rmwOuX4crV/DJyMDHatXenzYNgoK042+vPeBGX331FcuWLaN27do0b968yB2PrVYrP/30E9OnT6dPnz40btyYpKQkADIyMrBYLFy8eJGaERHad3Xiv0AKhVi1cDOLRatGJkQ5plMOHhRFRESo3bt3ezCc0ufL99+n95w5+J4/X7StriaTlnyjo8HNTRdPnjzJ6NGjWbt2LSaTCdB+g8mvFX1OTg4///wzP/74I7GxsRw7doxz586RmZmJXq+nWrVqBAcHc/fdd3Pp0iW++uorAgICGDBgAPPnz9fGb9ZM+wvGgeeADOCjonyRZs0gLq4oZwhRKul0ulilVER+n1WoKmNFlpzMgzNnFm+r6821BXbvdmvi9ff35/jx45w8eZLPP/+cmjVr5nXHAC0BL1++nNGjR+cl18DAQBo2bEiXLl1o3749PXr0+EOxno0bN/LDDz/w4Ycf3rrTbvhw7Y7ewbKxBUX9EgEB2rhClHNyp1uQnBytCtaJEyXb6qrXQ2iodgdXyKf+RZWYmMiQIUMICwujadOmHDhwgLvuuotx48ZRtWpVlFIkJCTw3//+lx49ehS6EaRSiqysLAICAm79ID1du4t35UMvo1HbDhwY6LoxhfASR3e6MqdbEDfXFlBKcfHixUIPc+XKFdatW8eECROw2+23fFazZk2Sk5Np3749L7/8MlOnTuXgwYPs27cPAJ1OR1hYGMOGDStS512dTvfHhAtaYpw4UZtCcQWTCSZNkoQrKgRJuvlxUlsAoAtg5Pf6Anc5Gu+22gKXLl2iX79+hIaG/mHzxaVLl1izZg1jx46lY8eOBAUF4e/vT9WqVRk0aBCfffYZWbfdYVaqVImuXbty7do1QHsYGBAQQHZ2dlG/eeHlPjAs5PKxAun12jjTprkmLiFKOZnTzY+T2gK53geeLeyYN2oL7Pjzn3nkkUe4fPkySimGDRtGQkICJ0+eJC0tDYvFgr+/P7Vq1SI0NJSBAwfSqVMnIiMjqVKlSoHDP/bYY2zYsIE5c+YQExND/fr1eeCBBwp8oFZiBoP2kDAiovjlHfV67e42OtptUy9ClDYyp5ufQjyd7wIMoQhJF0jw9yfstrvPWrVq0aJFC1q3bk2XLl3o1q1b3gqEooqNjWX58uW0adOGyMhIGjRoUKxxiiQ5WauHm5JSald3COFpjuZ0JenezmoFs9npGtsuQByg0KYW3rjxniMWnY7w4GCSz5zBaDSSkZHB7NmzefHFF10QuBcV1CMtPyYT2O3aHO60aXKHK8oleZBWFIWsLfBP4ATaBoCRQD/AWRkYP5OJhOhoLl++zMcff8zjjz9ePnqqGQzwxhu/PzBs1kx7z2yGKlW0nwaD9n7uA8rXX5eEKyokudO93cGD0L49XLlSpNN6An1wUqy7ShXYsUNbilbeWa3aX2BZWdpysJAQ8JVHCKJikM0RRWE0FuuhkA5tqsEhm00bvyLw9YXyXnFNiGKQ6YXbhYQ4bZJ4CdgEZAFWYBXwE+C0xpjUFhCiwpOkeztfX2jUyOEhFmAqUAuoCbwHrMfJWl3Q7vzkV2whKjRJuvkZPlyrBVCAWsCvwFW0u96dQHdnY0ptASEEknTz98wzWoVXV1IKRoxw7ZhCiDJHkm5+pLaAEMJNJOkWRGoLCCHcQJJuQXJrCwQGFj/xSm0BIcRtJOk6EhysFSAPDS36VIPJpJ3n5gLmQoiyRZKuM8HB2i618eO1jQ0OVjUAWrI1GmHCBK1wuSRcIcRNJOkWhtQWEEK4iNReKC6pLSCEKIDUXnAHqS0ghCgGmV4QQggPkqQrhBAeJElXCCE8SJKuEEJ4kCRdIYTwIIdLxnQ63QUgyXPhCCFEudBQKVUrvw8cJl0hhBCuJdMLQgjhQZJ0hRDCgyTpCiGEB0nSFUIID5KkK4QQHvT/IWt6bROVVlAAAAAASUVORK5CYII=\n", "text/plain": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "import grblas\n", "grblas.io.draw(g3.value)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Inspect the steps required for translations\n", "\n", "Rather than actually converting `g` into other formats, let’s ask Metagraph how it will do the conversion. Each conversion requires a translator (written by plugin developers) to convert between the two formats. However, even if there isn’t a direct translator between two formats, Metagraph will find a path and take several translation steps as needed to perform the task.\n", "\n", "The mechanism for viewing the plan is to invoke the translation from ``res.plan.translate`` rather than ``res.translate``. Other than the additional ``.plan``, the call signature is identical.\n", "\n", "In this first example, there is a direct function which translates between `NetworkXGraphType` and `ScipyGraphType`." ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "execution": { "iopub.execute_input": "2020-12-08T20:14:57.951387Z", "iopub.status.busy": "2020-12-08T20:14:57.950007Z", "iopub.status.idle": "2020-12-08T20:14:57.958301Z", "shell.execute_reply": "2020-12-08T20:14:57.959416Z" } }, "outputs": [ { "data": { "text/plain": [ "[Direct Translation]\n", "NetworkXGraphType -> ScipyGraphType" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "res.plan.translate(g, res.types.Graph.ScipyGraphType)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "In this next example, there is no direct function which convert `NetworkXGraphType` into a `GrblasGraphType`. Instead, we have to first convert to `ScipyGraphType` and then to `GrblasGraphType` before finally arriving at our desired format.\n", "\n", "While Metagraph will do the conversion automatically, understanding the steps involved helps users plan for expected computation time and memory usage. If needed, plugin developers can write a plugin to provide a direct translation path. " ] }, { "cell_type": "code", "execution_count": 18, "metadata": { "execution": { "iopub.execute_input": "2020-12-08T20:14:57.964327Z", "iopub.status.busy": "2020-12-08T20:14:57.962905Z", "iopub.status.idle": "2020-12-08T20:14:57.971236Z", "shell.execute_reply": "2020-12-08T20:14:57.972116Z" } }, "outputs": [ { "data": { "text/plain": [ "[Multi-step Translation]\n", "(start) NetworkXGraphType\n", " -> ScipyGraphType\n", " (end) -> GrblasGraphType" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "res.plan.translate(g, res.types.Graph.GrblasGraphType)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Algorithm Example #1: Breadth First Search\n", "\n", "Algorithms are described initially in an abstract definition. For bfs_iter, we take a `Graph` and return a `Vector` indicating the NodeIDs in the order visited.\n", "\n", "After the abstract definition is written, multiple concrete implementations are written to operate on concrete types.\n", "\n", "Let's look at the signature and specific implementations available for bfs_iter." ] }, { "cell_type": "code", "execution_count": 19, "metadata": { "execution": { "iopub.execute_input": "2020-12-08T20:14:57.977362Z", "iopub.status.busy": "2020-12-08T20:14:57.974907Z", "iopub.status.idle": "2020-12-08T20:14:57.983393Z", "shell.execute_reply": "2020-12-08T20:14:57.983922Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Signature:\n", "\t(graph: metagraph.types.Graph, source_node: NodeID, depth_limit: int = -1) -> metagraph.types.Vector\n", "Implementations:\n", "\t(graph: NetworkXGraphType({}), source_node: NodeID, depth_limit: int = -1) -> NumpyVectorType({})\n", "\t(graph: ScipyGraphType({}), source_node: NodeID, depth_limit: int = -1) -> NumpyVectorType({})\n" ] } ], "source": [ "res.algos.traversal.bfs_iter.signatures" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We see that there are two implementations available, each with a different type of input graph.\n", "\n", "---\n", "Let's perform a breadth-first search with our different representations of `g`. We should get approximately the same answer no matter which implementation is chosen (same NodeIDs within each depth level of the traversal)." ] }, { "cell_type": "code", "execution_count": 20, "metadata": { "execution": { "iopub.execute_input": "2020-12-08T20:14:57.990205Z", "iopub.status.busy": "2020-12-08T20:14:57.989315Z", "iopub.status.idle": "2020-12-08T20:14:57.995911Z", "shell.execute_reply": "2020-12-08T20:14:57.996680Z" } }, "outputs": [ { "data": { "text/plain": [ "array([0, 1, 3, 4, 2, 7, 5, 6])" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "cc = res.algos.traversal.bfs_iter(g, 0)\n", "cc" ] }, { "cell_type": "code", "execution_count": 21, "metadata": { "execution": { "iopub.execute_input": "2020-12-08T20:14:58.003546Z", "iopub.status.busy": "2020-12-08T20:14:58.002883Z", "iopub.status.idle": "2020-12-08T20:14:58.009339Z", "shell.execute_reply": "2020-12-08T20:14:58.010067Z" } }, "outputs": [ { "data": { "text/plain": [ "array([0, 1, 3, 4, 2, 7, 5, 6])" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "cc2 = res.algos.traversal.bfs_iter(g2, 0)\n", "cc2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "Similar to how we can view the plan for translations, we can view the plan for algorithms.\n", "\n", "No translation is needed because we already have a concrete implementation which takes a `NetworkXGraph` as input." ] }, { "cell_type": "code", "execution_count": 22, "metadata": { "execution": { "iopub.execute_input": "2020-12-08T20:14:58.016530Z", "iopub.status.busy": "2020-12-08T20:14:58.015649Z", "iopub.status.idle": "2020-12-08T20:14:58.022271Z", "shell.execute_reply": "2020-12-08T20:14:58.023030Z" } }, "outputs": [ { "data": { "text/plain": [ "nx_breadth_first_search_iter\n", "(graph: NetworkXGraphType({}), source_node: NodeID, depth_limit: int = -1) -> NumpyVectorType({})\n", "=====================\n", "Argument Translations\n", "---------------------\n", "** graph **\n", "NetworkXGraphType\n", "** source_node **\n", "NodeID\n", "** depth_limit **\n", "int\n", "---------------------" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "res.plan.algos.traversal.bfs_iter(g, 0)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "In the next example, `g2` also satisfies a concrete implementation, so no input translation is required." ] }, { "cell_type": "code", "execution_count": 23, "metadata": { "execution": { "iopub.execute_input": "2020-12-08T20:14:58.030263Z", "iopub.status.busy": "2020-12-08T20:14:58.029380Z", "iopub.status.idle": "2020-12-08T20:14:58.035036Z", "shell.execute_reply": "2020-12-08T20:14:58.035694Z" } }, "outputs": [ { "data": { "text/plain": [ "ss_breadth_first_search_iter\n", "(graph: ScipyGraphType({}), source_node: NodeID, depth_limit: int = -1) -> NumpyVectorType({})\n", "=====================\n", "Argument Translations\n", "---------------------\n", "** graph **\n", "ScipyGraphType\n", "** source_node **\n", "NodeID\n", "** depth_limit **\n", "int\n", "---------------------" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "res.plan.algos.traversal.bfs_iter(g2, 0)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Algorithm Example #2: Pagerank\n", "\n", "Let's look at the same pieces of information, but for pagerank. Pagerank takes a `Graph` and returns a `NodeMap` indicating the rank value of each node in the graph.\n", "\n", "First, let's verify the signature and the implementations available.\n", "\n", "We see that there are two implementations available, taking a `NetworkXGraph` or `GrblasGraph` as input." ] }, { "cell_type": "code", "execution_count": 24, "metadata": { "execution": { "iopub.execute_input": "2020-12-08T20:14:58.043403Z", "iopub.status.busy": "2020-12-08T20:14:58.042484Z", "iopub.status.idle": "2020-12-08T20:14:58.046921Z", "shell.execute_reply": "2020-12-08T20:14:58.047606Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Signature:\n", "\t(graph: Graph({'edge_type': 'map', 'edge_dtype': ('float', 'int')}), damping: float = 0.85, maxiter: int = 50, tolerance: float = 1e-05) -> metagraph.types.NodeMap\n", "Implementations:\n", "\t(graph: GrblasGraphType({}), damping: float = 0.85, maxiter: int = 50, tolerance: float = 1e-05) -> GrblasNodeMapType({})\n", "\t(graph: NetworkXGraphType({}), damping: float = 0.85, maxiter: int = 50, tolerance: float = 1e-05) -> PythonNodeMapType({})\n" ] } ], "source": [ "res.algos.centrality.pagerank.signatures" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "Let's look at the steps required in the plan if we start with a `ScipyGraph`. Then let's perform the computation.\n", "\n", "We see that the `ScipyGraph` will need to be translated to a `GrblasGraph` in order to call the algorithm. **Metagraph will do this for us automatically.**" ] }, { "cell_type": "code", "execution_count": 25, "metadata": { "execution": { "iopub.execute_input": "2020-12-08T20:14:58.057050Z", "iopub.status.busy": "2020-12-08T20:14:58.056155Z", "iopub.status.idle": "2020-12-08T20:14:58.059041Z", "shell.execute_reply": "2020-12-08T20:14:58.059861Z" } }, "outputs": [ { "data": { "text/plain": [ "grblas_pagerank\n", "(graph: GrblasGraphType({}), damping: float = 0.85, maxiter: int = 50, tolerance: float = 1e-05) -> GrblasNodeMapType({})\n", "=====================\n", "Argument Translations\n", "---------------------\n", "** graph ** [Direct Translation]\n", "ScipyGraphType -> GrblasGraphType\n", "** damping **\n", "float\n", "** maxiter **\n", "int\n", "** tolerance **\n", "float\n", "---------------------" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "res.plan.algos.centrality.pagerank(g2)" ] }, { "cell_type": "code", "execution_count": 26, "metadata": { "execution": { "iopub.execute_input": "2020-12-08T20:14:58.071036Z", "iopub.status.busy": "2020-12-08T20:14:58.070086Z", "iopub.status.idle": "2020-12-08T20:14:58.076393Z", "shell.execute_reply": "2020-12-08T20:14:58.076953Z" } }, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pr = res.algos.centrality.pagerank(g2)\n", "pr" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The result is a `GrblasNodeMap` which can be inspected by looking at the underlying `.value`." ] }, { "cell_type": "code", "execution_count": 27, "metadata": { "execution": { "iopub.execute_input": "2020-12-08T20:14:58.086103Z", "iopub.status.busy": "2020-12-08T20:14:58.085196Z", "iopub.status.idle": "2020-12-08T20:14:58.116991Z", "shell.execute_reply": "2020-12-08T20:14:58.118097Z" } }, "outputs": [ { "data": { "text/html": [ "
\n", "\n", "
v4
\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
grblas.Vector
nvals
size
dtype
88FP64
\n", "
\n", "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
01234567
0.119910.119910.1291910.119910.1953840.1330080.09304150.0896458
\n", "
" ], "text/plain": [ "\"v_4\" nvals size dtype\n", "grblas.Vector 8 8 FP64\n", "---------------------------------\n", " 0 1 2 3 4 5 6 \\\n", " 0.11991 0.11991 0.129191 0.11991 0.195384 0.133008 0.0930415 \n", "\n", " 7 \n", " 0.0896458 " ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pr.value" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's translate it to a numpy array." ] }, { "cell_type": "code", "execution_count": 28, "metadata": { "execution": { "iopub.execute_input": "2020-12-08T20:14:58.124987Z", "iopub.status.busy": "2020-12-08T20:14:58.123385Z", "iopub.status.idle": "2020-12-08T20:14:58.134019Z", "shell.execute_reply": "2020-12-08T20:14:58.135102Z" } }, "outputs": [ { "data": { "text/plain": [ "array([0.11990989, 0.11990989, 0.12919109, 0.11990989, 0.19538403,\n", " 0.13300793, 0.09304149, 0.08964579])" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pr_array = res.translate(pr, res.types.NodeMap.NumpyNodeMapType)\n", "pr_array.value" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now let's verify that we get the same answer with the NetworkX implementation of Pagerank. \n", "We can ensure the NetworkX implementation is called by passing in a NetworkXGraph. Because no translations\n", "are required, it will choose that implementation.\n", "\n", "The result is a `PythonNodeMapType`, which is simply a Python `dict`." ] }, { "cell_type": "code", "execution_count": 29, "metadata": { "execution": { "iopub.execute_input": "2020-12-08T20:14:58.139932Z", "iopub.status.busy": "2020-12-08T20:14:58.138478Z", "iopub.status.idle": "2020-12-08T20:14:58.150137Z", "shell.execute_reply": "2020-12-08T20:14:58.151277Z" } }, "outputs": [ { "data": { "text/plain": [ "{0: 0.11990989117844908,\n", " 1: 0.11990989117844908,\n", " 3: 0.11990989117844908,\n", " 4: 0.1953840289789895,\n", " 2: 0.12919108800740858,\n", " 5: 0.13300793197881575,\n", " 6: 0.09304148578762082,\n", " 7: 0.08964579171181795}" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pr2 = res.algos.centrality.pagerank(g)\n", "pr2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Translate to a numpy array and verify the same results (within tolerance)" ] }, { "cell_type": "code", "execution_count": 30, "metadata": { "execution": { "iopub.execute_input": "2020-12-08T20:14:58.156308Z", "iopub.status.busy": "2020-12-08T20:14:58.154747Z", "iopub.status.idle": "2020-12-08T20:14:58.164351Z", "shell.execute_reply": "2020-12-08T20:14:58.165368Z" } }, "outputs": [ { "data": { "text/plain": [ "array([0.11990989, 0.11990989, 0.12919109, 0.11990989, 0.19538403,\n", " 0.13300793, 0.09304149, 0.08964579])" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pr2_array = res.translate(pr2, res.types.NodeMap.NumpyNodeMapType)\n", "pr2_array.value" ] }, { "cell_type": "code", "execution_count": 31, "metadata": { "execution": { "iopub.execute_input": "2020-12-08T20:14:58.170026Z", "iopub.status.busy": "2020-12-08T20:14:58.168617Z", "iopub.status.idle": "2020-12-08T20:14:58.177367Z", "shell.execute_reply": "2020-12-08T20:14:58.178501Z" } }, "outputs": [ { "data": { "text/plain": [ "array([ True, True, True, True, True, True, True, True])" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "abs(pr2_array - pr_array.value) < 1e-15" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.9" } }, "nbformat": 4, "nbformat_minor": 4 }