Assignment Problem/Hungarian Algorithm - Table Input and Manipulation

Question

I'm currently working on a college algorithms assignment, which involves creating an implementation for The Assignment Problem, or the Hungarian Algorithm. So far, I've coded a program that I believed was capable of performing the first 2 steps of the algorithm, which are:

• Step 1: In each row, subtract the minimum value in that row with each element.
• Step 2: In each column, subtract the minimum value in that column with each element.

Currently, my program is able to display 3 stages of the table (2D Vector) that it's manipulating:

• "Data", which is the table that is originally inputted.
• "Min Row Cots", which is the table after step 1 is performed.
• "Cost Matrix", which is the table after step 2 is performed.

The program correctly manipulates the table for the first example that I used, which is a 4x4 table with the following data:

A	B	C	D
56	59	52	53
62	67	59	49
55	64	58	51
58	60	54	48

However, this program cannot handle non-square tables, such as a 4x3.

Before trying to code steps 3-5 of the algorithm, I wanted to make sure that my program could handle uneven tables, so I came up with an example in the form of a 4x3 table. I wasn't sure if it would manipulate it correctly, but I atleast expected it to display the initial input table, 'data', correctly. However, this did not happen- When given the 4x3 example, the program displays an incorrectly rotated form of what the 'data' table should actually look like, and then proceeds to crash.

With this in mind, I was wondering if anyone had ideas as to what's happening, and possibly how I can fix it? If so, I would greatly appreciate it! My code is below:

#include <iostream>
#include <vector>

class AssignmentProblem
{
private:
    int Row;
    int Column;
    std::vector<std::vector<int>> data;
public:
    AssignmentProblem(std::vector<std::vector<int>> NewData, int NewRow, int NewColumn)
    {
        Row = NewRow;
        Column = NewColumn;
        data = NewData;
    }

    // ********************************************************************************* //
    // Take the minimum cost of each row, and adjust the matrix accordingly:
    std::vector<int> RowMinimums(std::vector<std::vector<int>> data)
    {
        std::vector<int> row_minimums;

        for (int i = 0; i < Row; i++)
        {
            int minimum = INT_MAX;
            for (int j = 0; j < Column; j++)
            {
                if (data[i][j] < minimum)
                {
                    minimum = data[i][j];
                }
            }
            row_minimums.push_back(minimum);
        }

        return row_minimums;
    }

    std::vector<std::vector<int>> MinRowCosts(std::vector<std::vector<int>> data)
    {
        std::vector<int> row_minimums = RowMinimums(data);
        std::vector<std::vector<int>> min_row_costs;

        for (int i = 0; i < Row; i++)
        {
            std::vector<int> row;
            for (int j = 0; j < Column; j++)
            {
                row.push_back(data[j][i] - row_minimums[j]);
            }
            min_row_costs.push_back(row);
            row.clear();
        }

        return min_row_costs;
    }

    // ********************************************************************************* //
    // ********************************************************************************* //
    // Take the minimum cost of each column, and adjust the matrix accordingly:
    std::vector<int> ColumnMinimums(std::vector<std::vector<int>> min_row_costs)
    {
        std::vector<int> column_minimums;

        for (int i = 0; i < Column; i++)
        {
            int minimum = INT_MAX;
            for (int j = 0; j < Row; j++)
            {
                if (min_row_costs[i][j] < minimum)
                {
                    minimum = min_row_costs[i][j];
                }
            }
            column_minimums.push_back(minimum);
        }

        return column_minimums;
    }

    std::vector<std::vector<int>> MinColumnCosts(std::vector<std::vector<int>> min_row_costs)
    {
        std::vector<int> column_minimums = ColumnMinimums(min_row_costs);
        std::vector<std::vector<int>> min_column_costs;

        for (int i = 0; i < Column; i++)
        {
            std::vector<int> column;
            for (int j = 0; j < Row; j++)
            {
                column.push_back(min_row_costs[j][i] - column_minimums[j]);
            }
            min_column_costs.push_back(column);
            column.clear();
        }

        return min_column_costs;
    }

    // ********************************************************************************* //

    std::vector<std::vector<int>> calculateCostMatrix(std::vector<std::vector<int>> data)
    {
        std::vector<std::vector<int>> min_row_costs = MinRowCosts(data);

        std::cout << "Min Row Costs = " << std::endl;
        for (int i = 0; i < Row; i++)
        {
            std::cout << "< ";
            for (int j = 0; j < Column; j++)
            {
                std::cout << min_row_costs[j][i] << " ";
            }
            std::cout << " >" << std::endl;
        }
        std::cout << std::endl;

        std::vector<std::vector<int>> cost_matrix = MinColumnCosts(min_row_costs);

        std::cout << "Cost Matrix = " << std::endl;
        for (int i = 0; i < Row; i++)
        {
            std::cout << "< ";
            for (int j = 0; j < Column; j++)
            {
                std::cout << cost_matrix[i][j] << " ";
            }
            std::cout << " >" << std::endl;
        }
        return cost_matrix;
    }
};

int main()
{
    int Row = 4;
    int Column = 3; // Broken Example (4x3 Table).
    //int Column = 4; // Working Example (4x4 Table).

    //std::vector<std::vector<int>> data  = {{56,59,52,53}, {62,67,59,49}, {55,64,58,51}, {58,60,54,48}}; // Working Example (4x4 Table).
    std::vector<std::vector<int>> data = {{11,12,18,40},{14,15,13,22},{11,17,19,23}};  // Broken Example (4x3 Table)

    std::cout << "Data = " << std::endl;
    for (int i = 0; i < Row; i++)
    {
        std::cout << "< ";
        for (int j = 0; j < Column; j++)
        {
            std::cout << data[j][i] << " ";
        }
        std::cout << " >" << std::endl;
    }
    std::cout << std::endl;

    AssignmentProblem AP(data, Column, Row);

    std::vector<std::vector<int>> costs = AP.calculateCostMatrix(data);

    return 0;
}

Sidenote: I apologize if my code is hard to read or follow.. I'm still fairly new to programming, and am working on readability.

Answer 1

Row and column subscripts transposed

You have transposed row and column coordinates in many places in your program. Most of the references to data[j][i] should put i first, because i is the row subscript.

I recommend dropping i and j, and replacing them with row and col. That way you won't lose track of which subscript should go first. Here, for example, is one of your functions, after making that change.

Note: the row subscript always goes first, e.g., min_row_costs[row][col], even when the outer loop is a column loop.

    // Take the minimum cost of each column, and adjust the matrix accordingly:
    std::vector<int> ColumnMinimums(std::vector<std::vector<int>> min_row_costs)
    {
        std::vector<int> column_minimums;

        for (int col = 0; col < Column; col++)
        {
            int minimum = INT_MAX;
            for (int row = 0; row < Row; row++)
            {
                if (min_row_costs[row][col] < minimum)
                {
                    minimum = min_row_costs[row][col];
                }
            }
            column_minimums.push_back(minimum);
        }

        return column_minimums;
    }

Similarly, it is wrong to reference row_minimums[j], when j is a column subscript. That should be row_minimums[i], or, better yet, row_minimums[row].

Call function size to get n_rows and n_cols

Side note: The vector carries with it the number of rows and columns.

void example(std::vector<std::vector<int>> matrix)
{
    // You do not have to pass the sizes as parameters.
    // Call member function `size` to get `n_rows` and `n_cols`.
    auto const n_rows{ matrix.size() };
    auto const n_cols{ matrix.front().size() };

    // There is no guarantee, however, that every row has 
    // the same number of columns. If there is a possibility 
    // that row-length is not uniform, you can always check.
    for (auto const& row : matrix)
        if (row.size() != n_cols)
            throw std::runtime_error("row size varies.");
}