pytenet.bipartite_graph

Implementation of the Hopcroft-Karp algorithm, based on https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm

Functions

minimum_vertex_cover(graph)

Find a minimum vertex cover based on Kőnig's theorem.

Classes

BipartiteGraph(num_u, num_v, edges)	Data structure representing a bipartite graph G = ((U, V), E), where U and V are the vertices in the left and right partition, respectively, and E the edges.
HopcroftKarp(graph)	Implementation of the Hopcroft-Karp algorithm to find a maximum-cardinality matching, storing the temporary data for running the algorithm.