Simplify Graph.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import json\n",
    "from collections import Counter\n",
    "import matplotlib.pyplot as plt\n",
    "% matplotlib inline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "fname = \"/Users/jonathanraiman/Desktop/datasets/category_graph.json\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "with open(fname, \"rt\") as f:\n",
    "    graph = json.load(f)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Clean broken, disconnected elements, from graph:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "bad_keys = []\n",
    "for key in graph.keys():\n",
    "    if \"[[\" in key or \"]]\" in key:\n",
    "        bad_keys.append(key)\n",
    "for key in bad_keys:\n",
    "    del graph[key]\n",
    "\n",
    "for el in graph.keys():\n",
    "    kids = []\n",
    "    for child in graph[el]:\n",
    "        if \"[[\" in child or \"]]\" in child:\n",
    "            continue\n",
    "        if child.lower().startswith(\"category:\"):\n",
    "            if \"Category:\" + child.split(\":\",1)[1] in graph:\n",
    "                kids.append(\"Category:\" + child.split(\":\",1)[1])\n",
    "        else:\n",
    "            kids.append(child)\n",
    "    graph[el] = kids"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Special Nodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 173,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "cats = set()\n",
    "articles = set()\n",
    "for key, value in graph.items():\n",
    "    if key.startswith(\"Category:\"):\n",
    "        cats.add(key.replace(\"Category:\", \"\"))\n",
    "    for child in value:\n",
    "        if not child.startswith(\"Category:\"):\n",
    "            articles.add(child)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 174,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "fixed_points = cats & articles\n",
    "blacklist = [\" in \", \" District\", \" County\"]\n",
    "def in_blacklist(art, bl):\n",
    "    for el in bl:\n",
    "        if el in art:\n",
    "            return True\n",
    "    return False\n",
    "non_date_fixed_points = set([art for art in fixed_points if not in_blacklist(art, blacklist)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "inverse_graph = {}\n",
    "for key in graph.keys():\n",
    "    for child in graph[key]:\n",
    "        if child in inverse_graph:\n",
    "            inverse_graph[child].append(key)\n",
    "        else:\n",
    "            inverse_graph[child] = [key]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Can find the root of wikipedia by looking at [Category:Main topic classifications](https://en.wikipedia.org/wiki/Category:Main_topic_classifications) online and finding the parent for this category. Going up this leads to **Category:Articles**, which has **Category:Contents** as parent. **Category:Contents** has no parent, and is the most meta of all articles."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "root = \"Category:Contents\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "fname_inverted = \"/Users/jonathanraiman/Desktop/datasets/category_graph.inverted.json\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "with open(fname_inverted, \"wt\") as f:\n",
    "    json.dump(inverse_graph, f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "with open(fname_inverted, \"rt\") as f:\n",
    "    inverse_graph = json.load(f)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Upward edges"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "def get_node_depth(root, graph):\n",
    "    visited_nodes = set()\n",
    "    node_queue    = deque()\n",
    "    depth         = {root: 0}\n",
    "    node_queue.appendleft(root)\n",
    "    visited_nodes.add(root)\n",
    "    \n",
    "    while len(node_queue) > 0:\n",
    "        node = node_queue.pop()\n",
    "        if node in graph:\n",
    "            for child in graph[node]:\n",
    "                if child not in visited_nodes:\n",
    "                    node_queue.appendleft(child)\n",
    "                    visited_nodes.add(child)\n",
    "                    depth[child] = depth[node] + 1\n",
    "    return depth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "depth = get_node_depth(root, graph)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Export ontology to format of the form:\n",
    "```\n",
    "root -> child\n",
    "child -> subchild\n",
    "         grandchild\n",
    "```\n",
    "for easy serialization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "import gzip\n",
    "import numpy as np\n",
    "def save_graph_from_root(root, graph, outpath, connector=\"->\", max_log1p_degree=7, max_depth = 99999):\n",
    "    global inverse_graph\n",
    "    save_nodes = set()\n",
    "    node_queue = deque()\n",
    "    node_queue.appendleft(root)\n",
    "    save_nodes.add(root)\n",
    "    depth = {root: 0}\n",
    "    \n",
    "    def acceptable_node(node):\n",
    "        if depth[node] > max_depth:\n",
    "            return False\n",
    "        return (\n",
    "            not node.startswith(\"Category:\")\n",
    "            or node in graph) and not node.lower().startswith(\"wikipedia:\") and \\\n",
    "            not node.lower().startswith(\"file:\") and \\\n",
    "            not node.lower().startswith(\"template:\")\n",
    "    \n",
    "    with gzip.open(outpath, \"wt\") as fout:\n",
    "        while len(node_queue) > 0:\n",
    "            node = node_queue.pop()\n",
    "            first = True\n",
    "            if node in graph:\n",
    "                if np.log1p(len(graph[node])) <= max_log1p_degree:\n",
    "                    for child in graph[node]:\n",
    "                        if child not in depth:\n",
    "                            depth[child] = depth[node] + 1\n",
    "                        if acceptable_node(child):\n",
    "                            if first:\n",
    "                                fout.write(\"%s%s%s\\n\" % (node, connector, child))\n",
    "                            else:\n",
    "                                fout.write(\"%s\\n\" % (child,))\n",
    "                            first = False\n",
    "                            if child not in save_nodes:\n",
    "                                node_queue.appendleft(child)\n",
    "                                save_nodes.add(child)\n",
    "    return save_nodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Save a subgraph starting from a specific point\n",
    "\n",
    "Starting with **Category:Sports** or **Category::Animals** we can find all descendants for this particular domain.\n",
    "We can also do the same with all of wikipedia by starting at **Category:Contents**:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "visited = save_graph_from_root(\"Category:Sports\", graph,\n",
    "                     \"/Users/jonathanraiman/Desktop/datasets/sports_ontology.txt.gz\",\n",
    "                    max_log1p_degree = 7, max_depth = 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "visited = save_graph_from_root(\"Category:Animals\", graph,\n",
    "                     \"/Users/jonathanraiman/Desktop/datasets/animal_ontology.txt.gz\",\n",
    "                    max_log1p_degree = 7, max_depth = 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "art_visited = [vis for vis in visited if not vis.startswith(\"Category:\")]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 132,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "visited = save_graph_from_root(root, graph,\n",
    "                     \"/Users/jonathanraiman/Desktop/datasets/ontology.txt.gz\",\n",
    "                    max_log1p_degree = 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "degrees = [(len(graph[node]), node) for node in graph.keys()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 127,
   "metadata": {
    "collapsed": false,
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1095.6331584284585"
      ]
     },
     "execution_count": 127,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.expm1(7)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Visualize distributions of degrees. Most categories have between 3 and 55 children, however there exits outliers. If we perform a cutoff $D_{\\mathrm{max}}$ with $\\mathrm{log}( 1 +  D_{\\mathrm{max}}) = 7$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": [
       "iVBORw0KGgoAAAANSUhEUgAAAYsAAAEACAYAAABCl1qQAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\n",
       "AAALEgAACxIB0t1+/AAAFHZJREFUeJzt3X+s3fV93/Hna3GCyEBQp5v5ZQJqTRVnbAFWiBZN9UJD\n",
       "3GkCKlXB2VLc1aqiug1ZNG2DTAqOIkVhU0LJJpC2OGBooSBoKaiU2oRYylSBgQFx4jCbLd7sC5jK\n",
       "BNJs2oaV9/44nzufOJf7OcfXvuce83xIR/58P+f7/d73F+49r/P5fr7fc1JVSJI0n7826QIkSUuf\n",
       "YSFJ6jIsJEldhoUkqcuwkCR1GRaSpK55wyLJyiTfTPLdJN9Jcl3r35Rkf5Jn2+NXhra5IcmeJC8k\n",
       "uWKo/5IkO9tztwz1n5Tk3tb/RJL3Dj23Psnu9rj22B66JGlUme8+iyRnAGdU1XNJTgGeAa4GPgb8\n",
       "VVV95Yj1VwN3A78InA08BqyqqkqyA/jdqtqR5BHgq1X1aJKNwN+qqo1JrgF+tarWJVkOPAVc0nb/\n",
       "DHBJVb1+DI9fkjSCeUcWVfVKVT3X2j8CvscgBAAyxyZXAfdU1ZtVtRd4EbgsyZnAqVW1o613J4PQ\n",
       "AbgS2NLaDwCXt/ZHga1V9XoLiG3A2jGPT5J0DIw8Z5HkPOAi4InW9akkzyfZnOT01ncWsH9os/0M\n",
       "wuXI/hkOh87ZwD6AqjoEvJHkPfPsS5K0yEYKi3YK6n7g022EcRtwPvAB4GXgy8etQknSxC3rrZDk\n",
       "nQxOD/1+VT0IUFWvDj3/NeDhtjgDrBza/BwGI4KZ1j6yf3abc4GXkiwDTquqg0lmgDVD26wEHp+j\n",
       "Pj/cSpKOQlXNNZ3wliu/5YPBvMSdwM1H9J851P4McHdrrwaeA97FYOTxXzk8if4kcFnb5yPA2ta/\n",
       "EbittdcBf9jay4H/BpwO/Mxse44aa75jWOoPYNOka3i71j/NtVv/5B8nQP01zvq9kcWHgE8A307y\n",
       "bOv7LPDxJB8ACvg+8Mn2k3cluQ/YBRwCNlarqoXCHcDJwCNV9Wjr3wzclWQPcLAFBlX1WpIvMLgi\n",
       "CuDz5ZVQkjQR84ZFVf0n5p7X+LN5tvki8MU5+p8BLpyj//8wuBR3rn3dDtw+X42SpOPPO7gnb/uk\n",
       "C1ig7ZMuYAG2T7qABdo+6QIWaPukC1ig7ZMuYDHNe1PeNEhSNc4kjSRp7NdORxaSpC7DQpLUZVhI\n",
       "kroMC0lSl2EhSerqftyH5jfux4145ZakaWRYHBOj5oU5IWk6eRpKktRlWEiSugwLSVKXYSFJ6jIs\n",
       "JEldhoUkqcuwkCR1GRaSpC7DQpLUZVhIkroMC0lSl2EhSeoyLCRJXYaFJKnLsJAkdRkWkqQuw0KS\n",
       "1GVYSJK63lZfqzrO92X7XdmSdNjbKiwGRskLc0KShnkaSpLUZVhIkroMC0lSl2EhSeoyLCRJXYaF\n",
       "JKnLsJAkdc0bFklWJvlmku8m+U6S61r/8iTbkuxOsjXJ6UPb3JBkT5IXklwx1H9Jkp3tuVuG+k9K\n",
       "cm/rfyLJe4eeW99+xu4k1x7bQ5ckjao3sngT+ExVvR/4IPA7Sd4HXA9sq6oLgG+0ZZKsBq4BVgNr\n",
       "gVuTzN7hdhuwoapWAauSrG39G4CDrf9m4Ka2r+XA54BL2+PG4VCSJC2eecOiql6pquda+0fA94Cz\n",
       "gSuBLW21LcDVrX0VcE9VvVlVe4EXgcuSnAmcWlU72np3Dm0zvK8HgMtb+6PA1qp6vapeB7YxCCBJ\n",
       "0iIbec4iyXnARcCTwIqqOtCeOgCsaO2zgP1Dm+1nEC5H9s+0ftq/+wCq6hDwRpL3zLMvSdIiG+mz\n",
       "oZKcwuBd/6er6q8On1mCqqpxPqDveEiyaWhxe1Vtn1ApkrQkJVkDrDna7bthkeSdDILirqp6sHUf\n",
       "SHJGVb3STjG92vpngJVDm5/DYEQw09pH9s9ucy7wUpJlwGlVdTDJDD95YCuBx+eqsao29Y5Dkt7O\n",
       "2pvo7bPLSW4cZ/ve1VABNgO7qur3hp56CFjf2uuBB4f61yV5V5LzgVXAjqp6BfhhksvaPn8d+JM5\n",
       "9vVrDCbMAbYCVyQ5PcnPAB8B/nycg5MkHRu9kcWHgE8A307ybOu7AfgScF+SDcBe4GMAVbUryX3A\n",
       "LuAQsLGqZk9RbQTuAE4GHqmqR1v/ZuCuJHuAg8C6tq/XknwBeKqt9/k20S1JWmQ5/Fo+nZLUqF9U\n",
       "NJhbGe37LI79PsfbryQdT+O8doJ3cEuSRmBYSJK6DAtJUpdhIUnqMiwkSV2GhSSpy7CQJHUZFpKk\n",
       "LsNCktRlWEiSugwLSVKXYSFJ6jIsJEldhoUkqcuwkCR1GRaSpC7DQpLUZVhIkroMC0lSl2EhSeoy\n",
       "LCRJXYaFJKnLsJAkdRkWkqQuw0KS1GVYSJK6DAtJUpdhIUnqMiwkSV2GhSSpy7CQJHUZFpKkLsNC\n",
       "ktRlWEiSugwLSVJXNyySfD3JgSQ7h/o2Jdmf5Nn2+JWh525IsifJC0muGOq/JMnO9twtQ/0nJbm3\n",
       "9T+R5L1Dz61Psrs9rj02hyxJGtcoI4vbgbVH9BXwlaq6qD3+DCDJauAaYHXb5tYkadvcBmyoqlXA\n",
       "qiSz+9wAHGz9NwM3tX0tBz4HXNoeNyY5/SiPU5K0AN2wqKpvAT+Y46nM0XcVcE9VvVlVe4EXgcuS\n",
       "nAmcWlU72np3Ale39pXAltZ+ALi8tT8KbK2q16vqdWAbPx1akqRFsJA5i08leT7J5qF3/GcB+4fW\n",
       "2Q+cPUf/TOun/bsPoKoOAW8kec88+5IkLbKjDYvbgPOBDwAvA18+ZhVJkpacZUezUVW9OttO8jXg\n",
       "4bY4A6wcWvUcBiOCmdY+sn92m3OBl5IsA06rqoNJZoA1Q9usBB6fq54km4YWt1fV9vGOSJJObEnW\n",
       "8JOvqeNtX1Wj/JDzgIer6sK2fGZVvdzanwF+sar+cZvgvpvBhPTZwGPAz1dVJXkSuA7YAfwp8NWq\n",
       "ejTJRuDCqvrtJOuAq6tqXZvgfhq4mMH8yDPAxW3+Yri2qqq55k/mOo4azM131+TY73O8/UrS8TTO\n",
       "ayeMMLJIcg/wS8DPJtkH3AisSfIBBq+S3wc+CVBVu5LcB+wCDgEb63AabQTuAE4GHqmqR1v/ZuCu\n",
       "JHuAg8C6tq/XknwBeKqt9/kjg0KStDhGGlksZY4sJGl8444svINbktRlWEiSugwLSVKXYSFJ6jIs\n",
       "JEldhoUkqcuwkCR1GRaSpC7DQpLUZVhIkroMC0lSl2EhSeo6qu+zeDsYfECgJAkMi3mM/kmyknSi\n",
       "MywW2TgjFj/OXNJSYVgsOkcskqaPE9ySpC7DQpLUZVhIkrqcs1jCRp0MdyJc0vFmWCxpo2SFOSHp\n",
       "+PM0lCSpy7CQJHUZFpKkLsNCktRlWEiSugwLSVKXYSFJ6jIsJEldhoUkqcuwkCR1GRaSpC7DQpLU\n",
       "ZVhIkrr81NkTgN/rLel4MyxOCH6vt6Tjq3saKsnXkxxIsnOob3mSbUl2J9ma5PSh525IsifJC0mu\n",
       "GOq/JMnO9twtQ/0nJbm39T+R5L1Dz61vP2N3kmuPzSFLksY1ypzF7cDaI/quB7ZV1QXAN9oySVYD\n",
       "1wCr2za3Jpl9O3sbsKGqVgGrkszucwNwsPXfDNzU9rUc+BxwaXvcOBxKkqTF0w2LqvoW8IMjuq8E\n",
       "trT2FuDq1r4KuKeq3qyqvcCLwGVJzgROraodbb07h7YZ3tcDwOWt/VFga1W9XlWvA9v46dCSJC2C\n",
       "o70aakVVHWjtA8CK1j4L2D+03n7g7Dn6Z1o/7d99AFV1CHgjyXvm2ZckaZEt+NLZqipGn2GVJE2h\n",
       "o70a6kCSM6rqlXaK6dXWPwOsHFrvHAYjgpnWPrJ/dptzgZeSLANOq6qDSWaANUPbrAQen6uYJJuG\n",
       "FrdX1fajOShJOlElWcNPvqaOt/1gYND9IecBD1fVhW353zCYlL4pyfXA6VV1fZvgvpvBhPTZwGPA\n",
       "z1dVJXkSuA7YAfwp8NWqejTJRuDCqvrtJOuAq6tqXZvgfhq4mME1n88AF7f5i+HaatR7Bwb3I4wy\n",
       "CArjXY46yXXH26f3WUiC8V47YYSRRZJ7gF8CfjbJPgZXKH0JuC/JBmAv8DGAqtqV5D5gF3AI2FiH\n",
       "02gjcAdwMvBIVT3a+jcDdyXZAxwE1rV9vZbkC8BTbb3PHxkUkqTFMdLIYilzZOHIQtL4xh1Z+NlQ\n",
       "kqQuw0KS1GVYSJK6DAtJUpdhIUnqMiwkSV2GhSSpy7CQJHUZFpKkLsNCktRlWEiSugwLSVKXYSFJ\n",
       "6jIsJEldhoUkqcuwkCR1GRaSpC7DQpLUZVhIkroMC0lSl2EhSeoyLCRJXYaFJKlr2aQL0OJKUqOu\n",
       "W1U5nrVImh6GxdvOqFlhTkg6zNNQkqQuw0KS1GVYSJK6DAtJUpdhIUnqMiwkSV2GhSSpy7CQJHUZ\n",
       "FpKkLsNCktRlWEiSuhYUFkn2Jvl2kmeT7Gh9y5NsS7I7ydYkpw+tf0OSPUleSHLFUP8lSXa2524Z\n",
       "6j8pyb2t/4kk711IvZKko7PQkUUBa6rqoqq6tPVdD2yrqguAb7RlkqwGrgFWA2uBW5PMflrdbcCG\n",
       "qloFrEqytvVvAA62/puBmxZYryTpKByL01BHfjzplcCW1t4CXN3aVwH3VNWbVbUXeBG4LMmZwKlV\n",
       "taOtd+fQNsP7egC4/BjUK0ka07EYWTyW5Okkv9X6VlTVgdY+AKxo7bOA/UPb7gfOnqN/pvXT/t0H\n",
       "UFWHgDeSLF9gzZKkMS30+yw+VFUvJ/kbwLYkLww/WVU1zpftHK0km4YWt1fV9uP9MyVpmiRZA6w5\n",
       "2u0XFBZV9XL79y+T/DFwKXAgyRlV9Uo7xfRqW30GWDm0+TkMRhQzrX1k/+w25wIvJVkGnFZVr81R\n",
       "x6aFHIcknejam+jts8tJbhxn+6M+DZXk3UlObe2/DlwB7AQeAta31dYDD7b2Q8C6JO9Kcj6wCthR\n",
       "Va8AP0xyWZvw/nXgT4a2md3XrzGYMJckLbKFjCxWAH/cLmhaBvxBVW1N8jRwX5INwF7gYwBVtSvJ\n",
       "fcAu4BCwsapmT1FtBO4ATgYeqapHW/9m4K4ke4CDwLoF1Ksx+X3dkmbl8Ov1dEpSo75QDV78Rjne\n",
       "MN53VU9y3Un//MG6hoU0XcZ57QTv4JYkjcCwkCR1GRaSpC7DQpLUZVhIkroMC0lSl2EhSeoyLCRJ\n",
       "XYaFJKnLsJAkdRkWkqQuw0KS1GVYSJK6DAtJUtdCv1ZVAkb/7gs/ylyaToaFjpFRv3tD0jTyNJQk\n",
       "qcuwkCR1GRaSpC7DQpLUZVhIkroMC0lSl2EhSeoyLCRJXd6Up0U16p3e4N3e0lJiWGiRjZoV5oS0\n",
       "lHgaSpLUdUKMLJJ8ctI1SNKJLFUjn0JekgbnwH/jf/XXvP8d8KOTRv/Au3FOl0xy3Un//HHWHW+f\n",
       "zllIx0+SGudv7AQJi1GO4YI3YM9pb/cX4Gmq1bCQjp9xw8I5C0lS1wkxZ6ETk5fZSkuHYaElzMts\n",
       "paXC01CSpC7DQpLUteTDIsnaJC8k2ZPkX026Hi1NSWrUx6RrlabRkg6LJO8A/j2wFlgNfDzJ+yZb\n",
       "1bG2fdIFLND2SRfQ1IiPw5KsWdQSjzHrn6xpr39cSzosgEuBF6tqb1W9CfwhcNWEazrGtk+6gAXa\n",
       "PukCxjY0wvjmlI9A1ky6gAVaM+kCFmjNpAtYTEs9LM4G9g0t72990gLMjjJuZL4RiKe2pMOW+qWz\n",
       "I/4RfviN/jr7Tl5YKXr7Gf3S3eMVGN4/oqViSX/cR5IPApuqam1bvgH4cVXdNLTO0j0ASVrCTpjP\n",
       "hkqyDPgvwOXAS8AO4ONV9b2JFiZJbzNL+jRUVR1K8rvAnwPvADYbFJK0+Jb0yEKStDQs9auh3tI0\n",
       "36yXZGWSbyb5bpLvJLlu0jUdjSTvSPJskocnXcu4kpye5P4k30uyq82PTY0kN7Tfn51J7k5y0qRr\n",
       "mk+Sryc5kGTnUN/yJNuS7E6yNcnpk6xxPm9R/79tvz/PJ/mjJKdNssa3MlftQ8/98yQ/TrK8t5+p\n",
       "DIsT4Ga9N4HPVNX7gQ8CvzNl9c/6NLCL0S8bWkpuAR6pqvcBfxuYmtObSc4Dfgu4uKouZHCKdt0k\n",
       "axrB7Qz+XoddD2yrqguAb7TlpWqu+rcC76+qvwPsBm5Y9KpGM1ftJFkJfAT476PsZCrDgim/Wa+q\n",
       "Xqmq51r7RwxeqM6abFXjSXIO8A+BrzFlH/va3gH+/ar6OgzmxqpqhMuvl4wfMnjD8e52Eci7gZnJ\n",
       "ljS/qvoW8IMjuq8EtrT2FuDqRS1qDHPVX1XbqurHbfFJ4JxFL2wEb/HfHuArwL8cdT/TGhYnzM16\n",
       "7V3iRQx+2abJzcC/AH7cW3EJOh/4yyS3J/nPSf5jkndPuqhRVdVrwJeB/8HgKsHXq+qxyVZ1VFZU\n",
       "1YHWPgCsmGQxC/SbwCOTLmJUSa4C9lfVt0fdZlrDYhpPe/yUJKcA9wOfbiOMqZDkHwGvVtWzTNmo\n",
       "olkGXAzcWlUXA/+TpX0K5Cck+TngnwHnMRiRnpLkn0y0qAWqwZU2U/l3neRfA/+3qu6edC2jaG+M\n",
       "PsvgIwz+f3dvu2kNixlg5dDySgaji6mR5J3AA8DvV9WDk65nTH8PuDLJ94F7gA8nuXPCNY1jP4N3\n",
       "VU+15fsZhMe0+LvAX1TVwao6BPwRg/8n0+ZAkjMAkpwJvDrhesaW5DcYnI6dprD+OQZvNJ5vf8Pn\n",
       "AM8k+ZvzbTStYfE0sCrJeUneBVwDPDThmkaWJMBmYFdV/d6k6xlXVX22qlZW1fkMJlYfr6prJ13X\n",
       "qKrqFWBfkgta1y8D351gSeN6AfhgkpPb79IvM7jQYNo8BKxv7fXAVL1pSrKWwanYq6rqf0+6nlFV\n",
       "1c6qWlFV57e/4f0MLpaYN6ynMizau6nZm/V2AfdO2c16HwI+AfyDdunps+0Xb1pN4+mDTwF/kOR5\n",
       "BldDfXHC9Yysqp4H7mTwpmn2nPN/mFxFfUnuAf4C+IUk+5L8U+BLwEeS7AY+3JaXpDnq/03g3wGn\n",
       "ANva3/CtEy3yLQzVfsHQf/thI/39elOeJKlrKkcWkqTFZVhIkroMC0lSl2EhSeoyLCRJXYaFJKnL\n",
       "sJAkdRkWkqSu/we225Y0XFjemQAAAABJRU5ErkJggg==\n"
      ],
      "text/plain": [
       "<matplotlib.figure.Figure at 0x1f3766940>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.hist(np.log1p(degrees), bins = 30);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Edges going up are parts of cycles. Let's detect them:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def get_upward_edges(depthmap, linking):\n",
    "    upward_connections = set()\n",
    "    total = 0\n",
    "    for key in linking.keys():\n",
    "        for child in linking[key]:\n",
    "            # if child is higher up in the tree\n",
    "            # then this is an upward connection\n",
    "            if key in depthmap:\n",
    "                if child.startswith(\"Category:\"):\n",
    "                    if depthmap[key] < depthmap[child]:\n",
    "                        upward_connections.add((key, child))\n",
    "                    total += 1\n",
    "    return (upward_connections, total)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 164,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def get_connected_articles(roots, linking):\n",
    "    connected_articles = set()\n",
    "    visited = set()\n",
    "    to_visit = list(roots)\n",
    "    while len(to_visit) > 0:\n",
    "        root = to_visit.pop()\n",
    "        visited.add(root)\n",
    "        for child in linking.get(\"Category:\"+root,[]):\n",
    "            if child.startswith(\"Category:\"):\n",
    "                if child[9:] not in visited:\n",
    "                    to_visit.append(child[9:])\n",
    "            else:\n",
    "                connected_articles.add(child)\n",
    "    return connected_articles"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 165,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "connected_arts = get_connected_articles(non_date_fixed_points, graph)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 166,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4946350"
      ]
     },
     "execution_count": 166,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(connected_arts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "targets = {}\n",
    "with gzip.open(\"/Users/jonathanraiman/Desktop/datasets/index2target.clean.gz\", \"rb\") as f:\n",
    "    for k, l in enumerate(f):\n",
    "        l2 = uber_decode(l)\n",
    "        targets[l2.strip()] = k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "detected      = set()\n",
    "missing       = set()\n",
    "iffy_detected = set()\n",
    "for title in art_visited:\n",
    "    if title in targets:\n",
    "        detected.add((title, targets[title]))\n",
    "    elif preprocess_title(title) in targets:\n",
    "        detected.add((preprocess_title(title), targets[preprocess_title(title)]))\n",
    "    else:\n",
    "        if \"(\" in title:\n",
    "            if title.split(\"(\", 1)[0].strip() in targets:\n",
    "                iffy_detected.add((title.split(\"(\", 1)[0].strip(), targets[title.split(\"(\", 1)[0].strip()]))\n",
    "            else:\n",
    "                missing.add(title)\n",
    "        else:\n",
    "            missing.add(title)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import sqlite3\n",
    "import xml_cleaner\n",
    "import wikipedia_ner.parse\n",
    "import gzip\n",
    "from os.path import join, isdir, exists\n",
    "\n",
    "def uber_decode(s):\n",
    "    try:\n",
    "        return s.decode(\"utf-8\")\n",
    "    except:\n",
    "        return s.decode(\"unicode-escape\")\n",
    "\n",
    "def preprocess_title(s):\n",
    "    return \" \".join([word\n",
    "              for sentence in xml_cleaner.tokenize(s)\n",
    "              for word in sentence])\n",
    "\n",
    "\n",
    "inpath = \"/Users/jonathanraiman/Desktop/datasets/enwiki.db\"\n",
    "outpath = \"/Users/jonathanraiman/Desktop/datasets/wiki_animals_onto/\"\n",
    "sqlite_conn = sqlite3.connect(\n",
    "    inpath,\n",
    "    detect_types=sqlite3.PARSE_DECLTYPES)\n",
    "insert_into_db, update_in_db, update_lines_in_db, get_obj_from_db, get_lines_from_db = wikipedia_ner.parse.sqlite_utils.create_schema(sqlite_conn, [\n",
    "        (\"lines\", \"pickle\"),\n",
    "        (\"parents\", \"pickle\")\n",
    "    ],\n",
    "    \"articles\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "missing = 0\n",
    "found   = 0\n",
    "corpuses = []\n",
    "total = 100000\n",
    "\n",
    "max_labels = 1\n",
    "\n",
    "\n",
    "for title, num in list(detected | iffy_detected)[:total]:\n",
    "    objs = get_lines_from_db(num)\n",
    "    if objs is not None and type(objs[0]) is not list:\n",
    "        corpuses.append(objs[0])\n",
    "        found += 1\n",
    "    else:\n",
    "        missing += 1\n",
    "        \n",
    "fix_succeeded = 0\n",
    "fix_failed    = 0\n",
    "failed        = []\n",
    "sqlite_conn.close()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "tsv = True\n",
    "if tsv:\n",
    "    outpath_fname = outpath\n",
    "    if isdir(outpath_fname):\n",
    "        outpath_fname = join(outpath_fname, \"train.tsv.gz\")\n",
    "    with gzip.open(outpath_fname, \"wt\") as fout:\n",
    "        for k, corpus in enumerate(corpuses):\n",
    "            for example in corpus.example:\n",
    "                kept_triggers = []\n",
    "                for trigger in example.trigger:\n",
    "                    if trigger.trigger.lower().startswith(\"category:\") or trigger.trigger.lower().startswith(\"category :\"):\n",
    "                        continue\n",
    "                    elif len(trigger.trigger.strip()) > 0:\n",
    "                        if trigger.trigger.strip() in visited:\n",
    "                            if trigger.trigger.startswith(\"Category:\"):\n",
    "                                print(\"hello\")\n",
    "                            kept_triggers.append(trigger.trigger)\n",
    "                        else:\n",
    "                            new_trigger = (trigger.trigger\n",
    "                                .replace(\"( \", \"(\")     \\\n",
    "                                .replace(\" )\", \")\")     \\\n",
    "                                .replace(\" , \", \", \")   \\\n",
    "                                .replace(\" : \", \":\")    \\\n",
    "                                .replace(\" 's \", \"'s\")  \\\n",
    "                                .replace(\"s ' \", \"s' \") \\\n",
    "                                .replace(\" - \", \"-\")    \\\n",
    "                                .replace(\" l' \", \" l'\") \\\n",
    "                                .replace(\"l ' \", \"l' \") \\\n",
    "                                .replace(\" d' \", \" d'\"))\n",
    "                            new_trigger = new_trigger[0].upper() + new_trigger[1:]\n",
    "                            if new_trigger in visited:\n",
    "                                kept_triggers.append(new_trigger)\n",
    "                                fix_succeeded += 1\n",
    "                            else:\n",
    "                                failed.append(trigger.trigger)\n",
    "                                fix_failed += 1\n",
    "\n",
    "                if len(kept_triggers) > 0 and len(kept_triggers) <= max_labels:\n",
    "                    fout.write(\" \".join(example.words))\n",
    "                    for trig in kept_triggers:\n",
    "                        if \"Category:\" in trig:\n",
    "                            pass\n",
    "                        fout.write(\"\\t\")\n",
    "                        fout.write(trig)\n",
    "                    fout.write(\"\\n\")\n",
    "sqlite_conn.close()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "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.4.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}