dynamic_graph.h

/*
   Copyright 2020 František Bráblík
 
   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at
 
       http://www.apache.org/licenses/LICENSE-2.0
 
   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.
*/
#pragma once
 
#include "graph.h"
#include "node.h"
#include "edge.h"
#include "exceptions.h"
 
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <functional> // std::function
#include <utility> // std::move
#include <algorithm> // std::max_element, std::max
 
namespace dyng {
 
 
class dynamic_graph {
public:
    dynamic_graph() = default;
 
    node_id add_node(unsigned time) {
        node_id id = m_last_node_id++;
        add_modification(time, [n = node(id)](graph_state& graph){
            graph.push_node(std::move(n));
        });
        return id;
    }
 
    edge_id add_edge(unsigned time, node_id one, node_id two) {
        edge_id id = m_last_edge_id++;
        add_modification(time, [e = edge(id, one, two)](graph_state& graph){
            graph.push_edge(std::move(e));
        });
        return id;
    }
 
    void remove_node(unsigned time, node_id id) {
        add_modification(time, [id](graph_state& graph){
            graph.remove_node(id);
        });
    }
 
    void remove_edge(unsigned time, edge_id id) {
        add_modification(time, [id](graph_state& graph){
            graph.remove_edge(id);
        });
    }
 
    void build() {
        m_states.clear();
        apply_modifications();
        set_bool_values();
    }
 
    void build(std::vector<graph_state> states) {
        m_modifications.clear();
        m_states = std::move(states);
        set_bool_values();
        recalculate_ids();
    }
 
    void clear() {
        m_states.clear();
        m_modifications.clear();
    }
 
 
    std::vector<graph_state>& states() { return m_states; }
 
 
    const std::vector<graph_state>& states() const { return m_states; }
 
 
    unsigned node_count() const { return m_last_node_id; }
 
 
    unsigned edge_count() const { return m_last_edge_id; }
 
private:
    unsigned m_last_node_id = 0;
    unsigned m_last_edge_id = 0;
 
    std::vector<graph_state> m_states;
    std::vector<std::vector<std::function<void(graph_state&)>>> m_modifications;
 
 
    void add_modification(unsigned time, std::function<void(graph_state&)> operation) {
        if (time >= m_modifications.size()) {
            m_modifications.resize(time + 1);
        }
        m_modifications[time].push_back(operation);
    }
 
    void apply_modifications() {
        m_states.reserve(m_modifications.size());
        for (const auto& mod : m_modifications) {
            graph_state new_state;
            if (!m_states.empty()) {
                new_state = m_states.back();
            }
            for (const auto& operation : mod) {
                operation(new_state);
            }
            m_states.push_back(std::move(new_state));
        }
        // remove applied modifications
        m_modifications.clear();
    }
 
    void recalculate_ids() {
        auto id_comp = [](const auto& a, const auto& b){ return a.id() < b.id(); };
        auto max_id = [id_comp](auto begin, auto end){
            return std::max_element(begin, end, id_comp)->id().value;
        };
        for (const auto& state : m_states) {
            if (!state.nodes().empty()) {
                m_last_node_id = std::max(m_last_node_id,
                        max_id(state.nodes().begin(), state.nodes().end()) + 1);
            }
            if (!state.edges().empty()) {
                m_last_edge_id = std::max(m_last_edge_id,
                        max_id(state.edges().begin(), state.edges().end()) + 1);
            }
        }
    }
 
    void set_bool_values() {
        for (unsigned i = 0; i < m_states.size(); ++i) {
            for (auto& node : m_states[i].nodes()) {
                node.is_old((i < m_states.size() - 1)
                        && !m_states[i + 1].node_exists(node.id()));
                node.is_new((i > 0)
                        && !m_states[i - 1].node_exists(node.id()));
            }
            for (auto& edge : m_states[i].edges()) {
                edge.is_old((i < m_states.size() - 1)
                        && !m_states[i + 1].edge_exists(edge.id()));
                edge.is_new((i > 0)
                        && !m_states[i - 1].edge_exists(edge.id()));
            }
        }
    }
};
 
} // namespace dyng