closest.c File Reference

#include <assert.h>
#include <cgraph/list.h>
#include <limits.h>
#include <neatogen/kkutils.h>
#include <neatogen/closest.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <util/alloc.h>
#include <util/sort.h>

Include dependency graph for closest.c:

Go to the source code of this file.

Data Structures
struct	Pair
struct	PairHeap

Macros
#define	LT(p, q)   ((p).dist < (q).dist)
#define	EQ(p, q)   ((p).dist == (q).dist)
#define	sub(h, i)   (*pairs_get((h), (i)))
#define	left(i)   (2*(i))
#define	right(i)   (2*(i)+1)
#define	parent(i)   ((i)/2)
#define	insideHeap(h, i)   ((i)<h->heapSize)
#define	greaterPriority(h, i, j)    (LT(h->data[i],h->data[j]) || ((EQ(h->data[i],h->data[j])) && (rand()%2)))
#define	exchange(h, i, j)

Functions
static void	push (pairs_t *s, Pair x)
static bool	pop (pairs_t *s, Pair *x)
static void	heapify (PairHeap *h, size_t i)
static void	freeHeap (PairHeap *h)
static void	initHeap (PairHeap *h, double *place, size_t *ordering, size_t n)
static bool	extractMax (PairHeap *h, Pair *max)
static void	insert (PairHeap *h, Pair edge)
static int	cmp (const void *a, const void *b, void *context)
static void	find_closest_pairs (double *place, size_t n, int num_pairs, pairs_t *pairs_stack)
static void	add_edge (vtx_data *graph, int u, int v)
static void	construct_graph (size_t n, pairs_t *edges_stack, vtx_data **New_graph)
void	closest_pairs2graph (double *place, int n, int num_pairs, vtx_data **graph)

Macro Definition Documentation

EQ

#define EQ	(		p,
			q
	)		((p).dist == (q).dist)

Definition at line 37 of file closest.c.

exchange

#define exchange	(		h,
			i,
			j
	)

Value:

        {Pair temp; \
        temp=h->data[i]; \
        h->data[i]=h->data[j]; \
        h->data[j]=temp; \
}

Definition at line 85 of file closest.c.

greaterPriority

#define greaterPriority	(		h,
			i,
			j
	)		(LT(h->data[i],h->data[j]) || ((EQ(h->data[i],h->data[j])) && (rand()%2)))

Definition at line 82 of file closest.c.

insideHeap

#define insideHeap	(		h,
			i
	)		((i)<h->heapSize)

Definition at line 81 of file closest.c.

left

#define left

(

i

)

(2*(i))

Definition at line 78 of file closest.c.

LT

#define LT	(		p,
			q
	)		((p).dist < (q).dist)

Definition at line 36 of file closest.c.

parent

#define parent

(

i

)

((i)/2)

Definition at line 80 of file closest.c.

right

#define right

(

i

)

(2*(i)+1)

Definition at line 79 of file closest.c.

sub

#define sub	(		h,
			i
	)		(*pairs_get((h), (i)))

Definition at line 67 of file closest.c.

Function Documentation

add_edge()

static void add_edge ( vtx_data *  graph, int  u, int  v  )

static

Definition at line 248 of file closest.c.

References graph(), and NULL.

Referenced by construct_graph().

Here is the call graph for this function:

Here is the caller graph for this function:

closest_pairs2graph()

void closest_pairs2graph	(	double *	place,
		int	n,
		int	num_pairs,
		vtx_data **	graph
	)

Definition at line 315 of file closest.c.

References construct_graph(), find_closest_pairs(), graph(), and num_pairs.

Referenced by iterativePCA_1D().

Here is the call graph for this function:

Here is the caller graph for this function:

cmp()

static int cmp ( const void *  a, const void *  b, void *  context  )

static

Definition at line 161 of file closest.c.

Referenced by find_closest_pairs().

Here is the caller graph for this function:

construct_graph()

static void construct_graph ( size_t  n, pairs_t *  edges_stack, vtx_data **  New_graph  )

static

Definition at line 265 of file closest.c.

References add_edge(), vtx_data::edges, vtx_data::ewgts, free(), gv_calloc(), vtx_data::nedges, pop(), sub, and top().

Referenced by closest_pairs2graph().

Here is the call graph for this function:

Here is the caller graph for this function:

extractMax()

static bool extractMax ( PairHeap *  h, Pair *  max  )

static

Definition at line 133 of file closest.c.

References PairHeap::data, heapify(), and PairHeap::heapSize.

Referenced by find_closest_pairs().

Here is the call graph for this function:

Here is the caller graph for this function:

find_closest_pairs()

static void find_closest_pairs ( double *  place, size_t  n, int  num_pairs, pairs_t *  pairs_stack  )

static

Definition at line 175 of file closest.c.

References cmp(), extractMax(), free(), freeHeap(), gv_calloc(), gv_sort(), initHeap(), insert(), left, neighbor, num_pairs, push(), and right.

Referenced by closest_pairs2graph().

Here is the call graph for this function:

Here is the caller graph for this function:

freeHeap()

static void freeHeap ( PairHeap *  h )

static

Definition at line 110 of file closest.c.

References PairHeap::data, and free().

Referenced by find_closest_pairs().

Here is the call graph for this function:

Here is the caller graph for this function:

heapify()

static void heapify ( PairHeap *  h, size_t  i  )

static

Definition at line 91 of file closest.c.

References exchange, greaterPriority, insideHeap, left, and right.

Referenced by extractMax(), and initHeap().

Here is the caller graph for this function:

initHeap()

static void initHeap ( PairHeap *  h, double *  place, size_t *  ordering, size_t  n  )

static

Definition at line 115 of file closest.c.

References PairHeap::data, edge, gv_calloc(), heapify(), PairHeap::heapSize, PairHeap::maxSize, and SIZE_MAX.

Referenced by find_closest_pairs().

Here is the call graph for this function:

Here is the caller graph for this function:

insert()

static void insert ( PairHeap *  h, Pair  edge  )

static

Definition at line 145 of file closest.c.

References PairHeap::data, edge, exchange, greaterPriority, gv_recalloc(), PairHeap::heapSize, PairHeap::maxSize, and parent.

Referenced by Blocks::Blocks(), find_closest_pairs(), Block::findMinInConstraint(), and Blocks::split().

Here is the call graph for this function:

Here is the caller graph for this function:

pop()

static bool pop ( pairs_t *  s, Pair *  x  )

static

Definition at line 50 of file closest.c.

References free(), and top().

Here is the call graph for this function:

push()

static void push ( pairs_t *  s, Pair  x  )

static

Definition at line 41 of file closest.c.

References copy(), and gv_alloc().

Referenced by find_closest_pairs().

Here is the call graph for this function:

Here is the caller graph for this function: