Метод ветвей и границ для задачи коммивояжера

map<T, T> SolveMerchantProblem()
    {
        vector<pair<T, T>> buffer;
        map<T, T> result;
 
        vector<vector<ElemntOfMatrix>> BufferMatrix = vector<vector<ElemntOfMatrix>>
            (AdjMatrix.size(), vector<ElemntOfMatrix>(AdjMatrix.size()));
 
        //В задачу коммивояжера пути могут не существовать только на главной диагонали таблицы смежности
        for (int i = 0; i < AdjMatrix.size(); i++)
        {
            for (int j = 0; j < AdjMatrix.size(); j++)
            {
                if (i == j)
                {
                    BufferMatrix[i][j].isNonExistantFromStart = true;
                    BufferMatrix[i][j].value = 0;
                }
                else
                    BufferMatrix[i][j].value = AdjMatrix[i][j];
            }
        }
 
        cout << "Starting table: " << endl << endl;
 
        PrintTable(BufferMatrix);
 
        int counter = 0;
 
        while (buffer.size() != VertexList.size())
        {
            cout << "----------------------" << endl << endl;;
 
            PrintTable(BufferMatrix);
 
            vector<int> MinElementsOfRows;
 
            cout << endl <<"Row minimum elements:" << endl;
 
            for (int i = 0; i < BufferMatrix.size(); i++)
            {
                int minValue = startMinValue;
 
                for (int j = 0; j < BufferMatrix.size(); j++)
                {
                    if (!BufferMatrix[i][j].isNonExistantFromStart && !BufferMatrix[i][j].isNonExistantFromReduction)
                    {
                        if (minValue > BufferMatrix[i][j].value)
                            minValue = BufferMatrix[i][j].value;
                    }
                }
 
                if (minValue == startMinValue)
                    minValue = 0;
 
                cout << i << " : " << minValue << endl;
                MinElementsOfRows.push_back(minValue);
            }
 
            cout << "Matrix after row reduction:" << endl << endl;;
 
            for (int i = 0; i < BufferMatrix.size(); i++)
            {
                for (int j = 0; j < BufferMatrix.size(); j++)
                {
                    if (BufferMatrix[i][j].value != 0)
                        BufferMatrix[i][j].value -= MinElementsOfRows[i];
                }       
            }
 
            PrintTable(BufferMatrix);
 
            vector<int> MinElemntsOfColumns;
 
            cout << endl << endl << "Minimum column elements:" << endl;
 
            for (int i = 0; i < BufferMatrix.size(); i++)
            {
                int minValue = startMinValue;
 
                for (int j = 0; j < BufferMatrix.size(); j++)
                {
                    if (!BufferMatrix[j][i].isNonExistantFromStart && !BufferMatrix[j][i].isNonExistantFromReduction)
                    {
                        if (minValue > BufferMatrix[j][i].value)
                            minValue = BufferMatrix[j][i].value;
                    }   
                }
 
                if (minValue == startMinValue)
                    minValue = 0;
 
                cout << i << " : " << minValue << endl;
 
                MinElemntsOfColumns.push_back(minValue);
            }
 
            for (int i = 0; i < BufferMatrix.size(); i++)
            {
                for (int j = 0; j < BufferMatrix.size(); j++)
 
                    if (BufferMatrix[j][i].value != 0)
                        BufferMatrix[j][i].value -= MinElemntsOfColumns[i];
            }
 
            cout << endl << "Matrix after second reduction: " << endl << endl;
 
            PrintTable(BufferMatrix);
 
            vector<ZeroElement> ZeroElements;
 
            for (int i = 0; i < BufferMatrix.size(); i++)
            {
                for (int j = 0; j < BufferMatrix.size(); j++)
                {
                    if (BufferMatrix[i][j].value == 0 && !BufferMatrix[i][j].isNonExistantFromStart && 
                        !BufferMatrix[i][j].isNonExistantFromReduction)
                    {
                        int minRow = startMinValue;
                        int minColumn = startMinValue;
 
                        for (int uj = 0; uj < BufferMatrix.size(); uj++)
                        {
                            if (!BufferMatrix[i][uj].isNonExistantFromStart && 
                                !BufferMatrix[i][uj].isNonExistantFromReduction && j != uj)
                            {
                                if (minRow > BufferMatrix[i][uj].value)
                                    minRow = BufferMatrix[i][uj].value;
                            }   
                        }
 
                        for (int ui = 0; ui < BufferMatrix.size(); ui++)
                        {
                            if (!BufferMatrix[ui][j].isNonExistantFromStart && 
                                !BufferMatrix[ui][j].isNonExistantFromReduction && ui != i)
                            {
                                if (minColumn > BufferMatrix[ui][j].value)
                                    minColumn = BufferMatrix[ui][j].value;
                            }
                        }
 
                        if (minRow == startMinValue)
                            minRow = 0;
 
                        if (minColumn == startMinValue)
                            minColumn = 0;
 
                        ZeroElement element(i, j, minColumn + minRow);
                        ZeroElements.push_back(element);
                    }
                }
            }
 
            if (ZeroElements.size() == 0)
            {
                cout << "No more zero elements, finding obvious routes" << endl;
 
                for (int i = 0; i < VertexList.size(); i++)
                {
                    bool flag = false;
 
                    if (result.find(VertexList[i].Data) == result.end())
                    {
                        for (int j = 0; j < VertexList.size() && !flag; j++)
                        {
                            if (i == j)
                                continue;
 
                            bool does_exist = false;
 
                            for (auto& elm : result)
                            {
                                if (elm.second == VertexList[j].Data)
                                {
                                    does_exist = true;
                                    break;
                                }
                            }
 
                            flag = !does_exist;
 
                            if (flag)
                                result[VertexList[i].Data] = VertexList[j].Data;
                        }
                    }
                }
 
                return result;
            }
 
            ZeroElement maxElement = ZeroElements[0];
 
            cout << "Zero elements:" << endl;
 
            for (int i = 0; i < ZeroElements.size(); i++)
                cout << ZeroElements[i].Row << " " << ZeroElements[i].Column << " " << ZeroElements[i].Value << endl;
 
            for (int i = 0; i < ZeroElements.size(); i++)
            {
                if (maxElement.Value < ZeroElements[i].Value)
                    maxElement = ZeroElements[i];
            }
 
            pair<T, T> to_add;
 
            to_add.first = VertexList[maxElement.Row].Data;
            to_add.second = VertexList[maxElement.Column].Data;
 
            for (int i = 0; i < buffer.size(); i++)
            {
                if (to_add.first == buffer[i].second)
                {
                    BufferMatrix[GetVertexIndex(to_add.second)][GetVertexIndex(buffer[i].first)].isNonExistantFromReduction = true;
                    BufferMatrix[GetVertexIndex(to_add.second)][GetVertexIndex(buffer[i].first)].value = 0;
                }
            }
 
            buffer.push_back(to_add);
 
            cout << "Result pair: " << to_add.first << " " << to_add.second << endl;
 
            result[VertexList[maxElement.Row].Data] = VertexList[maxElement.Column].Data;
 
            for (int i = 0; i < BufferMatrix.size(); i++)
            {
                BufferMatrix[maxElement.Row][i].isNonExistantFromReduction = true;
                BufferMatrix[maxElement.Row][i].value = 0;
            }
                
 
            for (int i = 0; i < BufferMatrix.size(); i++)
            {
                BufferMatrix[i][maxElement.Column].isNonExistantFromReduction = true;
                BufferMatrix[i][maxElement.Column].value = 0;
            }
 
            BufferMatrix[maxElement.Row][maxElement.Column].isNonExistantFromReduction = true;
            BufferMatrix[maxElement.Column][maxElement.Row].isNonExistantFromReduction = true;
 
            BufferMatrix[maxElement.Row][maxElement.Column].value = 0;
            BufferMatrix[maxElement.Column][maxElement.Row].value = 0;
 
            cout << "Matrix after full reduction: " << endl << endl;
 
            PrintTable(BufferMatrix);
        }
 
        return result;
    }

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <cmath>
 
using namespace std;
 
constexpr size_t npos = static_cast<size_t>(-1);
const int startMinValue = 10000;
 
struct ElementOfMatrix
{
    int value;
    bool exists = true;
};
 
struct ZeroElement
{
    size_t Row;
    size_t Column;
    int Value;
 
    ZeroElement() = default;
 
    ZeroElement(size_t row, size_t column, int value) : Row(row), Column(column), Value(value) {}
};
 
 
 
template<typename T>
struct GraphElement
{
    // there was other GUI-related variables
    T Data;
};
 
template <typename T>
class Graph
{
private:
    vector<GraphElement<T>> VertexList;
    vector<vector<int>> AdjMatrix;
 
public:
    Graph(vector<GraphElement<T>> vertices, vector<vector<int>> matrix) : VertexList(std::move(vertices)), AdjMatrix(std::move(matrix))
    {
        if (VertexList.size() != AdjMatrix.size())
            throw std::invalid_argument("vertices.size() != matrix.size()");
 
        for (const auto& row : AdjMatrix)
            if (row.size() != AdjMatrix.size())
                throw std::invalid_argument("non-square matrix");
    }
 
    size_t GetVertexCount()
    {
        return VertexList.size();
    }
 
    T GetVertex(size_t index)
    {
        return VertexList[index].Data;
    }
 
    bool CanSolveMerchantProblem()
    {
        if (VertexList.size() < 3)
            return false;
 
        bool result = true;
 
        for (size_t i = 0; i < AdjMatrix.size() && result; i++)
        {
            for (size_t j = 0; j < AdjMatrix.size() && result; j++)
                result = i == j || (AdjMatrix[i][j] != 0 && AdjMatrix[i][j] != -1);
        }
 
        return result;
    }
 
    map<T, T> SolveMerchantProblem()
    {
        vector<pair<T, T>> buffer;
        map<T, T> result;
 
        vector<vector<ElementOfMatrix>> BufferMatrix(AdjMatrix.size(), vector<ElementOfMatrix>(AdjMatrix.size()));
 
        //В задачу коммивояжера пути могут не существовать только на главной диагонали таблицы смежности
        for (size_t i = 0; i < AdjMatrix.size(); i++)
        {
            for (size_t j = 0; j < AdjMatrix.size(); j++)
            {
                if (i == j)
                {
                    BufferMatrix[i][j].exists = false;
                    BufferMatrix[i][j].value = 0;
                }
                else
                    BufferMatrix[i][j].value = AdjMatrix[i][j];
            }
        }
 
        cout << "Starting table: " << endl << endl;
 
        PrintTable(BufferMatrix);
 
        // TODO: figure out why was here int counter = 0;
 
        while (buffer.size() != VertexList.size())
        {
            cout << "----------------------" << endl << endl;
 
            PrintTable(BufferMatrix);
 
            vector<int> MinElementsOfRows;
 
            cout << endl <<"Row minimum elements:" << endl;
 
            for (size_t i = 0; i < BufferMatrix.size(); i++)
            {
                int minValue = startMinValue;
 
                for (size_t j = 0; j < BufferMatrix.size(); j++)
                {
                    if (BufferMatrix[i][j].exists)
                    {
                        if (minValue > BufferMatrix[i][j].value)
                            minValue = BufferMatrix[i][j].value;
                    }
                }
 
                if (minValue == startMinValue)
                    minValue = 0;
 
                cout << i << " : " << minValue << endl;
                MinElementsOfRows.push_back(minValue);
            }
 
            cout << "Matrix after row reduction:" << endl << endl;
 
            for (size_t i = 0; i < BufferMatrix.size(); i++)
            {
                for (size_t j = 0; j < BufferMatrix.size(); j++)
                {
                    if (BufferMatrix[i][j].value != 0)
                        BufferMatrix[i][j].value -= MinElementsOfRows[i];
                }
            }
 
            PrintTable(BufferMatrix);
 
            vector<int> MinElemntsOfColumns;
 
            cout << endl << endl << "Minimum column elements:" << endl;
 
            for (size_t i = 0; i < BufferMatrix.size(); i++)
            {
                int minValue = startMinValue;
 
                for (size_t j = 0; j < BufferMatrix.size(); j++)
                {
                    if (BufferMatrix[j][i].exists)
                    {
                        if (minValue > BufferMatrix[j][i].value)
                            minValue = BufferMatrix[j][i].value;
                    }
                }
 
                if (minValue == startMinValue)
                    minValue = 0;
 
                cout << i << " : " << minValue << endl;
 
                MinElemntsOfColumns.push_back(minValue);
            }
 
            for (size_t i = 0; i < BufferMatrix.size(); i++)
            {
                for (size_t j = 0; j < BufferMatrix.size(); j++)
 
                    if (BufferMatrix[j][i].value != 0)
                        BufferMatrix[j][i].value -= MinElemntsOfColumns[i];
            }
 
            cout << endl << "Matrix after second reduction: " << endl << endl;
 
            PrintTable(BufferMatrix);
 
            vector<ZeroElement> ZeroElements;
 
            for (size_t i = 0; i < BufferMatrix.size(); i++)
            {
                for (size_t j = 0; j < BufferMatrix.size(); j++)
                {
                    if (BufferMatrix[i][j].value == 0 && BufferMatrix[i][j].exists)
                    {
                        int minRow = startMinValue;
                        int minColumn = startMinValue;
 
                        for (size_t uj = 0; uj < BufferMatrix.size(); uj++)
                        {
                            if (BufferMatrix[i][uj].exists && j != uj)
                            {
                                if (minRow > BufferMatrix[i][uj].value)
                                    minRow = BufferMatrix[i][uj].value;
                            }
                        }
 
                        for (size_t ui = 0; ui < BufferMatrix.size(); ui++)
                        {
                            if (BufferMatrix[ui][j].exists && ui != i)
                            {
                                if (minColumn > BufferMatrix[ui][j].value)
                                    minColumn = BufferMatrix[ui][j].value;
                            }
                        }
 
                        if (minRow == startMinValue)
                            minRow = 0;
 
                        if (minColumn == startMinValue)
                            minColumn = 0;
 
                        ZeroElement element(i, j, minColumn + minRow);
                        ZeroElements.push_back(element);
                    }
                }
            }
 
            if (ZeroElements.empty())
            {
                cout << "No more zero elements, finding obvious routes" << endl;
 
                for (size_t i = 0; i < VertexList.size(); i++)
                {
                    bool flag = false;
 
                    if (result.find(VertexList[i].Data) == result.end())
                    {
                        for (size_t j = 0; j < VertexList.size() && !flag; j++)
                        {
                            if (i == j)
                                continue;
 
                            bool does_exist = false;
 
                            for (auto& elm : result)
                            {
                                if (elm.second == VertexList[j].Data)
                                {
                                    does_exist = true;
                                    break;
                                }
                            }
 
                            flag = !does_exist;
 
                            if (flag)
                                result[VertexList[i].Data] = VertexList[j].Data;
                        }
                    }
                }
 
                return result;
            }
 
            ZeroElement maxElement = ZeroElements[0];
 
            cout << "Zero elements:" << endl;
 
            for (size_t i = 0; i < ZeroElements.size(); i++)
                cout << ZeroElements[i].Row << " " << ZeroElements[i].Column << " " << ZeroElements[i].Value << endl;
 
            for (size_t i = 0; i < ZeroElements.size(); i++)
            {
                if (maxElement.Value < ZeroElements[i].Value)
                    maxElement = ZeroElements[i];
            }
 
            pair<T, T> to_add;
 
            to_add.first = VertexList[maxElement.Row].Data;
            to_add.second = VertexList[maxElement.Column].Data;
 
            for (size_t i = 0; i < buffer.size(); i++)
            {
                if (to_add.first == buffer[i].second)
                {
                    BufferMatrix[GetVertexIndex(to_add.second)][GetVertexIndex(buffer[i].first)].exists = false;
                    BufferMatrix[GetVertexIndex(to_add.second)][GetVertexIndex(buffer[i].first)].value = 0;
                }
            }
 
            buffer.push_back(to_add);
 
            cout << "Result pair: " << to_add.first << " " << to_add.second << endl;
 
            result[VertexList[maxElement.Row].Data] = VertexList[maxElement.Column].Data;
 
            for (size_t i = 0; i < BufferMatrix.size(); i++)
            {
                BufferMatrix[maxElement.Row][i].exists = false;
                BufferMatrix[maxElement.Row][i].value = 0;
            }
 
 
            for (size_t i = 0; i < BufferMatrix.size(); i++)
            {
                BufferMatrix[i][maxElement.Column].exists = false;
                BufferMatrix[i][maxElement.Column].value = 0;
            }
 
            BufferMatrix[maxElement.Row][maxElement.Column].exists = false;
            BufferMatrix[maxElement.Column][maxElement.Row].exists = false;
 
            BufferMatrix[maxElement.Row][maxElement.Column].value = 0;
            BufferMatrix[maxElement.Column][maxElement.Row].value = 0;
 
            cout << "Matrix after full reduction: " << endl << endl;
 
            PrintTable(BufferMatrix);
        }
 
        return result;
    }
 
    void PrintTable(vector<vector<ElementOfMatrix>> to_print)
    {
        if (VertexList.size() == 0)
        {
            cout << "PrintTable: VertexList empty" << endl;
            return;
        }
 
        size_t greatestLength = GetWidestLength();
        size_t dividerLength = (VertexList.size() + 1) * (greatestLength + 1);
 
        for (size_t i = 0; i < greatestLength; i++)
            cout << "_";
 
        cout << "|";
 
        for (size_t i = 0; i < VertexList.size(); i++)
        {
            PrintWithSpaces(VertexList[i].Data, greatestLength);
 
            cout << "|";
        }
 
        PrintDivideLine(dividerLength);
 
        for (size_t i = 0; i < AdjMatrix.size(); i++)
        {
            PrintWithSpaces(VertexList[i].Data, greatestLength);
 
            cout << "|";
 
            for (size_t j = 0; j < AdjMatrix.size(); j++)
            {
                if (!to_print[i][j].exists)
                    PrintWithSpaces("m", greatestLength);
                else
                    PrintWithSpaces(to_string(to_print[i][j].value), greatestLength);
 
                cout << "|";
            }
 
            PrintDivideLine(dividerLength);
        }
    }
 
    int GetWeight(T vertex1, T vertex2)
    {
        size_t v1index = GetVertexIndex(vertex1);
        size_t v2index = GetVertexIndex(vertex2);
 
        if (v1index == npos || v2index == npos)
        {
            cout << "GetWeight: out of bound" << endl;
            return -1;
        }
 
        int result = -1;
 
        if (AdjMatrix[v1index][v2index] == 0 || AdjMatrix[v1index][v2index] == -1)
        {
            if (AdjMatrix[v2index][v1index] != 0)
            {
                cout << "GetWeight: reverse path" << endl;
                result = AdjMatrix[v2index][v1index];
            }
        }
        else
            result = AdjMatrix[v1index][v2index];
 
        return result;
    }
 
    void Clear()
    {
        VertexList.clear();
        AdjMatrix.clear();
    }
 
private:
 
    size_t GetVertexIndex(T vertex)
    {
        size_t result = npos;
 
        for (size_t i = 0; i < VertexList.size() && result == npos; i++)
        {
            if (VertexList[i].Data == vertex)
                result = i;
        }
 
        return result;
    }
 
    size_t GetWidestLength()
    {
        size_t result = 0;
 
        for (size_t i = 0; i < VertexList.size(); i++)
        {
            string element = VertexList[i].Data;
 
            if (result < element.length())
                result = element.length();
        }
 
        for (size_t i = 0; i < VertexList.size(); i++)
        {
            for (size_t j = 0; j < VertexList.size(); j++)
            {
                string element = to_string(AdjMatrix[i][j]);
 
                if (result < element.length())
                    result = element.length();
            }
        }
 
        return result;
    }
 
    void PrintWithSpaces(const string& element, size_t maxLength)
    {
        cout << element;
 
        for (size_t u = 0; u < maxLength - element.length(); u++)
            cout << " ";
    }
 
    void PrintDivideLine(size_t Length)
    {
        cout << endl;
 
        for (size_t i = 0; i < Length; i++)
            cout << "-";
 
        cout << endl;
    }
};
 
int main() {
    Graph<string> mainGraph(
        std::vector<GraphElement<string>>{ {"A1"}, {"A2"}, {"A3"}, {"A4"}, {"A5"}, {"A6"}},
        std::vector<std::vector<int>>{
            std::vector<int>{ 0, 58, 65, 99, 51, 13},
            std::vector<int>{65,  0, 26, 30,  7, 50},
            std::vector<int>{52, 56,  0, 57, 50, 33},
            std::vector<int>{25,  1, 89,  0, 14, 17},
            std::vector<int>{86, 74, 22, 13,  0, 70},
            std::vector<int>{64,  6, 37, 57, 31,  0},
        }
    );
 
    string chosenElement = mainGraph.GetVertex(0);
 
    if (!mainGraph.CanSolveMerchantProblem()) {
        std::cout << "Impossible to solve" << '\n';
    } else {
        map<string, string> solution = mainGraph.SolveMerchantProblem();
 
        int totalDistance = 0;
        string current = chosenElement;
        string result = current;
        for (size_t i = 0; i < mainGraph.GetVertexCount(); i++) {
            result += " -> " + solution[current];
            totalDistance += mainGraph.GetWeight(current, solution[current]);
            current = solution[current];
        }
        cout << "Path: " << result << "\nTotal distance: " << totalDistance << endl;
    }
}