Vertex Cover (python implementation)


MINIMUM VERTEX-COVER
Description
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).
Vertex-cover.svg
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.
Minimum-vertex-cover.svg

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)


Comments

Popular posts from this blog

Transportation Problem (Vogel algorithm python)

IP scanning in python