Source code for tryalgo.bipartite_vertex_cover

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
Bipartie vertex cover
jill-jenn vie et christoph durr - 2014-2018
"""


from tryalgo.bipartite_matching import max_bipartite_matching


def _alternate(u, bigraph, visitU, visitV, matchV):
    """extend alternating tree from free vertex u.
      visitU, visitV marks all vertices covered by the tree.
    """
    visitU[u] = True
    for v in bigraph[u]:
        if not visitV[v]:
            visitV[v] = True
            assert matchV[v] is not None  # otherwise match is not maximum
            _alternate(matchV[v], bigraph, visitU, visitV, matchV)


[docs]def bipartite_vertex_cover(bigraph): """Bipartite minimum vertex cover by Koenig's theorem :param bigraph: adjacency list, index = vertex in U, value = neighbor list in V :assumption: U = V = {0, 1, 2, ..., n - 1} for n = len(bigraph) :returns: boolean table for U, boolean table for V :comment: selected vertices form a minimum vertex cover, i.e. every edge is adjacent to at least one selected vertex and number of selected vertices is minimum :complexity: `O(|V|*|E|)` """ V = range(len(bigraph)) matchV = max_bipartite_matching(bigraph) matchU = [None for u in V] for v in V: # -- build the mapping from U to V if matchV[v] is not None: matchU[matchV[v]] = v visitU = [False for u in V] # -- build max alternating forest visitV = [False for v in V] for u in V: if matchU[u] is None: # -- starting with free vertices in U _alternate(u, bigraph, visitU, visitV, matchV) inverse = [not b for b in visitU] return (inverse, visitV)