Generation of all permutation and combination of Matchings in a Bipartite graph and its applications

This paper discusses an approach to generate all permutations and combinations of valid matching edges, valid pass-through edges and un-matched edges of a Bipartite graph (B-graph). Matchings would range from no-match to perfect-match. B-graph is represented as matrix where rows and columns represent two disjoint sets of vertex and its values represent the edges. It involves 3 stages of operation to get all sets of valid matched edges, pass-through edges and unmatched edges of a B-graph. In first stage, the rows and columns of a perfect-match B-graph matrix are swapped to get all permutations. In second stage, each of those B-graph matrix are superimposed over set of binary-matrix (generated by incrementing integers) and AND logical operation is performed on the matrix values to create all combinations of the B-graph. In third stage, the invalid B-graphs are eliminated by checking for invalid-pass-through edges. If pass-through edges are not required, then third stage can be eliminated. Generating all permutations and combinations of B-graphs aids as an input to validate various Matching algorithms and also to represent Redundancy models of High Availability platforms.