Back to index

python-biopython  1.60
Functions
KDTree.h File Reference
#include "Neighbor.h"
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions

struct KDTreeKDTree_init (int dim, int bucket_size)
void KDTree_destroy (struct KDTree *tree)
int KDTree_set_data (struct KDTree *tree, float *coords, long int nr_points)
long int KDTree_get_count (struct KDTree *tree)
long int KDTree_neighbor_get_count (struct KDTree *tree)
int KDTree_search_center_radius (struct KDTree *tree, float *coord, float radius)
void KDTree_copy_indices (struct KDTree *tree, long *indices)
void KDTree_copy_radii (struct KDTree *tree, float *radii)
int KDTree_neighbor_search (struct KDTree *tree, float neighbor_radius, struct Neighbor **neighbors)
int KDTree_neighbor_simple_search (struct KDTree *tree, float radius, struct Neighbor **neighbors)

Function Documentation

void KDTree_copy_indices ( struct KDTree tree,
long *  indices 
)

Definition at line 695 of file KDTree.c.

{
    long int i;

    if (tree->_count==0) return;

    for(i=0; i<tree->_count; i++)
    {
        indices[i]=tree->_radius_list[i].index;
    }
}

Here is the caller graph for this function:

void KDTree_copy_radii ( struct KDTree tree,
float *  radii 
)

Definition at line 707 of file KDTree.c.

{
    long int i;

    if (tree->_count==0) return;

    for(i=0; i<tree->_count; i++)
    {
        radii[i]=tree->_radius_list[i].value;
    }
}

Here is the caller graph for this function:

void KDTree_destroy ( struct KDTree tree)

Definition at line 303 of file KDTree.c.

{
    /* clean up KD tree */
    if (!tree) return;
    Node_destroy(tree->_root);
    Region_destroy(tree->_query_region);
    if (tree->_center_coord) free(tree->_center_coord);
    if (tree->_coords) free(tree->_coords);
    if (tree->_data_point_list) free(tree->_data_point_list);
    if (tree->_neighbor_list) free(tree->_neighbor_list);
    free(tree);
}

Here is the call graph for this function:

Here is the caller graph for this function:

long int KDTree_get_count ( struct KDTree tree)

Definition at line 467 of file KDTree.c.

{       
    return tree->_count;
}

Here is the caller graph for this function:

struct KDTree* KDTree_init ( int  dim,
int  bucket_size 
) [read]

Definition at line 271 of file KDTree.c.

{
    struct KDTree* tree;

    tree = malloc(sizeof(struct KDTree));
    if (!tree) return NULL;

    tree->_center_coord= malloc(dim*sizeof(float));
    if (tree->_center_coord==NULL)
    {
        free(tree);
        return NULL;
    }

    tree->dim=dim;

    Region_dim=tree->dim;

    tree->_query_region=NULL;
    tree->_root=NULL;
    tree->_coords=NULL;
    tree->_radius_list = NULL;
    tree->_count=0;
    tree->_neighbor_count=0;
    tree->_neighbor_list = NULL;
    tree->_bucket_size=bucket_size;
    tree->_data_point_list = NULL;
    tree->_data_point_list_size = 0;

    return tree;
}

Here is the caller graph for this function:

long int KDTree_neighbor_get_count ( struct KDTree tree)

Definition at line 472 of file KDTree.c.

{       
    return tree->_neighbor_count;
}

Here is the caller graph for this function:

int KDTree_neighbor_search ( struct KDTree tree,
float  neighbor_radius,
struct Neighbor **  neighbors 
)

Definition at line 1052 of file KDTree.c.

{
    long int i;
    int ok;
    Region_dim=tree->dim;

    if(tree->_neighbor_list)
    {
        free(tree->_neighbor_list);
        tree->_neighbor_list = NULL;
    }
    tree->_neighbor_count=0;
    /* note the use of r^2 to avoid use of sqrt */
    tree->_neighbor_radius=neighbor_radius;
    tree->_neighbor_radius_sq=neighbor_radius*neighbor_radius;

    if (Node_is_leaf(tree->_root))
    {
        /* this is a boundary condition */
        /* bucket_size>nr of points */
        ok = KDTree_search_neighbors_in_bucket(tree, tree->_root);
    }
    else
    {
        /* "normal" situation */
        struct Region *region;
        /* start with [-INF, INF] */
        region= Region_create(NULL, NULL);
        if (!region) return 0;
        ok = KDTree__neighbor_search(tree, tree->_root, region, 0);
        Region_destroy(region);
    }
    if (!ok) return 0;

    *neighbors = NULL;
    for (i = 0; i < tree->_neighbor_count; i++)
    {
        struct Neighbor* neighbor = malloc(sizeof(struct Neighbor));
        if (!neighbor)
        {
            while(1)
            {
                neighbor = *neighbors;
                if (!neighbor) return 0;
                *neighbors = neighbor->next;
                free(neighbor);
            }
        }
        *neighbor = tree->_neighbor_list[i];
        neighbor->next = *neighbors;
        *neighbors = neighbor;
    }

    return 1;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int KDTree_neighbor_simple_search ( struct KDTree tree,
float  radius,
struct Neighbor **  neighbors 
)

Definition at line 1110 of file KDTree.c.

{
    long int i;
    int ok = 1;

    Region_dim=tree->dim;

    tree->_neighbor_radius=radius;
    tree->_neighbor_radius_sq=radius*radius;

    tree->_neighbor_count=0;
    if (tree->_neighbor_list)
    {
        free(tree->_neighbor_list);
        tree->_neighbor_list = NULL;
    }

    DataPoint_sort(tree->_data_point_list, tree->_data_point_list_size, 0);

    for (i=0; i<tree->_data_point_list_size; i++)
    {
        float x1;
        long int j;
        struct DataPoint p1;

        p1=tree->_data_point_list[i];
        x1=p1._coord[0];

        for (j=i+1; j<tree->_data_point_list_size; j++)
        {
            struct DataPoint p2;
            float x2;

            p2=tree->_data_point_list[j];
            x2=p2._coord[0];

            if (fabs(x2-x1)<=radius)
            {
                ok = KDTree_test_neighbors(tree, &p1, &p2);
                if (!ok) break;
            }
            else
            {
                break;
            }
        }
    }

    if (!ok) return 0;

    *neighbors = NULL;

    for (i = 0; i < tree->_neighbor_count; i++)
    {
        struct Neighbor* neighbor = malloc(sizeof(struct Neighbor));
        if (!neighbor)
        {
            while(1)
            {
                neighbor = *neighbors;
                if (!neighbor) return 0;
                *neighbors = neighbor->next;
                free(neighbor);
            }
        }
        *neighbor = tree->_neighbor_list[i];
        neighbor->next = *neighbors;
        *neighbors = neighbor;
    }

    return 1;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int KDTree_search_center_radius ( struct KDTree tree,
float *  coord,
float  radius 
)

Definition at line 647 of file KDTree.c.

{
    int i;
    int dim = tree->dim;
    float* left = malloc(dim*sizeof(float));
    float* right = malloc(dim*sizeof(float));
    if (left==NULL || right==NULL)
    {
        if (left) free(left);
        if (right) free(right);
        return 0;
    }

    Region_dim=tree->dim;

    if (tree->_radius_list)
    {
        free(tree->_radius_list);
        tree->_radius_list = NULL;
    }
    tree->_count=0;

    tree->_radius=radius;
    /* use of r^2 to avoid sqrt use */
    tree->_radius_sq=radius*radius;

    for (i=0; i<tree->dim; i++)
    {
        left[i]=coord[i]-radius;
        right[i]=coord[i]+radius;
        /* set center of query */
        tree->_center_coord[i]=coord[i];
    }

    /* clean up! */
    if (coord) free(coord);

    Region_destroy(tree->_query_region);
    tree->_query_region= Region_create(left, right);

    free(left);
    free(right);

    if (!tree->_query_region) return 0;

    return KDTree_search(tree, NULL, NULL, 0);
}

Here is the call graph for this function:

Here is the caller graph for this function:

int KDTree_set_data ( struct KDTree tree,
float *  coords,
long int  nr_points 
)

Definition at line 610 of file KDTree.c.

{
    long int i;
    int ok;

    Region_dim=tree->dim;

    /* clean up stuff from previous use */
    Node_destroy(tree->_root);
    if (tree->_coords) free(tree->_coords);
    if (tree->_radius_list)
    {
        free(tree->_radius_list);
        tree->_radius_list = NULL;
    }
    tree->_count=0;
    /* keep pointer to coords to delete it */
    tree->_coords=coords;
        
    for (i=0; i<nr_points; i++)
    {
        ok = KDTree_add_point(tree, i, coords+i*tree->dim);
        if (!ok) 
        {
            free(tree->_data_point_list);
            tree->_data_point_list = NULL;
            tree->_data_point_list_size = 0;
            return 0;
        }
    }

    /* build KD tree */
    tree->_root=KDTree_build_tree(tree, 0, 0, 0);
    if(!tree->_root) return 0;
    return 1;
}

Here is the call graph for this function:

Here is the caller graph for this function: