Vertex Cover (python implementation)

Formally, a vertex-cover of an undirected graph G=(V, E) is a subset V′ of V such that if edge (u, v) is an edge of G, then u is in V′, or v is in V′, or both. The set V′ is said to "cover" the edges of G. The following figure shows examples of vertex covers in two graphs (and the set V' is marked with red).
A minimum vertex cover is a vertex cover of smallest possible size. The vertex cover number \tau is the size of a minimum vertex cover. The following figure shows examples of minimum vertex covers in the previous graphs.

Assume that every vertex has an associated cost of c(v)\geq 0.
minimize\sum_{v \in V} c(v) x_v  (minimize the total cost)
subject tox_u+x_v\geq 1for all \{u,v\} \in E(cover every edge of the graph)
x_v\in\{0,1\}for all v\in V.(every vertex is either in the vertex cover or not)

Python implementation(running-time: exponential)

import itertools

class Vertex_Cover:

    def __init__(self, graph):
        self.graph = graph

    def validity_check(self, cover):
        is_valid = True        for i in range(len(self.graph)):
            for j in range(i+1, len(self.graph[i])):
                if self.graph[i][j] == 1 and cover[i] != '1' and cover[j] != '1':
                    return False
        return is_valid

    def vertex_cover_naive(self):
        n = len(self.graph)
        minimum_vertex_cover = n
        a = list(itertools.product(*["01"] * n))
        for i in a:
            if Vertex_Cover.validity_check(ins, i):
                counter = 0                for value in i:
                    if value == '1':
                        counter += 1                minimum_vertex_cover = min(counter, minimum_vertex_cover)

        return minimum_vertex_cover

if __name__ == '__main__':
    graph =[[0, 1, 1, 1, 1],[1, 0, 0, 0, 1],[1, 0, 0, 1, 1], [1, 0, 1, 0, 1], [1, 1, 1, 1, 0]]
    ins = Vertex_Cover(graph)

    print 'the minimum vertex-cover is:', Vertex_Cover.vertex_cover_naive(ins)


Popular posts from this blog

Transportation Problem (Vogel algorithm python)

cProfile python (benchmark)