Given a matching in a bipartite graph, find either a
vertex
cover of the same size or an
augmenting path with respect
to the matching, thereby demonstrating that the matching is not
maximum. Complexity:
O((m + n) * log(n)).
An
alternating path is a path whose edges belong alternately to
the matching and not to the matching. An
augmenting path is an
alternating path that starts from and ends on the vertices that are
not covered by the matching. A matching is maximum if and only if
there is no augmenting path with respect to it.
augmentingPath (matching []) empty == Left (Set.empty, Set.empty)
augmentingPath (matching []) (edge 1 2) == Right [1,2]
augmentingPath (matching [(1,2)]) (path [1,2,3]) == Left (Set.empty, Set.singleton 2)
augmentingPath (matching [(3,2)]) (path [1,2,3,4]) == Right [1,2,3,4]
isLeft (augmentingPath (maxMatching x) x) == True