coding-hometask-2-1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "# Задание по курсу «Дискретная оптимизация», МФТИ, весна 2017"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "## Задача 2-1. Применяем простейший локальный поиск.\n",
    "\n",
    "В этой задаче Вам предлагается попробовать стандартную технику локального поиска (local search) в применении к задаче о сбалансированном разбиении графа. Мы будем рассматривать безвесовый вариант задачи с параметром балансировки $\\alpha=\\frac{1}{2}$:\n",
    "\n",
    "**Даны:**\n",
    "* $G=(V,E)$ — граф без весов на рёбрах\n",
    "\n",
    "**Найти:**\n",
    "* Разбиение $V=V'\\sqcup V''$, такое, что $V'=\\lfloor |V|/2 \\rfloor$ и число рёбер между $V'$ и $V''$ минимально возможное.\n",
    "\n",
    "Сделайте следующее:\n",
    "* [Скачайте](http://mat.gsia.cmu.edu/COLOR/instances.html#XXMYC) файлы mycielX.col  (`for X in range(1,8)`).  (Если интересно, откуда такие графы берутся и чем интересны, см. конструкцию Зыкова—Мыцельского [здесь](https://docs.com/dainiak/3327).)\n",
    "* Для каждого из графов найдите локальным поиском локально минимальное (по количеству рёбер между частями) разбиение вершин графа на две части, мощности которых отличаются не более чем на единицу. \n",
    "* Ваша функция `basic_local_search` должна принимать на вход граф в формате, предоставляемом функцией `read_col_file`, и возвращать найденное локально минимальное разбиение просто как множество либо список вершин, лежащих в одной любой из двух компонент разбиения."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def read_col_file(filename):\n",
    "    with open(filename, 'r') as file:\n",
    "        vertices, edges = set(), set()\n",
    "        for line in file:\n",
    "            line = line.strip()\n",
    "            if line.startswith('p'):\n",
    "                vertices = set(range(1, int(line.split()[-2]) + 1))\n",
    "            elif line.startswith('e'):\n",
    "                edges.add(tuple(map(int, line.split()[-2:])))\n",
    "        return (vertices, edges)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "def random_partition(graph):\n",
    "    return set(random.sample(graph[0], len(graph[0]) // 2))\n",
    "\n",
    "def partition_weight(graph, partition):\n",
    "    weight = 0\n",
    "    for u, v in graph[1]:\n",
    "        if (u in partition) != (v in partition):\n",
    "            weight += 1\n",
    "    return weight\n",
    "\n",
    "def local_candidates(graph, partition):\n",
    "    complement = graph[0] - partition\n",
    "    result = []\n",
    "    for u in partition:\n",
    "        for v in complement:\n",
    "            new_partition = set(partition)\n",
    "            new_partition.remove(u)\n",
    "            new_partition.add(v)\n",
    "            result.append(new_partition)\n",
    "    return result\n",
    "\n",
    "def optimal_candidate(graph, partition):\n",
    "    min_weight = partition_weight(graph, partition)\n",
    "    best_candidate = partition\n",
    "    candidates = local_candidates(graph, partition)\n",
    "    flag_new = False\n",
    "    for i, c in enumerate(candidates):\n",
    "        new_weight = partition_weight(graph, c)\n",
    "        if new_weight < min_weight:\n",
    "            min_weight = new_weight\n",
    "            best_candidate = c\n",
    "            flag_new = True\n",
    "    return (flag_new, best_candidate, min_weight)\n",
    "    \n",
    "def basic_local_search(graph):\n",
    "    flag_change, partition = True, random_partition(graph)\n",
    "    while flag_change:\n",
    "        flag_change, partition, weight = optimal_candidate(graph, partition)\n",
    "    return partition, weight"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "myciel3.col: weight = 8, partition =  {1, 4, 5, 9, 10}\n",
      "myciel4.col: weight = 27, partition =  {1, 2, 3, 6, 7, 8, 9, 12, 13, 16, 22}\n",
      "myciel5.col: weight = 92, partition =  {2, 3, 4, 11, 12, 14, 17, 21, 23, 25, 29, 30, 33, 35, 36, 37, 39, 40, 41, 42, 43, 44, 47}\n",
      "myciel6.col: weight = 300, partition =  {2, 6, 7, 8, 10, 11, 12, 13, 16, 17, 18, 19, 21, 22, 24, 26, 29, 31, 34, 45, 46, 49, 51, 53, 54, 55, 56, 58, 60, 62, 64, 65, 66, 67, 68, 69, 72, 73, 74, 76, 78, 79, 81, 84, 92, 93, 95}\n",
      "myciel7.col: weight = 914, partition =  {1, 3, 4, 6, 11, 13, 15, 22, 23, 24, 29, 34, 36, 38, 45, 47, 53, 54, 55, 56, 57, 60, 62, 65, 67, 70, 76, 77, 78, 79, 80, 83, 85, 88, 90, 91, 94, 95, 96, 101, 108, 110, 113, 117, 119, 123, 124, 125, 126, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 148, 149, 150, 151, 152, 155, 157, 159, 160, 161, 162, 163, 166, 167, 169, 170, 171, 172, 173, 174, 175, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 191}\n"
     ]
    }
   ],
   "source": [
    "for X in range (3, 8):\n",
    "    graph = read_col_file('coding-hometask-2-1-files/myciel{:d}.col'.format(X))\n",
    "    result = basic_local_search(graph)\n",
    "    print(\"myciel{:d}.col: weight = {:d}, partition = \".format(X, result[1]), result[0])"
   ]
  }
 ],
 "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}