python project

{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "***\n", "\n", "## Problem Set 8: Final Project\n", "\n", ">CSC427, semester 202 (jan-may 2020)\n", "<br>\n", "burton rosenberg\n", "<br>\n", "univ of miami\n", "<br>\n", "(c) 2020 all rights reserved\n", "\n", "<br>\n", "_*Created: 20 April 2020*_\n", "<br>\n", "_*Last update: 2 May 2020*_\n", "\n", "***\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Student's Name: (your name here)\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Statement of the project\n", "\n", "In this final project, the study of P and NP will be practiced.\n", "\n", "Your tasks are to,\n", "\n", "1- Write a polynomial time predicate VerifyPath.find_if_path, that given a graph and two vertices,\n", " returns true if the two vertices are vertices in the graph, and there is a path in the graph connecting\n", " the two vertices. Else it returns False.\n", "\n", "2- Write a polynomial time predicate VerifyKCover.verify, that given a graph and a list of vertices, \n", " returns true if the list of vertices is a vertex-covering of the graph. That is, ever edge of the\n", " graph has at least one end vertice in the given cover. Else it returns False.\n", " \n", "3- Write an exponential time search algoirthm, SolveKCover.search_brute_force, that given a graph and\n", " an integer k, returns a vertex-covering with exactly k vertices of the graph, or else returns the\n", " empty list. The algorithm will work by enumerating all subsets of k vertices from the set of all\n", " the graph's vertices, and will apply the verifying on each such candidate solution.\n", " \n", "4- Write a polynomial time reduction Reduction.reduce from 3-SAT to Vertex Cover, that is, which given\n", " an instance of 3-SAT produces a graph and a number k, such that 3-SAT is satisfiable if and only\n", " if the graph has a k covering.\n", " \n", "5- Write a polynomail time function Reduction.pullback, which given a 3-SAT to Vertex Cover reduction,\n", " and a k cover, produces a satisfying assignment for the 3-SAT instance, the subject of the reduction.\n", " \n", "6- *Complete method Reduction.solve.* \n", " Write a 3-SAT solver that solves a 3-SAT instance by reducing it to a Vertex Cover\n", " instance, solves the instance by brute force, and pulls back the vertex cover solution to a satisfying \n", " assignment for the 3-SAT instance. \n", " \n", "\n", " \n", " " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Description of data structure\n", "\n", "__Description of a graph__\n", "\n", "1- A graph is made up of vertices and edges. Each edge is a pair of vertices\n", "\n", "2- A vertex will be represented as a string, to be thought of as the name of the vertex.\n", "\n", "3- An edge will be represented as a Python pair. The two members of the pair will be the vertex name.\n", "\n", "4- This is a directed graph. The graph edge goes from the first element of the pair to the second.\n", "\n", "5- A graph will be a Python list of pairs.\n" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "# Example of a graph. The textbook graph of Figure 0.16 is represented -\n", "\n", "figure_0_16 = [\n", " ('1','2'),\n", " ('1','5'),\n", " ('2','1'),\n", " ('2','4'),\n", " ('5','4'),\n", " ('5','6'),\n", " ('6','1'),\n", " ('6','3')\n", "]\n", "\n", "# here are some examples where path would be true, for this graph\n", "\n", "figure_0_16_true = [\n", " ('6','3'),\n", " ('6','4'),\n", " ('2','5'),\n", " ('1','3')\n", "]\n", "\n", "# and here are some where path would be false\n", "\n", "figure_0_16_false =[\n", " ('3','6'),\n", " ('4','1')\n", "]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "__Description of a 3-SAT__\n", "\n", "1- A 3-SAT is made up of clauses, signed variables, and variables.\n", "\n", "2- A variable will be represented as a string, to be thought of as the name of the variable.\n", "\n", "3- A signed variable is a Python pair. The first element is a variable name and the second\n", " element is 0 or 1. \n", " * If 0, the sign of the variable is positive, the variable is appearing\n", " without negation; \n", " * If 1, the sign of the variable is negative, the variable is appearing\n", " negated.\n", "\n", "4- A clause is Python list of 3 signed variables.\n", "\n", "5- An instance of 3-SAT is a Python list of clauses.\n" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "# The 3-SAT in Figure 7.33 is represented - \n", "\n", "figure_7_45 = [\n", " [('x1',0),('x1',0),('x2',0)],\n", " [('x1',1),('x2',1),('x2',1)],\n", " [('x1',1),('x2',0),('x2',0)]\n", "]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "__Description of an instance of k-VC__\n", "\n", "An instance of a k vertex cover problem is a Python pair.\n", "\n", " * The first element of the pair is the integer k\n", " * The second element of the pair is a graph\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "***\n", "\n", "## Student workspace\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### P-Time Path algorithm" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "\n", "class VerifyPath:\n", " \n", " @staticmethod\n", " def find_if_path(graph,source,dest):\n", "\n", " pass\n", "\n", " # data structures:\n", " # visited, a set of visited vertices \n", " # edge_dict, a dictionary from a vertex to a list of neighbors\n", " # q, a list of unvisited vertices, known to be reachable \n", " # from source, to be visited\n", " \n", " visited = set([source])\n", " edge_dict = {source:[]} # should be a list of neighbors of source\n", " q = edge_dict[source]\n", "\n", " pass\n", " \n", " while len(q)>0:\n", " \n", " pass\n", "\n", " pass\n", " \n", " return dest in visited\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### P-Time Vertex Cover verifier" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "class VerifyKCover:\n", " \n", " def __init__(self,graph,verbose=set()):\n", " self.graph = graph\n", " self.verbose = verbose\n", "\n", " def verify(self,cover):\n", " \"\"\"\n", " verify that the vertex list given is a k-cover\n", " \"\"\"\n", " \n", " pass\n", " \n", " return True\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exp-Time Vertex Cover solver" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": [ "\n", "class SolveKCover:\n", " \n", " def __init__(self,graph,verbose=set()):\n", " self.graph = graph\n", " self.verbose = verbose\n", " self.verifier = VerifyKCover(graph,verbose)\n", " \n", " self.iterate_idx = 0\n", " self.k = 0\n", " \n", " # make a list of vertices of the graph\n", " v = set()\n", " for edge in graph:\n", " v.add(edge[0])\n", " v.add(edge[1])\n", " self.vertices = list(v)\n", " \n", " def get_vertices(self):\n", " return self.vertices\n", " \n", " def get_verifier(self):\n", " return self.verifier\n", " \n", " def get_ith_bit(self,i,n):\n", " return (n//2**i)%2\n", "\n", " def count_ones(self,n):\n", " count = 0\n", " while n>0:\n", " count += n%2\n", " n = n//2\n", " return count\n", "\n", " def new_iteration(self,k):\n", " self.k = k\n", " self.iterate_idx = 0\n", " \n", " def next_iterate(self):\n", " idx = self.iterate_idx + 1\n", " while (self.count_ones(idx)!=self.k):\n", " idx += 1\n", " self.iterate_idx = idx\n", " return idx\n", "\n", " def select_vertices_by_index(self,idx):\n", " l = len(self.vertices)\n", " i = 0\n", " selected = []\n", " while idx>0 and i<l:\n", " if idx%2 == 1:\n", " selected.append(self.vertices[i]) \n", " idx = idx//2\n", " i +=1\n", " return selected\n", "\n", " def search_brute_force(self,k):\n", "\n", " n_vertices = len(self.vertices)\n", " if k>n_vertices:\n", " return []\n", " if k<=0:\n", " return []\n", "\n", " assert(k>0)\n", "\n", " pass\n", "\n", " return []\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Some examples of how to use the enumerating functions" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1\n", "2\n", "4\n", "8\n", "16\n", "32\n", "64\n", "128\n", "256\n", "512\n", "1024\n", "2048\n", "4096\n", "number of s/sets = 20\n", "1:\t['var_0', 'var_3', 'var_2']\n", "2:\t['var_0', 'var_3', 'var_4']\n", "3:\t['var_0', 'var_2', 'var_4']\n", "4:\t['var_3', 'var_2', 'var_4']\n", "5:\t['var_0', 'var_3', 'var_1']\n", "6:\t['var_0', 'var_2', 'var_1']\n", "7:\t['var_3', 'var_2', 'var_1']\n", "8:\t['var_0', 'var_4', 'var_1']\n", "9:\t['var_3', 'var_4', 'var_1']\n", "10:\t['var_2', 'var_4', 'var_1']\n", "11:\t['var_0', 'var_3', 'var_5']\n", "12:\t['var_0', 'var_2', 'var_5']\n", "13:\t['var_3', 'var_2', 'var_5']\n", "14:\t['var_0', 'var_4', 'var_5']\n", "15:\t['var_3', 'var_4', 'var_5']\n", "16:\t['var_2', 'var_4', 'var_5']\n", "17:\t['var_0', 'var_1', 'var_5']\n", "18:\t['var_3', 'var_1', 'var_5']\n", "19:\t['var_2', 'var_1', 'var_5']\n", "20:\t['var_4', 'var_1', 'var_5']\n" ] } ], "source": [ "# using the functions implemented in SOlveKCover to\n", "# enumerate the integers with binary representation \n", "# containing exact one 1 bit. e.g. 1, 2, 4, ...\n", " \n", "def iterator_pure_powers(n_max):\n", " skc = SolveKCover([('a','a')])\n", " skc.new_iteration(1)\n", " idx = skc.next_iterate()\n", " while idx<n_max:\n", " print(idx)\n", " idx = skc.next_iterate()\n", "\n", "iterator_pure_powers(5000)\n", "\n", "# using the functions implemented in SOlveKCover to\n", "# enumerate all subsets of 3 items from a set of n items\n", " \n", "def enumerate_3_sets(n):\n", "\n", " graph = []\n", " for i in range(n):\n", " var = 'var_{}'.format(i)\n", " graph.append((var,var))\n", "\n", " skc = SolveKCover(graph)\n", " skc.new_iteration(3)\n", " idx = skc.next_iterate()\n", " idx_max = 2**len(graph)\n", " print('number of s/sets = {}'.format(int(n*(n-1)*(n-2)/6)))\n", " i = 1\n", " while idx<idx_max:\n", " print('{}:\\t{}'.format(i,skc.select_vertices_by_index(idx)))\n", " idx = skc.next_iterate()\n", " i += 1\n", "\n", " \n", "enumerate_3_sets(6)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Reducing 3-SAT to k-VC" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [], "source": [ "import re\n", "\n", "class Reduction:\n", "\n", " def __init_(self,verbose=set()):\n", " self.verbose = verbose\n", "\n", " @staticmethod\n", " def reduce(instance_3sat):\n", " \"\"\"\n", " The widget: create C_3 for every clause, and K_2 for each variable.\n", " Assocate each of the vertices in the C_3 with a variable in the clause, and the\n", " pair of vertices in the K_2 with the postive and negated forms of the variable.\n", " \n", " Also create an edge from the vertex in C_3 for variable v (resp not v) to the\n", " vertices in K_2 for variable v (resp not v)\n", " \n", " Any cover must be at least n+2m, for n variables and m clauses. The cover sought has k = n+2m.\n", " \"\"\"\n", " \n", " # collect up the nodes\n", " all_var = set()\n", " for clause in instance_3sat:\n", " for var in clause:\n", " all_var.add(var[0])\n", " \n", " instance_vc = []\n", " \n", " pass\n", " \n", " return (0,instance_vc)\n", " \n", " @staticmethod\n", " def pullback(vertex_cover):\n", " assignment = {}\n", "\n", " pass\n", " \n", " return assignment\n", " \n", " @staticmethod\n", " def solve(instance_3sat):\n", "\n", " pass\n", " \n", " return []\n", " \n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "***\n", "\n", "## A basic test" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "*** begin verify_path_tests ***\n", "\tBAD: (6,3) gives True\n", "*** fails verify_path_tests ***\n", "\n", "\n", "*** begin verify_path_tests ***\n", "\tOK: (a,d) gives False\n", "\tOK: (e,d) gives False\n", "\tBAD: (c,b) gives True\n", "*** fails verify_path_tests ***\n", "\n", "\n", "*** begin verify_path_tests ***\n", "\tOK: (e,e) gives True\n", "\tBAD: (a,c1) gives True\n", "*** fails verify_path_tests ***\n", "\n", "\n", "*** begin verify k cover tests ***\n", "\tOK: ['b', 'd', 'f'] gives True\n", "\tOK: ['g1', 'g2', 'e', 'a', 'c'] gives True\n", "\tBAD: ['c', 'e', 'g2'] gives False\n", "*** fails verify k cover tests ***\n", "\n", "\n", "*** begin SolveKCover tests ***\n", "\tOK: 1\n", "\tOK: 2\n", "\tBAD: 3\n", "*** fails SolveKCover tests ***\n", "\n" ] }, { "data": { "text/plain": [ "False" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def verify_path_tests(graph,tests):\n", " print(\"\\n*** begin verify_path_tests ***\")\n", " for test in tests:\n", " if VerifyPath.find_if_path(graph, test[1], test[2]) != test[0]:\n", " print('\\tBAD: ({},{}) gives {}'.format(test[1],test[2],test[0]))\n", " print(\"*** fails verify_path_tests ***\\n\")\n", " return False\n", " print('\\tOK: ({},{}) gives {}'.format(test[1],test[2],test[0]))\n", " print(\"*** passes verify_path_tests ***\\n\")\n", " return True\n", "\n", "\n", "def verity_k_cover_tests(graph,tests):\n", " print(\"\\n*** begin verify k cover tests ***\")\n", " v = VerifyKCover(graph)\n", " for test in tests:\n", " if v.verify(test[1]) != test[0]:\n", " print('\\tBAD: {} gives {}'.format(test[1],test[0]))\n", " print(\"*** fails verify k cover tests ***\\n\")\n", " return False\n", " print('\\tOK: {} gives {}'.format(test[1],test[0]))\n", " print(\"*** passes verify k cover tests ***\\n\")\n", " return True\n", "\n", "\n", "def solve_k_cover_example(graph,ks):\n", " print(\"\\n*** begin SolveKCover tests ***\")\n", " s = SolveKCover(graph)\n", " for k in ks:\n", " solution = s.search_brute_force(k[1])\n", " if k[0]:\n", " if (len(solution)>0) and not s.get_verifier().verify(solution):\n", " print('\\tBAD: {}'.format(k[1]))\n", " print(\"*** fails SolveKCover tests ***\\n\")\n", " return False\n", " if len(solution)==0:\n", " print('\\tBAD: {}'.format(k[1]))\n", " print(\"*** fails SolveKCover tests ***\\n\")\n", " return False \n", " if not k[0] and (len(solution)>0):\n", " print('\\tBAD: {}'.format(k[1]))\n", " print(\"*** fails SolveKCover tests ***\\n\")\n", " return False\n", " print('\\tOK: {}'.format(k[1]))\n", " print(\"*** passes SolveKCover tests ***\\n\")\n", " return True\n", "\n", "\n", "# Example of a graph. The textbook graph of Figure 0.16 is represented -\n", "\n", "figure_0_16 = [\n", " ('1','2'),\n", " ('1','5'),\n", " ('2','1'),\n", " ('2','4'),\n", " ('5','4'),\n", " ('5','6'),\n", " ('6','1'),\n", " ('6','3')\n", "]\n", "\n", "# here are some examples where path would be true, for this graph\n", "\n", "figure_0_16_answers = [\n", " (True,'6','3'),\n", " (True,'6','4'),\n", " (True,'2','5'),\n", " (True,'1','3'),\n", " (False,'3','6'),\n", " (False,'4','1')\n", "]\n", "\n", "gr1 = [('a','b'),('b','c'),('c','a'),('d','e')]\n", "gr1_answers = [(False,'a','d'), (False,'e','d'),\n", " (True,'c','b'),(True,'a','c')]\n", "\n", "gr2 = [('a','b1'),('b1','c1'),('a','b2'),('b2','c2'),('b3','a'),('c3','b3'),('e','e')]\n", "gr2_answers = [(True,'e','e'),(True,'a','c1'),(True,'c3','c1'),(False,'c3','e'),(False,'c2','a')]\n", "\n", "gr3 = [('a','b'),('b','c'),('c','d'),('d','a'),('d','e'),('e','f'),('f','g1'),('f','g2')]\n", "gr3_answers = [[True,['b','d','f']],[True,['g1','g2','e','a','c']],[False,['c','e','g2']]]\n", "gr3_k_solvable = [[False,1],[False,2],[True,3],[True,4],[True,5]]\n", "\n", "verify_path_tests(figure_0_16,figure_0_16_answers)\n", "verify_path_tests(gr1,gr1_answers)\n", "verify_path_tests(gr2,gr2_answers)\n", "verity_k_cover_tests(gr3,gr3_answers)\n", "solve_k_cover_example(gr3,gr3_k_solvable)\n" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[]\n", "[]\n", "[]\n", "[]\n" ] } ], "source": [ "figure_7_45 = [\n", " [('x1',0),('x1',0),('x2',0)],\n", " [('x1',1),('x2',1),('x2',1)],\n", " [('x1',1),('x2',0),('x2',0)]\n", "]\n", "Reduction.reduce(figure_7_45)\n", "print(Reduction.solve(figure_7_45))\n", "\n", "sat_1 = [\n", " [('a',0),('b',0),('c',0)]\n", "]\n", "print(Reduction.solve(sat_1))\n", "\n", "sat_2= [\n", " [('a',1),('a',1),('a',1)]\n", "]\n", "print(Reduction.solve(sat_2))\n", "\n", "sat_3 = [\n", " [('a',0),('b',0),('c',0)],\n", " [('a',1),('b',1),('c',1)]\n", "]\n", "print(Reduction.solve(sat_3))" ] }, { "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.6.4" } }, "nbformat": 4, "nbformat_minor": 2 }