How to modify algorithm to get all maximal matchings in bipartite graph?

Question

I use the following code to find maximal matching in bipartite graph (I've tried to add a few comments):

#include <iostream>

using namespace std;

// definition of lists elements
//-------------------------------
struct slistEl
{
  slistEl * next;
  int data;
};

// definition objective type queue
//---------------------------------
class queue
{
  private:
    slistEl * head;
    slistEl * tail;

  public:
    queue();      
    ~queue();     
    bool empty(void);
    int  front(void);
    void push(int v);
    void pop(void);
};

queue::queue()
{
  head = tail = NULL;
}

queue::~queue()
{
  while(head) pop();
}

bool queue::empty(void)
{
  return !head;
}

int queue::front(void)
{
  if(head) return head->data;
  else     return -10000;
}

void queue::push(int v)
{
  slistEl * p = new slistEl;
  p->next = NULL;
  p->data = v;
  if(tail) tail->next = p;
  else     head = p;
  tail = p;
}

void queue::pop(void)
{
  if(head)
  {
    slistEl * p = head;
    head = head->next;
    if(!head) tail = NULL;
    delete p;
  }
}

//---------------
// main part
//---------------

queue Q;                          // queue
int *Color;                       // colors of vertexes
slistEl **graf;                   // adjacency array
int **C;                          // matrix of capacity
int **F;                          // matrix of nett flow
int *P;                           // array of prev
int *CFP;                         // array of residual capacity
int n,m,fmax,cp,v,u,i,j;          // 
bool esc;                         // 
slistEl *pr, *rr;                 // pointer for list elements


int main(int argc, char *argv[])
{

  // n - number of vertexes
  // m - number of edges

  cin >> n >> m;


  Color = new int [n];             
  graf = new slistEl * [n];       
  for(i = 0; i < n; i++)
  {
    graf[i] = NULL;
    Color[i] = 0;
  }

  C = new int * [n+2];            
  F = new int * [n+2];            
  for(i = 0; i <= n + 1; i++)
  {
    C[i] = new int [n+2];
    F[i] = new int [n+2];
    for(j = 0; j <= n + 1; j++)
    {
      C[i][j] = 0;
      F[i][j] = 0;
    }
  }

  P = new int [n+2];             
  CFP = new int [n+2];           

  // reading edges definition and adding to adjacency list

  for(i = 0; i < m; i++)
  {
    cin >> v >> u;
    pr = new slistEl;
    pr->data = u;
    pr->next = graf[v];
    graf[v]  = pr;

    pr = new slistEl;
    pr->data = v;
    pr->next = graf[u];
    graf[u]  = pr;
  }

for(i = 0; i < n; i++){
         cin>> Color[i];
      }



    for(i = 0; i < n; i++)
      if(Color[i] == -1)
      {
        for(pr = graf[i]; pr; pr = pr -> next) // neighbours of blue
          C[i][pr->data] = 1;     // capacity to red
        C[n][i] = 1;              // capacity  to source
      }
      else C[i][n+1] = 1;         // capacity edges to outfall

    //**  Edmonds-Karp algorithm **

    fmax = 0;

    while(true)
    {
      for(i = 0; i <= n + 1; i++) P[i] = -1;

      P[n] = -2;
      CFP[n] = MAXINT;

      while(!Q.empty()) Q.pop();
      Q.push(n);

      esc = false;

      while(!Q.empty())
      {
        v = Q.front(); Q.pop();

        for(u = 0; u <= n + 1; u++)
        {
          cp = C[v][u] - F[v][u];
          if(cp && (P[u] == -1))
          {
            P[u] = v;
            if(CFP[v] > cp) CFP[u] = cp; else CFP[u] = CFP[v];
            if(u == n+1)
            {
              fmax += CFP[n+1];
              i = u;
              while(i != n)
              {
                v = P[i];
                F[v][i] += CFP[n+1];
                F[i][v] -= CFP[n+1];
                i = v;
              }
              esc = true; break;
            }
            Q.push(u);
          }
        }
        if(esc) break;
      }
      if(!esc) break;
    }

    // showing reuslts


    if(fmax > 0)
      for(v = 0; v < n; v++)
        for(u = 0; u < n; u++)
          if((C[v][u] == 1) && (F[v][u] == 1))
            cout << v << " - " << u << endl;

  cout << endl;

  // cleaning

  delete [] Color;               

  for(i = 0; i < n; i++)
  {
    pr = graf[i];
    while(pr)
    {
      rr = pr;
      pr = pr->next;
      delete rr;
    }
  }

  delete [] graf;               

  for(i = 0; i <= n + 1; i++)
  {
    delete [] C[i];
    delete [] F[i];
  }
  delete [] C;                    
  delete [] F;                    

  delete [] P;                  
  delete [] CFP;                

  return 0;
}

It returns only one maximal matching. For example for data:

6 7
0 3 0 5
1 3 1 4 1 5
2 3 2 5
1 1 1 -1 -1 -1

But there are more maximal matchings.

I don't know, how should I modify it to get all results and I would like to ask somebody for help. Thank you in advance.

Answer 1

That algorithm is only efficient to get you a maximum matching.

If you want all maximal matching you have to consider the case where any matching is a maximal matching. In that case you have N! possibilities.

Since you will need to visit all solutions your complexity will be O(N!) at least. Therefore, forget the code you have, you can just try all possible matchings using a recursive algorithm and keep the set of maximal matching you get.