graph.cpp - master - annabasalyga/Traffic_simulator

graph.cpp
361 строка10 KB
Anna
Final version n.1
22 янв 2026, 15:55
22 янв 2026, 15:55d0e56e2
#include <iostream>

#include "graph.h"


DirectedGraph::DirectedGraph() {
    if (!font.loadFromFile("font.ttf")) {
        std::cerr << "Failed to load font.ttf\n";
    }
}

int DirectedGraph::getBestPathIndex() const {
    return bestPathIndex;
}

int DirectedGraph::getAlternativePathIndex() const {
    return alternativePathIndex;
}

void DirectedGraph::addVertex(int id, sf::Vector2f pos) {
    positions[id] = pos;
}

void DirectedGraph::changeVertexPos(int id, sf::Vector2f pos) {
    return addVertex(id, pos);
}

sf::Vector2f DirectedGraph::getVertexPos(int id) {
    return positions[id];
}

void DirectedGraph::addEdge(int from, int to) {
    Edge e;
    e.from = from;
    e.to = to;

    adj[from].push_back(e);
}

void DirectedGraph::updateEdgeLoad(int from, int to, int load) {
    for (auto& e : adj[from]) {
        if (e.to == to) {
            e.currentLoad = load;
            std::cout << "Load was changed to " << load << std::endl;
            break;
        }
    }
    recalc();
}

void DirectedGraph::updateHistory() {
    for (auto& [u, edges] : adj) {
        for (auto& e : edges) {
            e.history.push_back(e.currentLoad);
        }
    }
}

void DirectedGraph::setStartEnd(int s, int e) {
    start = s;
    end = e;
    findAllPaths();
}

void DirectedGraph::findAllPaths() {
    allPaths.clear();
    if (start < 0 || end < 0) return;
    std::vector<int> path{ start };
    std::map<int, bool> used;
    dfs(start, path, used);
    recalc();
}

const std::vector<std::vector<int>>& DirectedGraph::getPaths() const {
    return allPaths;
}

bool DirectedGraph::isPointOnEdge(sf::Vector2f p, const Edge& e, float tolerance) {
    sf::Vector2f a = positions[e.from];
    sf::Vector2f b = positions[e.to];

    sf::Vector2f ap = p - a;
    sf::Vector2f ab = b - a;

    float ab2 = ab.x * ab.x + ab.y * ab.y;
    float t = std::max(0.f, std::min(1.f, (ap.x * ab.x + ap.y * ab.y) / ab2));

    sf::Vector2f closest = a + ab * t;
    float dist = std::hypot(p.x - closest.x, p.y - closest.y);

    return dist <= tolerance;
}

DirectedGraph::Edge* DirectedGraph::getEdgeAt(sf::Vector2f p) {
    for (auto& [u, edges] : adj) {
        for (auto& e : edges) {
            if (isPointOnEdge(p, e)) {
                return &e;
            }
        }
    }
    return nullptr;
}

int DirectedGraph::getVertexAt(sf::Vector2f p) {
    for (auto& [id, pos] : positions) {
        if (std::hypot(p.x - pos.x, p.y - pos.y) < 20) {
            return id;
        }
    }
    return -1;
}

double DirectedGraph::predictEdge(const Edge& e) const {
    if (e.history.empty()) {
        return e.currentLoad;
    }
    
    double sum = 0;
    for (int v : e.history) {
        sum += v;
    }

    return sum / e.history.size();
}

double DirectedGraph::predictPath(const std::vector<int>& path) const {
    double predCost = 0;
    for (size_t i = 0; i + 1 < path.size(); ++i) {
        for (const auto& e : adj.at(path[i])) {
            if (e.to == path[i + 1]) {
                predCost += predictEdge(e);
                break;
            }
        }
    }
    return predCost;
}

double DirectedGraph::pathCost(const std::vector<int>& path) const {
    double cost = 0;
    for (size_t i = 0; i + 1 < path.size(); ++i) {
        for (const auto& e : adj.at(path[i])) {
            if (e.to == path[i + 1]) {
                cost += e.currentLoad;
                break;
            }
        }
    }
    return cost;
}

void DirectedGraph::draw(sf::RenderWindow& win) {
    for (auto& [u, edges] : adj) {
        for (auto& e : edges) {

            bool inBest = false;
            bool inAlt = false;
            bool isSelected = (u == selectedFrom && e.to == selectedTo);

            if (alternativePathIndex != -1) {
                const auto& alternative = allPaths[alternativePathIndex];
                for (size_t j = 0; j + 1 < alternative.size(); ++j) {
                    if (alternative[j] == u && alternative[j + 1] == e.to) {
                        inAlt = true;
                        break;
                        /*col = sf::Color(120, 0, 255);*/ // ����������
                    }
                }
            }


            if (bestPathIndex != -1) {
                const auto& best = allPaths[bestPathIndex];
                for (size_t j = 0; j + 1 < best.size(); ++j) {
                    if (best[j] == u && best[j + 1] == e.to) {
                        inBest = true;
                        break;
                        /*col = sf::Color::Green;*/
                    }

                }
            }

            sf::Color col;

            if (inBest && inAlt) {
                col = sf::Color::White;
            }
            else if (inBest) {
                col = sf::Color::Green;
            }
            else if (inAlt) {
                col = sf::Color(120, 0, 255);
            }
            else {
                col = sf::Color(150, 150, 150);
            }

            sf::Vector2f a = positions[u];
            sf::Vector2f b = positions[e.to];

            // �����������
            sf::Vector2f dir = b - a;
            float len = std::sqrt(dir.x * dir.x + dir.y * dir.y);
            if (len == 0) continue;
            dir /= len;

            sf::Vector2f normal(-dir.y, dir.x);

            float vertexRadius = 20.f;
            float thickness = isSelected ? 10.f : 6.f;
            float arrowLength = 30.f;
            float arrowWidth = 18.f;

            // �����
            sf::Vector2f start = a + dir * vertexRadius;
            sf::Vector2f end = b - dir * (vertexRadius + arrowLength * 0.6f);

            sf::Vertex body[4];
            body[0].position = start + normal * thickness * 0.5f;
            body[1].position = start - normal * thickness * 0.5f;
            body[2].position = end - normal * thickness * 0.5f;
            body[3].position = end + normal * thickness * 0.5f;

            sf::Vector2f mid = (positions[u] + positions[e.to]) / 2.f;

            if (inBest && inAlt) {
                // ������ � ����������
                body[0].color = sf::Color(120, 0, 255);
                body[1].color = sf::Color(120, 0, 255);

                // ����� � ������
                body[2].color = sf::Color::Green;
                body[3].color = sf::Color::Green;
            }
            else if (inBest) {
                for (auto& v : body)
                    v.color = sf::Color::Green;
            }
            else if (inAlt) {
                for (auto& v : body)
                    v.color = sf::Color(120, 0, 255);
            }
            else {
                for (auto& v : body)
                    v.color = sf::Color(150, 150, 150);
            }

            win.draw(body, 4, sf::Quads);

            // ���������
            sf::Vector2f tip = b - dir * vertexRadius;
            sf::Vector2f base = tip - dir * arrowLength;

            sf::Vector2f left = base + normal * arrowWidth * 0.5f;
            sf::Vector2f right = base - normal * arrowWidth * 0.5f;

            sf::Color arrowColor =
                inBest ? sf::Color::Green :
                inAlt ? sf::Color(120, 0, 255) :
                sf::Color(150, 150, 150);

            sf::Vertex arrow[3] = {
                sf::Vertex(tip, arrowColor),
                sf::Vertex(left, arrowColor),
                sf::Vertex(right, arrowColor)
            };

            win.draw(arrow, 3, sf::Triangles);

            // load
            sf::Text t;
            t.setFont(font);
            t.setCharacterSize(24);
            t.setFillColor(sf::Color::Black);
            t.setString(std::to_string(e.currentLoad));
            t.setPosition(mid);
            win.draw(t);
        }
    }

    // �������
    for (const auto& [id, pos] : positions) {
        float R = 20.f;
        sf::CircleShape c(R);
        c.setPosition(pos - sf::Vector2f(R, R));

        if (id == start) c.setFillColor(sf::Color::White);
        else if (id == end) c.setFillColor(sf::Color::Black);
        else c.setFillColor(sf::Color(100, 200, 255));

        win.draw(c);
    }
}

void DirectedGraph::dfs(int v, std::vector<int>& path, std::map<int, bool>& used) {
    if (v == end) {
        allPaths.push_back(path);
        return;
    }
    used[v] = true;
    for (auto& e : adj[v]) {
        if (!used[e.to]) {
            path.push_back(e.to);
            dfs(e.to, path, used);
            path.pop_back();
        }
    }
    used[v] = false;

    /*for (size_t i = 0; i < allPaths.size(); ++i) {
        for (size_t j = 0; j < allPaths[i].size(); ++j) {
            std::cout << allPaths[i][j] << " ";
        }
        std::cout << std::endl;
    }*/
}

void DirectedGraph::recalc() {
    bestPathIndex = -1;
    alternativePathIndex = -1;

    if (allPaths.empty()) {
        std::cout << "No paths" << std::endl;
        return;
    }

    double minCost = std::numeric_limits<double>::max();
    for (size_t i = 0; i < allPaths.size(); ++i) {
        double c = pathCost(allPaths[i]);
        if (c < minCost) {
            minCost = c;
            bestPathIndex = static_cast<int>(i);
            std::cout << "New best path (cost: " << c << ")";
        }
    }

    size_t minLength = std::numeric_limits<size_t>::max();
    double minCostForLength = std::numeric_limits<double>::max();

    for (size_t i = 0; i < allPaths.size(); ++i) {
        if (static_cast<int>(i) == bestPathIndex) continue;

        size_t currentLength = allPaths[i].size();
        double currentCost = pathCost(allPaths[i]);

        if (currentLength < minLength) {
            minLength = currentLength;
            minCostForLength = currentCost;
            alternativePathIndex = static_cast<int>(i);
        }

        else if (currentLength == minLength) {
            if (currentCost < minCostForLength) {
                minCostForLength = currentCost;
                alternativePathIndex = static_cast<int>(i);
            }
        }
    }
}