Verbesserung gesucht

Hi

Es geht um eine Umsetzung des Johnson's Algorithm für das Clustering.

Wie kann ich folgenden Code verbessern im Sinn auf Speicher, Geschwindigkeit und Richtigkeit (zB const correctness)

#ifndef CLUSTERING_H
#define CLUSTERING_H

#include <vector>
#include <map>

class Clustering
{
    public:
        class Point
        {
            public:
                Point( double _x = 0, double _y = 0 )
                :   id( last_id++ ), x( _x ), y( _y )
                {   }
                static int last_id;
                int id;
                double x;
                double y;
        };

        typedef std::vector< std::pair<double, double> > Points;
        typedef std::map<int, Point> Cluster;
        typedef std::map<int, Cluster> Clusters;

        // Ctor: Creates for every single point a cluster
        Clustering( const Points& points );
        virtual ~Clustering();
        const Clusters& get_clusters() const;

        // Starts computation
        // max_dist: maximal distance for points in a cluster
        void compute_clusters( const double max_dist = 127 );

    private:
        void merge_clusters( Cluster& a, Cluster& b );
        std::pair< double, std::pair<int, int> > find_closest_clusters() const;
        double single_link_dist( const Cluster& a, const Cluster& b ) const;
        double dist( const Point& a, const Point& b ) const;

        Clusters clusters;
};

#endif // CLUSTERING_H
//-----------------------------------------------------//
//
#include "Clustering.h"

#include <cmath>
#include <iomanip>
#include <iostream>

Clustering::Clustering( const Clustering::Points& points )
{
    for( Points::const_iterator it = points.begin();
         it != points.end(); ++it )
    {
        Point point( it->first, it->second );
        Cluster cluster;
        cluster.insert( std::make_pair( point.id, point ) );
        clusters.insert( std::make_pair( point.id, cluster ) );
    }
}

Clustering::~Clustering()
{
    //dtor
}

const Clustering::Clusters& Clustering::get_clusters() const
{
    return clusters;
}

void Clustering::compute_clusters( const double max_dist )
{
    std::pair< double, std::pair<int, int> > result = find_closest_clusters();
    while( result.first < max_dist )
    {
        Clusters::iterator a = clusters.find( result.second.first );
        Clusters::iterator b = clusters.find( result.second.second );
        merge_clusters( a->second, b->second );
        clusters.erase( b );
        result = find_closest_clusters();
    }
}

void Clustering::merge_clusters
    ( Clustering::Cluster& a, Clustering::Cluster& b )
{
    a.insert( b.begin(), b.end() );
    b.clear();
}

std::pair< double, std::pair<int, int> > Clustering::find_closest_clusters() const
{
    double min = std::numeric_limits<double>::max();
    int a = 0;
    int b = 0;
    for( Clusters::const_iterator it_a = clusters.begin();
         it_a != clusters.end(); ++it_a )
    {
        Clusters::const_iterator it_b = it_a;
        ++it_b;
        for( ; it_b != clusters.end(); ++it_b )
        {
            double dist = single_link_dist( it_a->second, it_b->second );
            if( 0 < dist && dist < min )
            {
                min = dist;
                a = it_a->first;
                b = it_b->first;
            }
        }
    }
    return std::make_pair( min, std::make_pair( a, b ) );
}

double Clustering::single_link_dist
    ( const Clustering::Cluster& a, const Clustering::Cluster& b ) const
{
    double min = std::numeric_limits<double>::max();
    double tmp = min;
    for( Cluster::const_iterator it_a = a.begin();
         it_a != a.end(); ++it_a )
    {
        for( Cluster::const_iterator it_b = b.begin();
             it_b != b.end(); ++it_b )
        {
            tmp = dist( it_a->second, it_b->second );
            if( tmp < min ) min = tmp;
        }
    }
    return min;
}

double Clustering::dist( const Clustering::Point& a, const Clustering::Point& b ) const
{
    return fabs( a.x - b.x ) + fabs( a.y - b.y );
}

int Clustering::Point::last_id = 0;

Für jegliche Tipps, Kritiken und Anregungen offen

MfG
Anton P.

*push*

Undertaker

das hier: http://www.lim.univ-mrs.fr/~thiel/npic/src/dist_gsym.c
ist wohl auch eine implementation dieses algos (steht jedenfalls in den comments). kannst' ja mal mit deinem vergleichen...

Undertaker schrieb:

das hier: http://www.lim.univ-mrs.fr/~thiel/npic/src/dist_gsym.c
ist wohl auch eine implementation dieses algos (steht jedenfalls in den comments). kannst' ja mal mit deinem vergleichen...

Danke, aber das ist ein anderer, der macht Permutationen.

*push*

funktionieren tut es ja, wollt nur mal bitten den code anzuschauen obs richtig ist.

BorisDieKlinge

überflieg sieht gut aus:)