Vertex Cover

In this example we demostrate how to find compute a vertex cover in undirected graphs.

Start by importing the package.

import jgrapht
import jgrapht.algorithms.vertexcover as vc
import jgrapht.drawing.draw_matplotlib as drawing
import matplotlib.pyplot as plt

We start by creating a “star” graph with a few additional edges.

g = jgrapht.create_graph(directed=False, weighted=False)

for i in range(11):
    g.add_vertex(i)

for i in range(10):
    g.add_edge(i, 10)

print(g)

Out:

({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, {0={0,10}, 1={1,10}, 2={2,10}, 3={3,10}, 4={4,10}, 5={5,10}, 6={6,10}, 7={7,10}, 8={8,10}, 9={9,10}})

Then, we execute the 2 approximation algorithm of R. Bar-Yehuda and S. Even.

weight, vertex_cover = vc.baryehuda_even(g)

The result is a tuple which contains whether the weight and the vertex cover. Although it failed to find the optimum which is 1.0, the returned solution is at most twice the optimum.

print('Vertex cover weight: {}'.format(weight))
print('Vertex cover: {}'.format(vertex_cover))

Out:

Vertex cover weight: 2.0
Vertex cover: {0, 10}

Ploting the graph and separate color for the vertex cover vertices. component.

positions = drawing.layout(g, name="fruchterman_reingold", seed=17)

drawing.draw_jgrapht_vertices(g, positions=positions, vertex_list=vertex_cover, vertex_color='red')

non_vertex_cover = g.vertices - vertex_cover
drawing.draw_jgrapht_vertices(g, positions=positions, vertex_list=non_vertex_cover, vertex_color='gray')

drawing.draw_jgrapht_edges(g, positions=positions)

plt.show()