Convert Recursive algorithm to Iterative

Question

I am trying to implement following algorithm to a iterative one but I am not able to do it properly. Can some one please help me with this. Its a bipartite matching algorithm and I am having trouble in converting the bpm function to iterative one.

// A DFS based recursive function that returns true if a
// matching for vertex u is possible
bool bpm(bool bpGraph[M][N], int u, bool seen[], int matchR[]) 
{
    // Try every job one by one
    for (int v = 0; v < N; v++)
    {
        // If applicant u is interested in job v and v is
        // not visited
        if (bpGraph[u][v] && !seen[v])
        {
            seen[v] = true; // Mark v as visited

            // If job 'v' is not assigned to an applicant OR
            // previously assigned applicant for job v (which is matchR[v]) 
            // has an alternate job available. 
            // Since v is marked as visited in the above line, matchR[v] 
            // in the following recursive call will not get job 'v' again
            if (matchR[v] < 0 || bpm(bpGraph, matchR[v], seen, matchR))
            {
                matchR[v] = u;
                return true;
            }
        }
    }
    return false;
}

// Returns maximum number of matching from M to N
int maxBPM(bool bpGraph[M][N])
{
    // An array to keep track of the applicants assigned to
    // jobs. The value of matchR[i] is the applicant number
    // assigned to job i, the value -1 indicates nobody is
    // assigned.
    int matchR[N];

    // Initially all jobs are available
    memset(matchR, -1, sizeof(matchR));

    int result = 0; // Count of jobs assigned to applicants
    for (int u = 0; u < M; u++)
    {
        // Mark all jobs as not seen for next applicant.
        bool seen[N];
        memset(seen, 0, sizeof(seen));

        // Find if the applicant 'u' can get a job
        if (bpm(bpGraph, u, seen, matchR))
            result++;
    }
    return result;
}

This should be a straightforward translation from recursive DFS to iterative using a stack. — dfb, Mar 14 '16 at 16:24
This looks like a dupe of [How to implement depth first search for graph with non-recursive aprroach](http://stackoverflow.com/q/21508765/572670). If you think it is not, please elaborate why, or I will close as dupe. — amit, Mar 14 '16 at 16:47
its different as the way we process the current will depends the output of rest of the recursive dfs calls. the iterative algorithm process the current node and move to next iterations. — funkyme, Mar 14 '16 at 17:09

score 2 · Answer 1 · answered Mar 14 '16 at 17:27

The trick is that you need a stack of actions. So when you enter the loop you first add to the stack all of the things you will do after what WOULD have been your recursive call, and THEN put the recursive call in. They will execute in the opposite order, and when you're doing the second half, you know what happened in the first half.

In pseudo-code something like this

function somethingRecursive(stuff):
    beforeRecursive(stuff)
    somethingRecursive(whatever)
    afterRecursive(stuff)

becomes something like this:

while actions:
   action = actions.pop()
   if action.unwind:
       afterRecursive(action.stuff)
   else:
       beforeRecursive(action.stuff)
       actions.push(new Action(unwind, stuff))
       actions.push(new Action(recurse, whatever))

can you please add some more details in the context of problem I shared. I am still having trouble to transform my code. — funkyme, Mar 14 '16 at 18:04
@Microbotz Sorry, my generosity to random Internet strangers does not include coding in C. But you'll want to start by thinking through what kind of struct you'll store an action in. Then how you want to implement your stack. And then you should be in business. — btilly, Mar 15 '16 at 19:09

score 0 · Answer 2 · answered Mar 17 '16 at 06:05

Finally I got it working.

typedef struct 
{
    int uParam;
    int vLocal;
    int location;
}bpmState;

bool bpm_nr(bool bpGraph[M][N], int uParam, int matchR[]) 
{
    bool seen[N];
    memset(seen, 0, sizeof(seen));
    stack<bpmState> states;
    states.push({ uParam, 0, 1 });
    bool rvalue = false;
    while (!states.empty())
    {
        auto state = states.top();
        states.pop();
        switch (state.location) 
        {
        case 1:
            for (int v = state.vLocal, u = state.uParam; v < N; v++) 
            {
                if (bpGraph[u][v] && !seen[v]) 
                {
                    seen[v] = true;
                    if (matchR[v] < 0) 
                    {
                        matchR[v] = u;
                        rvalue = true;
                    }
                    else 
                    {
                        states.push({ u, v, 2 });
                        states.push({ matchR[v], 0, 1 });
                    }
                    break;
                }
            }
            break;
        case 2:
            if (rvalue) 
            {
                matchR[state.vLocal] = state.uParam;
                rvalue = true;
            }
            else 
            {
                states.push({ state.uParam, state.vLocal + 1, 1 });
            }
            break;
        }
    }
    return rvalue;
}

Convert Recursive algorithm to Iterative

2 Answers2