/*
Search::ContextGraph - XS implementation
(C) 2003 Schuyler Erle, Maciej Ceglowski
This is free software, released
under the GPL. See LICENSE for more
information.
*/
# include "cns.h"
# include <unistd.h>
# include <stdlib.h>
# include <stdio.h>
# include <string.h>
# include <math.h>
# define debug 0
Edge *new_edge ( Edge *edge, long sink, float weight ) {
/* Initialize a given edge struct. */
edge->sink = sink;
edge->weight = weight;
return edge;
}
Node *new_node ( Node *node, NodeType type, long capacity ) {
/* Initialize a given node struct. */
//node->type = type;
node->degree = 0;
node->capacity = capacity;
node->edges = calloc( capacity, sizeof(Node) );
memset( node->edges, 0, capacity * sizeof(Node) );
if (debug)
fprintf(stderr, "%p new_node(%d) capacity = %ld\n", node, type, capacity );
return node;
}
Graph *new_graph ( Graph *graph, long capacity,
float activationThreshold, float collectionThreshold, long maxDepth) {
/* Initialize a given graph struct. */
graph->size = 0;
graph->capacity = capacity;
graph->activationThreshold = activationThreshold;
graph->collectionThreshold = collectionThreshold;
graph->maxDepth = maxDepth;
graph->nodes = calloc( capacity, sizeof(Node) );
graph->energy = calloc( capacity, sizeof(float) );
memset( graph->nodes, 0, capacity * sizeof(Node) );
return graph;
}
void free_node (Node *node) {
free( node->edges );
}
void free_graph (Graph *graph) {
long n;
/*fprintf( stderr, "%p graph size: %ld\n", graph, graph->size );*/
for (n = 0; n < graph->size; n++)
free_node( graph->nodes + n );
free( graph->energy);
free( graph->nodes );
free( graph );
}
void reset_graph( Graph *graph ) {
graph->energy = realloc( graph->energy, graph->size * sizeof(float) );
memset( graph->energy, 0, graph->size * sizeof(float) );
graph->numCalls = 0;
graph->maxDepth = -1;
}
Edge *add_edge ( Node *node, long sink, float weight ) {
long deg = ++(node->degree);
long cap = node->capacity;
Edge *edge;
if (debug)
printf( "* adding edge -> %ld(%f) to %p (%ld / %ld)\n",
sink, weight, node, deg, cap );
/* If we have more edges than we've allocated memory for, reallocate. */
if (deg > cap) {
//if( cap < 255 ) {
// node->capacity = cap + 256;
//fprintf( stderr, "\tincreasing node capacity %d , %d\n", node->capacity , cap);
//} else {
//printf( "\tdoubling node capacity %d\n", node->capacity);
node->capacity *= 2;
//}
node->edges = realloc( node->edges, node->capacity * sizeof(Edge) );
memset( node->edges + cap, 0,
( node->capacity - cap ) * sizeof(Edge) );
}
/* Initialize the new edge. */
edge = node->edges + deg - 1;
new_edge( edge, sink, weight );
return edge;
}
int preallocate ( Graph *graph, int nodecount ) {
int original;
original = graph->capacity;
if ( original < nodecount ) {
printf( "Pre-allocationg graph capacity (was %d) to %d\n", original, nodecount );
graph->capacity = nodecount;
graph->nodes = realloc( graph->nodes, graph->capacity * sizeof(Node));
memset( graph->nodes + original, 0, (graph->capacity - original) * sizeof(Node) );
}
return 1;
}
void presize_node( Graph *graph, long id, int size ) {
Node *n = ( graph->nodes + id );
long deg = n->degree;
long cap = n->capacity;
if ( cap < size ) {
n->capacity = size;
n->edges = realloc( n->edges, size * sizeof( Edge ));
memset( n->edges + cap, 0, (n->capacity -cap ) * sizeof(Edge));
//printf( "Presizing node capacity (was %d) to %d\n", cap, n->capacity );
}
}
Node *add_node ( Graph *graph, long id, NodeType type, long capacity ) {
Node *node;
/* If the index of the to-be-created node is bigger than we've allocated,
* we need to reallocated. */
if (debug)
fprintf( stderr, "%p add_node %ld/%d (%d)\n",
graph, id, graph->size, graph->capacity);
if (id >= graph->size) {
long cap = graph->capacity;
graph->size = id + 1;
/* Increase the capacity until it's bigger than the number of nodes
* we need, if such need be, and then resize the lists if the capacity
* changed. */
while (graph->size > graph->capacity )
graph->capacity *= 2;
if (graph->capacity > cap) {
graph->nodes = realloc(
graph->nodes, graph->capacity * sizeof(Node));
memset( graph->nodes + cap, 0, (graph->capacity - cap) * sizeof(Node) );
}
}
if (debug)
fprintf( stderr, "%p --> size: %d capacity: %d\n",
graph, graph->size, graph->capacity);
/* Initialize the new node, unless there already is such a node. */
node = graph->nodes + id;
if ( node->capacity == 0 ){
new_node( node, type, capacity );
if (debug)
fprintf( stderr, "%p --> new node\n",
node);
} else {
fprintf( stderr, "node %p ", node );
}
return node;
}
int energize_node( Graph *graph, long id, float energy, int isStartingPoint) {
Node *node = graph->nodes + id;
float *slot = graph->energy + id;
float subenergy = 0;
static int depth = 0;
long n;
// Keep track of some search statistics
graph->numCalls++;
if ( ++depth > graph->maxDepth )
graph->maxDepth = depth;
if (debug){
int i;
for (i = 0; i< depth;i++)
fprintf( stderr, " ");
fprintf(stderr, "%ld: energizing %f + %f\n", id, node->energy, energy);
}
/* Activate the node and calculate the propagating energy. */
*slot += energy;
if (node->degree) {
//printf( "* denominator is %f\n", denom );
subenergy = energy / (log( node->degree ) + 1);
}
/* Special case handling for nodes with just one neighbor
Normally, we don't propagate energy at a singleton node
But if it's the query node, we want to continue the search */
if ( node->degree == 1 ) {
if ( isStartingPoint == 0 ){
depth--;
return 0;
} else {
subenergy = energy;
}
}
/* **********************/
/* Bail if the subenergy isn't big enough to propagate. */
if (subenergy < graph->activationThreshold){
depth--;
return 0;
}
/* Otherwise, recurse through our neighbors. */
if (debug){
int i;
for (i = 0; i< depth;i++)
fprintf( stderr, " ");
fprintf(stderr, "%ld: propagating subenergy %f to %d neighbors\n",
id, subenergy, node->degree);
}
for (n = 0; n < node->degree; n++) {
energize_node( graph,
node->edges[n].sink, node->edges[n].weight * subenergy , 0 );
}
if (debug){
int i;
for (i = 0; i< depth;i++)
fprintf( stderr, " ");
fprintf(stderr, "%ld: finished\n", id);
}
depth--;
return 1;
}
int compare_results( const void *a, const void *b ) {
const Edge *x = a, *y = b;
/* Sort nodes in descending order by energy. */
return (x->weight > y->weight ? -1 :
(x->weight < y->weight ? 1 : 0));
}
Edge *collect_results( Graph *graph ) {
/* The result list will be a NULL-terminated list of edge structs. The
* weight entry in each struct will contain the accumulated activation energy
* of each sink. */
long n, m;
int result_size = 64;
Edge *result = calloc( result_size, sizeof(Edge) );
/* Find the nodes that scored higher than the threshold. */
for (n = 0, m = 0; n < graph->size; n++ ) {
if ( *( graph->energy + n) > graph->collectionThreshold ) {
Edge *e = result + m++;
e->sink = n;
e->weight = *( graph->energy + n);
}
/* Expand as necessary to fit the result list */
while ( (m+1) > result_size ) {
result_size *= 2;
result = realloc( result, result_size * sizeof( Edge ));
}
}
memset( result + m, 0, sizeof(Edge) );
return result;
}