AdjacencyList.hpp

#pragma once
 
#include <Core/Containers/AlignedStdVector.hpp>
#include <Core/Containers/VectorArray.hpp>
#include <Eigen/Core>
#include <iostream>
 
namespace Ra {
namespace Core {
 
using ParentList   = AlignedStdVector<int>;
using LevelList    = AlignedStdVector<uint8_t>;
using ChildrenList = AlignedStdVector<uint8_t>;
using Adjacency    = AlignedStdVector<ChildrenList>;
 
class RA_CORE_API AdjacencyList
{
  public:
    enum class ConsistencyStatus {
        Valid,
        IncompatibleChildrenAndParentList,
        WrongParentOrdering,
        WrongParentIndex,
        InconsistentParentIndex,
        NonLeafNodeWithoutChild
    };
 
    // CONSTRUCTOR
    AdjacencyList();
    explicit AdjacencyList( const uint n );
    AdjacencyList( const AdjacencyList& adj );
    AdjacencyList& operator=( const AdjacencyList& ) = default;
 
    // DESTRUCTOR
    ~AdjacencyList();
 
    // NODE
    uint addRoot();
    uint addNode( const uint parent );
    void pruneLeaves( std::vector<uint>& pruned, std::vector<bool>& delete_flag );
    void pruneLeaves();
    VectorArray<Eigen::Matrix<uint, 2, 1>> extractEdgeList( bool include_leaf = false ) const;
 
    // SIZE
    inline uint size() const;
    inline void clear();
 
    // QUERY
    ConsistencyStatus computeConsistencyStatus() const;
    inline bool isEmpty() const { return ( size() == 0 ); }
    inline bool isRoot( const uint i ) const;
    inline bool isLeaf( const uint i ) const;
    inline bool isBranch( const uint i ) const;
    inline bool isJoint( const uint i ) const;
    inline bool isEdge( const uint i, const uint j ) const;
 
    inline const Adjacency& children() const { return m_child; }
 
    inline const ParentList& parents() const { return m_parent; }
 
    // VARIABLE
  private:
    Adjacency m_child;
    ParentList m_parent;
    LevelList m_level;
};
 
RA_CORE_API std::ofstream& operator<<( std::ofstream& ofs, const AdjacencyList& p );
 
inline uint AdjacencyList::size() const {
    CORE_ASSERT( m_parent.size() == m_child.size(), "List size inconsistency" );
    return m_parent.size();
}
 
inline void AdjacencyList::clear() {
    m_child.clear();
    m_parent.clear();
}
 
inline bool AdjacencyList::isRoot( const uint i ) const {
    CORE_ASSERT( i < size(), " Index i out of bounds " );
    return ( m_parent[i] == -1 );
}
 
inline bool AdjacencyList::isLeaf( const uint i ) const {
    CORE_ASSERT( i < size(), " Index i out of bounds " );
    return ( m_child[i].size() == 0 );
}
 
inline bool AdjacencyList::isBranch( const uint i ) const {
    CORE_ASSERT( i < size(), " Index i out of bounds " );
    return ( m_child[i].size() > 1 );
}
 
inline bool AdjacencyList::isJoint( const uint i ) const {
    CORE_ASSERT( i < size(), " Index i out of bounds " );
    return ( m_child[i].size() == 1 );
}
 
inline bool AdjacencyList::isEdge( const uint i, const uint j ) const {
    CORE_ASSERT( i < size(), " Index i out of bounds " );
    CORE_ASSERT( j < size(), " Index j out of bounds " );
    for ( const auto& item : m_child[i] ) {
        if ( item == j ) return true;
    }
    return false;
}
} // namespace Core
} // namespace Ra