augment package:algebraic-graphs

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