finding the connected components of a graph

clusters.cpp

#include <QQueue>
#include <QSet>

#include <iostream>

#include <cstdint>


class Pixel
{
public:
    int64_t x;
    int64_t y;
    Pixel(int64_t x_, int64_t y_) : x(x_), y(y_) {}
    Pixel(const Pixel & other) : x(other.x), y(other.y) {}
};

bool operator== (const Pixel &p1, const Pixel &p2) noexcept
{
    return (p1.x == p2.x && p1.y == p2.y);
}

uint qHash(const Pixel &p, uint seed)
{
    uint hash = seed;
    hash = 97 * hash + p.x;
    hash = 97 * hash + p.y;
    return hash;
}

QList< QSet<Pixel> > getClusters(const QSet<Pixel> & hitPixels)
{
    QSet<Pixel> clusterlessPixels;
    QList< QSet<Pixel> > clusters;

    // initially, no hit pixel is part of a cluster
    clusterlessPixels.unite(hitPixels);

    // while there are clusterless pixels left
    while (!clusterlessPixels.empty()) {
        QSet<Pixel> currentCluster;
        QQueue<Pixel> visitUs;

        // fetch any clusterless pixel
        QSetIterator<Pixel> iter(clusterlessPixels);
        Pixel p = iter.next();

        // add it to the queue
        visitUs.enqueue(p);

        // while there are candidates for the cluster
        while (!visitUs.isEmpty()) {
            // take one
            Pixel v = visitUs.dequeue();

            // it's part of our new cluster
            currentCluster.insert(p);

            // and thus no longer clusterless
            clusterlessPixels.remove(p);

            // now check the neighbors
            int64_t xoff;
            int64_t yoff;
            for (xoff = -1; xoff <= 1; ++xoff) {
                for (yoff = -1; yoff <= 1; ++yoff) {
                    if (xoff == 0 && yoff == 0) {
                        // that's me; I've already been handled
                        continue;
                    }

                    Pixel neighbor(v.x + xoff, v.y + yoff);

                    // returns true iff the item actually was in the set
                    if (clusterlessPixels.remove(neighbor)) {
                        // this neighbor was hit too; it's part of the cluster
                        currentCluster.insert(neighbor);
                        // perhaps its neighbors were hit too?
                        visitUs.enqueue(neighbor);
                    }
                }
            }
        }

        // no more hit neighbors -- our cluster is complete
        clusters.append(currentCluster);

        // and thus we loop as long as there are any clusterless pixels
    }

    // at this point, all pixels have been assigned clusters
    return clusters;
}

int main(void)
{
    // /012345
    // 5######
    // 4 ##
    // 3######
    // 2
    // 1
    // 0 #

    QSet<Pixel> hitPixels;
    hitPixels.insert(Pixel(1, 0));
    hitPixels.insert(Pixel(3, 0));
    hitPixels.insert(Pixel(3, 1));
    hitPixels.insert(Pixel(3, 2));
    hitPixels.insert(Pixel(3, 3));
    hitPixels.insert(Pixel(3, 4));
    hitPixels.insert(Pixel(3, 5));
    hitPixels.insert(Pixel(4, 1));
    hitPixels.insert(Pixel(4, 2));
    hitPixels.insert(Pixel(5, 0));
    hitPixels.insert(Pixel(5, 1));
    hitPixels.insert(Pixel(5, 2));
    hitPixels.insert(Pixel(5, 3));
    hitPixels.insert(Pixel(5, 4));
    hitPixels.insert(Pixel(5, 5));

    QList< QSet<Pixel> > clusters = getClusters(hitPixels);
    int i;
    for (i = 0; i < clusters.size(); ++i) {
        const QSet<Pixel> &cluster = clusters[i];
        std::cout << "a cluster of" << std::endl;
        QSetIterator<Pixel> iter(cluster);
        while (iter.hasNext()) {
            const Pixel &p = iter.next();
            std::cout << "  (" << p.x << ", " << p.y << ")" << std::endl;
        }
    }
    return 0;
}