Using ford fulkerson to place N employees in M positions with roles

Question

I'm trying to solve a mathematical problem using Ford-Fulkerson, but I have some problems.

This is the problem

    I have a list of employees (Jack, John, Al, ...).
    I have a list of roles (R1, R2, R3, ...).
    I have a list of working positions (W1, W2, W3, ...).

    Every employee has a set of roles, like Jack has R1 and R2, ...
    Every working position has a set of roles that can support,
    like to work in position W1 you need R1 or R2, ...

I need to find the best configuration of employees - working positions, to be sure that every working position has an employee with the right roles to work there (one employee per position).

I tried using this algorithm http://www.geeksforgeeks.org/maximum-bipartite-matching/

I built a matrix where I have a row for every employee and a column for every working position. I put in the X row, Y column the value 1 if the X employee can work in the Y position, otherwise I put 0.

The algorithm above, rewritten in PHP, works great until the number of employees <= the number of positions.

If I have more employees than positions, the algorithm calculation time tends to diverge to infinite.

Here is the algorithm code:

function maxMatch($matrix, $cols) {
    $match = array();
    foreach ($cols as $v => $item) {
        $match[$item] = -1;
    }
    $result = 0;
    foreach ($matrix as $u => $row) {
        $seen = array();
        foreach ($cols as $v => $item) {
            $seen[$item] = 0;
        }
        if ($this->checkVertex($matrix, $u, $seen, $match)) {
            print_r($match);
            $result++;
        }
    }
    return $match;
}

function checkVertex($matrix, $u, $seen, &$match) {
    foreach ($matrix[$u] as $v => $row) {
        if ($matrix[$u][$v] && !$seen[$v]) {
            $seen[$v] = TRUE;
            if ($match[$v] < 0 || $this->checkVertex($matrix, $match[$v], $seen, $match)) {
                $match[$v] = $u;
                return TRUE;
            }
        }
    }
    return FALSE;
}

Everything is like the algorithm in the link above, except that I pass the $cols array, containing the indexes of the columns (because they are position IDs and not numeric ordered).

This is how I create the matrix:

function createMatrix($year, $month, $day, $shift) {
    global $sql;

    $result = $sql->query("VERY HUGE SELECT FOR EMPLOYEES AND POSITIONS MATCH");

    while ($row = $result->fetch_assoc()) {
        $matrix[$row['employee']][$row['position']] = 1;
    }
    return $matrix;
}

so I put 1 only where I have a match between employees and positions.

Anyone has any clue on how to resolve the problem? Thanks in advance

Answer 1

You pass seen by value. It is not correct. It should be passed by reference. What you have now is actually some kind of backtracking(the original algorithm time complexity proof is based on a fact that each vertex can be visited at most once during the depth-first-search and it is not true in your current implementation). That's why it works slow. Passing seen by reference should fix it.