LeetCode #1066 - Campus Bikes II

Question

The following code implements the Hungarian algorithm. The algorithm is used to find minimum cost perfect matching on a bipartite graph.

Looking for comments on correctness, efficiency, clarity and idiomatic C++ usages. It passes all tests on LeetCode.

class Solution
{
public:
    int assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes)
    {
        if (workers.size() == 0)
        {
            return 0;
        }
        if (bikes.size() == 0)
        {
            return 0;
        }
        vector<vector<int>> costs;
        costs.resize(workers.size());
        for (int i = 0; i < workers.size(); i++)
        {
            costs[i].resize(bikes.size());
            for (int j = 0; j < bikes.size(); j++)
            {
                int wx = workers[i][0];
                int wy = workers[i][1];
                int bx = bikes[j][0];
                int by = bikes[j][1];
                int dx = wx - bx;
                int dy = wy - by;
                dx = dx > 0 ? dx : -dx;
                dy = dy > 0 ? dy : -dy;
                costs[i][j] = dx + dy;
            }
        }
        vector<pair<int, int>> answer = hungarian(costs);
        int result = 0;
        for (auto edge : answer)
        {
            result += costs[edge.first][edge.second];
        }
        return result;
    }
private:
    // Implementation of the Hungarian algorithm for finding a minimum cost perfect matching
    // The implementation is based on the description on https://en.wikipedia.org/wiki/Hungarian_algorithm
    vector<pair<int, int>> hungarian(const vector<vector<int>>& costs)
    {
        // The problem of finding a minimum cost assignment is the same as
        // finding the minimum cost perfect matching between the rows (workers) and the columns (jobs)
        int n = (int)costs.size();
        int m = (int)costs[0].size();

        // At all times, the algorithm maintains an integer named potential for all nodes.
        // The algorithm make sure potential(u) + potential(v) <= cost[u,v]
        // The nodes that represents the row are [0,n) and the nodes that represents the columns are [n, m + n)
        // Potential values are initialized to 0.
        vector<int> potential;
        potential.resize(m + n);
        for (int i = 0; i < m + n; i++)
        {
            potential[i] = 0;
        }

        // We maintain a directed graph, the edges of the graph is tight (i.e. potential(u) + potential(v) = cost[u,v]).
        // The edges from [n, m + n) back to [0, n) has to form a matching. (i.e. these edges does not share source/target)
        vector<vector<bool>> direction;
        direction.resize(n);
        for (int i = 0; i < n; i++)
        {
            direction[i].resize(m);
            for (int j = 0; j < m; j++)
            {
                direction[i][j] = true;
            }
        }

        // If a node is involved in the matching, the matched flag will be true.
        vector<bool> matched;
        matched.resize(m + n);
        for (int i = 0; i < m + n; i++)
        {
            matched[i] = false;
        }

        // We will do a BFS to find paths. The parent array store the parent node used to discover a node.
        vector<int> parent;
        parent.resize(m + n);

        while (true)
        {
            queue<int> bfs;
            for (int i = 0; i < m + n; i++)
            {
                // Parent == -1 means it is not enqueued yet, so there is no parent
                parent[i] = -1;
            }

            for (int i = 0; i < n; i++)
            {
                if (!matched[i])
                {
                    bfs.push(i);
                    // Parent == -2 means it is enqueued because it is a not matched source node.
                    // It should NOT be enqueued again
                    parent[i] = -2;
                }
            }

            // This is just a standard BFS, note that the cost and direction array must be read from row to column
            while (bfs.size() > 0)
            {
                int visiting = bfs.front();
                bfs.pop();
                if (visiting < n)
                {
                    for (int neighbor = n; neighbor < m + n; neighbor++)
                    {
                        bool tight = costs[visiting][neighbor - n] - potential[visiting] - potential[neighbor] == 0;
                        if (direction[visiting][neighbor - n] && tight)
                        {
                            if (parent[neighbor] == -1)
                            {
                                bfs.push(neighbor);
                                parent[neighbor] = visiting;
                            }
                        }
                    }
                }
                else
                {
                    for (int neighbor = 0; neighbor < n; neighbor++)
                    {
                        bool tight = costs[neighbor][visiting - n] - potential[visiting] - potential[neighbor] == 0;
                        if (!direction[neighbor][visiting - n] && tight)
                        {
                            if (parent[neighbor] == -1)
                            {
                                bfs.push(neighbor);
                                parent[neighbor] = visiting;
                            }
                        }
                    }
                }
            }

            bool found = false;
            for (int i = n; i < m + n; i++)
            {
                if (!matched[i] && parent[i] != -1)
                {
                    // If there is a way to reach from a source unmatched node to a target
                    // unmatched node, then we have an augmenting path, using the parent
                    // pointer chain, we can reverse all the paths to increasing the size
                    // of the matching by 1.
                    found = true;
                    int current = i;
                    while (true)
                    {
                        if (parent[current] == -2)
                        {
                            matched[i] = true;
                            matched[current] = true;
                            break;
                        }
                        int small = min(current, parent[current]);
                        int large = max(current, parent[current]);
                        direction[small][large - n] = !direction[small][large - n];
                        current = parent[current];
                    }
                    break;
                }
            }

            if (!found)
            {
                // If we cannot find an augmenting path, we will modify the potential
                // so that we have more nodes reachable from the unmatched sources
                int delta = -1;
                for (int i = 0; i < n; i++)
                {
                    if (parent[i] != -1)
                    {
                        for (int j = n; j < m + n; j++)
                        {
                            if (parent[j] == -1)
                            {
                                // Make sure the delta does not violate the constraint
                                // between each pair of reachable source/unreachable target
                                int margin = costs[i][j - n] - potential[i] - potential[j];
                                if (delta == -1 || margin < delta)
                                {
                                    delta = margin;
                                }
                            }
                        }
                    }
                }
                if (delta == -1)
                {
                    break;
                }
                for (int i = 0; i < n; i++)
                {
                    if (parent[i] != -1)
                    {
                        // For each reachable source, the potential is increased by delta
                        potential[i] += delta;
                    }
                }
                for (int i = n; i < m + n; i++)
                {
                    if (parent[i] != -1)
                    {
                        // For each reachable target, the potential is decreased by delta
                        potential[i] -= delta;
                    }
                }
                // After the manipulation:
                // The potential is feasible for reachable source, reachable target because the sum didn't change.
                // The potential is feasible for reachable source, unreachable target because the increase is checked earlier.
                // The potential is feasible for unreachable source, reachable target because the sum decrease.
                // The potential is feasible for unreachable source, unreachable target because the sum didn't change.
            }
        }
        vector<pair<int, int>> answer;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (!direction[i][j])
                {
                    answer.push_back(make_pair(i, j));
                }
            }
        }
        return answer;
    }
};

Answer 1

So in general the code is already quite good. It is well formated and easily readable.

From what I can see the most important task ahead is to familiarize yourself better with the stl and all the things it brings to the table:

1. Use qualified calls

   The habit of using namespace std is a vary bad one you should try to avoid as soon as possible. It doesnt really save you a lot and can get you in trouble quickly.

2. Use the appropriate member functions

   if (workers.size() == 0)
   {
       return 0;
   }
   

   This is technically correct and not even too bad performance wise for std::vector. However this is terrible for every other container. All containers feature a empty() method that should be used

   if (workers.empty())
   {
       return 0;
   }
   

   The advantages are numerous. First you can never be too sure if workers.size() == 0 is really correct. Did he mean != 0 or maybe == 1 or whatever. With empty the intend is clear and there are only two possible cases which are often quite obvious to check. Also for any non-continuous container e.g std::unorderd_set, std::set, std::forward_list and std::list the determination of size requires a full traversal of the container. In contrast empty only checks a single pointer. So it is considerable cheaper.

3. Know the constructors

   The elements in the standard containers are value constructed

   vector<int> potential;
   potential.resize(m + n);
   for (int i = 0; i < m + n; i++)
   {
       potential[i] = 0;
   }
   

   Is equivalent to this

   vector<int> potential(m + n);
   

   If you have a certain value in mind you can also write it more explicitely as

   vector<int> potential(m + n, 0);
   

   This also works for nested containers so instead of

   vector<vector<bool>> direction;
   direction.resize(n);
   for (int i = 0; i < n; i++)
   {
       direction[i].resize(m);
       for (int j = 0; j < m; j++)
       {
           direction[i][j] = true;
       }
   }
   

   We can write

   vector<vector<bool>> direction(n, std::vector<bool>(m, true));
   

4. Try to enforce const correctness

   I know this can seem like a lot of clutter but always mark constants as const so code like

   bool tight = costs[visiting][neighbor - n] - potential[visiting] - potential[neighbor] == 0;
   if (direction[visiting][neighbor - n] && tight)
       ...
   

   Should be written as

   const bool tight = costs[visiting][neighbor - n] - potential[visiting] - potential[neighbor] == 0;
   if (direction[visiting][neighbor - n] && tight)
       ...
   

   There is a great talk by Kate Gregory about it. In a nutshell you want to convey as much information as possible, so that any variable that is not const sticks out

5. Do not build mountains

   There is only one occurence of it but try to avoid writing canyons like

   for (...) {
       if (condition) {
           ...
       }
   }
   

   In this example there is only one level of identation but from personal expirience I can tell you that these mountains grow. Instead use early returns/continues

   for (...) {
       if (!condition) {
           continue;
       }
       ...
   }
   

   This greatly improves readability if there are multiple nested conditions and also makes is much clearer what is a precondition and what not.

6. Know you algorithms

   The stl offers a great variety of algorithms. There are numerous cases where you could use std::accumulate or std::copy_if. Try to learn those algorithms by heart. In general you can assume that the algorithms of the standard library are better tested and more performant that what you or I could cook up