binary_relation.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import itertools as it"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Read data from file"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "with open (\"data.txt\", 'r') as data: #read data \n",
    "    dataset = [[int(x) for x in line.split()] for line in data]  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of R: 10\n"
     ]
    }
   ],
   "source": [
    "make_R = lambda lst, sz: [lst[i:i+sz] for i in range(0, len(lst), sz)]\n",
    "R = make_R(dataset, 15)\n",
    "print(\"Number of R: {}\".format(len(R)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### K-optimization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "def check_x(S):\n",
    "    max_k = np.array([])\n",
    "    opt_k = np.array([])\n",
    "    for i, x in zip(range(len(S)),S):\n",
    "        if np.any(S-x > 0): #формуємо множину k-макс. елементів\n",
    "            continue\n",
    "        max_k = np.append(max_k, i+1)\n",
    "        if np.sum(x) == 15: #формуємо множину k-опт. елементів\n",
    "            opt_k = np.append(opt_k, i+1)\n",
    "        \n",
    "    return max_k, opt_k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "def k_optimization(Rn):\n",
    "    I = (Rn == Rn.T)*Rn #формуємо симетричну частину\n",
    "    P = Rn-I #формуємо асиметричну частину\n",
    "    N = (Rn == Rn.T)-I #формуємо відношення непорівнюваності\n",
    "    \n",
    "    for i in range(1,5):\n",
    "        if i==1:\n",
    "            S1=I+P+N\n",
    "            max_1, opt_1 = check_x(S1)\n",
    "        elif i==2:\n",
    "            S2=P+N\n",
    "            max_2, opt_2 = check_x(S2)\n",
    "        elif i==3:\n",
    "            S3=P+I\n",
    "            max_3, opt_3 = check_x(S3)\n",
    "        elif i==4:\n",
    "            S4=P\n",
    "            max_4, opt_4 = check_x(S4)\n",
    "            \n",
    "    parameters = {\"1_max\": max_1,\n",
    "                 \"1_opt\": opt_1,\n",
    "                 \"2_max\": max_2,\n",
    "                 \"2_opt\": opt_2,\n",
    "                 \"3_max\": max_3,\n",
    "                 \"3_opt\": opt_3,\n",
    "                 \"4_max\": max_4,\n",
    "                 \"4_opt\": opt_4}\n",
    "    \n",
    "    return parameters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_information_k_opt(parameters, num_r):\n",
    "    print(\"____R{}____\".format(num_r))\n",
    "    print(\"1-max: {}\".format(parameters[\"1_max\"]))\n",
    "    print(\"1-opt: {}\".format(parameters[\"1_opt\"]))\n",
    "    print(\"2-max: {}\".format(parameters[\"2_max\"]))\n",
    "    print(\"2-opt: {}\".format(parameters[\"2_opt\"]))\n",
    "    print(\"3-max: {}\".format(parameters[\"3_max\"]))\n",
    "    print(\"3-opt: {}\".format(parameters[\"3_opt\"]))\n",
    "    print(\"4-max: {}\".format(parameters[\"4_max\"]))\n",
    "    print(\"4-opt: {}\".format(parameters[\"4_opt\"])) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Neumann-Morgenstern optimization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_pereriz(R):\n",
    "    verkhi_pererizy = []\n",
    "    R_t = R.T\n",
    "    for i in range(len(R)):\n",
    "        itemindex = (np.where(R_t[i]==1))[0]\n",
    "        verkhi_pererizy.append(itemindex)\n",
    "    return verkhi_pererizy "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "def make_S0(verkhi_pererizy):\n",
    "    S, S_delta = dict(), dict()\n",
    "  \n",
    "    buffer = []\n",
    "    for a, index_for_S0 in zip(verkhi_pererizy, range(len(verkhi_pererizy))):\n",
    "        if a.size == 0:\n",
    "            buffer.append(index_for_S0)\n",
    "\n",
    "    S[\"S0\"] = buffer\n",
    "    S_delta[\"S0\"] = S[\"S0\"]\n",
    "    return S, S_delta"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "def make_S(S, S_delta, R, verkhi_pererizy):\n",
    "    current_i = 0\n",
    "    l = 0\n",
    "    while(len(S[\"S\"+str(current_i)])!= len(R)):\n",
    "        buffer = []\n",
    "    \n",
    "        for a, index in zip(verkhi_pererizy, range(len(verkhi_pererizy))):\n",
    "            inclusion_check = np.in1d(a, S[\"S\"+str(current_i)]) # индекс предыдущего S. Если щас находим S1,то тут должна быть S0\n",
    "\n",
    "            if np.all(inclusion_check == True):\n",
    "                buffer.append(index)\n",
    "\n",
    "        if buffer == S[\"S\"+str(current_i)]: # если поточне = попередньому \n",
    "            buffer += list(set(range(len(verkhi_pererizy))) - set(S[\"S\"+str(current_i)]))\n",
    "\n",
    "        current_i += 1\n",
    "        l += 1\n",
    "        S[\"S\"+str(current_i)] = buffer\n",
    "        delta = list(set(S[\"S\"+str(current_i)]) - set(S[\"S\"+str(current_i-1)]))\n",
    "        S_delta[\"S\"+str(current_i)+\"_d\"] = delta \n",
    "    return S, S_delta, l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "def make_Q(S_delta, Q, verkhi_pererizy, L):\n",
    "    buffer = []\n",
    "    for l in range(1,L+1):\n",
    "        for delta in S_delta[\"S\"+str(l)+\"_d\"]:\n",
    "            inclusion_check = np.in1d(verkhi_pererizy[delta], Q[\"Q\"+str(l-1)])\n",
    "\n",
    "        if np.all(inclusion_check == False):\n",
    "            buffer.append(delta)\n",
    "\n",
    "        Q[\"Q\"+str(l)] = Q[\"Q\"+str(l-1)] + buffer\n",
    "    return Q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Neumann_Morgenstern_optimization(R):\n",
    "    verkhi_pererizy = get_pereriz(R) #знаходимо верхні перерізи для всіх альтернатив\n",
    "\n",
    "    S, S_delta, Q = dict(), dict(), dict()\n",
    "    S, S_delta = make_S0(verkhi_pererizy) #S0\n",
    "\n",
    "    S, S_delta, l = make_S(S, S_delta, R, verkhi_pererizy) #STEP 1\n",
    "\n",
    "    Q[\"Q0\"] = S[\"S0\"] #Q0\n",
    "    Q = make_Q(S_delta, Q, verkhi_pererizy, l) #STEP 2\n",
    "\n",
    "    С = Q[\"Q\"+str(l)]\n",
    "    C0 = [x+1 for x in С]\n",
    "    return C0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_information_NM(s, num_r):\n",
    "    print(\"____R{}____\".format(num_r))\n",
    "    print(\"Xнм: {}\".format(s))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Check acyclicity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [],
   "source": [
    "def acyclicity_graph(matrix): #перевірка відношення на аціклічність методом графу\n",
    "    size = len(matrix)\n",
    "    E = []\n",
    "    for i in range(size):\n",
    "        for j in range(size):\n",
    "            if matrix[i][j] == 1:\n",
    "                E.append((i+1,j+1))\n",
    "    graph = {}\n",
    "    for k, ir in it.groupby(sorted(E), key=lambda x: x[0]):\n",
    "        graph[k] = {e for _, e in ir}\n",
    "\n",
    "    # видаляємо всі вершини які не можуть бути частиною циклу (мають вхідні та вихідні ребра тільки)\n",
    "    sub_graph = {}\n",
    "    while True:\n",
    "        vertex_set = set(graph).intersection(it.chain.from_iterable(graph.values()))\n",
    "        sub_graph = {k: vertex_set & vs for k, vs in graph.items()\n",
    "                     if k in vertex_set and vertex_set & vs}\n",
    "\n",
    "        if sub_graph == graph:\n",
    "            break\n",
    "        else:\n",
    "            graph = sub_graph\n",
    "\n",
    "    if graph: #чи є підграф\n",
    "        return False\n",
    "    else:\n",
    "        return True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Сomputation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "____R1____\n",
      "1-max: [3.]\n",
      "1-opt: [3.]\n",
      "2-max: [3.]\n",
      "2-opt: []\n",
      "3-max: [3.]\n",
      "3-opt: [3.]\n",
      "4-max: [3.]\n",
      "4-opt: []\n",
      "____R2____\n",
      "Xнм: [8, 2, 3, 6]\n",
      "____R3____\n",
      "Xнм: [2, 5, 6]\n",
      "____R4____\n",
      "1-max: []\n",
      "1-opt: []\n",
      "2-max: []\n",
      "2-opt: []\n",
      "3-max: []\n",
      "3-opt: []\n",
      "4-max: []\n",
      "4-opt: []\n",
      "____R5____\n",
      "Xнм: [1, 4, 12, 14]\n",
      "____R6____\n",
      "1-max: [ 5.  6.  8. 11. 14.]\n",
      "1-opt: [ 5.  6.  8. 11. 14.]\n",
      "2-max: [ 5.  6. 11.]\n",
      "2-opt: [ 5.  6. 11.]\n",
      "3-max: []\n",
      "3-opt: []\n",
      "4-max: [ 5.  6. 11.]\n",
      "4-opt: []\n",
      "____R7____\n",
      "1-max: [ 4.  7.  8. 13. 14.]\n",
      "1-opt: [ 4.  7.  8. 13. 14.]\n",
      "2-max: [ 4.  8. 13.]\n",
      "2-opt: [ 4.  8. 13.]\n",
      "3-max: []\n",
      "3-opt: []\n",
      "4-max: [ 4.  8. 13.]\n",
      "4-opt: []\n",
      "____R8____\n",
      "1-max: []\n",
      "1-opt: []\n",
      "2-max: []\n",
      "2-opt: []\n",
      "3-max: []\n",
      "3-opt: []\n",
      "4-max: []\n",
      "4-opt: []\n",
      "____R9____\n",
      "1-max: [ 1.  4.  7.  9. 10. 11.]\n",
      "1-opt: [ 1.  4.  7.  9. 10. 11.]\n",
      "2-max: [ 1.  4.  7.  9. 10. 11.]\n",
      "2-opt: [ 1.  4.  7.  9. 10. 11.]\n",
      "3-max: [ 1.  3.  5.  7. 11.]\n",
      "3-opt: []\n",
      "4-max: [ 1.  7. 11.]\n",
      "4-opt: []\n",
      "____R10____\n",
      "Xнм: [1, 2, 11, 7]\n"
     ]
    }
   ],
   "source": [
    "for num_r, r_i in zip(range(len(R)),R):\n",
    "    Rn = np.array(r_i)\n",
    "    \n",
    "    if acyclicity_graph(Rn):\n",
    "        solution = Neumann_Morgenstern_optimization(Rn)\n",
    "        print_information_NM(list(set(solution)), num_r+1)\n",
    "    else:\n",
    "        parameters = k_optimization(Rn)\n",
    "        print_information_k_opt(parameters, num_r+1)\n"
   ]
  }
 ],
 "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.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}