MRGraph.h

Go to the documentation of this file.

#pragma once
 
#include "MRVector.h"
#include "MRId.h"
#include "MRBitSet.h"
#include <cassert>
#include <functional>
 
namespace MR
{
 
class Graph
{
public:
    using VertId = GraphVertId;
    using EdgeId = GraphEdgeId;
 
    using VertBitSet = GraphVertBitSet;
    using EdgeBitSet = GraphEdgeBitSet;
 
    using Neighbours = std::vector<EdgeId>; // sorted by edgeID
    using NeighboursPerVertex = Vector<Neighbours, VertId>;
 
    struct EndVertices
    {
        VertId v0, v1; // v0 < v1
        [[nodiscard]] VertId otherEnd( VertId a ) const
        {
            assert( a == v0 || a == v1 );
            return a == v0 ? v1 : v0;
        }
        void replaceEnd( VertId what, VertId with )
        {
            assert( what != with );
            assert( ( v0 == what && v1 != with ) || ( v1 == what && v0 != with ) );
            if ( v0 == what )
                v0 = with;
            else
                v1 = with;
            if ( v0 > v1 )
                std::swap( v0, v1 );
        }
        auto operator <=>( const EndVertices& ) const = default;
    };
    using EndsPerEdge = Vector<EndVertices, EdgeId>;
 
    MRMESH_API void construct( NeighboursPerVertex neighboursPerVertex, EndsPerEdge endsPerEdge );
 
    [[nodiscard]] size_t vertSize() const { return neighboursPerVertex_.size(); }
 
    [[nodiscard]] const VertBitSet & validVerts() const { return validVerts_; }
 
    [[nodiscard]] bool valid( VertId v ) const { return validVerts_.test( v ); }
 
    [[nodiscard]] size_t edgeSize() const { return endsPerEdge_.size(); }
 
    [[nodiscard]] const EdgeBitSet & validEdges() const { return validEdges_; }
 
    [[nodiscard]] bool valid( EdgeId e ) const { return validEdges_.test( e ); }
 
    [[nodiscard]] const Neighbours & neighbours( VertId v ) const { return neighboursPerVertex_[v]; }
 
    [[nodiscard]] const EndVertices & ends( EdgeId e ) const { return endsPerEdge_[e]; }
 
    [[nodiscard]] MRMESH_API EdgeId findEdge( VertId a, VertId b ) const;
 
    [[nodiscard]] bool areNeighbors( VertId a, VertId b ) const { return findEdge( a, b ).valid(); }
 
    MRMESH_API void merge( VertId remnant, VertId dead, std::function<void( EdgeId remnant, EdgeId dead )> onMergeEdges );
 
    MRMESH_API bool checkValidity() const;
 
private:
    VertBitSet validVerts_;
    EdgeBitSet validEdges_;
 
    NeighboursPerVertex neighboursPerVertex_;
    EndsPerEdge endsPerEdge_;
};
 
} //namespace MR