triggeralgs::dbscan::IncrementalDBSCAN Class Reference

#include <dbscan.hpp>

Public Member Functions
	IncrementalDBSCAN (float eps, unsigned int minPts, size_t pool_size=100000)
void	add_primitive (const triggeralgs::TriggerPrimitive &prim, std::vector< Cluster > *completed_clusters=nullptr)
void	add_point (float time, float channel, std::vector< Cluster > *completed_clusters=nullptr)
void	add_hit (Hit *new_hit, std::vector< Cluster > *completed_clusters=nullptr)
void	trim_hits ()
std::vector< Hit * >	get_hits () const
std::map< int, Cluster >	get_clusters () const
uint64_t	get_first_prim_time () const

Private Member Functions
void	cluster_reachable (Hit *seed_hit, Cluster &cluster)

Private Attributes
float	m_eps
float	m_minPts
std::vector< Hit >	m_hit_pool
size_t	m_pool_begin
size_t	m_pool_end
std::vector< Hit * >	m_hits
float	m_latest_time { 0 }
uint64_t	m_first_prim_time {0}
std::map< int, Cluster >	m_clusters

Detailed Description

Definition at line 57 of file dbscan.hpp.

Constructor & Destructor Documentation

IncrementalDBSCAN()

triggeralgs::dbscan::IncrementalDBSCAN::IncrementalDBSCAN ( float eps, unsigned int minPts, size_t pool_size = 100000 )

inline

Definition at line 60 of file dbscan.hpp.

        : m_eps(eps)
        , m_minPts(minPts)
        , m_pool_begin(0)
        , m_pool_end(0)
    {
        for(size_t i=0; i<pool_size; ++i){
            m_hit_pool.emplace_back(0,0);
        }
    }

Member Function Documentation

add_hit()

void triggeralgs::dbscan::IncrementalDBSCAN::add_hit	(	Hit *	new_hit,
		std::vector< Cluster > *	completed_clusters = nullptr )

Definition at line 153 of file dbscan.cpp.

{
    // TODO: this should be a member variable, not a static, in case
    // there are multiple IncrementalDBSCAN instances
    static int next_cluster_index = 0;
 
    m_hits.push_back(new_hit);
    m_latest_time = new_hit->time;
 
    // All the clusters that this hit neighboured. If there are
    // multiple clusters neighbouring this hit, we'll merge them at
    // the end
    std::set<int> clusters_neighbouring_hit;
 
    // Find all the hit's neighbours
    neighbours_sorted(m_hits, *new_hit, m_eps, m_minPts);
 
    for (auto neighbour : new_hit->neighbours) {
        if (neighbour->cluster != kUndefined && neighbour->cluster != kNoise &&
            neighbour->neighbours.size() + 1 >= m_minPts) {
            // This neighbour is a core point in a cluster. Add the cluster to the list of
            // clusters that will contain this hit
            clusters_neighbouring_hit.insert(neighbour->cluster);
        }
    }
 
    if (clusters_neighbouring_hit.empty()) {
        // This hit didn't match any existing cluster. See if we can
        // make a new cluster out of it. Otherwise mark it as noise
 
        if (new_hit->neighbours.size() + 1 >= m_minPts) {
            // std::cout << "New cluster starting at hit time " << new_hit->time << " with " << new_hit->neighbours.size() << " neighbours" << std::endl;
            new_hit->connectedness = Connectedness::kCore;
            auto new_it = m_clusters.emplace_hint(
                m_clusters.end(), next_cluster_index, next_cluster_index);
            Cluster& new_cluster = new_it->second;
            new_cluster.completeness = Completeness::kIncomplete;
            new_cluster.add_hit(new_hit);
            next_cluster_index++;
            cluster_reachable(new_hit, new_cluster);
        }
        else{
            // std::cout << "New hit time " << new_hit->time << " with " << new_hit->neighbours.size() << " neighbours is noise" << std::endl;
        }
    } else {
        // This hit neighboured at least one cluster. Add the hit and
        // its noise neighbours to the first cluster in the list, then
        // merge the rest of the clusters into it
 
        auto index_it = clusters_neighbouring_hit.begin();
 
        auto it = m_clusters.find(*index_it);
        assert(it != m_clusters.end());
        Cluster& cluster = it->second;
        // std::cout << "Adding hit time " << new_hit->time << " with " << new_hit->neighbours.size() << " neighbours to existing cluster" << std::endl;
        cluster.add_hit(new_hit);
 
        // TODO: this seems wrong: we're adding this hit's neighbours
        // to the cluster even if this hit isn't a core point, but if
        // I wrap the whole thing in "if(new_hit is core)" then the
        // results differ from classic DBSCAN
        for (auto q : new_hit->neighbours) {
            if (q->cluster == kUndefined || q->cluster == kNoise) {
                // std::cout << "  Adding hit time " << q->time << " to existing cluster" << std::endl;
                cluster.add_hit(q);
            }
            // If the neighbouring hit q has exactly m_minPts
            // neighbours, it must have become a core point by the
            // addition of new_hit. Add q's neighbours to the cluster
            if(q->neighbours.size() + 1 == m_minPts){
                for (auto r : q->neighbours) {
                    cluster.add_hit(r);
                }
            }
        }
 
 
        ++index_it;
 
        for (; index_it != clusters_neighbouring_hit.end(); ++index_it) {
 
            auto other_it = m_clusters.find(*index_it);
            assert(other_it != m_clusters.end());
            Cluster& other_cluster = other_it->second;
            cluster.steal_hits(other_cluster);
        }
    }
 
    // Last case: new_hit and its neighbour are both noise, but the
    // addition of new_hit makes the neighbour a core point. So we
    // start a new cluster at the neighbour, and walk out from there
    for (auto& neighbour : new_hit->neighbours) {
        if(neighbour->neighbours.size() + 1 >= m_minPts){
            // std::cout << "new_hit's neighbour at " << neighbour->time << " has " << neighbour->neighbours.size() << " neighbours, so is core" << std::endl;
            if(neighbour->cluster==kNoise || neighbour->cluster==kUndefined){
                if(new_hit->cluster==kNoise || new_hit->cluster==kUndefined){
                    auto new_it = m_clusters.emplace_hint(
                                                          m_clusters.end(), next_cluster_index, next_cluster_index);
                    Cluster& new_cluster = new_it->second;
                    new_cluster.completeness = Completeness::kIncomplete;
                    new_cluster.add_hit(neighbour);
                    next_cluster_index++;
                    cluster_reachable(neighbour, new_cluster);
                }
            }
        }
        else {
            // std::cout << "new_hit's neighbour at " << neighbour->time << " has " << neighbour->neighbours.size() << " neighbours, so is NOT core" << std::endl;
        }
    }
 
 
    // Delete any completed clusters from the list. Put them in the
    // `completed_clusters` vector, if that vector was passed
    auto clust_it = m_clusters.begin();
    while (clust_it != m_clusters.end()) {
        Cluster& cluster = clust_it->second;
 
        if (cluster.latest_time < m_latest_time - m_eps) {
            cluster.completeness = Completeness::kComplete;
        }
 
        if (cluster.completeness == Completeness::kComplete) {
            if(completed_clusters){
                // TODO: room for std::move here?
                //
                // Clusters that got merged into another cluster had
                // their hits cleared, and were set kComplete, by
                // steal_hits
                if(cluster.hits.size()!=0){
                    completed_clusters->push_back(cluster);
                }
            }
            clust_it = m_clusters.erase(clust_it);
            continue;
        } else {
            ++clust_it;
        }
    }
}

add_point()

void triggeralgs::dbscan::IncrementalDBSCAN::add_point	(	float	time,
		float	channel,
		std::vector< Cluster > *	completed_clusters = nullptr )

Definition at line 126 of file dbscan.cpp.

{
    Hit& new_hit=m_hit_pool[m_pool_end];
    new_hit.reset(time, channel);
    ++m_pool_end;
    if(m_pool_end==m_hit_pool.size()) m_pool_end=0;
    add_hit(&new_hit, completed_clusters);
}

add_primitive()

void triggeralgs::dbscan::IncrementalDBSCAN::add_primitive	(	const triggeralgs::TriggerPrimitive &	prim,
		std::vector< Cluster > *	completed_clusters = nullptr )

Definition at line 137 of file dbscan.cpp.

{
    if(m_first_prim_time==0){
        m_first_prim_time=prim.time_start;
    }
    
    Hit& new_hit=m_hit_pool[m_pool_end];
    new_hit.reset(1e-2*(prim.time_start-m_first_prim_time), prim.channel, &prim);
    ++m_pool_end;
    if(m_pool_end==m_hit_pool.size()) m_pool_end=0;
 
    add_hit(&new_hit, completed_clusters);
}

cluster_reachable()

void triggeralgs::dbscan::IncrementalDBSCAN::cluster_reachable ( Hit * seed_hit, Cluster & cluster )

private

Definition at line 95 of file dbscan.cpp.

{
    // Loop over all neighbours (and the neighbours of core points, and so on)
    std::vector<Hit*> seedSet(seed_hit->neighbours.begin(),
                              seed_hit->neighbours.end());
 
    while (!seedSet.empty()) {
        Hit* q = seedSet.back();
        seedSet.pop_back();
        // Change noise to a border point
        if (q->connectedness == Connectedness::kNoise) {
            cluster.add_hit(q);
        }
 
        if (q->cluster != kUndefined) {
            continue;
        }
 
        cluster.add_hit(q);
 
        // If q is a core point, add its neighbours to the search list
        if (q->neighbours.size() + 1 >= m_minPts) {
            q->connectedness = Connectedness::kCore;
            seedSet.insert(
                seedSet.end(), q->neighbours.begin(), q->neighbours.end());
        }
    }
}

get_clusters()

std::map< int, Cluster > triggeralgs::dbscan::IncrementalDBSCAN::get_clusters ( ) const

inline

Definition at line 83 of file dbscan.hpp.

{ return m_clusters; }

get_first_prim_time()

uint64_t triggeralgs::dbscan::IncrementalDBSCAN::get_first_prim_time ( ) const

inline

Definition at line 85 of file dbscan.hpp.

{ return m_first_prim_time; }

get_hits()

std::vector< Hit * > triggeralgs::dbscan::IncrementalDBSCAN::get_hits ( ) const

inline

Definition at line 81 of file dbscan.hpp.

{ return m_hits; }

trim_hits()

void triggeralgs::dbscan::IncrementalDBSCAN::trim_hits

(

)

Definition at line 295 of file dbscan.cpp.

{
    // Find the earliest time of a hit in any cluster in the list (active or
    // not)
    float earliest_time = std::numeric_limits<float>::max();
 
    for (auto& cluster : m_clusters) {
        earliest_time =
            std::min(earliest_time, (*cluster.second.hits.begin())->time);
    }
 
    // If there were no clusters, set the earliest_time to the latest time
    // (otherwise it would still be FLOAT_MAX)
    if (m_clusters.empty()) {
        earliest_time = m_latest_time;
    }
    auto last_it = std::lower_bound(m_hits.begin(),
                                    m_hits.end(),
                                    earliest_time - 10 * m_eps,
                                    time_comp_lower);
 
    m_hits.erase(m_hits.begin(), last_it);
}

Member Data Documentation

m_clusters

std::map<int, Cluster> triggeralgs::dbscan::IncrementalDBSCAN::m_clusters

private

Definition at line 102 of file dbscan.hpp.

m_eps

float triggeralgs::dbscan::IncrementalDBSCAN::m_eps

private

Definition at line 94 of file dbscan.hpp.

m_first_prim_time

uint64_t triggeralgs::dbscan::IncrementalDBSCAN::m_first_prim_time {0}

private

Definition at line 100 of file dbscan.hpp.

{0};

m_hit_pool

std::vector<Hit> triggeralgs::dbscan::IncrementalDBSCAN::m_hit_pool

private

Definition at line 96 of file dbscan.hpp.

m_hits

std::vector<Hit*> triggeralgs::dbscan::IncrementalDBSCAN::m_hits

private

Definition at line 98 of file dbscan.hpp.

m_latest_time

float triggeralgs::dbscan::IncrementalDBSCAN::m_latest_time { 0 }

private

Definition at line 99 of file dbscan.hpp.

{ 0 }; // The latest time of a hit in the vector of hits

m_minPts

float triggeralgs::dbscan::IncrementalDBSCAN::m_minPts

private

Definition at line 95 of file dbscan.hpp.

m_pool_begin

size_t triggeralgs::dbscan::IncrementalDBSCAN::m_pool_begin

private

Definition at line 97 of file dbscan.hpp.

m_pool_end

size_t triggeralgs::dbscan::IncrementalDBSCAN::m_pool_end

private

Definition at line 97 of file dbscan.hpp.

---

The documentation for this class was generated from the following files:

• /github/workspace/dunedaq/sourcecode/triggeralgs/include/triggeralgs/dbscan/dbscan.hpp
• /github/workspace/dunedaq/sourcecode/triggeralgs/src/dbscan/dbscan.cpp