graph_example.cpp - master - matv3ys/QueueDriver

graph_example.cpp
357 строк14 KB
matv3ys
sparse graph
04 фев 2026, 12:26
04 фев 2026, 12:26656eb7b
#pragma once

#include <vector>
#include <set>
#include <unordered_map>
#include <stack>
#include <algorithm>
#include <stdexcept>
#include <iterator>

/**
 * Класс разреженного графа (SparseGraph).
 * 
 * vertex_type: Тип данных, на который указывают вершины графа.
 */
template <typename vertex_type>
class SparseGraph {
public:
    // Тип индекса для детерминированности
    using VertexID = unsigned;

protected:
    // Внутренняя структура, описывающая вершину
    struct VertexNode {
        vertex_type* ptr;            // Указатель на пользовательские данные
        std::set<VertexID> succs;    // Множество индексов последователей
        std::set<VertexID> preds;    // Множество индексов предшественников
        bool is_active;              // Флаг, занят ли слот (нужен для механизма переиспользования ID)

        VertexNode() : ptr(nullptr), is_active(false) {}
    };

    // Основное хранилище вершин. Индекс в векторе соответствует VertexID.
    std::vector<VertexNode> vertices_;

    // Стек свободных индексов для переиспользования памяти и ID (обеспечивает детерминированность)
    std::stack<VertexID> free_indices_;

    // Обратное соответствие: Указатель -> ID вершины.
    // Используем unordered_map для быстрого поиска O(1).
    std::unordered_map<vertex_type*, VertexID> ptr_to_id_;

    /**
     * Виртуальный метод-хук, вызываемый перед фактическим удалением вершины (очисткой слота).
     * Позволяет наследникам удалять связанные данные.
     */
    virtual void OnBeforeVertexRemoved(VertexID id) {
        // По умолчанию ничего не делаем
    }

public:
    // -------------------------------------------------------------------------
    // 4) Конструкторы
    // -------------------------------------------------------------------------
    
    SparseGraph() = default;

    explicit SparseGraph(size_t initial_capacity) {
        vertices_.reserve(initial_capacity);
        ptr_to_id_.reserve(initial_capacity);
    }

    virtual ~SparseGraph() = default;

    // -------------------------------------------------------------------------
    // Методы работы с вершинами
    // -------------------------------------------------------------------------

    /**
     * 5) Вставка вершины.
     * Сложность: Амортизированная O(1).
     */
    VertexID AddVertex(vertex_type* ptr) {
        if (!ptr) {
            throw std::invalid_argument("Vertex pointer cannot be null");
        }
        if (ptr_to_id_.find(ptr) != ptr_to_id_.end()) {
            // Вершина уже существует, возвращаем ее ID
            return ptr_to_id_[ptr];
        }

        VertexID id;
        if (!free_indices_.empty()) {
            // Переиспользуем старый индекс
            id = free_indices_.top();
            free_indices_.pop();
            // Слот уже существует, просто обновляем его
            vertices_[id].ptr = ptr;
            vertices_[id].succs.clear();
            vertices_[id].preds.clear();
            vertices_[id].is_active = true;
        } else {
            // Создаем новый слот
            id = static_cast<VertexID>(vertices_.size());
            VertexNode node;
            node.ptr = ptr;
            node.is_active = true;
            vertices_.push_back(node);
        }

        ptr_to_id_[ptr] = id;
        return id;
    }

    /**
     * 5) Удаление вершины (стандартное).
     * Удаляет вершину и все инцидентные ей ребра.
     * Сложность: O(deg(V) * log(N)) из-за обновлений set в соседях.
     */
    void RemoveVertex(vertex_type* ptr) {
        auto it = ptr_to_id_.find(ptr);
        if (it == ptr_to_id_.end()) return;

        VertexID id = it->second;
        RemoveVertexById(id);
    }

    // -------------------------------------------------------------------------
    // Методы работы с ребрами
    // -------------------------------------------------------------------------

    /**
     * 5) Вставка ребра.
     * Сложность: O(log(deg)) для std::set.
     */
    void AddEdge(vertex_type* from, vertex_type* to) {
        // Гарантируем, что вершины существуют (или добавляем их)
        VertexID u = AddVertex(from);
        VertexID v = AddVertex(to);

        if (u == v) return; // Игнорируем петли, если необходимо

        vertices_[u].succs.insert(v);
        vertices_[v].preds.insert(u);
    }

    /**
     * 5) Удаление ребра.
     * Сложность: O(log(deg)).
     */
    void RemoveEdge(vertex_type* from, vertex_type* to) {
        auto it_u = ptr_to_id_.find(from);
        auto it_v = ptr_to_id_.find(to);

        if (it_u == ptr_to_id_.end() || it_v == ptr_to_id_.end()) return;

        VertexID u = it_u->second;
        VertexID v = it_v->second;

        vertices_[u].succs.erase(v);
        vertices_[v].preds.erase(u);
    }

    // -------------------------------------------------------------------------
    // 6) "Умное" удаление с сохранением связности (Bypass)
    // -------------------------------------------------------------------------
    
    /**
     * Удаляет список вершин, связывая всех их предшественников со всеми их последователями.
     */
    void ContractVertices(const std::vector<vertex_type*>& vertices_to_remove) {
        for (auto* ptr : vertices_to_remove) {
            auto it = ptr_to_id_.find(ptr);
            if (it == ptr_to_id_.end()) continue;

            VertexID id = it->second;
            VertexNode& node = vertices_[id];

            // Для каждого предшественника (P) и каждого последователя (S) удаляемой вершины:
            // Создаем ребро P -> S.
            for (VertexID p_id : node.preds) {
                // Если p_id сам удаляется в этом цикле, связь все равно создается,
                // но будет обработана при удалении p_id (если порядок позволяет) 
                // или просто исчезнет. 
                // Обычно при "сжатии" важно соединить "входы" с "выходами".
                
                // Избегаем создания петель P -> P
                for (VertexID s_id : node.succs) {
                    if (p_id == s_id) continue;
                    
                    // Добавляем ребро P -> S
                    vertices_[p_id].succs.insert(s_id);
                    vertices_[s_id].preds.insert(p_id);
                }
            }

            // После перелинковки удаляем вершину штатным способом
            RemoveVertexById(id);
        }
    }

    // -------------------------------------------------------------------------
    // 8) Методы доступа и обратного соответствия
    // -------------------------------------------------------------------------

    bool HasVertex(vertex_type* ptr) const {
        return ptr_to_id_.find(ptr) != ptr_to_id_.end();
    }

    // Получить указатель по ID
    vertex_type* GetVertexPtr(VertexID id) const {
        if (id >= vertices_.size() || !vertices_[id].is_active) {
            return nullptr;
        }
        return vertices_[id].ptr;
    }

    // Получить ID по указателю
    VertexID GetVertexId(vertex_type* ptr) const {
        auto it = ptr_to_id_.find(ptr);
        if (it == ptr_to_id_.end()) {
            throw std::out_of_range("Vertex not found");
        }
        return it->second;
    }

    // Получить последователей (указатели)
    std::vector<vertex_type*> GetSuccessors(vertex_type* ptr) const {
        std::vector<vertex_type*> result;
        auto it = ptr_to_id_.find(ptr);
        if (it == ptr_to_id_.end()) return result;

        const auto& succs = vertices_[it->second].succs;
        result.reserve(succs.size());
        for (VertexID s_id : succs) {
            result.push_back(vertices_[s_id].ptr);
        }
        return result;
    }

    // Получить предшественников (указатели)
    std::vector<vertex_type*> GetPredecessors(vertex_type* ptr) const {
        std::vector<vertex_type*> result;
        auto it = ptr_to_id_.find(ptr);
        if (it == ptr_to_id_.end()) return result;

        const auto& preds = vertices_[it->second].preds;
        result.reserve(preds.size());
        for (VertexID p_id : preds) {
            result.push_back(vertices_[p_id].ptr);
        }
        return result;
    }

protected:
    // Внутренний метод удаления по ID
    void RemoveVertexById(VertexID id) {
        if (id >= vertices_.size() || !vertices_[id].is_active) return;

        // 1. Вызываем хук для наследников (Req 7)
        OnBeforeVertexRemoved(id);

        VertexNode& node = vertices_[id];

        // 2. Удаляем упоминания об этой вершине у соседей (Succ/Pred)
        // Удаляем id из списков последователей у предшественников
        for (VertexID p_id : node.preds) {
            if (p_id < vertices_.size() && vertices_[p_id].is_active) {
                vertices_[p_id].succs.erase(id);
            }
        }
        // Удаляем id из списков предшественников у последователей
        for (VertexID s_id : node.succs) {
            if (s_id < vertices_.size() && vertices_[s_id].is_active) {
                vertices_[s_id].preds.erase(id);
            }
        }

        // 3. Чистим мапу указателей
        ptr_to_id_.erase(node.ptr);

        // 4. Помечаем слот как свободный и очищаем данные
        node.is_active = false;
        node.ptr = nullptr;
        node.succs.clear();
        node.preds.clear();

        // 5. Возвращаем ID в пул свободных
        free_indices_.push(id);
    }
};

// =============================================================================
// 7) Пример класса-наследника с дополнительной информацией (Req 7)
// =============================================================================

/**
 * Расширенный граф, который хранит дополнительные данные для каждой вершины.
 * 
 * DataT: Тип данных, жестко привязанный к вершине.
 */
template <typename vertex_type, typename DataT>
class AugmentedSparseGraph : public SparseGraph<vertex_type> {
public:
    using Base = SparseGraph<vertex_type>;
    using VertexID = typename Base::VertexID;

private:
    // Хранилище дополнительных данных. 
    // Индекс соответствует VertexID из базового класса.
    std::vector<DataT> node_data_;

    // Вектор флагов инициализации, чтобы знать, есть ли данные в слоте
    // (опционально, зависит от того, есть ли у DataT конструктор по умолчанию)
    std::vector<bool> data_valid_;

protected:
    // Переопределяем хук удаления, чтобы чистить данные
    void OnBeforeVertexRemoved(VertexID id) override {
        if (id < data_valid_.size()) {
            data_valid_[id] = false;
            // Можно вызвать деструктор явно или присвоить дефолтное значение,
            // если DataT тяжелый объект.
            node_data_[id] = DataT(); 
        }
        // Вызов базовой логики не требуется, так как в базе он пустой, 
        // но для хорошего тона можно оставить.
        Base::OnBeforeVertexRemoved(id);
    }

public:
    AugmentedSparseGraph() = default;
    explicit AugmentedSparseGraph(size_t capacity) : Base(capacity) {
        node_data_.reserve(capacity);
        data_valid_.reserve(capacity);
    }

    /**
     * Добавление вершины с прикрепленными данными.
     */
    void AddVertexWithData(vertex_type* ptr, const DataT& data) {
        // Добавляем вершину через базовый класс, получаем ID
        VertexID id = this->AddVertex(ptr);

        // Расширяем вектора данных, если нужно
        if (id >= node_data_.size()) {
            node_data_.resize(id + 1);
            data_valid_.resize(id + 1, false);
        }

        node_data_[id] = data;
        data_valid_[id] = true;
    }

    /**
     * Получение данных по указателю на вершину.
     */
    DataT* GetData(vertex_type* ptr) {
        if (!this->HasVertex(ptr)) return nullptr;
        VertexID id = this->GetVertexId(ptr);
        
        if (id < data_valid_.size() && data_valid_[id]) {
            return &node_data_[id];
        }
        return nullptr;
    }
};