directedgraph.cpp

#include "graph.h"
#include "directedgraph.h"
#include <algorithm>
#include <stack>
#include <queue>
#include <climits>
#include <set>

void DirectedGraph::generateGraph(bool allowNegativeWeights) {
    generateGraph(allowNegativeWeights, -1);
}

void DirectedGraph::generateGraph(bool allowNegativeWeights, int edgeCount = -1) {
    std::random_device rd;
    std::mt19937 gen(rd());

    int minW = allowNegativeWeights ? DEFAULT_NMIN_WEIGHT : DEFAULT_MIN_WEIGHT;
    int maxW = DEFAULT_MAX_WEIGHT;

    std::uniform_int_distribution<int> weightDist(minW, maxW);

    clearMatrix();


    generateConnectedDAG(gen, weightDist);
    generateCapacityAndCostMatrices(gen);
}

void DirectedGraph::addEdge(int from, int to, int weight){
    validateVertex(from);
    validateVertex(to);
    set(from, to, weight);
}

void DirectedGraph::printInfo() const {
    std::cout << "Directed Graph (may be disconnected)\n";
    std::cout << "Vertices: " << getRows() << "\n";

    int edgeCount = 0;
    for (int i = 0; i < getRows(); ++i) {
        for (int j = 0; j < getCols(); ++j) {
            if (get(i, j)) edgeCount++;
        }
    }
    std::cout << "Edges: " << edgeCount << "\n";

    auto [minW, maxW] = findMinMaxWeights();
    std::cout << "Min weight: " << minW << ", Max weight: " << maxW << "\n";
}

void DirectedGraph::clearMatrix() {
    for (int i = 0; i < getRows(); ++i) {
        for (int j = 0; j < getCols(); ++j) {
            set(i, j, 0);
        }
    }
}

void DirectedGraph::generateConnectedDAG(std::mt19937& gen,
                           std::uniform_int_distribution<int>& weightDist) {
    int vertices = getRows();


    for (int i = 0; i < vertices - 1; ++i) {
        int weight;
           do {
               weight = weightDist(gen);
           } while (weight == 0);
        set(i, i + 1, weight);
    }


    std::uniform_real_distribution<double> probDist(0.0, 1.0);
    for (int i = 0; i < vertices; ++i) {
        for (int j = i + 1; j < vertices; ++j) {
            if (i + 1 != j) {
                double distance = j - i;
                double prob = champernownePDF(distance);

                if (probDist(gen) < prob) {
                    int weight;
                    do {
                        weight = weightDist(gen);
                    } while (weight == 0);
                    set(i, j, weight);
                }
            }
        }
    }
}

Graph::ShimbelResult DirectedGraph::calculateShimbelGeneral() const {
    int n = getRows();
    ShimbelResult result;


    result.min_paths = std::vector<std::vector<int>>(n, std::vector<int>(n, INT_MAX));
    result.max_paths = std::vector<std::vector<int>>(n, std::vector<int>(n, INT_MIN));
    result.reachable = std::vector<std::vector<bool>>(n, std::vector<bool>(n, false));


    for (int i = 0; i < n; ++i) {
        result.min_paths[i][i] = 0;
        result.max_paths[i][i] = 0;
        result.reachable[i][i] = true;

        for (int j = 0; j < n; ++j) {
            if (get(i, j) != 0) {
                result.min_paths[i][j] = get(i, j);
                result.max_paths[i][j] = get(i, j);
                result.reachable[i][j] = true;
            }
        }
    }


    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (result.min_paths[i][k] != INT_MAX && result.min_paths[k][j] != INT_MAX) {
                    if (result.min_paths[i][j] > result.min_paths[i][k] + result.min_paths[k][j]) {
                        result.min_paths[i][j] = result.min_paths[i][k] + result.min_paths[k][j];
                        result.reachable[i][j] = true;
                    }
                }

                if (result.max_paths[i][k] != INT_MIN && result.max_paths[k][j] != INT_MIN) {
                    if (result.max_paths[i][j] < result.max_paths[i][k] + result.max_paths[k][j]) {
                        result.max_paths[i][j] = result.max_paths[i][k] + result.max_paths[k][j];
                        result.reachable[i][j] = true;
                    }
                }
            }
        }
    }

    return result;
}

Graph::ShimbelResult DirectedGraph::calculateShimbel(int steps) const {
    int n = getRows();
    ShimbelResult result;


    result.min_paths = std::vector<std::vector<int>>(n, std::vector<int>(n, INT_MAX));
    result.max_paths = std::vector<std::vector<int>>(n, std::vector<int>(n, INT_MIN));
    result.reachable = std::vector<std::vector<bool>>(n, std::vector<bool>(n, false));


    if (steps == 0) {
        for (int i = 0; i < n; ++i) {
            result.min_paths[i][i] = 0;
            result.max_paths[i][i] = 0;
            result.reachable[i][i] = true;
        }
        return result;
    }


    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (get(i, j) != 0) {
                result.min_paths[i][j] = get(i, j);
                result.max_paths[i][j] = get(i, j);
                result.reachable[i][j] = true;
            }
        }
    }


    for (int s = 2; s <= steps; ++s) {
        auto temp_min = std::vector<std::vector<int>>(n, std::vector<int>(n, INT_MAX));
        auto temp_max = std::vector<std::vector<int>>(n, std::vector<int>(n, INT_MIN));
        auto temp_reachable = std::vector<std::vector<bool>>(n, std::vector<bool>(n, false));

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                for (int k = 0; k < n; ++k) {

                    if (result.reachable[i][k] && get(k, j) != 0) {

                        int new_min = result.min_paths[i][k] + get(k, j);
                        if (new_min < temp_min[i][j]) {
                            temp_min[i][j] = new_min;
                        }


                        int new_max = result.max_paths[i][k] + get(k, j);
                        if (new_max > temp_max[i][j]) {
                            temp_max[i][j] = new_max;
                        }

                        temp_reachable[i][j] = true;
                    }
                }
            }
        }

        result.min_paths = temp_min;
        result.max_paths = temp_max;
        result.reachable = temp_reachable;
    }

    return result;
}

Graph::PathResult DirectedGraph::findPaths(int from, int to, int maxSteps) const {
    PathResult result;
    result.exists = false;
    result.count = 0;

    validateVertex(from);
    validateVertex(to);


    std::vector<int> currentPath;
    findAllPaths(from, to, maxSteps, currentPath, result);

    return result;
}

void DirectedGraph::findAllPaths(int current, int target, int stepsLeft,
                               std::vector<int>& path, PathResult& result) const {
    path.push_back(current);


    if (current == target && path.size() > 1) {
        result.exists = true;
        result.count++;
        result.paths.push_back(path);
    }


    if (stepsLeft != 0) {
        for (int next = 0; next < getRows(); ++next) {
            if (get(current, next) != 0) {
                int newStepsLeft = (stepsLeft == -1) ? -1 : stepsLeft - 1;
                findAllPaths(next, target, newStepsLeft, path, result);
            }
        }
    }

    path.pop_back();
}

Graph::BellmanFordResult DirectedGraph::bellmanFord(int source) const {
    int n = getRows();
    BellmanFordResult result;
    result.iterations = 0;
    result.distances.assign(n, INT_MAX);
    result.predecessors.assign(n, -1);
    result.hasNegativeCycle = false;
    result.distances[source] = 0;


    std::queue<int> vertexQueue;
    std::vector<bool> inQueue(n, false);
    std::vector<int> relaxCount(n, 0);

    vertexQueue.push(source);
    inQueue[source] = true;
    relaxCount[source] = 1;


    while (!vertexQueue.empty()) {
        int u = vertexQueue.front();
        vertexQueue.pop();
        inQueue[u] = false;


        for (int v = 0; v < n; ++v) {
            result.iterations++;
            int weight = get(u, v);
            if (weight != 0 && result.distances[u] != INT_MAX) {
                if (result.distances[v] > result.distances[u] + weight) {
                    result.distances[v] = result.distances[u] + weight;
                    result.predecessors[v] = u;
                    relaxCount[v]++;
                    result.iterations++;


                    if (relaxCount[v] > n) {
                        result.hasNegativeCycle = true;


                        int cycleVertex = v;
                        for (int i = 0; i < n; ++i) {
                            cycleVertex = result.predecessors[cycleVertex];
                        }


                        std::vector<bool> inCycle(n, false);
                        for (int v = cycleVertex; ; v = result.predecessors[v]) {
                            if (inCycle[v]) break;
                            inCycle[v] = true;
                        }


                        for (int v = 0; v < n; ++v) {
                            if (inCycle[v]) {
                                result.distances[v] = INT_MIN;
                            }
                        }

                        return result;
                    }

                    if (!inQueue[v]) {
                        vertexQueue.push(v);
                        inQueue[v] = true;
                    }
                }
            }
        }
    }

    return result;
}

std::vector<int> DirectedGraph::getPath(int from, int to,
                                      const std::vector<int>& predecessors,
                                      const std::vector<int>& distances) const {
    std::vector<int> path;


    if (from == to) {
        path.push_back(from);
        return path;
    }


    if (predecessors[to] == -1 || distances[to] == INT_MAX) {
        return path;
    }


    for (int v = to; v != -1; v = predecessors[v]) {
        path.push_back(v);

        if (path.size() > predecessors.size()) {
            return std::vector<int>();
        }
    }


    std::reverse(path.begin(), path.end());

    if (path.empty() || path[0] != from) {
        return std::vector<int>();
    }

    return path;
}


void DirectedGraph::generateCapacityAndCostMatrices(std::mt19937& gen) {
    int n = getRows();
    std::uniform_int_distribution<int> costDist(1, 5);


    capacityMatrix.assign(n, std::vector<int>(n, 0));
    costMatrix.assign(n, std::vector<int>(n, 0));

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            int weight = get(i, j);

            if (weight != 0) {

                int capacity = std::max(0, weight);
                capacityMatrix[i][j] = capacity;


                costMatrix[i][j] = costDist(gen);
            } else {
                capacityMatrix[i][j] = 0;
                costMatrix[i][j] = 0;
            }
        }
    }
}


std::vector<std::vector<int>> DirectedGraph::getCapacityMatrix() const {
    return capacityMatrix;
}

std::vector<std::vector<int>> DirectedGraph::getCostMatrix() const {
    return costMatrix;
}


bool DirectedGraph::bfsFordFulkerson(int s, int t, const std::vector<std::vector<int>>& residualGraph, std::vector<int>& parent) const {
    int n = getRows();
    std::fill(parent.begin(), parent.end(), -1);
    parent[s] = -2;

    std::queue<std::pair<int, int>> q;
    q.push({s, INT_MAX});

    while (!q.empty()) {
        int u = q.front().first;
        int current_flow = q.front().second;
        q.pop();

        for (int v = 0; v < n; ++v) {

            if (parent[v] == -1 && residualGraph[u][v] > 0) {
                parent[v] = u;
                int new_flow = std::min(current_flow, residualGraph[u][v]);

                if (v == t) {
                    return true;
                }
                q.push({v, new_flow});
            }
        }
    }
    return false;
}


DirectedGraph::MaxFlowResult DirectedGraph::maxFlowFordFulkerson(int source, int sink) const {
    MaxFlowResult result;
    int n = getRows();


    try {
        validateVertex(source);
        validateVertex(sink);
    } catch (const std::out_of_range& e) {
        result.success = false;
        result.message = "Некорректный исток или сток.";
        return result;
    }
    if (source == sink) {
        result.success = false;
        result.message = "Исток и сток не могут совпадать.";
        return result;
    }


    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (capacityMatrix[i][j] < 0) {
                result.success = false;
                result.message = "Ошибка: Обнаружена отрицательная пропускная способность.";
                return result;
            }
        }
    }


    std::vector<std::vector<int>> residualGraph = capacityMatrix;

    result.flowMatrix.assign(n, std::vector<int>(n, 0));
    std::vector<int> parent(n);
    result.maxFlowValue = 0;
    result.iterations = 0;


    while (bfsFordFulkerson(source, sink, residualGraph, parent)) {
        result.iterations++;


        int pathFlow = INT_MAX;
        for (int v = sink; v != source; v = parent[v]) {
            int u = parent[v];
            pathFlow = std::min(pathFlow, residualGraph[u][v]);
        }

        if (pathFlow == 0) {
            break;
        }


        for (int v = sink; v != source; v = parent[v]) {
            int u = parent[v];
            residualGraph[u][v] -= pathFlow;
            residualGraph[v][u] += pathFlow;

        }


        result.maxFlowValue += pathFlow;
    }


    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (capacityMatrix[i][j] > 0) {

                result.flowMatrix[i][j] = capacityMatrix[i][j] - residualGraph[i][j];

                if (result.flowMatrix[i][j] < 0) result.flowMatrix[i][j] = 0;
            } else {
                result.flowMatrix[i][j] = 0;
            }
        }
    }

    result.success = true;
    result.message = "Максимальный поток успешно найден.";
    return result;
}

DirectedGraph::MinCostFlowResult DirectedGraph::minCostFlow(int source, int sink, int targetFlow) const {
    MinCostFlowResult result;
    int n = getRows();


    try {
        validateVertex(source);
        validateVertex(sink);
    } catch (const std::out_of_range& e) {
        result.success = false;
        result.message = "Некорректный исток или сток.";
        return result;
    }
    if (source == sink) {
        result.success = false;
        result.message = "Исток и сток не могут совпадать.";
        return result;
    }
     if (targetFlow < 0) {
        result.success = false;
        result.message = "Целевой поток не может быть отрицательным.";
        return result;
    }
    if (targetFlow == 0) {
        result.success = true;
        result.targetReached = true;
        result.message = "Целевой поток равен 0.";
        result.flowMatrix.assign(n, std::vector<int>(n, 0));
        return result;
    }



    if (costMatrix.empty() || costMatrix.size() != n || costMatrix[0].size() != n) {
         result.success = false;
         result.message = "Матрица стоимостей не инициализирована корректно.";
         return result;
    }



    result.flowMatrix.assign(n, std::vector<int>(n, 0));
    result.totalCost = 0;
    result.flowAmount = 0;
    result.iterations = 0;


    while (result.flowAmount < targetFlow) {
        result.iterations++;


        std::vector<long long> distances(n, LLONG_MAX);
        std::vector<int> predecessors(n, -1);
        std::vector<int> edge_type(n, 0);

        distances[source] = 0;


        for (int iter = 1; iter < n; ++iter) {
            bool updated = false;

            for (int u = 0; u < n; ++u) {
                 if (distances[u] == LLONG_MAX) continue;

                for (int v = 0; v < n; ++v) {

                    int cap_uv = capacityMatrix[u][v];
                    int flow_uv = result.flowMatrix[u][v];
                    if (cap_uv > 0 && flow_uv < cap_uv) {
                        int cost_uv = costMatrix[u][v];
                        long long new_dist = distances[u] + cost_uv;
                        if (new_dist < distances[v]) {
                            distances[v] = new_dist;
                            predecessors[v] = u;
                            edge_type[v] = 1;
                            updated = true;
                        }
                    }



                     int flow_vu = result.flowMatrix[v][u];
                    if (capacityMatrix[v][u] > 0 && flow_vu > 0) {
                        int cost_vu = costMatrix[v][u];
                        long long new_dist = distances[u] - cost_vu;
                        if (new_dist < distances[v]) {
                            distances[v] = new_dist;
                            predecessors[v] = u;
                            edge_type[v] = -1;
                            updated = true;
                        }
                    }
                }
            }
             if (!updated) break;
        }







        if (distances[sink] == LLONG_MAX) {
            result.message = "Сток недостижим в остаточной сети. Невозможно достичь целевой поток.";
            result.success = false;
            break;
        }


        int deltaFlow = INT_MAX;
        int pathCost = 0;


        deltaFlow = std::min(deltaFlow, targetFlow - result.flowAmount);


        int current_v = sink;
        while (current_v != source) {
            int prev_u = predecessors[current_v];
            if (prev_u == -1) {
                result.success = false;
                result.message = "Ошибка восстановления пути.";
                return result;
            }

            int type = edge_type[current_v];
            int capacity_on_edge;

            if (type == 1) {
                capacity_on_edge = capacityMatrix[prev_u][current_v] - result.flowMatrix[prev_u][current_v];
            } else if (type == -1) {
                capacity_on_edge = result.flowMatrix[current_v][prev_u];
            } else {
                 result.success = false;
                 result.message = "Ошибка типа ребра при восстановлении пути.";
                 return result;
            }

            deltaFlow = std::min(deltaFlow, capacity_on_edge);
            current_v = prev_u;
        }



        if (deltaFlow <= 0) {

             break;
        }



        result.flowAmount += deltaFlow;
        result.totalCost += (long long)deltaFlow * distances[sink];
        result.targetFlowValue = targetFlow;


        current_v = sink;
        while (current_v != source) {
            int prev_u = predecessors[current_v];
            int type = edge_type[current_v];

            if (type == 1) {
                result.flowMatrix[prev_u][current_v] += deltaFlow;
            } else if (type == -1) {
                result.flowMatrix[current_v][prev_u] -= deltaFlow;
            }
            current_v = prev_u;
        }
    }


    if (result.flowAmount >= targetFlow) {
        result.targetReached = true;
        result.message = "Целевой поток достигнут.";



    } else if (result.success) {
         result.message = "Достигнут максимально возможный поток ("
                        + std::to_string(result.flowAmount)
                        + "), который меньше целевого ("
                        + std::to_string(targetFlow) + ").";
         result.success = false;
    }


    return result;
}