https://github.com/tue-alga/CoordinatedSchematization
Raw File
Tip revision: 9ffc292c946498d56f7938a86628adba534a9085 authored by TUE\bacusters on 01 July 2021, 09:20:10 UTC
Add base schematization library
Tip revision: 9ffc292
EdgeTrackingObserver.cpp
#include "SchematLib/MapSimplification/EdgeTrackingObserver.h"
namespace SchematLib::MapSimplification
{
    void EdgeTrackingObserver::lockIncrementTimestamp()
    {
        if (m_timestepLocked) return;
        ++timeStamp;
        m_timestepLocked = true;
    }

    void EdgeTrackingObserver::unlockIncrementTimestamp()
    {
        m_timestepLocked = false;
    }

    bool EdgeTrackingObserver::hasEdge(std::size_t edgeID) const
    {
        return m_edgeMapping.find(edgeID) != m_edgeMapping.end();
    }

    bool EdgeTrackingObserver::hasVertex(std::size_t edgeID) const
    {
        return m_vertexMapping.find(edgeID) != m_vertexMapping.end();
    }

    std::pair<bool, std::size_t> EdgeTrackingObserver::edgePathExists(const EdgePath& path) const
    {
        if (m_edgePathToId.find(path) != m_edgePathToId.end())
        {
            return {true, m_edgePathToId.at(path)};
        }
        /*auto reverted = path.reverted();
        if (m_edgePathToId.find(reverted) != m_edgePathToId.end())
        {
            return { true, m_edgePathToId.at(reverted) };
        }*/
        return {false, 0};
    }

    std::size_t EdgeTrackingObserver::addEdgePath(EdgePath&& path)
    {
        auto localPath = std::move(path);
        localPath.id = m_currentEdgePathId;
        ++m_currentEdgePathId;
        m_edgePaths[localPath.id] = localPath;
        m_edgePathToId[localPath] = localPath.id;
        //m_edgePathToId[localPath.reverted()] = localPath.id;
        return localPath.id;
    }

    std::size_t EdgeTrackingObserver::addEdgePathIfNotExists(EdgePath&& path)
    {
        auto localPath = std::move(path);
        auto [exists, id] = edgePathExists(localPath);
        if (exists)
        {
            return id;
        }
        return addEdgePath(std::move(localPath));
    }

    void EdgeTrackingObserver::verifyMapsSelf(std::size_t edgeId) const
    {
        if (!isSelf(m_edgeMapping.at(edgeId)))
        {
            std::cout << "Does not map to self: " << edgeId << ", maps to index type " << m_edgeMapping.at(edgeId).
                index() << '\n';
            outputMapping(m_edgeMapping.at(edgeId), std::cout);
            std::cout << "\n";
            throw std::runtime_error("Expected edge to map to self");
        }
        if (m_useSpecialEdgeIds)
        {
            auto otherEId = SEF::flipCanonical(edgeId);
            if (!isSelf(m_edgeMapping.at(otherEId)))
            {
                std::cout << "Does not map to self: " << otherEId << ", maps to index type " << m_edgeMapping.
                    at(otherEId).index() << '\n';
                outputMapping(m_edgeMapping.at(otherEId), std::cout);
                std::cout << "\n";
                throw std::runtime_error("Expected edge to map to self");
            }
        }
    }

    void EdgeTrackingObserver::initialize(const std::set<std::size_t>& originalVertexIds,
                                          const std::map<std::size_t, std::pair<std::size_t, std::size_t>>&
                                          originalEdgeIds)
    {
        TimestampScope scope(this);
        // To make it easy for ourselves, trivially map originals to themselves.
        for (const auto& kv : originalEdgeIds)
        {
            if (SEF::isCanonical(kv.first))
            {
                handleNewEdge(kv.first, kv.second.first, kv.second.second);
                maxEId = std::max(maxEId, kv.first);
            }
        }
        for (auto v : originalVertexIds)
        {
            handleNewVertex(v);
            maxVId = std::max(maxVId, v);
        }
    }

    void EdgeTrackingObserver::selfMappingEdges(std::vector<std::size_t>& output) const
    {
        for (const auto& kv : m_edgeMapping)
        {
            if (isSelf(kv.second)) output.push_back(kv.first);
        }
    }

    void EdgeTrackingObserver::verifyEdgeIntegrity(const std::set<std::size_t>& edges) const
    {
        for (auto kv : m_edgeMapping)
        {
            if (m_useSpecialEdgeIds && SEF::isNonCanonical(kv.first))
            {
                if (isSelf(kv.second) && edges.find(SEF::flipCanonical(kv.first)) == edges.end())
                {
                    std::cout << kv.first << " -- " << SEF::flipCanonical(kv.first);
                    throw std::runtime_error("Missing non-canonical counter part");
                }
                continue;
            }
            if (isSelf(kv.second) && edges.find(kv.first) == edges.end())
            {
                std::cout << "Error: " << "Missing edge in graph " << kv.first << '\n';
                throw std::runtime_error("Missing edge in graph");
            }
        }
        // Reverse
        for (auto e : edges)
        {
            if (m_edgeMapping.find(e) == m_edgeMapping.end()) throw
                std::runtime_error("Edge in graph, but not tracker");
            if (!isSelf(m_edgeMapping.at(e))) throw std::runtime_error("Edge in graph maps to somehwere else!");
        }
    }

    void EdgeTrackingObserver::verifyVertexIntegrity(const std::set<std::size_t>& vertices) const
    {
        for (auto kv : m_vertexMapping)
        {
            if (isSelf(kv.second) && vertices.find(kv.first) == vertices.end())
            {
                std::cout << "Error: " << "Missing vertex in graph " << kv.first << '\n';
                //throw std::runtime_error("Missing vertex in graph");
            }
        }
        // Reverse
        for (auto v : vertices)
        {
            if (m_vertexMapping.find(v) == m_vertexMapping.end()) throw std::runtime_error(
                "Vertex in graph, but not tracker");
            if (!isSelf(m_vertexMapping.at(v)))
            {
                auto res = m_vertexMapping.at(v);
                std::cout << "Vertex in graph maps to somehwere else! v=" + std::to_string(v) + ", map type " +
                    std::to_string(res.index()) << " \n";
                outputMapping(m_vertexMapping.at(v), std::cout);
                throw std::runtime_error(
                    "Vertex in graph maps to somehwere else! v=" + std::to_string(v) + ", map type " + std::to_string(
                        res.index()));
            }
        }
    }

    void EdgeTrackingObserver::verifyFaceIntegrity(const std::set<std::size_t>& faces) const
    {
        for (auto kv : m_faceMapping)
        {
            if (isSelf(kv.second) && faces.find(kv.first) == faces.end())
            {
                std::cout << "Error: " << "Missing face in graph " << kv.first << '\n';
                throw std::runtime_error("Missing face in graph");
            }
        }
        // Reverse
        for (auto f : faces)
        {
            if (m_faceMapping.find(f) == m_faceMapping.end()) throw std::runtime_error(
                "Vertex in graph, but not tracker");
            if (!isSelf(m_faceMapping.at(f)))
            {
                auto res = m_faceMapping.at(f);
                std::cout << "Face in graph maps to somehwere else! v=" + std::to_string(f) + ", map type " +
                    std::to_string(res.index()) << " \n";
                outputMapping(res, std::cout);
                throw std::runtime_error(
                    "Face in graph maps to somehwere else! v=" + std::to_string(f) + ", map type " + std::to_string(
                        res.index()));
            }
        }
    }

    void EdgeTrackingObserver::verifyIntegrity(const std::set<std::size_t>& edges,
                                               const std::set<std::size_t>& vertices) const
    {
        verifyEdgeIntegrity(edges);
        verifyVertexIntegrity(vertices);
    }

    void EdgeTrackingObserver::verifyIntegrity(const std::set<std::size_t>& edges,
                                               const std::set<std::size_t>& vertices,
                                               const std::set<std::size_t>& faces) const
    {
        verifyEdgeIntegrity(edges);
        verifyVertexIntegrity(vertices);
        verifyFaceIntegrity(faces);
    }

    void EdgeTrackingObserver::handleNewVertex(std::size_t vertexId)
    {
        //TODO: reinstate
        //if (m_vertexMapping.find(vertexId) != m_vertexMapping.end()) throw std::runtime_error("Duplicate vertex id!");
        if (m_vertexMapping.find(vertexId) != m_vertexMapping.end()) return;
        m_vertexMapping[vertexId] = withCurrentTimestamp(Self{vertexId});
        ++m_eventCount;
        maxVId = std::max(maxVId, vertexId);
    }

    void EdgeTrackingObserver::handleVertexInsert(std::size_t edge, std::size_t newVertex, std::size_t newStartEdge,
                                                  std::size_t newEndEdge)
    {
        auto epId = addEdgePath(EdgePath{{newStartEdge, newEndEdge}, 0});
        TimestampScope scope(this);
        m_edgeMapping[edge] = withCurrentTimestamp(ViaEdgePath{epId, true});
        m_edgeMapping[newStartEdge] = withCurrentTimestamp(Self{newStartEdge});
        m_edgeMapping[newEndEdge] = withCurrentTimestamp(Self{newEndEdge});
        m_vertexMapping[newVertex] = withCurrentTimestamp(Self{newVertex});
        ++m_eventCount;
    }

    void EdgeTrackingObserver::handleVertexDelete(std::size_t vertex)
    {
        m_vertexMapping[vertex] = withCurrentTimestamp(Deleted{});
        ++m_eventCount;
    }

    void EdgeTrackingObserver::handleVertexMerge(std::size_t vertex, std::size_t mergeVertex)
    {
        if (vertex == mergeVertex) throw std::runtime_error("Invalid merge: merging to self!");
        //LogLine() << "Merging vertex  " << vertex << " to vertex  " << mergeVertex;
        m_vertexMapping[vertex] = withCurrentTimestamp(Vertex{mergeVertex});
        ++m_eventCount;
    }

    void EdgeTrackingObserver::handleJunctionReroute(const FaceTreeReroute<long double>& reroute)
    {
        const auto id = junctionId;
        m_junctions[id] = reroute;
        ++junctionId;
        TimestampScope scope(this);
        for (auto e : reroute.affected_edges())
        {
            m_edgeMapping[e] = withCurrentTimestamp(ViaSubgraph{id, e});
            if (m_useSpecialEdgeIds)
            {
                m_edgeMapping[SEF::flipCanonical(e)] = withCurrentTimestamp(ViaSubgraph{id, SEF::flipCanonical(e)});
            }
        }
        for (auto v : reroute.affected_vertices())
        {
            m_vertexMapping[v] = withCurrentTimestamp(ViaSubgraph{id, v});
        }
        for (auto v : reroute.vertices())
        {
            if (reroute.is_terminal_vertex(v)) continue;
            handleNewVertex(v);
        }
        for (const auto& e : reroute.edges())
        {
            if (SEF::isCanonical(e.id))
            {
                handleNewEdge(e.id, e.source, e.target);
            }
        }
        unlockIncrementTimestamp();
    }

    void EdgeTrackingObserver::handleNewEdge(std::size_t edgeId, std::size_t srcVert, std::size_t targetVert)
    {
        if (m_edges.find(edgeId) != m_edges.end()) throw std::runtime_error("Duplicate edge id!");
        auto [minV, maxV] = std::minmax(srcVert, targetVert);
        //LogLine() << "New edge: " << edgeId << " from " << srcVert << " to " << targetVert;
        m_edges[edgeId] = std::make_pair(minV, maxV);
        TimestampScope scope(this);
        m_edgeMapping[edgeId] = withCurrentTimestamp(Self{edgeId});
        ++m_eventCount;
        maxEId = std::max(maxEId, edgeId);
        if (m_useSpecialEdgeIds)
        {
            m_edges[SpecialEdgeIdFunctions::flipCanonical(edgeId)] = std::make_pair(maxV, minV);
            m_edgeMapping[SpecialEdgeIdFunctions::flipCanonical(edgeId)] = withCurrentTimestamp(Self{
                SpecialEdgeIdFunctions::flipCanonical(edgeId)
            });
        }
    }

    void EdgeTrackingObserver::handleEdgeReplace(std::size_t edgeId, const std::vector<std::size_t>& replacementEdges)
    {
        verifyMapsSelf(edgeId);
        handleEdgeReroute(std::vector<std::size_t>{edgeId}, replacementEdges);
    }

    void EdgeTrackingObserver::handleEdgeCollapse(std::size_t edge, std::size_t mergeVertex)
    {
        verifyMapsSelf(edge);
        TimestampScope scope(this);
        //LogLine() << "Edge collapse " << edge << " to vert " << mergeVertex;
        m_edgeMapping[edge] = withCurrentTimestamp(Vertex{mergeVertex});
        ++m_eventCount;
        if (m_useSpecialEdgeIds)
        {
            m_edgeMapping[SEF::flipCanonical(edge)] = withCurrentTimestamp(Vertex{mergeVertex});
        }
    }

    void EdgeTrackingObserver::handleEdgeEdgeMerge(std::size_t edge, std::size_t mergeEdge)
    {
        verifyMapsSelf(edge);
        verifyMapsSelf(mergeEdge);
        //LogLine() << "Edge merge " << edge << " to edge " << mergeEdge;
        if (isVertex(m_edgeMapping[mergeEdge])) throw std::runtime_error("Merging to edge that is merged to vertex!");
        TimestampScope scope(this);
        m_edgeMapping[edge] = withCurrentTimestamp(Edge{mergeEdge});
        ++m_eventCount;
        if (m_useSpecialEdgeIds)
        {
            m_edgeMapping[SEF::flipCanonical(edge)] = withCurrentTimestamp(Edge{SEF::flipCanonical(mergeEdge)});
        }
    }

    void EdgeTrackingObserver::handleEdgeDelete(std::size_t edge)
    {
        verifyMapsSelf(edge);
        TimestampScope scope(this);
        m_edgeMapping[edge] = withCurrentTimestamp(Deleted{});
        ++m_eventCount;
        if (m_useSpecialEdgeIds)
        {
            m_edgeMapping[SEF::flipCanonical(edge)] = withCurrentTimestamp(Deleted{});
        }
    }

    void EdgeTrackingObserver::handleEdgeReroute(const std::vector<std::size_t>& originalRoute,
                                                 const std::vector<std::size_t>& targetRoute)
    {
        if (targetRoute.size() == 0) throw std::runtime_error("Empty replacement path");
        TimestampScope scope(this);
        // Check
        {
            for (auto el : originalRoute) { verifyMapsSelf(el); }

            std::set<std::size_t> incoming;
            incoming.insert(originalRoute.begin(), originalRoute.end());
            for (auto e : targetRoute)
            {
                if (incoming.find(e) != incoming.end())
                {
                    std::cout << "Edge in input and output for reroute: " << e << '\n';
                    std::cout << "Original: ";
                    for (auto el : originalRoute)std::cout << " " << el;
                    std::cout << '\n';
                    std::cout << "Reroute: ";
                    for (auto el : targetRoute)std::cout << " " << el;
                    std::cout << '\n';
                    throw std::runtime_error("Edge in input and output for reroute!");
                }
            }
        }

        if (targetRoute.empty()) throw std::runtime_error("Empty route given to rerouting!");

        if (originalRoute.size() == 1 && targetRoute.size() == 1)
        {
            handleEdgeEdgeMerge(originalRoute.front(), targetRoute.front());
            return;
        }

        if (originalRoute.size() == 1)
        {
            auto targetEp = EdgePath{targetRoute, 0};
            auto [targetExists, targetId] = edgePathExists(targetEp);
            if (!targetExists)
            {
                targetId = addEdgePath(std::move(targetEp));
            }

            verifyMapsSelf(originalRoute[0]);
            m_edgeMapping[originalRoute[0]] = withCurrentTimestamp(ViaEdgePath{targetId, true,originalRoute[0] });
        }
        else if (targetRoute.size() == 1)
        {
            auto ep = EdgePath{originalRoute, 0};
            const auto id = addEdgePathIfNotExists(std::move(ep));
            m_pathMapping[id] = Edge{targetRoute[0]};
            for (auto e : originalRoute)
            {
                verifyMapsSelf(e);
                m_edgeMapping[e] = withCurrentTimestamp(ViaEdgePath{id, false,e});
            }
        }
        else
        {
            // Find if the original route is already an edge path.
            auto ep = EdgePath{originalRoute, 0};
            auto targetEp = EdgePath{targetRoute, 0};
            const auto id = addEdgePathIfNotExists(std::move(ep));
            const auto targetId = addEdgePathIfNotExists(std::move(targetEp));

            m_pathMapping[id] = withCurrentTimestamp(ViaEdgePath{targetId, false,id});
            // Findout if the route is a logical subsegment in all affected edges.
            for (auto e : originalRoute)
            {
                verifyMapsSelf(e);
                m_edgeMapping[e] = withCurrentTimestamp(ViaEdgePath{id, false,e});
            }
        }
        ++m_eventCount;
        if (m_useSpecialEdgeIds)
        {
            handleEdgeRerouteSpecialEdges(originalRoute, targetRoute);
        }
    }

    void EdgeTrackingObserver::handleEdgeRerouteSpecialEdges(const std::vector<std::size_t>& originalRouteIn,
                                                             const std::vector<std::size_t>& targetRouteIn)
    {
        std::vector<std::size_t> originalRoute = originalRouteIn;
        std::vector<std::size_t> targetRoute = targetRouteIn;
        SEF::reverseCanonicalComplement(originalRoute);
        SEF::reverseCanonicalComplement(targetRoute);
        if (targetRoute.size() == 0) throw std::runtime_error("Empty replacement path");
        // Check
        {
            std::set<std::size_t> incoming;
            incoming.insert(originalRoute.begin(), originalRoute.end());
            for (auto e : targetRoute)
            {
                if (incoming.find(e) != incoming.end())
                {
                    std::cout << "Edge in input and output for reroute: " << e << '\n';
                    throw std::runtime_error("Edge in input and output for reroute!");
                }
            }
        }

        if (targetRoute.empty()) throw std::runtime_error("Empty route given to rerouting!");
        if (originalRoute.size() == 1)
        {
            auto targetEp = EdgePath{targetRoute, 0};
            auto [targetExists, targetId] = edgePathExists(targetEp);
            if (!targetExists)
            {
                targetId = addEdgePath(std::move(targetEp));
            }
            m_edgeMapping[originalRoute[0]] = withCurrentTimestamp(ViaEdgePath{targetId, true,originalRoute[0] });
        }
        else if (targetRoute.size() == 1)
        {
            auto ep = EdgePath{originalRoute, 0};
            const auto id = addEdgePathIfNotExists(std::move(ep));
            m_pathMapping[id] = Edge{targetRoute[0]};
            for (auto e : originalRoute)
            {
                m_edgeMapping[e] = withCurrentTimestamp(ViaEdgePath{id, false,e });
            }
        }
        else
        {
            // Find if the original route is already an edge path.
            auto ep = EdgePath{originalRoute, 0};
            auto targetEp = EdgePath{targetRoute, 0};
            const auto id = addEdgePathIfNotExists(std::move(ep));
            const auto targetId = addEdgePathIfNotExists(std::move(targetEp));

            m_pathMapping[id] = withCurrentTimestamp(ViaEdgePath{targetId, false,id});
            // Findout if the route is a logical subsegment in all affected edges.
            for (auto e : originalRoute)
            {
                m_edgeMapping[e] = withCurrentTimestamp(ViaEdgePath{id, false,e});
            }
        }
        ++m_eventCount;
    }
}
back to top