Bacon-Oracle.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "6ec2f7c8",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "\n",
    "from queue import PriorityQueue\n",
    "import networkx as nx\n",
    "from pyvis.network import Network"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "8d8d0c83",
   "metadata": {},
   "outputs": [],
   "source": [
    "movies_df = pd.read_csv('data/movies_data.csv')\n",
    "cast_df = pd.read_csv('data/cast_data.csv')\n",
    "cast_and_movies_df = pd.read_csv('data/cast_and_movies_data.csv')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "e50d67fe",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>id</th>\n",
       "      <th>title</th>\n",
       "      <th>year</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>15724</td>\n",
       "      <td>Dama de noche</td>\n",
       "      <td>1993</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>23331</td>\n",
       "      <td>Pesn o geroyakh</td>\n",
       "      <td>1983</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>31458</td>\n",
       "      <td>El huésped del sevillano</td>\n",
       "      <td>1970</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>35423</td>\n",
       "      <td>Kate &amp; Leopold</td>\n",
       "      <td>2001</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>36606</td>\n",
       "      <td>Another Time, Another Place</td>\n",
       "      <td>1983</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "      id                        title  year\n",
       "0  15724                Dama de noche  1993\n",
       "1  23331              Pesn o geroyakh  1983\n",
       "2  31458     El huésped del sevillano  1970\n",
       "3  35423               Kate & Leopold  2001\n",
       "4  36606  Another Time, Another Place  1983"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "movies_df.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "a7a201d9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>id</th>\n",
       "      <th>name</th>\n",
       "      <th>birth</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>Fred Astaire</td>\n",
       "      <td>1899.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>2</td>\n",
       "      <td>Lauren Bacall</td>\n",
       "      <td>1924.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>3</td>\n",
       "      <td>Brigitte Bardot</td>\n",
       "      <td>1934.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>4</td>\n",
       "      <td>John Belushi</td>\n",
       "      <td>1949.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>5</td>\n",
       "      <td>Ingmar Bergman</td>\n",
       "      <td>1918.0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   id             name   birth\n",
       "0   1     Fred Astaire  1899.0\n",
       "1   2    Lauren Bacall  1924.0\n",
       "2   3  Brigitte Bardot  1934.0\n",
       "3   4     John Belushi  1949.0\n",
       "4   5   Ingmar Bergman  1918.0"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cast_df.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "0ebeeeff",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>person_id</th>\n",
       "      <th>movie_id</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>844752</td>\n",
       "      <td>15724</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>869732</td>\n",
       "      <td>15724</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>194720</td>\n",
       "      <td>15724</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>650495</td>\n",
       "      <td>15724</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>8738</td>\n",
       "      <td>31458</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   person_id  movie_id\n",
       "0     844752     15724\n",
       "1     869732     15724\n",
       "2     194720     15724\n",
       "3     650495     15724\n",
       "4       8738     31458"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cast_and_movies_df.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bb0cba12",
   "metadata": {},
   "source": [
    "# Graph construction"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "5c6f78d6",
   "metadata": {},
   "outputs": [],
   "source": [
    "import queue"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c5317b4f",
   "metadata": {},
   "source": [
    "### I got the code of the cell below from GeeksForGeeks:\n",
    "\n",
    "https://www.geeksforgeeks.org/minimum-number-of-edges-between-two-vertices-of-a-graph/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "1fb3e2b3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def minEdgeBFS(edges, u, v, n):\n",
    "    \n",
    "    # visited[n] for keeping track\n",
    "    # of visited node in BFS\n",
    "    visited = [0] * n\n",
    "\n",
    "    # Initialize distances as 0\n",
    "    distance = [0] * n\n",
    "\n",
    "    # queue to do BFS.\n",
    "    Q = queue.Queue()\n",
    "    distance[u] = 0\n",
    "\n",
    "    Q.put(u)\n",
    "    visited[u] = True\n",
    "    while (not Q.empty()):\n",
    "        x = Q.get()\n",
    "        \n",
    "        for i in range(len(edges[x])):\n",
    "            if (visited[edges[x][i]]):\n",
    "                continue\n",
    "\n",
    "            # update distance for i\n",
    "            distance[edges[x][i]] = distance[x] + 1\n",
    "            Q.put(edges[x][i])\n",
    "            visited[edges[x][i]] = 1\n",
    "    return distance[v]\n",
    "\n",
    "# function for addition of edge\n",
    "def addEdge(edges, u, v):\n",
    "    edges[u].append(v)\n",
    "    edges[v].append(u)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "04719930",
   "metadata": {},
   "outputs": [],
   "source": [
    "kevin_bacon_id = 102"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ad806f42",
   "metadata": {},
   "source": [
    "### Here, I am sampling only 5% of the data, for demonstration purposes.\n",
    "\n",
    "My computer couldn't build the graph with all the actors, it's just too much for it!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "d4840b47",
   "metadata": {},
   "outputs": [],
   "source": [
    "kevin_bacon_df = cast_and_movies_df[cast_and_movies_df['person_id'] == kevin_bacon_id]\n",
    "cast_and_movies_df_without_bacon = cast_and_movies_df[cast_and_movies_df['person_id'] != kevin_bacon_id]\n",
    "\n",
    "sample_ids = pd.Series(cast_and_movies_df_without_bacon['person_id'].unique()).sample(frac=0.05).unique()\n",
    "\n",
    "sampled_cast_movies_df = cast_and_movies_df[cast_and_movies_df['person_id'].isin(sample_ids)]\n",
    "sampled_cast_movies_df = pd.concat([sampled_cast_movies_df, kevin_bacon_df])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "e6cc366f",
   "metadata": {},
   "outputs": [],
   "source": [
    "person_nodes = {}\n",
    "for i, value in enumerate(sampled_cast_movies_df['person_id'].sort_values().unique()):\n",
    "    person_nodes[i] = value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "46852ec0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "27036"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(person_nodes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "a0857427",
   "metadata": {},
   "outputs": [],
   "source": [
    "movie_edges = {}\n",
    "for i, value in enumerate(sampled_cast_movies_df['movie_id'].sort_values().unique()):\n",
    "    movie_edges[i] = value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "0dabb45e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "53493"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(movie_edges)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e3a7c77e",
   "metadata": {},
   "source": [
    "### The cells below are meant to be run only once, to create the graph, and it takes a while to finish."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "a185efbf",
   "metadata": {},
   "outputs": [],
   "source": [
    "# n = len(movie_edges)\n",
    "# edges = [[] for i in range(n)]\n",
    "\n",
    "# for i in sampled_cast_movies_df.values:\n",
    "#     p_node_value = i[0]\n",
    "#     m_edge_value = i[1]\n",
    "\n",
    "#     p_node = list(person_nodes.keys())[list(person_nodes.values()).index(p_node_value)]\n",
    "#     m_edge = list(movie_edges.keys())[list(movie_edges.values()).index(m_edge_value)]\n",
    "    \n",
    "#     addEdge(edges, m_edge, p_node)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "34fd2c9a",
   "metadata": {},
   "outputs": [],
   "source": [
    "# pd.DataFrame(edges).to_csv('data/graph.csv')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "5cde9f49",
   "metadata": {},
   "outputs": [],
   "source": [
    "# sampled_cast_movies_df.to_csv('data/sampled_cast_and_movies_data.csv', index=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "060ba029",
   "metadata": {},
   "source": [
    "# Executing Breadth-First Search (BFS)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "ed1901ba",
   "metadata": {},
   "outputs": [],
   "source": [
    "sampled_cast_movies_df = pd.read_csv('data/sampled_cast_and_movies_data.csv')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "id": "3f3d24e5",
   "metadata": {},
   "outputs": [],
   "source": [
    "graph = pd.read_csv('data/graph.csv', sep=',').drop('Unnamed: 0', axis=1)\n",
    "graph = [graph.iloc[i].dropna().astype(int).to_list() for i in graph.index]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "id": "1ddb5675",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([\"'Crazy' Bob Cook\", \"'Dirty Dave' Grimsley\", \"'University' Jeevan\",\n",
       "       ..., 'Ülle Lichtfeldt', 'Ülo Voitka', 'Þórey Birgisdóttir'],\n",
       "      dtype=object)"
      ]
     },
     "execution_count": 130,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cast_df[cast_df['id'].isin(sampled_cast_movies_df['person_id'].unique())][\n",
    "    'name'\n",
    "].sort_values().values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 120,
   "id": "6458a56f",
   "metadata": {},
   "outputs": [],
   "source": [
    "example_id = sampled_cast_movies_df.sample(1).values[0][0]\n",
    "example_name = cast_df[cast_df['id'] == example_id]['name'].iloc[0]\n",
    "example_id_graph_node = list(person_nodes.keys())[list(person_nodes.values()).index(example_id)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 121,
   "id": "d2938a93",
   "metadata": {},
   "outputs": [],
   "source": [
    "kevin_bacon_id_graph_node = list(person_nodes.keys())[list(person_nodes.values()).index(kevin_bacon_id)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "id": "60061fc2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>id</th>\n",
       "      <th>name</th>\n",
       "      <th>birth</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>424</th>\n",
       "      <td>437</td>\n",
       "      <td>Woody Harrelson</td>\n",
       "      <td>1961.0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "      id             name   birth\n",
       "424  437  Woody Harrelson  1961.0"
      ]
     },
     "execution_count": 122,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# randomly chosen actor\n",
    "cast_df[cast_df['id'] == example_id]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "id": "87f11685",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Woody Harrelson is 4 movies away from Kevin Bacon.\n"
     ]
    }
   ],
   "source": [
    "n = len(graph)\n",
    "result = minEdgeBFS(graph, example_id_graph_node, kevin_bacon_id_graph_node, n)\n",
    "print(f\"{example_name} is {result} movies away from Kevin Bacon.\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "46b1ad1a",
   "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.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}