Reductions. 3SAT problem and vertext cover. PLEASE HELP IMPLEMENT algorithm F and H.

Algorithm F: takes a file like in.txt and converts it into tmp.txt

Alogorithm H: parses solutiono soltuion from vertex cover and outputs satifying assignment

lab prompt is below. I am given a propostion as an in.txt and i have to use an alogorithm F to transform that into a tmp.txt file and construct a graph, i have provided graph.py as well. That tmp.txt which represents the graph as an edge list is passed into the vertexcover.py(which i have provided) which decides find the vertex cover for me and if there is a solution or no solution. Whether there is a solution or not, it gets passed to algorithm H which parses the solutiono solution and outputs the satisfying assignment.

the algorithms should be in their one and utilize the provided classes. WILL GIVE THUMBS UP and please dont use chatgpt and actually help

graph.py

vertexcover.py

example in.txt,tmp.txt, and out.txt

Part 1: The Vertex Cover Problem Given a graph G=(V,E), a vertex cover is a subset of vertices SV such that every edge in E is incident to at least one vertex in S. For example: Stated as a decision problem, the (Decision) Vertex Cover Problem asks for a vertex cover of cardinality k. In the above graph, {p0,r0,r1,p1,r2,r2} is a vertex cover, and proof that there exists a vertex cover of cardinality 6 . There also exist vertex covers of cardinality 7, but none of cardinality 5. The given vertex_cover,py implements a naive, brute force algorithm 2 to solve this problem. It accepts as a command line argument the name of a file containing a threshold and an edge list: >$ python3 vertex_cover.py tmp1,txt Vertex cover on 6 vertices: p00,r02,r11,p10,r20,r21 >$ echo $ ? 0 .... if the graph contains a vertex cover of the desired cardinality, vertex_cover.py prints the covering vertices and terminates with exit status 0 . If not, it terminates with exit status 1: >$ python3 vertex_cover.py tmp3.txt No vertex cover on 4 vertices. >$ echo \$? 1 1 Assuming that the complexity of the reduction itself was negligible compared to that of the algorithm for B. 2 It turns out that brute force, in this case, is also the best known approach. For example, the above proposition could be represented as: (pqr)&(prp)&(rrr) Your program must accept as a command line argument the name of a file containing a proposition as described above, then print to stdout a satisfying assignment (if one exists) according to the following format: - Each variable must appear as a literal: those assigned a value of T must appear unaltered; those assigned a value of F must appear negated. - The satisfying assignment must appear as a single comma-separated line of literals, sorted in alphabetical order by their variables. For example: >$./ compile.sh >$./ run, sh in 1. txt Satisfying assignment: p,q,r You may further assume that there will exist exactly zero or one satisfying assignments, and that no satisfying assignment will involve one literal that satisfies multiple clauses, such that output as described above will be unique. Your program will be tested using diff, so its printed output must match exactly. graph.py implementation of a greph datustructore. Class Graph: "n" A collection of vertices connected by edges n"n def_init_(self, vertices = []): * The backing adjacency dictionary: self, matrix = \{vertex: set() for vertex in vertices\} def eq (self, other): return type (other) == Graph and self, matrix == other. matrix def repr_(self): ["xs:xs"X(repr(v),repr(self[v])) for v in se1f]) def _len_(self): return len(self, matrix) dof _iter_(self): def _contains__(self, item): return item in self, matrix def getitem_(self, key): return self,matrix[key] def setitem (self, key, value): self. matrix[key] = value def add_vertex(graph, vertex): Add a vertex to a graph if it does not exist. :param graph: A graph to which to add a vertex :param vertex: The vertex to be added :return: The vertex's adjacency set return graph.matrix.5etdefault(vertex, set()) def add_edge(graph, vertex_u, vertex_v): Add an edge to a graph, adding vertices first if they do not exist. :param graph: A graph to which to add an edge :param vertex_u: The edge's first endpoint :param vertex_v: The edge's second endpoint :return: The resulting graph *1. add_vertex (graph, vertex_u). add(vertex_v) add_vertex (graph, vertex_v). add(vertex_u) return graph def remove_vertex (graph, vertex): Remove a vertex from a graph if it exists, along with all incident edges. def remove_vertex(graph, vertex): Remove a vertex from a graph if it exists, along with all incident edges. :param graph: A graph from which to remove a vertex :param vertex: The vertex to be removed :return: The vertex's former adjacency set un. for neighbor in graph.matrix.get(vertex, set()): graph.matrix.get(neighbor, set()). discard(vertex) return graph.matrix.pop(vertex, set()) def remove_edge(graph, vertex_u, vertex_v): Remove an edge from a graph if it exists :param graph: A graph from which to remove an edge :param vertex_u: The edge's first endpoint :param vertex_v: The edge's second endpoint :return: The resulting graph graph.matrix.get(vertex_u, set ()).discard(vertex_v) graph.matrix.get(vertex_v, set ()).discard(vertex_u) return graph h.py >... :param vertex u : The edge's tirst endpoint :param vertex_v: The edge's second endpoint :return: The resulting graph graph,matrix,get (vertex_u, set()),discard(vertex_v) graph.matrix.get(vertex_v, set()), discard(vertex_u) return graph def read_graph(graph_file): Read a graph from a file. :param graph_file: An open file containing an edge list ireturn: The corresponding new graph an graph = Graph() for edge in graph_file: add_edge(graph, *(vertex.strip() for vertex in edge,split("," "))) return graph aoN Uunzad s[o07ue7IquodutsKs7uodut def _is_cover(graph_g, vertices): Determine if a subset of vertices covers a graph. :param graph_g: A graph to be covered :param vertices: A subset of the graph's vertices ireturn: True if the vertices cover the graph's edges, False otherwise "n.." for vertex_u in graph_g: for vertex_v in graph_g[vertex_u]: If vertex_u not in vertices and vertex_v not in vertices: return False return True def main(argv): with open(argv[1], " r ") as graph_file: k = int (graph_file.readine()) graph_g = graph.read_graph(graph_file) cover = vertex_cover (graph_g, k) if cover is not None: print("Vertex cover on zd vertices: " zk ) print(", ".join(sonted(cover))) return else: n.n for vertex_u in graph_g: for vertex_v in graph_g[vertex_u]: if vertex_u not in vertices and vertex_v not in vertices: return False return True def main(argv): with open(argv[1], " r ") as graph_file: k=int( graph_file, readline ()) graph_g = graph.read_graph(graph_file) cover = vertex_cover(graph_B, k) if cover is not None: print (", ".join(sorted(cover))) return else: print ("No vertex cover on 8d vertices." xk ) return 1 If _ name__ = " main__": sys, exit (main (sys, argy)) E tmp1.txt 6 p00, q01 q1,r2 re2, peo p10, r11 r11, p12 p12,p10 r20,r21 r21,r22 r22,r2 p00, p10 p00, p12 r02, r20 r02, r21 r02,r22 r11, r20 r11, r21 r11,r22 out1.txt 1 Satisfying assignment: p,q,r