kargers_with_networkx.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Karger's min-cut with networkx"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Links:\n",
    "### https://www.youtube.com/watch?v=sXHr3CDAeWE&list=PLOQjlWvnI0faRpH2oJcyW4CuM5Clt8a2n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Randomized min-cut (Karger's algorithm)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import copy\n",
    "import random\n",
    "import networkx as nx"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Functions definition"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sample_edge(G):\n",
    "    # O(1) time and memory\n",
    "    # choose a node uar\n",
    "    u = random.sample(G.nodes, 1)[0]\n",
    "    \n",
    "    # choose a second node uar from neighbors of u\n",
    "    v = random.sample([x for x in G.__getitem__(u)], 1)[0]\n",
    "        \n",
    "    return [u,v]\n",
    "\n",
    "def print_state(G):\n",
    "    # O(1) time and memory\n",
    "    print('number of edges:', G.number_of_edges())\n",
    "    print('list of nodes:', list(G.nodes))\n",
    "    print('list of edges:', list(G.edges(data=True)))\n",
    "        \n",
    "def get_weight(G):\n",
    "    # O(m) time and O(1) memory\n",
    "    output = 0\n",
    "    for edge in G.edges(data=True):\n",
    "        output += edge[2]['weight']\n",
    "                \n",
    "    return output"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Graph definition"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "G = nx.MultiGraph()\n",
    "G.add_edge(0, 1, weight=0.5)\n",
    "G.add_edge(0, 2, weight=0.25)\n",
    "G.add_edge(2, 1, weight=0.125)\n",
    "\n",
    "# parallel edge\n",
    "G.add_edge(0, 1, weight=1)\n",
    "\n",
    "G.add_edge(3, 1, weight=2)\n",
    "G.add_edge(2, 3, weight=4)\n",
    "G.add_edge(4, 3, weight=8)\n",
    "G.add_edge(2, 4, weight=16)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### test functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "number of edges: 8\n",
      "list of nodes: [0, 1, 2, 3, 4]\n",
      "list of edges: [(0, 1, {'weight': 0.5}), (0, 1, {'weight': 1}), (0, 2, {'weight': 0.25}), (1, 2, {'weight': 0.125}), (1, 3, {'weight': 2}), (2, 3, {'weight': 4}), (2, 4, {'weight': 16}), (3, 4, {'weight': 8})]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "31.875"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print_state(G)\n",
    "get_weight(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 0]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sample_edge(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "number of edges: 7\n",
      "list of nodes: [0, 1, 2, 4]\n",
      "list of edges: [(0, 1, {'weight': 0.5}), (0, 1, {'weight': 1}), (0, 2, {'weight': 0.25}), (1, 2, {'weight': 0.125}), (1, 4, {'weight': 2}), (2, 4, {'weight': 16}), (2, 4, {'weight': 4})]\n"
     ]
    }
   ],
   "source": [
    "# contract edge\n",
    "G = nx.contracted_nodes(G, 4, 3)\n",
    "G.remove_edges_from(list(nx.selfloop_edges(G)))\n",
    "print_state(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[4, 2]\n",
      "number of edges: 5\n",
      "list of nodes: [0, 1, 4]\n",
      "list of edges: [(0, 1, {'weight': 0.5}), (0, 1, {'weight': 1}), (0, 4, {'weight': 0.25}), (1, 4, {'weight': 2}), (1, 4, {'weight': 0.125})]\n"
     ]
    }
   ],
   "source": [
    "sample = sample_edge(G)\n",
    "print(sample)\n",
    "# contract edge\n",
    "G = nx.contracted_nodes(G, sample[0], sample[1])\n",
    "G.remove_edges_from(list(nx.selfloop_edges(G)))\n",
    "print_state(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 0]\n",
      "number of edges: 3\n",
      "list of nodes: [1, 4]\n",
      "list of edges: [(1, 4, {'weight': 2}), (1, 4, {'weight': 0.125}), (1, 4, {'weight': 0.25})]\n"
     ]
    }
   ],
   "source": [
    "sample = sample_edge(G)\n",
    "print(sample)\n",
    "# contract edge\n",
    "G = nx.contracted_nodes(G, sample[0], sample[1])\n",
    "G.remove_edges_from(list(nx.selfloop_edges(G)))\n",
    "print_state(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2.375"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_weight(G)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Karger's algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def contract(G_0):\n",
    "    # O(nm) time and O(m) memory, m = # edges\n",
    "    G = copy.deepcopy(G_0)\n",
    "    \n",
    "    # contract until only 2 nodes left\n",
    "    while len(G.nodes) > 2:\n",
    "        # contract edge\n",
    "        sample = sample_edge(G)\n",
    "        G = nx.contracted_nodes(G, sample[0], sample[1])\n",
    "        G.remove_edges_from(list(nx.selfloop_edges(G)))\n",
    "        \n",
    "    return get_weight(G)\n",
    "\n",
    "def Karger(G):\n",
    "    # O(nm^3) time and O(m^2) memory, m = # edges\n",
    "    print_state(G)\n",
    "    \n",
    "    c = 3 # (P(fail) <= e^(-c))\n",
    "    m = G.number_of_edges()\n",
    "    ans = get_weight(G)\n",
    "    ans_list = []\n",
    "    \n",
    "    # repeat cm^2 times: contract until only 2 nodes left\n",
    "    # and return best output\n",
    "    for _ in range(c*(m**2)):\n",
    "        ans_list.append(contract(G))\n",
    "        ans = min(ans, ans_list[-1])\n",
    "        \n",
    "    return ans, ans_list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Tests"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### INPUT 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "G = nx.MultiGraph()\n",
    "G.add_edge(0, 1, weight=0.5)\n",
    "G.add_edge(0, 2, weight=0.25)\n",
    "G.add_edge(2, 1, weight=0.125)\n",
    "\n",
    "# parallel edge\n",
    "G.add_edge(0, 1, weight=1)\n",
    "\n",
    "G.add_edge(3, 1, weight=2)\n",
    "G.add_edge(2, 3, weight=4)\n",
    "G.add_edge(4, 3, weight=8)\n",
    "G.add_edge(2, 4, weight=16)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "number of edges: 8\n",
      "list of nodes: [0, 1, 2, 3, 4]\n",
      "list of edges: [(0, 1, {'weight': 0.5}), (0, 1, {'weight': 1}), (0, 2, {'weight': 0.25}), (1, 2, {'weight': 0.125}), (1, 3, {'weight': 2}), (2, 3, {'weight': 4}), (2, 4, {'weight': 16}), (3, 4, {'weight': 8})]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(1.75,\n",
       " [1.75,\n",
       "  3.625,\n",
       "  12.375,\n",
       "  3.625,\n",
       "  22,\n",
       "  2.375,\n",
       "  2.375,\n",
       "  3.625,\n",
       "  2.375,\n",
       "  24,\n",
       "  21.625,\n",
       "  13.625,\n",
       "  24,\n",
       "  14,\n",
       "  24,\n",
       "  1.75,\n",
       "  12.375,\n",
       "  1.75,\n",
       "  1.75,\n",
       "  24,\n",
       "  24,\n",
       "  12.375,\n",
       "  1.75,\n",
       "  14,\n",
       "  2.375,\n",
       "  22,\n",
       "  21.625,\n",
       "  24,\n",
       "  1.75,\n",
       "  24,\n",
       "  22,\n",
       "  1.75,\n",
       "  1.75,\n",
       "  3.625,\n",
       "  3.625,\n",
       "  13.625,\n",
       "  3.625,\n",
       "  1.75,\n",
       "  1.75,\n",
       "  1.75,\n",
       "  2.375,\n",
       "  13.625,\n",
       "  20.375,\n",
       "  12.375,\n",
       "  1.75,\n",
       "  1.75,\n",
       "  21.625,\n",
       "  20.375,\n",
       "  24,\n",
       "  2.375,\n",
       "  12.375,\n",
       "  24,\n",
       "  12.375,\n",
       "  13.625,\n",
       "  1.75,\n",
       "  24,\n",
       "  24,\n",
       "  12.375,\n",
       "  1.75,\n",
       "  12.375,\n",
       "  24,\n",
       "  13.625,\n",
       "  1.75,\n",
       "  21.625,\n",
       "  2.375,\n",
       "  14,\n",
       "  20.375,\n",
       "  21.625,\n",
       "  3.625,\n",
       "  24,\n",
       "  3.625,\n",
       "  22,\n",
       "  14,\n",
       "  24,\n",
       "  1.75,\n",
       "  3.625,\n",
       "  22,\n",
       "  21.625,\n",
       "  2.375,\n",
       "  22,\n",
       "  14,\n",
       "  2.375,\n",
       "  24,\n",
       "  22,\n",
       "  1.75,\n",
       "  2.375,\n",
       "  1.75,\n",
       "  2.375,\n",
       "  14,\n",
       "  24,\n",
       "  2.375,\n",
       "  21.625,\n",
       "  24,\n",
       "  14,\n",
       "  12.375,\n",
       "  24,\n",
       "  2.375,\n",
       "  2.375,\n",
       "  24,\n",
       "  14,\n",
       "  14,\n",
       "  1.75,\n",
       "  24,\n",
       "  20.375,\n",
       "  14,\n",
       "  1.75,\n",
       "  24,\n",
       "  22,\n",
       "  14,\n",
       "  24,\n",
       "  1.75,\n",
       "  24,\n",
       "  20.375,\n",
       "  3.625,\n",
       "  24,\n",
       "  22,\n",
       "  21.625,\n",
       "  12.375,\n",
       "  20.375,\n",
       "  21.625,\n",
       "  1.75,\n",
       "  3.625,\n",
       "  24,\n",
       "  14,\n",
       "  20.375,\n",
       "  22,\n",
       "  24,\n",
       "  2.375,\n",
       "  1.75,\n",
       "  13.625,\n",
       "  22,\n",
       "  1.75,\n",
       "  20.375,\n",
       "  1.75,\n",
       "  22,\n",
       "  21.625,\n",
       "  3.625,\n",
       "  22,\n",
       "  1.75,\n",
       "  22,\n",
       "  13.625,\n",
       "  14,\n",
       "  20.375,\n",
       "  22,\n",
       "  14,\n",
       "  1.75,\n",
       "  24,\n",
       "  2.375,\n",
       "  14,\n",
       "  22,\n",
       "  20.375,\n",
       "  22,\n",
       "  14,\n",
       "  24,\n",
       "  1.75,\n",
       "  1.75,\n",
       "  24,\n",
       "  21.625,\n",
       "  20.375,\n",
       "  2.375,\n",
       "  12.375,\n",
       "  21.625,\n",
       "  2.375,\n",
       "  1.75,\n",
       "  2.375,\n",
       "  13.625,\n",
       "  20.375,\n",
       "  24,\n",
       "  22,\n",
       "  3.625,\n",
       "  21.625,\n",
       "  20.375,\n",
       "  2.375,\n",
       "  1.75,\n",
       "  20.375,\n",
       "  24,\n",
       "  14,\n",
       "  13.625,\n",
       "  3.625,\n",
       "  24,\n",
       "  22,\n",
       "  22,\n",
       "  24,\n",
       "  24,\n",
       "  1.75,\n",
       "  2.375,\n",
       "  3.625,\n",
       "  1.75,\n",
       "  13.625,\n",
       "  1.75,\n",
       "  14,\n",
       "  2.375])"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Karger(G)"
   ]
  },
  {
   "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.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}