Lab 3d - Dynamic Networks.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "aa21209d-1390-4493-8b45-8d8e085217d5",
   "metadata": {},
   "source": [
    "# Dynamic networks with DyNetX"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3766a502-a8e4-433f-954d-c7eaa344847c",
   "metadata": {},
   "source": [
    "DyNetx is built upon networkx and is designed to configure, model and analyze dynamic networks.\n",
    "\n",
    "In this tutorial we will introduce the DynGraph object that can be used to describe undirected, temporal graphs."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0dac0547-d220-461e-b4b7-93044aec4e9b",
   "metadata": {},
   "source": [
    "The easiest way to install pymnet is via pip:\n",
    "\n",
    "> pip install dynetx\n",
    "\n",
    "Start by importing the library:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "38ff7e87-1427-4893-a2bf-8cf79712564e",
   "metadata": {},
   "outputs": [],
   "source": [
    "import dynetx as dn"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cfb45655-bd00-48fd-bb8c-60b34b0a1236",
   "metadata": {},
   "source": [
    "## Creating a graph\n",
    "Create an empty dynamic graph with no nodes and no edges."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "9452df13-7552-4f9d-806e-478747c3f102",
   "metadata": {},
   "outputs": [],
   "source": [
    "g = dn.DynGraph(edge_removal=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "28be9081-e79d-4ede-857e-f35f9d4f0090",
   "metadata": {},
   "source": [
    "During the construction phase the edge_removal parameter allows to specify if the dynamic graph will allow edge removal or not."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c1d5411c-6e4f-41dd-9d86-d6ca3d694f64",
   "metadata": {},
   "source": [
    "## Interactions\n",
    "\n",
    "G can be grown by adding one interaction at a time. Every interaction is univocally defined by its endpoints, u and v, as well as its timestamp t."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "e4b19f14-880e-47d4-9b8d-134c3e8c3290",
   "metadata": {},
   "outputs": [],
   "source": [
    "g.add_interaction(u=1, v=2, t=0)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3bc67300-8e54-4e27-b657-f067fad6cecd",
   "metadata": {},
   "source": [
    "Moreover, also interaction duration can be specified at creation time, by setting kwarg e equal to the last timestamp at which the interaction is present:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "0b3a82da-dd19-4adf-b135-b907d5bda05b",
   "metadata": {},
   "outputs": [],
   "source": [
    "g.add_interaction(u=1, v=2, t=0, e=3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f329ac70-0cfa-4cc1-85e2-6b5d3e990c5b",
   "metadata": {},
   "source": [
    "In the above example the interaction (1, 2) appear at time 0 and vanish at time 3, thus being present in [0, 2].\n",
    "\n",
    "Interaction list can also be added: in such scenario all the interactions in the list will have a same timestamp (i.e. they will belong to a same network snapshot)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "06389c92-983c-4405-9765-1098283d100a",
   "metadata": {},
   "outputs": [],
   "source": [
    "g.add_interactions_from([(1, 2), (2, 3), (3, 1)], t=2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "949a2147-c73c-45ba-b330-24ed97b07690",
   "metadata": {},
   "source": [
    "The same method can be used to add any ebunch of interaction. An ebunch is any iterable container of interaction-tuples."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "fc0c92be-e0df-4585-8c1b-f081616c169c",
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "H = nx.karate_club_graph()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "ef2629c5-a961-4f9d-9361-5f94cf9e1fe9",
   "metadata": {},
   "outputs": [],
   "source": [
    "g.add_interactions_from(H.edges(), t=2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5131def6-1e2d-4d29-bf2d-730488fa7d58",
   "metadata": {},
   "source": [
    "## Nodes\n",
    "\n",
    "Flattened node degree can be computed via the usual degree method exposed by networkx graph objects. In order to get the time dependent degree a parameter t, identifying the desired snapshot, must be specified.\n",
    "\n",
    "Similarly, the neighbors method has been extended with a similar optional filtering parameter t."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2701f72e-636e-4fd0-9ff1-d82e52049b32",
   "metadata": {},
   "source": [
    "## Read graph from file\n",
    "\n",
    "DyNetx allows to read/write networks from files in two formats:\n",
    "\n",
    "- snapshot graph (extended edgelist)\n",
    "- interaction graph (extended edgelist)\n",
    "\n",
    "The former format describes the dynamic graph one edge per row as a 3-tuple"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fd60833e-8faa-4926-9f5f-626357ea4944",
   "metadata": {},
   "source": [
    "> n1 n2 t1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "13a61873-95ea-4fa7-bba8-e664942b7f6c",
   "metadata": {},
   "source": [
    "where\n",
    "\n",
    "- n1 and n2 are nodes\n",
    "- t1 is the timestamp of interaction appearance\n",
    "\n",
    "The latter format describes the dynamic graph one interaction per row as a 4-tuple\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "342410b9-ea17-4406-b3c2-28d30aaa5c49",
   "metadata": {},
   "source": [
    "> n1 n2 op t1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7a15ca60-aeab-41c0-a4f7-5e963acc571b",
   "metadata": {},
   "source": [
    "where\n",
    "\n",
    "- n1 and n2 are nodes\n",
    "- t1 is the timestamp of interaction appearance\n",
    "- op identify either the insertion, +, or deletion, - of the edge\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b96b409e-a655-4646-ae23-85e904ef3946",
   "metadata": {},
   "source": [
    "## Snapshot Graph\n",
    "In order to read a snapshot graph file"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "44bc5bc3-d111-4d0b-89c7-b9f34547a048",
   "metadata": {},
   "outputs": [],
   "source": [
    "g = dn.read_interactions(graph_filename, nodetype=int, timestamptype=int)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "29d85946-dd8e-4115-a3b7-bd33e8481051",
   "metadata": {},
   "source": [
    "in order to save a graph in the same format"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "91b90249-1230-4db6-9cd7-6ff91041812b",
   "metadata": {},
   "outputs": [],
   "source": [
    "dn.write_interactions(graph, graph_filename)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b29d03d9-b8e7-4edc-853f-75d1fc0a1485",
   "metadata": {},
   "source": [
    "## Snapshots and Interactions\n",
    "The timestamps associated to graph edges can be retrieved through\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "997e5321-4e54-42a2-b8a1-4661275ce825",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g.temporal_snapshots_ids()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6b77d372-cc50-4333-86a5-4372a08e209b",
   "metadata": {},
   "source": [
    "Similarly, the number of interactions in a given snapshot can be obtained via\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "1986095c-3e97-490b-a43f-cfc241a6d569",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g.number_of_interactions(t=0)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3dd17d21-ecda-49ee-b1cc-73ac8fbe4665",
   "metadata": {},
   "source": [
    "if the parameter t is not specified a dictionary snapshot->edges number will be returned."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "59d8f4e3-56bb-4b2d-a274-6fc6c6bffe94",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "78"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g.number_of_interactions()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f5379aef-b832-41a3-b3d2-67d43f1f39bd",
   "metadata": {},
   "source": [
    "## Slicing a Dynamic Network\n",
    "\n",
    "Once loaded a graph it is possible to extract from it a time slice, i.e., a time-span graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "8ac0491f-672c-4e50-84a3-9a4de1f4f995",
   "metadata": {},
   "outputs": [],
   "source": [
    "s = g.time_slice(t_from=1, t_to=2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c026ced4-52d7-4a08-a3a3-ff806218274d",
   "metadata": {},
   "source": [
    "the resulting DynGraph stored in s will be composed by nodes and interactions existing within the time span [1, 2]."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "98303d9a-cfd7-48d9-8db3-9e1fabd1a520",
   "metadata": {},
   "source": [
    "## Obtain the Interaction Stream\n",
    "\n",
    "A dynamic network can be also described as stream of interactions, a chronologically ordered list of interactions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "825ee2a6-71a0-4716-8fd2-87bf6d254226",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1, 2, '+', 0)\n",
      "(1, 2, '+', 2)\n",
      "(2, 3, '+', 2)\n",
      "(3, 1, '+', 2)\n",
      "(0, 1, '+', 2)\n",
      "(0, 2, '+', 2)\n",
      "(0, 3, '+', 2)\n",
      "(0, 4, '+', 2)\n",
      "(0, 5, '+', 2)\n",
      "(0, 6, '+', 2)\n",
      "(0, 7, '+', 2)\n",
      "(0, 8, '+', 2)\n",
      "(0, 10, '+', 2)\n",
      "(0, 11, '+', 2)\n",
      "(0, 12, '+', 2)\n",
      "(0, 13, '+', 2)\n",
      "(0, 17, '+', 2)\n",
      "(0, 19, '+', 2)\n",
      "(0, 21, '+', 2)\n",
      "(0, 31, '+', 2)\n",
      "(1, 3, '+', 2)\n",
      "(1, 7, '+', 2)\n",
      "(1, 13, '+', 2)\n",
      "(1, 17, '+', 2)\n",
      "(1, 19, '+', 2)\n",
      "(1, 21, '+', 2)\n",
      "(1, 30, '+', 2)\n",
      "(2, 7, '+', 2)\n",
      "(2, 8, '+', 2)\n",
      "(2, 9, '+', 2)\n",
      "(2, 13, '+', 2)\n",
      "(2, 27, '+', 2)\n",
      "(2, 28, '+', 2)\n",
      "(2, 32, '+', 2)\n",
      "(3, 7, '+', 2)\n",
      "(3, 12, '+', 2)\n",
      "(3, 13, '+', 2)\n",
      "(4, 6, '+', 2)\n",
      "(4, 10, '+', 2)\n",
      "(5, 6, '+', 2)\n",
      "(5, 10, '+', 2)\n",
      "(5, 16, '+', 2)\n",
      "(6, 16, '+', 2)\n",
      "(8, 30, '+', 2)\n",
      "(8, 32, '+', 2)\n",
      "(8, 33, '+', 2)\n",
      "(9, 33, '+', 2)\n",
      "(13, 33, '+', 2)\n",
      "(14, 32, '+', 2)\n",
      "(14, 33, '+', 2)\n",
      "(15, 32, '+', 2)\n",
      "(15, 33, '+', 2)\n",
      "(18, 32, '+', 2)\n",
      "(18, 33, '+', 2)\n",
      "(19, 33, '+', 2)\n",
      "(20, 32, '+', 2)\n",
      "(20, 33, '+', 2)\n",
      "(22, 32, '+', 2)\n",
      "(22, 33, '+', 2)\n",
      "(23, 25, '+', 2)\n",
      "(23, 27, '+', 2)\n",
      "(23, 29, '+', 2)\n",
      "(23, 32, '+', 2)\n",
      "(23, 33, '+', 2)\n",
      "(24, 25, '+', 2)\n",
      "(24, 27, '+', 2)\n",
      "(24, 31, '+', 2)\n",
      "(25, 31, '+', 2)\n",
      "(26, 29, '+', 2)\n",
      "(26, 33, '+', 2)\n",
      "(27, 33, '+', 2)\n",
      "(28, 31, '+', 2)\n",
      "(28, 33, '+', 2)\n",
      "(29, 32, '+', 2)\n",
      "(29, 33, '+', 2)\n",
      "(30, 32, '+', 2)\n",
      "(30, 33, '+', 2)\n",
      "(31, 32, '+', 2)\n",
      "(31, 33, '+', 2)\n",
      "(32, 33, '+', 2)\n",
      "(1, 2, '-', 3)\n"
     ]
    }
   ],
   "source": [
    "for e in g.stream_interactions():\n",
    "    print(e)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a1a4cc20-ff33-4ea3-b2f0-f3bdb0a22f5e",
   "metadata": {},
   "source": [
    "the stream_interactions method returns a generator that streams the interactions in g, where e is a 4-tuple (u, v, op, t)\n",
    "\n",
    "- u, v are nodes\n",
    "- op is a edge creation or deletion event (respectively +, -)\n",
    "- t is the interactions timestamp"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cf1ed54e-698c-411a-a3fd-80a30f8f56ef",
   "metadata": {},
   "source": [
    "## Time respecting paths\n",
    "\n",
    "Dynetx allows to extract time respecting paths "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "ff35b356-6e85-480e-9e6f-eaeae684af6e",
   "metadata": {},
   "outputs": [],
   "source": [
    "from dynetx import algorithms as al"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "043896c2-62ff-4aab-a276-f67a5a737710",
   "metadata": {},
   "outputs": [],
   "source": [
    "g = dn.DynGraph()\n",
    "g.add_interaction(\"A\", \"B\", 1, 4)\n",
    "g.add_interaction(\"B\", \"D\", 2, 5)\n",
    "g.add_interaction(\"A\", \"C\", 4, 8)\n",
    "g.add_interaction(\"B\", \"D\", 2, 4)\n",
    "g.add_interaction(\"B\", \"C\", 6, 10)\n",
    "g.add_interaction(\"B\", \"D\", 2, 4)\n",
    "g.add_interaction(\"A\", \"B\", 7, 9)\n",
    "path = al.time_respecting_paths(g, \"A\", \"D\", start=1, end=9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "45cbfaeb-0cb3-43b5-9c11-13943f8107f1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defaultdict(list,\n",
       "            {('A', 'D'): [(('A', 'B', 1), ('B', 'D', 2)),\n",
       "              (('A', 'B', 1), ('B', 'D', 3)),\n",
       "              (('A', 'B', 2), ('B', 'D', 3))]})"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "f687dda8-b2e5-44d2-b1d2-54af3f8b92fc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "al.path_duration(path[('A', 'D')][1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "c8cd4f61-a6be-4abc-be7c-8ab5ec146872",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "al.path_length(path[('A', 'D')][1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "8a71e140-4253-4f4a-be0a-ea55e306a1a3",
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 4/4 [00:00<00:00, 20.95it/s]\n"
     ]
    }
   ],
   "source": [
    "paths = al.all_time_respecting_paths(g, start=1, end=9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "5481d0fd-552f-48be-974e-c92ba44d8cd2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{('A', 'B'): [(('A', 'B', 1),),\n",
       "  (('A', 'B', 2),),\n",
       "  (('A', 'B', 3),),\n",
       "  (('A', 'C', 4), ('C', 'B', 6)),\n",
       "  (('A', 'C', 5), ('C', 'B', 6)),\n",
       "  (('A', 'C', 4), ('C', 'B', 7)),\n",
       "  (('A', 'C', 5), ('C', 'B', 7)),\n",
       "  (('A', 'C', 6), ('C', 'B', 7)),\n",
       "  (('A', 'B', 7),),\n",
       "  (('A', 'C', 4), ('C', 'B', 8)),\n",
       "  (('A', 'C', 5), ('C', 'B', 8)),\n",
       "  (('A', 'C', 6), ('C', 'B', 8)),\n",
       "  (('A', 'C', 7), ('C', 'B', 8)),\n",
       "  (('A', 'B', 8),),\n",
       "  (('A', 'C', 4), ('C', 'B', 9)),\n",
       "  (('A', 'C', 5), ('C', 'B', 9)),\n",
       "  (('A', 'C', 6), ('C', 'B', 9)),\n",
       "  (('A', 'C', 7), ('C', 'B', 9))],\n",
       " ('A', 'D'): [(('A', 'B', 1), ('B', 'D', 2)),\n",
       "  (('A', 'B', 1), ('B', 'D', 3)),\n",
       "  (('A', 'B', 2), ('B', 'D', 3))],\n",
       " ('A', 'C'): [(('A', 'C', 4),),\n",
       "  (('A', 'C', 5),),\n",
       "  (('A', 'C', 6),),\n",
       "  (('A', 'C', 7),),\n",
       "  (('A', 'B', 7), ('B', 'C', 8)),\n",
       "  (('A', 'B', 7), ('B', 'C', 9)),\n",
       "  (('A', 'B', 8), ('B', 'C', 9))],\n",
       " ('A', 'A'): [(('A', 'C', 4), ('C', 'B', 6), ('B', 'A', 7)),\n",
       "  (('A', 'C', 5), ('C', 'B', 6), ('B', 'A', 7)),\n",
       "  (('A', 'C', 4), ('C', 'B', 6), ('B', 'A', 8)),\n",
       "  (('A', 'C', 4), ('C', 'B', 7), ('B', 'A', 8)),\n",
       "  (('A', 'C', 5), ('C', 'B', 6), ('B', 'A', 8)),\n",
       "  (('A', 'C', 5), ('C', 'B', 7), ('B', 'A', 8)),\n",
       "  (('A', 'C', 6), ('C', 'B', 7), ('B', 'A', 8))],\n",
       " ('B', 'A'): [(('B', 'A', 1),),\n",
       "  (('B', 'A', 1), ('A', 'C', 4), ('C', 'B', 6), ('B', 'A', 7)),\n",
       "  (('B', 'A', 1), ('A', 'C', 5), ('C', 'B', 6), ('B', 'A', 7)),\n",
       "  (('B', 'A', 1), ('A', 'C', 4), ('C', 'B', 6), ('B', 'A', 8)),\n",
       "  (('B', 'A', 1), ('A', 'C', 4), ('C', 'B', 7), ('B', 'A', 8)),\n",
       "  (('B', 'A', 1), ('A', 'C', 5), ('C', 'B', 6), ('B', 'A', 8)),\n",
       "  (('B', 'A', 1), ('A', 'C', 5), ('C', 'B', 7), ('B', 'A', 8)),\n",
       "  (('B', 'A', 1), ('A', 'C', 6), ('C', 'B', 7), ('B', 'A', 8)),\n",
       "  (('B', 'A', 2),),\n",
       "  (('B', 'A', 3),),\n",
       "  (('B', 'A', 2), ('A', 'C', 4), ('C', 'B', 6), ('B', 'A', 7)),\n",
       "  (('B', 'A', 2), ('A', 'C', 5), ('C', 'B', 6), ('B', 'A', 7)),\n",
       "  (('B', 'A', 3), ('A', 'C', 4), ('C', 'B', 6), ('B', 'A', 7)),\n",
       "  (('B', 'A', 3), ('A', 'C', 5), ('C', 'B', 6), ('B', 'A', 7)),\n",
       "  (('B', 'A', 2), ('A', 'C', 4), ('C', 'B', 6), ('B', 'A', 8)),\n",
       "  (('B', 'A', 2), ('A', 'C', 4), ('C', 'B', 7), ('B', 'A', 8)),\n",
       "  (('B', 'A', 2), ('A', 'C', 5), ('C', 'B', 6), ('B', 'A', 8)),\n",
       "  (('B', 'A', 2), ('A', 'C', 5), ('C', 'B', 7), ('B', 'A', 8)),\n",
       "  (('B', 'A', 2), ('A', 'C', 6), ('C', 'B', 7), ('B', 'A', 8)),\n",
       "  (('B', 'A', 3), ('A', 'C', 4), ('C', 'B', 6), ('B', 'A', 8)),\n",
       "  (('B', 'A', 3), ('A', 'C', 4), ('C', 'B', 7), ('B', 'A', 8)),\n",
       "  (('B', 'A', 3), ('A', 'C', 5), ('C', 'B', 6), ('B', 'A', 8)),\n",
       "  (('B', 'A', 3), ('A', 'C', 5), ('C', 'B', 7), ('B', 'A', 8)),\n",
       "  (('B', 'A', 3), ('A', 'C', 6), ('C', 'B', 7), ('B', 'A', 8)),\n",
       "  (('B', 'C', 6), ('C', 'A', 7)),\n",
       "  (('B', 'A', 7),),\n",
       "  (('B', 'A', 8),)],\n",
       " ('B', 'C'): [(('B', 'A', 1), ('A', 'C', 4)),\n",
       "  (('B', 'A', 1), ('A', 'C', 5)),\n",
       "  (('B', 'A', 1), ('A', 'C', 6)),\n",
       "  (('B', 'A', 1), ('A', 'C', 7)),\n",
       "  (('B', 'A', 2), ('A', 'C', 4)),\n",
       "  (('B', 'A', 3), ('A', 'C', 4)),\n",
       "  (('B', 'A', 2), ('A', 'C', 5)),\n",
       "  (('B', 'A', 3), ('A', 'C', 5)),\n",
       "  (('B', 'A', 2), ('A', 'C', 6)),\n",
       "  (('B', 'A', 3), ('A', 'C', 6)),\n",
       "  (('B', 'A', 2), ('A', 'C', 7)),\n",
       "  (('B', 'A', 3), ('A', 'C', 7)),\n",
       "  (('B', 'C', 6),),\n",
       "  (('B', 'C', 7),),\n",
       "  (('B', 'C', 8),),\n",
       "  (('B', 'C', 6), ('C', 'A', 7), ('A', 'B', 8), ('B', 'C', 9)),\n",
       "  (('B', 'C', 9),)],\n",
       " ('B', 'B'): [(('B', 'A', 1), ('A', 'C', 4), ('C', 'B', 6)),\n",
       "  (('B', 'A', 1), ('A', 'C', 5), ('C', 'B', 6)),\n",
       "  (('B', 'A', 1), ('A', 'C', 4), ('C', 'B', 7)),\n",
       "  (('B', 'A', 1), ('A', 'C', 5), ('C', 'B', 7)),\n",
       "  (('B', 'A', 1), ('A', 'C', 6), ('C', 'B', 7)),\n",
       "  (('B', 'A', 1), ('A', 'C', 4), ('C', 'B', 8)),\n",
       "  (('B', 'A', 1), ('A', 'C', 5), ('C', 'B', 8)),\n",
       "  (('B', 'A', 1), ('A', 'C', 6), ('C', 'B', 8)),\n",
       "  (('B', 'A', 1), ('A', 'C', 7), ('C', 'B', 8)),\n",
       "  (('B', 'A', 1), ('A', 'C', 4), ('C', 'B', 9)),\n",
       "  (('B', 'A', 1), ('A', 'C', 5), ('C', 'B', 9)),\n",
       "  (('B', 'A', 1), ('A', 'C', 6), ('C', 'B', 9)),\n",
       "  (('B', 'A', 1), ('A', 'C', 7), ('C', 'B', 9)),\n",
       "  (('B', 'A', 2), ('A', 'C', 4), ('C', 'B', 6)),\n",
       "  (('B', 'A', 2), ('A', 'C', 5), ('C', 'B', 6)),\n",
       "  (('B', 'A', 3), ('A', 'C', 4), ('C', 'B', 6)),\n",
       "  (('B', 'A', 3), ('A', 'C', 5), ('C', 'B', 6)),\n",
       "  (('B', 'A', 2), ('A', 'C', 4), ('C', 'B', 7)),\n",
       "  (('B', 'A', 2), ('A', 'C', 5), ('C', 'B', 7)),\n",
       "  (('B', 'A', 2), ('A', 'C', 6), ('C', 'B', 7)),\n",
       "  (('B', 'A', 3), ('A', 'C', 4), ('C', 'B', 7)),\n",
       "  (('B', 'A', 3), ('A', 'C', 5), ('C', 'B', 7)),\n",
       "  (('B', 'A', 3), ('A', 'C', 6), ('C', 'B', 7)),\n",
       "  (('B', 'A', 2), ('A', 'C', 4), ('C', 'B', 8)),\n",
       "  (('B', 'A', 2), ('A', 'C', 5), ('C', 'B', 8)),\n",
       "  (('B', 'A', 2), ('A', 'C', 6), ('C', 'B', 8)),\n",
       "  (('B', 'A', 2), ('A', 'C', 7), ('C', 'B', 8)),\n",
       "  (('B', 'A', 3), ('A', 'C', 4), ('C', 'B', 8)),\n",
       "  (('B', 'A', 3), ('A', 'C', 5), ('C', 'B', 8)),\n",
       "  (('B', 'A', 3), ('A', 'C', 6), ('C', 'B', 8)),\n",
       "  (('B', 'A', 3), ('A', 'C', 7), ('C', 'B', 8)),\n",
       "  (('B', 'A', 2), ('A', 'C', 4), ('C', 'B', 9)),\n",
       "  (('B', 'A', 2), ('A', 'C', 5), ('C', 'B', 9)),\n",
       "  (('B', 'A', 2), ('A', 'C', 6), ('C', 'B', 9)),\n",
       "  (('B', 'A', 2), ('A', 'C', 7), ('C', 'B', 9)),\n",
       "  (('B', 'A', 3), ('A', 'C', 4), ('C', 'B', 9)),\n",
       "  (('B', 'A', 3), ('A', 'C', 5), ('C', 'B', 9)),\n",
       "  (('B', 'A', 3), ('A', 'C', 6), ('C', 'B', 9)),\n",
       "  (('B', 'A', 3), ('A', 'C', 7), ('C', 'B', 9)),\n",
       "  (('B', 'C', 6), ('C', 'A', 7), ('A', 'B', 8))],\n",
       " ('B', 'D'): [(('B', 'D', 2),), (('B', 'D', 3),)]}"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "paths"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a3cc49da-bfe6-40d3-9d42-2daed1ad9f15",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}