Hungarian.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 132,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# example cost matrix from https://en.wikipedia.org/wiki/Hungarian_algorithm\n",
    "cost_matrix = pd.DataFrame([[3,3,3],[3,2,3],[3,3,2]], columns=['Clean bathroom', 'Sweep floors', 'Wash windows'], index=['Glen', 'Steve', 'Alan'])\n",
    "#cost_matrix.index.name = 'Employee'\n",
    "#cost_matrix.columns.name = 'Task'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 133,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "       Clean bathroom  Sweep floors  Wash windows\n",
       "Glen                3             3             3\n",
       "Steve               3             2             3\n",
       "Alan                3             3             2"
      ]
     },
     "execution_count": 133,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cost_matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 137,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from munkres import Munkres\n",
    "\n",
    "def tall(matrix):\n",
    "    rows, cols = matrix.shape\n",
    "    return rows > cols\n",
    "\n",
    "def assign_matrix(cost_matrix):\n",
    "    m = Munkres()\n",
    "    if tall(cost_matrix):\n",
    "        transposed_assignments = m.compute(np.copy(cost_matrix.T))\n",
    "        return [(row, col) for col, row in transposed_assignments]\n",
    "    else:\n",
    "        return m.compute(np.copy(cost_matrix))\n",
    "\n",
    "def assign(cost_matrix_df):\n",
    "    matrix = cost_matrix_df.values\n",
    "    assignments = assign_matrix(matrix)\n",
    "    results = []\n",
    "    for i, (row, col) in enumerate(assignments):\n",
    "        cost = matrix[row][col]\n",
    "        task = cost_matrix_df.columns.values[col]\n",
    "        assignee = cost_matrix_df.index.values[row]\n",
    "        results.append([assignee, task, cost])\n",
    "    task_name = cost_matrix.columns.name or 'task'\n",
    "    assignee_name = cost_matrix_df.index.name or 'assignee'\n",
    "    return pd.DataFrame(results, columns=[assignee_name, task_name, 'cost']).set_index(assignee_name)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 138,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def report(cost_matrix):\n",
    "    assignments = assign(cost_matrix)\n",
    "    print assignments\n",
    "    print 'Total: $%d' % assignments.cost.sum()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 139,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "                    task  cost\n",
      "assignee                      \n",
      "Glen      Clean bathroom     3\n",
      "Steve       Sweep floors     2\n",
      "Alan        Wash windows     2\n",
      "Total: $7\n"
     ]
    }
   ],
   "source": [
    "report(cost_matrix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 142,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "wide_cost_matrix = pd.DataFrame([[3,3,3,2],[3,2,3,5],[3,3,2,6]], columns=['Clean bathroom', 'Sweep floors', 'Wash windows', 'Clean Fridge'], index=['Glen', 'Steve', 'Alan'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 143,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "       Clean bathroom  Sweep floors  Wash windows  Clean Fridge\n",
       "Glen                3             3             3             2\n",
       "Steve               3             2             3             5\n",
       "Alan                3             3             2             6"
      ]
     },
     "execution_count": 143,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "wide_cost_matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 144,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "                  task  cost\n",
      "assignee                    \n",
      "Glen      Clean Fridge     2\n",
      "Steve     Sweep floors     2\n",
      "Alan      Wash windows     2\n",
      "Total: $6\n"
     ]
    }
   ],
   "source": [
    "report(wide_cost_matrix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 145,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "tall_cost_matrix = pd.DataFrame([[3,3,3],[3,2,3],[3,3,2],[1,1,1]], columns=['Clean bathroom', 'Sweep floors', 'Wash windows'], index=['Glen', 'Steve', 'Alan', 'Intern'])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 146,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "        Clean bathroom  Sweep floors  Wash windows\n",
       "Glen                 3             3             3\n",
       "Steve                3             2             3\n",
       "Alan                 3             3             2\n",
       "Intern               1             1             1"
      ]
     },
     "execution_count": 146,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tall_cost_matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 147,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "                    task  cost\n",
      "assignee                      \n",
      "Intern    Clean bathroom     1\n",
      "Steve       Sweep floors     2\n",
      "Alan        Wash windows     2\n",
      "Total: $5\n"
     ]
    }
   ],
   "source": [
    "report(tall_cost_matrix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}