file requires Jupiter notebook to be open
{
“cells”: [
{
“cell_type”: “markdown”,
“metadata”: {},
“source”: [
“\n”,
“\n”
]
},
{
“cell_type”: “markdown”,
“metadata”: {},
“source”: []
},
{
“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- A graph will be a Python list of pairs.\n”,
“\n”,
“5- The data structure can represent a directed graph or of an undirected graph. The algorithm makes \n”,
” the distinction.\n”,
“\n”,
” – The PATH algorithm is for directed graphs, hence it interprets the data structure where the\n”,
” edges are directed and go from the first element of the pair to the second. \n”,
” \n”,
” – The k-VC algorithm is for undirected graphs, hence it interprets the data structure\n”,
” where the edges are not directed.\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”,
“]\n”,
“\n”,
“# those are cases were the graph is considered a directed graph. \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
” 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_2’, ‘var_4’]\n”,
“2:\t[‘var_0’, ‘var_2’, ‘var_1’]\n”,
“3:\t[‘var_0’, ‘var_4’, ‘var_1’]\n”,
“4:\t[‘var_2’, ‘var_4’, ‘var_1’]\n”,
“5:\t[‘var_0’, ‘var_2’, ‘var_3’]\n”,
“6:\t[‘var_0’, ‘var_4’, ‘var_3’]\n”,
“7:\t[‘var_2’, ‘var_4’, ‘var_3’]\n”,
“8:\t[‘var_0’, ‘var_1’, ‘var_3’]\n”,
“9:\t[‘var_2’, ‘var_1’, ‘var_3’]\n”,
“10:\t[‘var_4’, ‘var_1’, ‘var_3’]\n”,
“11:\t[‘var_0’, ‘var_2’, ‘var_5’]\n”,
“12:\t[‘var_0’, ‘var_4’, ‘var_5’]\n”,
“13:\t[‘var_2’, ‘var_4’, ‘var_5’]\n”,
“14:\t[‘var_0’, ‘var_1’, ‘var_5’]\n”,
“15:\t[‘var_2’, ‘var_1’, ‘var_5’]\n”,
“16:\t[‘var_4’, ‘var_1’, ‘var_5’]\n”,
“17:\t[‘var_0’, ‘var_3’, ‘var_5’]\n”,
“18:\t[‘var_2’, ‘var_3’, ‘var_5’]\n”,
“19:\t[‘var_4’, ‘var_3’, ‘var_5’]\n”,
“20:\t[‘var_1’, ‘var_3’, ‘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
” 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.7.6”
}
},
“nbformat”: 4,
“nbformat_minor”: 2
}