[digraphanalysis-cvs] digraphanalysis/src/libdigraph Makefile, digraph.c, digraph.h,

[Jeff B. <jb...@us...>]

Update of /cvsroot/digraphanalysis/digraphanalysis/src/libdigraph
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv6897/libdigraph

Added Files:
	Makefile digraph.c digraph.h 
Log Message:
move our digraph structs and the functions that operate on them into a library


--- NEW FILE: digraph.h ---
/* $Id: digraph.h,v 1.1 2005/09/20 00:35:07 jbreker Exp $
 *
 * Copyright (C) 2005 Jeff Breker <jb...@sy...>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#ifndef _DIGRAPH_H_
#define _DIGRAPH_H_

#include <sys/queue.h>

#include <stdio.h>

struct listlink
{
	void *object;
	LIST_ENTRY(listlink) list;
};

/* This is LIST_HEAD(list, listlink); but with a function pointer embedded in
 * it for comparison and printing of its objects.
 */
struct list
{
	struct listlink *lh_first;
	int (*compare) (void *, void *);
	void (*print) (FILE *, void *);
};

struct node
{
	char		*uid;
	char		*uiddir;
	float		 msd;
	struct list	*links;
};


struct alias
{
	char		*uid;
	char		*name;
	struct node	*node;
};

struct graph
{
	struct list *alias_list;
	struct list *node_list;
};

int		 alias_compare(void *, void *);
void		 alias_free(struct alias *);
struct alias	*alias_new(char *, char *, struct node *);
void		 alias_print(FILE *, void *);

int		 graph_compare(void *, void *);
void		 graph_free(struct graph *);
struct graph	*graph_new(struct list *, struct list *);
void		 graph_print(FILE *, void *);

void		*list_add(struct list *,
			void *);
int		 list_compare(struct list *,
			struct list *);
struct list	*list_duplicate(struct list *);
void		*list_find(struct list *,
			void *);
void		 list_free(struct list *);
struct list	*list_intersection(struct list *,
			struct list *);
struct list	*list_merge(struct list *,
			struct list *);
struct list	*list_new(int (*) (void *, void *),
			void (*) (FILE *, void *));
struct listlink	*list_new_node(void *);
void		 list_print(FILE *,
			struct list *);
void		*list_remove(struct list *,
			void *);
unsigned int	 list_size(struct list *);
struct list	*list_subtract(struct list *,
			struct list *);
struct list	*list_union(struct list *,
			struct list *);

int		 node_compare(void *, void *);
int		 node_compare_msd(void *, void *);
unsigned int	 node_distance(struct node *, struct node *);
void		 node_free(struct node *);
void		 node_msd(struct node *, struct list *);
struct node	*node_new(char *);
void		 node_print(FILE *, void *);

#endif

--- NEW FILE: digraph.c ---
/* $Id: digraph.c,v 1.1 2005/09/20 00:35:07 jbreker Exp $
 *
 * Copyright (C) 2005 Jeff Breker <jb...@sy...>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#include <sys/queue.h>

#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "digraph.h"

int
alias_compare(void *obj1, void *obj2)
{
	struct alias *alias1 = obj1;
	struct alias *alias2 = obj2;

	return strcmp(alias1->uid, alias2->uid);
}

void
alias_free(struct alias *alias)
{
	free(alias->uid);
	free(alias->name);
	free(alias);
	alias = NULL;
}

struct alias *
alias_new(char *uid, char *name, struct node *node)
{
	struct alias	*alias;

	if((alias = (struct alias *) malloc(sizeof(struct alias))) != NULL)
	{
		if(((alias->uid = (char *) malloc(strlen(uid) + 1)) == NULL) ||
		   ((alias->name = (char *) malloc(strlen(name) + 1)) == NULL))
		{
			free(alias->name);
			free(alias->uid);
			free(alias);
			alias = NULL;
		}
		else
		{
			strlcpy(alias->uid, uid, strlen(uid) + 1);
			strlcpy(alias->name, name, strlen(name) + 1);
			alias->node = node;
		}
	}

	return alias;
}

void
alias_print(FILE *filep, void *alias)
{
	fprintf(filep, "%s", ((struct alias *) alias)->name);

	return;
}

int
graph_compare(void *arg1, void *arg2)
{
	struct graph	*graph1;
	struct graph	*graph2;

	graph1 = arg1;
	graph2 = arg2;

	return list_compare(graph1->node_list, graph2->node_list);
}

struct graph *
graph_new(struct list *alias_list, struct list *node_list)
{
	struct graph	*graph;

	if((graph = (struct graph *) malloc(sizeof(struct graph))) != NULL)
	{
		graph->alias_list = alias_list;
		graph->node_list = node_list;
	}

	return graph;
}

void
graph_print(FILE *filep, void *arg2)
{
	struct graph	*graph;
	struct listlink	*iter;
	struct alias	*alias;
	
	graph = arg2;
	
	LIST_FOREACH(iter, graph->node_list, list)
	{
		alias = list_find(graph->alias_list, alias_new(((struct node *) iter->object)->uid, "", NULL));
		
		fprintf(filep, "  ");	
		node_print(filep, iter->object);
		fprintf(filep, "  ");
		alias_print(filep, alias);
		fprintf(filep, "\n");
		
	}

	return;
}

void *
list_add(struct list *list, void *object)
{
	int i;
	struct listlink	*iter;
	struct listlink	*tmpnode;

	tmpnode = list_new_node(object);

	if(LIST_EMPTY(list))
		LIST_INSERT_HEAD(list, tmpnode, list);
	else
		LIST_FOREACH(iter, list, list)
		{
			if((i = list->compare(object, iter->object)) < 0)
			{
				if(iter == LIST_FIRST(list))
				{
					LIST_INSERT_HEAD(list, tmpnode, list);
				}
				else
					LIST_INSERT_BEFORE(iter, tmpnode, list);
				break;
			}
			else
				if(i == 0)
					return iter->object;
				else
					if(LIST_NEXT(iter, list) == NULL)
						LIST_INSERT_AFTER(iter, tmpnode, list);		
		}

	return object;
}

struct list *
list_duplicate(struct list *list)
{
	struct list *ret_list;

	if((ret_list = list_new(list->compare, list->print)) != NULL)
		if((ret_list = list_merge(ret_list, list)) == NULL)
		{
			list_free(ret_list);
			ret_list = NULL;
		}

	return ret_list;
}

/*
struct list *
list_duplicate(struct list *list)
{
	struct list *ret_list;
	struct listlink *list_link;

	ret_list = list_new(list->compare, list->print);

	LIST_FOREACH(list_link, list, list)
		list_add(ret_list, list_link->object);

	return ret_list;
}
*/

void *
list_find(struct list *list, void *object)
{
	void *ret_object;
	int i;
	struct listlink *iter;

	iter = NULL;
	ret_object = NULL;

	LIST_FOREACH(iter, list, list)
	{
		if((i = list->compare(iter->object, object)) == 0)
			ret_object = iter->object;
		if(i >= 0)
			break;
	}

	return ret_object;
}

void
list_free(struct list *list)
{
	struct listlink *iter;

	for(iter = LIST_FIRST(list); !LIST_EMPTY(list); iter = LIST_FIRST(list))
	{
		LIST_REMOVE(iter, list);
		free(iter);
		iter = NULL;
	}

	free(list);
	list = NULL;

	return;
}

struct list *
list_merge(struct list *list1, struct list *list2)
{
	struct listlink *iter;

	LIST_FOREACH(iter, list2, list)
		list_add(list1, iter->object);

	return list1;
}

struct list *
list_new(int (*compare) (void *, void *), void (*print) (FILE *, void *))
{
	struct list *list;

	if((list = (struct list *) malloc(sizeof(struct list))) != NULL)
	{
		LIST_INIT(list);

		list->compare = compare;
		list->print = print;
	}

	return list;
}

struct listlink *
list_new_node(void *object)
{
	struct listlink	*node;

	if((node = (struct listlink *) malloc(sizeof(struct listlink))) == NULL)
		return NULL;

	node->object = object;

	return node;
}

void *
list_remove(struct list *list, void *object)
{
	void *ret_object;
	struct listlink *iter;
	int i;

	ret_object = NULL;

	LIST_FOREACH(iter, list, list)
	{
		if((i = list->compare(iter->object, object)) == 0)
		{
			ret_object = iter->object;
			LIST_REMOVE(iter, list);
			free(iter);
		}
		if(i >= 0)
			break;
	}

	return ret_object;
}

unsigned int
list_size(struct list *list)
{
	struct listlink	*iter;
	unsigned int	 size;

	size = 0;
	
	LIST_FOREACH(iter, list, list)
		if((size + 1) != 0)
			++size;

	return size;
}

struct list *
list_union(struct list *list1, struct list *list2)
{
	struct list *list;

	if((list = list_duplicate(list1)) != NULL)
		if(list_merge(list, list2) == NULL)
		{
			list_free(list);
			list = NULL;
		}

	return list;
}

int
list_compare(struct list *list1, struct list *list2)
{
	return list1->compare(LIST_FIRST(list1)->object, LIST_FIRST(list2)->object);
}

struct list *
list_intersection(struct list *list1, struct list *list2)
{
	struct listlink *iter;
	struct list *ret_list;

	ret_list = list_new(list1->compare, list1->print);

	LIST_FOREACH(iter, list1, list)
		if(list_find(list2, iter->object) != NULL)
			list_add(ret_list, iter->object);

	return ret_list;
}

void
list_print(FILE *filep, struct list *list)
{
	struct listlink *iter;

	LIST_FOREACH(iter, list, list)
		list->print(filep, iter->object);

	return;
}

struct list *
list_subtract(struct list *list1, struct list *list2)
{
	struct listlink *iter;
	struct list *ret_list;

	ret_list = list_duplicate(list1);

	LIST_FOREACH(iter, list2, list)
		list_remove(ret_list, iter->object);

	return ret_list;
}

void
node_free(struct node *node)
{
	free(node->uid);
	list_free(node->links);
	free(node);
}

struct node *
node_new(char *uid)
{
	struct node *node;
	size_t len;

	node = (struct node *) malloc(sizeof(struct node *));

	len = strlen(uid) + 1;
	node->uid = (char *) malloc(len);
	node->uiddir = (char *) malloc((len >= 3)?3:len);
	strlcpy(node->uid, uid, len);
	strlcpy(node->uiddir, uid, (len >=3)?3:len);

	node->msd = 0;

	node->links = list_new(node_compare, node_print);

	return node;
}

void
node_print(FILE *filep, void *node)
{
	fprintf(filep, "%s", ((struct node *) node)->uid);

	return;
}

int
node_compare(void *node1, void *node2)
{
	return strcmp(((struct node *) node1)->uid, ((struct node *) node2)->uid);
}

int
node_compare_msd(void *node1, void *node2)
{
	int i;
	float float_tmp;

	float_tmp = ((struct node *) node1)->msd - ((struct node *) node2)->msd;
	if(float_tmp == (float) 0)
		i = node_compare(node1, node2);
	else
		if(float_tmp > (float) 0)
			i = 1;
		else
			i = (-1);

	return i;
}


/* keyto == node1
 * keyfrom == node2
 * traversed_keys == traversed_nodes
 * tmp_keys == tmp_nodes
 * list_merge_list == nodelist_merge
 */
unsigned int node_distance(struct node *node1, struct node *node2)
{
	unsigned int distance;
	unsigned int last_known_size, tmpsize;
	struct list *traversed_nodes, *tmp_nodes;
	struct listlink *tmp_node;

	traversed_nodes = list_new(node_compare, node_print);
	last_known_size = 0;
	distance = 1;

	list_merge(traversed_nodes, node1->links);
	while((tmpsize = list_size(traversed_nodes)) != last_known_size)
	{
		if(list_find(traversed_nodes, node2) != NULL)
			return distance;
		last_known_size = tmpsize;
		++distance;
		tmp_nodes = traversed_nodes;
		tmp_node = LIST_FIRST(tmp_nodes);
		traversed_nodes = list_new(node_compare, node_print);
		while(tmp_node != NULL)
		{
			list_add(traversed_nodes, tmp_node->object);
			list_merge(traversed_nodes, ((struct node *) tmp_node->object)->links);
			tmp_node = LIST_NEXT(tmp_node, list);
		}
	}

	return 0;
}

void
node_msd(struct node *node, struct list *nodes)
{
	unsigned int distance, i, num_nodes;
	struct listlink *iter;

	distance = 0;
	num_nodes = 0;

	LIST_FOREACH(iter, nodes, list)
	{
		i = node_distance(node, iter->object);
		if(i > 0)
		{
			distance += i;
			num_nodes++;
		}
	}

	node->msd = ((float) distance) / ((float) num_nodes);

	return;
}
 

--- NEW FILE: Makefile ---
LIB=		digraph
LIBDIR=		/usr/local/lib
LINTLIBDIR=	/usr/local/libdata/lint
SRCS=		digraph.c

.include <../../mk/bsd.lib.mk>