day 26 - karger's mincut.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from random import choice\n",
    "from itertools import combinations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def contract(graph, u, v):\n",
    "    aux, w = [], f'{u},{v}'\n",
    "    for x, y in graph:\n",
    "        x = w if x in [u, v] else x\n",
    "        y = w if y in [u, v] else y\n",
    "        if x < y:\n",
    "            aux.append((x, y))\n",
    "        elif x > y:\n",
    "            aux.append((y, x))\n",
    "    return aux"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def mincut(graph, n):\n",
    "    components, cost = ['', ''], float('inf')\n",
    "    \n",
    "    # n^2 attempts\n",
    "    for i in range(n * n):\n",
    "        aux = graph\n",
    "        \n",
    "        # remove edges one by one\n",
    "        while len(set(aux)) > 1:\n",
    "            aux = contract(aux, *choice(aux))\n",
    "            \n",
    "            # min cut so far\n",
    "            if len(aux) < cost:\n",
    "                components, cost = aux[0], len(aux)\n",
    "                \n",
    "    return components, cost"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## generate graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# fully connected\n",
    "nodes_a = [f'A{i}' for i in range(20)]\n",
    "graph_a = [(u, v) for u, v in combinations(nodes_a, 2)]\n",
    "\n",
    "# fully connected\n",
    "nodes_b = [f'B{i}' for i in range(20)]\n",
    "graph_b = [(u, v) for u, v in combinations(nodes_b, 2)]\n",
    "\n",
    "# interconnections\n",
    "graph_c = [(choice(nodes_a), choice(nodes_b)) for i in range(10)]\n",
    "\n",
    "graph = graph_a + graph_b + graph_c"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## run"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "best cut: 10\n",
      "component #1: A0,A3,A4,A7,A9,A16,A19,A2,A1,A5,A12,A18,A17,A8,A15,A13,A6,A10,A11,A14\n",
      "component #2: B0,B1,B16,B12,B15,B4,B17,B19,B9,B3,B5,B14,B18,B2,B11,B8,B10,B7,B6,B13\n"
     ]
    }
   ],
   "source": [
    "components, cost = mincut(graph, 40)\n",
    "print('best cut:', cost)\n",
    "print('component #1:', components[0])\n",
    "print('component #2:', components[1])"
   ]
  },
  {
   "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.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}