[digraphanalysis-cvs] digraphanalysis/src analysis.c, analysis.h, graph.c, input.c, list.c, list.h, node.c, node.h, output.c, output.h,

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

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

Modified Files:
	analysis.c analysis.h graph.c input.c list.c list.h node.c 
	node.h output.c output.h 
Log Message:
interm commit


Index: output.c
===================================================================
RCS file: /cvsroot/digraphanalysis/digraphanalysis/src/output.c,v
retrieving revision 1.4
retrieving revision 1.5
diff -C2 -d -r1.4 -r1.5
*** output.c	17 May 2005 00:16:07 -0000	1.4
--- output.c	24 May 2005 22:40:45 -0000	1.5
***************
*** 51,55 ****
   */
  void
! output_report(struct graphlist *graph_list)
  {
  	struct alias		*alias;
--- 51,55 ----
   */
  void
! output_report(struct list *graph_list)
  {
  	struct alias		*alias;

Index: node.c
===================================================================
RCS file: /cvsroot/digraphanalysis/digraphanalysis/src/node.c,v
retrieving revision 1.12
retrieving revision 1.13
diff -C2 -d -r1.12 -r1.13
*** node.c	18 May 2005 01:46:55 -0000	1.12
--- node.c	24 May 2005 22:40:45 -0000	1.13
***************
*** 21,24 ****
--- 21,25 ----
  
  #include "node.h"
+ #include "list.h"
  
  void
***************
*** 46,50 ****
  	node->msd = 0;
  
! 	node->links = nodelist_new();
  
  	return node;
--- 47,51 ----
  	node->msd = 0;
  
! 	node->links = list_new(node_compare);
  
  	return node;
***************
*** 59,73 ****
  }
  
! int node_compare(struct node *node1, struct node *node2)
  {
! 	return strcmp(node1->uid, node2->uid);
  }
  
! int node_compare_msd(struct node *node1, struct node *node2)
  {
  	int i;
  	float float_tmp;
  
! 	float_tmp = node1->msd - node2->msd;
  	if(float_tmp == (float) 0)
  		i = node_compare(node1, node2);
--- 60,76 ----
  }
  
! 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);
***************
*** 92,106 ****
  	unsigned int distance;
  	unsigned int last_known_size, tmpsize;
! 	struct nodelist *traversed_nodes, *tmp_nodes;
! 	struct nodelink *tmp_node;
  
! 	traversed_nodes = nodelist_new();
  	last_known_size = 0;
  	distance = 1;
  
! 	nodelist_merge(traversed_nodes, node1->links);
! 	while((tmpsize = nodelist_size(traversed_nodes)) != last_known_size)
  	{
! 		if(nodelist_find(traversed_nodes, node2) != NULL)
  			return distance;
  		last_known_size = tmpsize;
--- 95,109 ----
  	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);
  	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;
***************
*** 108,116 ****
  		tmp_nodes = traversed_nodes;
  		tmp_node = LIST_FIRST(tmp_nodes);
! 		traversed_nodes = nodelist_new();
  		while(tmp_node != NULL)
  		{
! 			nodelist_add(traversed_nodes, tmp_node->node);
! 			nodelist_merge(traversed_nodes, ((struct node *) tmp_node->node)->links);
  			tmp_node = LIST_NEXT(tmp_node, list);
  		}
--- 111,119 ----
  		tmp_nodes = traversed_nodes;
  		tmp_node = LIST_FIRST(tmp_nodes);
! 		traversed_nodes = list_new(node_compare);
  		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);
  		}
***************
*** 120,135 ****
  }
  
! void node_msd(struct node *node, struct nodelist *nodes)
  {
  	unsigned int distance, i, num_nodes;
! 	struct nodelink *iter;
  
  	distance = 0;
  	num_nodes = 0;
- 	iter = LIST_FIRST(nodes);
  
! 	while(iter != NULL)
  	{
! 		i = node_distance(node, iter->node);
  		if(i > 0)
  		{
--- 123,138 ----
  }
  
! 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)
  		{
***************
*** 137,141 ****
  			num_nodes++;
  		}
- 		iter = LIST_NEXT(iter, list);
  	}
  
--- 140,143 ----

Index: analysis.h
===================================================================
RCS file: /cvsroot/digraphanalysis/digraphanalysis/src/analysis.h,v
retrieving revision 1.1
retrieving revision 1.2
diff -C2 -d -r1.1 -r1.2
*** analysis.h	17 May 2005 00:12:45 -0000	1.1
--- analysis.h	24 May 2005 22:40:45 -0000	1.2
***************
*** 22,26 ****
  
  void			 analysis_nodes(struct graph *);
! struct graphlist	*analysis_seperate_nodes(struct graph *);
  int			 do_analysis(struct graph *, char *);
  
--- 22,26 ----
  
  void			 analysis_nodes(struct graph *);
! struct list	*analysis_seperate_nodes(struct graph *);
  int			 do_analysis(struct graph *, char *);
  

Index: list.c
===================================================================
RCS file: /cvsroot/digraphanalysis/digraphanalysis/src/list.c,v
retrieving revision 1.4
retrieving revision 1.5
diff -C2 -d -r1.4 -r1.5
*** list.c	18 May 2005 01:46:55 -0000	1.4
--- list.c	24 May 2005 22:40:45 -0000	1.5
***************
*** 22,47 ****
  #include <stdlib.h>
  
  #include "list.h"
  
  void *
! list_add(struct list *list, void *object, int (*compare)(void *, void *))
  {
  	int i;
! 	struct node_t *iter, *tmpnode;
  
  	tmpnode = list_new_node(object);
  	if(LIST_EMPTY(list))
! 		LIST_INSERT_HEAD(list, tmpnode, entries);
  	else
! 		LIST_FOREACH(iter, list, entries)
  		{
! 			if((i = compare(object, iter->object)) < 0)
  			{
  				if(iter == LIST_FIRST(list))
  				{
! 					LIST_INSERT_HEAD(list, tmpnode, entries);
  				}
  				else
! 					LIST_INSERT_BEFORE(iter, tmpnode, entries);
  				break;
  			}
--- 22,52 ----
  #include <stdlib.h>
  
+ #include "alias.h"
+ #include "graph.h"
+ #include "node.h"
  #include "list.h"
  
  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;
  			}
***************
*** 50,55 ****
  					return iter->object;
  				else
! 					if(LIST_NEXT(iter, entries) == NULL)
! 						LIST_INSERT_AFTER(iter, tmpnode, entries);		
  		}
  
--- 55,60 ----
  					return iter->object;
  				else
! 					if(LIST_NEXT(iter, list) == NULL)
! 						LIST_INSERT_AFTER(iter, tmpnode, list);		
  		}
  
***************
*** 57,105 ****
  }
  
! /* Returns NULL on error
!  */
! struct list_t *list_duplicate(struct list_t *list, int (*compare)(void *, void *))
  {
! 	struct list_t *ret_list;
  
! 	if((ret_list = list_new()) == NULL)
! 		return NULL;
! 	if(list_merge_list(ret_list, list, compare) == NULL)
! 		return NULL;
  
  	return ret_list;
  }
  
! void *list_find_object(struct list_t *list, void *object, int (*compare)(void *, void*))
  {
  	int i;
! 	struct node_t *iter;
  
! 	iter = LIST_FIRST(list);
  
! 	while(iter != NULL)
  	{
! 		if((i = compare(iter->object, object)) == 0)
! 			return iter->object;
! 		else
! 			if(i > 0)
! 				break;
! 		iter = LIST_NEXT(iter, entries);
  	}
  
! 	return NULL;
  }
  
! void list_free(struct list_t *list)
  {
! 	struct node_t *iter;
! 
! 	iter = LIST_FIRST(list);
  
! 	while(iter != NULL)
  	{
! 		LIST_FIRST(list) = LIST_NEXT(iter, entries);
  		free(iter);
! 		iter = LIST_FIRST(list);
  	}
  
--- 62,127 ----
  }
  
! struct list *
! list_duplicate(struct list *list)
  {
! 	struct list *ret_list;
  
! 	if((ret_list = list_new(list->compare)) != NULL)
! 		if(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_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;
  	}
  
***************
*** 110,148 ****
  }
  
! /* Returns
!  *	NULL on error
!  *	list1 on success
!  */
! struct list_t *list_merge_list(struct list_t *list1, struct list_t *list2, int (*compare)(void *, void *))
  {
! 	struct node_t *iter;
  
! 	LIST_FOREACH(iter, list2, entries)
! 		list_add_object(list1, iter->object, compare);
  
  	return list1;
  }
  
! /* Returns NULL on error
!  */
! struct list_t *list_new()
  {
! 	struct list_t *list;
  
! 	if((list = (struct list_t *) malloc(sizeof(struct list_t))) == NULL)
! 		return NULL;
  
! 	LIST_INIT(list);
  
  	return list;
  }
  
! /* Returns NULL on error
!  */
! struct node_t *list_new_node(void *object)
  {
! 	struct node_t *node;
  
! 	if((node = (struct node_t *) malloc(sizeof(struct node_t))) == NULL)
  		return NULL;
  
--- 132,167 ----
  }
  
! 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 *))
  {
! 	struct list *list;
  
! 	if((list = (struct list *) malloc(sizeof(struct list))) != NULL)
! 	{
! 		LIST_INIT(list);
  
! 		list->compare = compare;
! 	}
  
  	return list;
  }
  
! struct listlink *
! list_new_node(void *object)
  {
! 	struct listlink	*node;
  
! 	if((node = (struct listlink *) malloc(sizeof(struct listlink))) == NULL)
  		return NULL;
  
***************
*** 152,598 ****
  }
  
! void list_remove(struct list_t *list, void *object, int (*compare)(void *, void *))
  {
! 	struct node_t *iter;
  	int i;
  
! 	iter = LIST_FIRST(list);
  
! 	while(iter != NULL)
  	{
! 		if((i = compare(iter->object, object)) == 0)
  		{
! 			if(iter == LIST_FIRST(list))
! 				LIST_FIRST(list) = LIST_NEXT(iter, entries);
! 			else
! 				LIST_REMOVE(iter, entries);
  			free(iter);
- 			break;
  		}
! 		else
! 			if(i < 0)
! 				break;
! 		iter = LIST_NEXT(iter, entries);
! 	}
! 
! 	return;
! }
! 
! /* Optimize with quicksort or heapsort I think */ 
! struct list_t *list_resort(struct list_t *list, int (*compare)(void *, void *))
! {
! 	struct node_t *iter, *tmpiter;
! 
! 	iter = LIST_FIRST(list);
! 	LIST_FIRST(list) = NULL; 
! 
! 	while(iter != NULL)
! 	{
! 		list_add_object(list, iter->object, compare);
! 		tmpiter = iter;
! 		iter = LIST_NEXT(iter, entries);
! 		free(tmpiter);
  	}
  
! 	return list;
! }
! 
! unsigned int list_size(struct list_t *list)
! {
! 	unsigned int i = 0;
! 	struct node_t *iter;
! 
! 	LIST_FOREACH(iter, list, entries)
! 		++i;
! 
! 	return i;
! }
! /* Return
!  *	NULL on error
!  *	list on success
!  */
! struct list_t *list_union(struct list_t *list1, struct list_t *list2, int (*compare)(void *, void *))
! {
! 	struct list_t *list;
! 
! 	if(((list = list_new()) == NULL) ||
! 	   (list_merge_list(list, list1, compare) == NULL) ||
! 	   (list_merge_list(list, list2, compare) == NULL))
! 		return NULL;
! 
! 	return list;
  }
  
! 
! struct alias *
! aliaslist_add(struct list *alias_list, struct alias *alias)
  {
! 	int i;
! 	struct listlink *alias_iter, *alias_link;
! 
! 	alias_link = (struct listlink *) malloc(sizeof(struct listlink));
! 	alias_link->object = alias;
  
! 	if(LIST_EMPTY(alias_list))
! 		LIST_INSERT_HEAD(alias_list, alias_link, list);
! 	else
! 		LIST_FOREACH(alias_iter, alias_list, list)
! 		{
! 			if((i = alias_compare(alias, alias_iter->object)) < 0)
! 			{
! 				if(alias_iter == LIST_FIRST(alias_list))
! 					LIST_INSERT_HEAD(alias_list, alias_link, list);
! 				else
! 					LIST_INSERT_BEFORE(alias_iter, alias_link, list);
! 				break;
! 			}
! 			else
! 				if(i == 0)
! 					return alias_iter->object;
! 				else
! 					if(LIST_NEXT(alias_iter, list) == NULL)
! 						LIST_INSERT_AFTER(alias_iter, alias_link, list);		
! 		}
  
! 	return alias;
  }
  
  struct list *
! aliaslist_duplicate(struct list *alias_list1)
! {
! 	struct list *alias_list2;
! 	struct link *alias_link;
! 
! 	alias_list2 = list_new(alias_compare);
! 
! 	LIST_FOREACH(alias_link, alias_list1, list)
! 		aliaslist_add(alias_list2, alias_link->alias);
! 
! 	return alias_list2;
! }
! 
! /* This should take a struct alias, not a char */
! struct alias *
! aliaslist_find(struct aliaslist *alias_list, char *uid)
! {
! 	int i;
! 	struct aliaslink *alias_link;
! 
! 	alias_link = LIST_FIRST(alias_list);
! 
! 	LIST_FOREACH(alias_link, alias_list, list)
! 	{
! 		if((i = strcmp(((struct alias *) alias_link->alias)->uid, uid)) == 0)
! 			return alias_link->alias;
! 		else
! 			if(i > 0)
! 				break;
! 	}
! 
! 	return NULL;
! }
! 
! void
! aliaslist_free(struct aliaslist *alias_list)
! {
! 	struct aliaslink *alias_link;
! 
! 	LIST_FOREACH(alias_link, alias_list, list)
! 	{
! 		LIST_REMOVE(alias_link, list);
! 		alias_free(alias_link->alias);
! 		free(alias_link);
! 		alias_link = NULL;
! 	}
! 	free(alias_list);
! 
! 	return;
! }
! 
! struct aliaslist *
! aliaslist_new()
! {
! 	struct aliaslist	*list;
! 
! 	if((list = (struct aliaslist *) malloc(sizeof(struct aliaslist))) != NULL)
! 		LIST_INIT(list);
! 
! 	return list;
! }
! 
! struct graph *
! graphlist_add(struct graphlist *graph_list, struct graph *graph)
! {
! 	int i;
! 	struct graphlink *graph_iter, *graph_link;
! 
! 	graph_link = (struct graphlink *) malloc(sizeof(struct graphlink));
! 	graph_link->graph = graph;
! 
! 	if(LIST_EMPTY(graph_list))
! 		LIST_INSERT_HEAD(graph_list, graph_link, list);
! 	else
! 		LIST_FOREACH(graph_iter, graph_list, list)
! 		{
! 			if((i = graph_compare(graph, graph_iter->graph)) < 0)
! 			{
! 				if(graph_iter == LIST_FIRST(graph_list))
! 					LIST_INSERT_HEAD(graph_list, graph_link, list);
! 				else
! 					LIST_INSERT_BEFORE(graph_iter, graph_link, list);
! 				break;
! 			}
! 			else
! 				if(i == 0)
! 					return graph_iter->graph;
! 				else
! 					if(LIST_NEXT(graph_iter, list) == NULL)
! 						LIST_INSERT_AFTER(graph_iter, graph_link, list);
! 		}
! 
! 	return graph;
! }
! 
! struct graphlist *
! graphlist_new()
! {
! 	struct graphlist	*graphlist;
! 
! 	if((graphlist = (struct graphlist *) malloc(sizeof(struct graphlist))) != NULL)
! 		LIST_INIT(graphlist);
! 
! 	return graphlist;
! }
! struct node *
! nodelist_add(struct nodelist *node_list, struct node *node)
! {
! 	int i;
! 	struct nodelink *node_iter, *node_link;
! 
! 	node_link = (struct nodelink *) malloc(sizeof(struct nodelink));
! 	node_link->node = node;
! 
! 	if(LIST_EMPTY(node_list))
! 		LIST_INSERT_HEAD(node_list, node_link, list);
! 	else
! 		LIST_FOREACH(node_iter, node_list, list)
! 		{
! 			if((i = node_compare(node, node_iter->node)) < 0)
! 			{
! 				if(node_iter == LIST_FIRST(node_list))
! 					LIST_INSERT_HEAD(node_list, node_link, list);
! 				else
! 					LIST_INSERT_BEFORE(node_iter, node_link, list);
! 				break;
! 			}
! 			else
! 				if(i == 0)
! 					return node_iter->node;
! 				else
! 					if(LIST_NEXT(node_iter, list) == NULL)
! 						LIST_INSERT_AFTER(node_iter, node_link, list);
! 		}
! 
! 	return node;
! }
! 
! struct node *
! nodelist_add_msd(struct nodelist *node_list, struct node *node)
  {
! 	int i;
! 	struct nodelink *node_iter, *node_link;
! 
! 	node_link = (struct nodelink *) malloc(sizeof(struct nodelink));
! 	node_link->node = node;
  
! 	if(LIST_EMPTY(node_list))
! 		LIST_INSERT_HEAD(node_list, node_link, list);
! 	else
! 		LIST_FOREACH(node_iter, node_list, list)
  		{
! 			if((i = node_compare_msd(node, node_iter->node)) < 0)
! 			{
! 				if(node_iter == LIST_FIRST(node_list))
! 					LIST_INSERT_HEAD(node_list, node_link, list);
! 				else
! 					LIST_INSERT_BEFORE(node_iter, node_link, list);
! 				break;
! 			}
! 			else
! 				if(i == 0)
! 					return node_iter->node;
! 				else
! 					if(LIST_NEXT(node_iter, list) == NULL)
! 						LIST_INSERT_AFTER(node_iter, node_link, list);
  		}
  
! 	return node;
  }
  
  int
! nodelist_compare(struct nodelist *node_list1, struct nodelist *node_list2)
! {
! 	return nodelist_size(node_list2) - nodelist_size(node_list1);
! }
! 
! /* How should we go about duplicating a msd organized list.
!  */
! struct nodelist *
! nodelist_duplicate(struct nodelist *node_list1)
! {
! 	struct nodelist *node_list2;
! 	struct nodelink *node_link;
! 
! 	node_list2 = nodelist_new();
! 
! 	LIST_FOREACH(node_link, node_list1, list)
! 		nodelist_add(node_list2, node_link->node);
! 
! 	return node_list2;
! }
! 
! struct node *
! nodelist_find(struct nodelist *node_list, struct node *node)
! {
! 	int i;
! 	struct nodelink *node_link;
! 
! 	LIST_FOREACH(node_link, node_list, list)
! 		if((i = node_compare(node_link->node, node)) == 0)
! 			return node_link->node;
! 		else
! 			if(i > 0)
! 				break;
! 
! 	return NULL;
! }
! 
! void
! nodelist_free(struct nodelist *node_list)
! {
! 	struct nodelink *node_link, *tmp_link;
! 
! 	tmp_link = NULL;
! 
! 	LIST_FOREACH(node_link, node_list, list)
! 	{
! 		free(tmp_link);
! 		tmp_link = node_link;
! 		LIST_REMOVE(node_link, list);
! 	}
! 
! 	free(node_link);
! 	free(node_list);
! }
! 
! struct nodelist *
! nodelist_intersection(struct nodelist *node_list1, struct nodelist *node_list2)
  {
! 	struct nodelink *node_iter;
! 	struct nodelist *node_list;
! 
! 	node_list = nodelist_new();
! 	LIST_FOREACH(node_iter, node_list1, list)
! 		if(nodelist_find(node_list2, node_iter->node) != NULL)
! 			nodelist_add(node_list, node_iter->node);
! 
! 	return node_list;
  }
  
! struct nodelist *
! nodelist_merge(struct nodelist *node_list1, struct nodelist *node_list2)
  {
! 	struct nodelink *node_iter;
! 
! 	LIST_FOREACH(node_iter, node_list2, list)
! 		nodelist_add(node_list1, node_iter->node);
! 
! 	return node_list1;
! }
  
! struct nodelist *
! nodelist_new()
! {
! 	struct nodelist	*list;
  
! 	if((list = (struct nodelist *) malloc(sizeof(struct nodelist))) != NULL)
! 		LIST_INIT(list);
  
! 	return list;
  }
  
  void
! nodelist_print(FILE *filep, struct nodelist *node_list)
  {
! 	struct nodelink *node_link;
  
! 	LIST_FOREACH(node_link, node_list, list)
! 		node_print(filep, node_link->node);
  
  	return;
  }
  
! struct node *
! nodelist_remove(struct nodelist *node_list, struct node *node)
! {
! 	int i;
! 	struct node *tmp_node;
! 	struct nodelink *node_link;
! 
! 	LIST_FOREACH(node_link, node_list, list)
! 	{
! 		tmp_node = node_link->node;
! 		if((i = node_compare(tmp_node, node)) == 0)
! 		{
! 			LIST_REMOVE(node_link, list);
! 			free(node_link);
! 			return tmp_node;
! 		}
! 		else
! 			if(i > 0)
! 				break;
! 	}
! 
! 	return NULL;
! }
! 
! unsigned int
! nodelist_size(struct nodelist *node_list)
! {
! 	struct nodelink *node_iter;
! 	unsigned int size;
! 
! 	size = 0;
! 
! 	LIST_FOREACH(node_iter, node_list, list)
! 		++size;
! 
! 	return size;
! }
! 
! struct nodelist *
! nodelist_subtract(struct nodelist *node_list1, struct nodelist *node_list2)
  {
! 	struct nodelink *node_link;
! 	struct nodelist *node_list;
! 
! 	node_list = nodelist_duplicate(node_list1);
! 
! 	LIST_FOREACH(node_link, node_list2, list)
! 		nodelist_remove(node_list, node_link->node);
! 
! 	return node_list;
! }
  
! struct nodelist *
! nodelist_union(struct nodelist *node_list1, struct nodelist *node_list2)
! {
! 	struct nodelist *node_list;
  
! 	node_list = nodelist_duplicate(node_list1);
! 	nodelist_merge(node_list, node_list2);
  
! 	return node_list;
  }
  
- 
--- 171,270 ----
  }
  
! 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;
  
! 	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);
  
! 	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;
  }
  

Index: node.h
===================================================================
RCS file: /cvsroot/digraphanalysis/digraphanalysis/src/node.h,v
retrieving revision 1.9
retrieving revision 1.10
diff -C2 -d -r1.9 -r1.10
*** node.h	17 May 2005 14:30:26 -0000	1.9
--- node.h	24 May 2005 22:40:45 -0000	1.10
***************
*** 31,36 ****
  };
  
! int		 node_compare(struct node *, struct node *);
! int		 node_compare_msd(struct node *, struct node *);
  unsigned int	 node_distance(struct node *, struct node *);
  void		 node_free(struct node *);
--- 31,36 ----
  };
  
! int		 node_compare(void *, void *);
! int		 node_compare_msd(void *, void *);
  unsigned int	 node_distance(struct node *, struct node *);
  void		 node_free(struct node *);
***************
*** 38,55 ****
  void		 node_print(FILE *, struct node *);
  
- struct node	*nodelist_add(struct list *, struct node *);
- struct node	*nodelist_add_msd(struct list *, struct node *);
- int		 nodelist_compare(struct list *, struct list *);
- struct list	*nodelist_duplicate(struct list *);
- struct node	*nodelist_find(struct list *, struct node *);
- void		 nodelist_free(struct list *);
- struct list *nodelist_intersection(struct list *, struct list *);
- struct list	*nodelist_merge(struct list *, struct list *);
- struct list	*nodelist_new(void);
- void		 nodelist_print(FILE *, struct list *);
- struct node	*nodelist_remove(struct list *, struct node *);
- unsigned int	 nodelist_size(struct list *);
- struct list *nodelist_subtract(struct list *, struct list *);
- struct list *nodelist_union(struct list *, struct list *);
- 
  #endif /* _NODE_H_ */
--- 38,40 ----

Index: output.h
===================================================================
RCS file: /cvsroot/digraphanalysis/digraphanalysis/src/output.h,v
retrieving revision 1.1
retrieving revision 1.2
diff -C2 -d -r1.1 -r1.2
*** output.h	16 May 2005 23:59:03 -0000	1.1
--- output.h	24 May 2005 22:40:45 -0000	1.2
***************
*** 24,28 ****
  
  int	output_main_directory(char *);
! void	output_report(struct graphlist *);
  int	output_new_directory(char *);
  void	output_file(struct node *, struct graph *);
--- 24,28 ----
  
  int	output_main_directory(char *);
! void	output_report(struct list *);
  int	output_new_directory(char *);
  void	output_file(struct node *, struct graph *);

Index: input.c
===================================================================
RCS file: /cvsroot/digraphanalysis/digraphanalysis/src/input.c,v
retrieving revision 1.1
retrieving revision 1.2
diff -C2 -d -r1.1 -r1.2
*** input.c	17 May 2005 00:08:06 -0000	1.1
--- input.c	24 May 2005 22:40:45 -0000	1.2
***************
*** 22,25 ****
--- 22,26 ----
  #include "graph.h"
  #include "node.h"
+ #include "list.h"
  
  char *
***************
*** 65,69 ****
  	char		 type;
  
! 	for(c = type = getchar(); type == 'e' || type == 'n' || type == 'a'; c = type = getchar())
  	{
  		if(((c = getchar()) != ':') && (c != EOF))
--- 66,70 ----
  	char		 type;
  
! 	for(c = type = getchar(); type == 'e' || type == 'n'; c = type = getchar())
  	{
  		if(((c = getchar()) != ':') && (c != EOF))
***************
*** 75,99 ****
  		if(*field1 == EOF)
  			break;
! 		if(type != 'n') /* Grab 2nd field for edges and alias' */
  		{
  			if(((c = getchar()) != ':') && (c != EOF))
! 				errx(EX_DATAERR, "2: Invalid character, %c (ASCII: %d), encountered!\n", c, c);
  			if(c == EOF)
  				break;
! 			if((field2 = get_field()) == NULL)
  				errx(EX_OSERR, "Cannot allocate memory!\n");
! 			if(*field2 == EOF)
  				break;
- 			if(type == 'a') /* Grab 3rd field for an alias */
- 			{
- 				if(((c = getchar()) != ':') && (c != EOF))
- 					errx(EX_DATAERR, "3: Invalid character, %c (ASCII: %d), encountered!\n", c, c);
- 				if(c == EOF)
- 					break;
- 				if((field3 = get_field()) == NULL)
- 					errx(EX_OSERR, "Cannot allocate memory!\n");
- 				if(*field3 == EOF)
- 					break;
- 			}
  		}
  		if(((c = getchar()) != '\n') && (c != EOF))
--- 76,97 ----
  		if(*field1 == EOF)
  			break;
! 		if(((c = getchar()) != ':') && (c != EOF))
! 			errx(EX_DATAERR, "2: Invalid character, %c (ASCII: %d), encountered!\n", c, c);
! 		if(c == EOF)
! 			break;
! 		if((field2 = get_field()) == NULL)
! 			errx(EX_OSERR, "Cannot allocate memory!\n");
! 		if(*field2 == EOF)
! 			break;
! 		if(type == 'n') /* Grab 3rd field for an alias */
  		{
  			if(((c = getchar()) != ':') && (c != EOF))
! 				errx(EX_DATAERR, "3: Invalid character, %c (ASCII: %d), encountered!\n", c, c);
  			if(c == EOF)
  				break;
! 			if((field3 = get_field()) == NULL)
  				errx(EX_OSERR, "Cannot allocate memory!\n");
! 			if(*field3 == EOF)
  				break;
  		}
  		if(((c = getchar()) != '\n') && (c != EOF))
***************
*** 102,114 ****
  		switch (type)
  		{
! 		case 'a':
  			node1 = node_new(field1);
  			free(field1);
! 			if((node2 = nodelist_add(graph->node_list, node1)) != node1)
  				node_free(node1);
  			alias1 = alias_new(field2, field3, node2);
  			free(field2);
  			free(field3);
! 			if((alias2 = aliaslist_add(graph->alias_list, alias1)) != alias1)
  				alias_free(alias1);
  			break;
--- 100,112 ----
  		switch (type)
  		{
! 		case 'n':
  			node1 = node_new(field1);
  			free(field1);
! 			if((node2 = list_add(graph->node_list, node1)) != node1)
  				node_free(node1);
  			alias1 = alias_new(field2, field3, node2);
  			free(field2);
  			free(field3);
! 			if((alias2 = list_add(graph->alias_list, alias1)) != alias1)
  				alias_free(alias1);
  			break;
***************
*** 116,137 ****
  			node1 = node_new(field1);
  			free(field1);
! 			if((node2 = nodelist_add(graph->node_list, node1)) != node1)
  				node_free(node1);
  			node1 = node_new(field2);
  			free(field2);
! 			if((node3 = nodelist_add(graph->node_list, node1)) != node1)
  				node_free(node1);
! 			if((node1 = nodelist_add(node2->links, node3)) != node3)
  				node_free(node3);
  			break;
- 		/* a lines will eventually be renamed to n lines, when this happens
- 		 * the following gets ripped out.
- 		 */
- 		case 'n':
- 			node1 = node_new(field1);
- 			free(field1);
- 			if((node2 = nodelist_add(graph->node_list, node1)) != node1)
- 				node_free(node1);
- 			break;
  		}
  
--- 114,126 ----
  			node1 = node_new(field1);
  			free(field1);
! 			if((node2 = list_add(graph->node_list, node1)) != node1)
  				node_free(node1);
  			node1 = node_new(field2);
  			free(field2);
! 			if((node3 = list_add(graph->node_list, node1)) != node1)
  				node_free(node1);
! 			if((node1 = list_add(node2->links, node3)) != node3)
  				node_free(node3);
  			break;
  		}
  

Index: list.h
===================================================================
RCS file: /cvsroot/digraphanalysis/digraphanalysis/src/list.h,v
retrieving revision 1.6
retrieving revision 1.7
diff -C2 -d -r1.6 -r1.7
*** list.h	18 May 2005 01:46:55 -0000	1.6
--- list.h	24 May 2005 22:40:45 -0000	1.7
***************
*** 34,37 ****
--- 34,38 ----
  	struct listlink *lh_first;
  	int (*compare) (void *, void *);
+ 	void (*print) (FILE *, void *);
  };
  
***************
*** 49,55 ****
  			struct list *);
  struct list	*list_new(int (*) (void *, void *));
  void		 list_print(FILE *,
  			struct list *);
! void		 list_remove(struct list *,
  			void *);
  unsigned int	 list_size(struct list *);
--- 50,57 ----
  			struct list *);
  struct list	*list_new(int (*) (void *, 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 *);

Index: graph.c
===================================================================
RCS file: /cvsroot/digraphanalysis/digraphanalysis/src/graph.c,v
retrieving revision 1.4
retrieving revision 1.5
diff -C2 -d -r1.4 -r1.5
*** graph.c	18 May 2005 01:46:55 -0000	1.4
--- graph.c	24 May 2005 22:40:45 -0000	1.5
***************
*** 25,33 ****
  graph_compare(struct graph *graph1, struct graph *graph2)
  {
! 	return nodelist_compare(graph1->node_list, graph2->node_list);
  }
  
  struct graph *
! graph_new(struct aliaslist *alias_list, struct nodelist *node_list)
  {
  	struct graph	*graph;
--- 25,33 ----
  graph_compare(struct graph *graph1, struct graph *graph2)
  {
! 	return list_compare(graph1->node_list, graph2->node_list);
  }
  
  struct graph *
! graph_new(struct list *alias_list, struct list *node_list)
  {
  	struct graph	*graph;

Index: analysis.c
===================================================================
RCS file: /cvsroot/digraphanalysis/digraphanalysis/src/analysis.c,v
retrieving revision 1.1
retrieving revision 1.2
diff -C2 -d -r1.1 -r1.2
*** analysis.c	17 May 2005 00:12:45 -0000	1.1
--- analysis.c	24 May 2005 22:40:45 -0000	1.2
***************
*** 16,20 ****
--- 16,26 ----
   */
  
+ #include <sys/queue.h>
+ 
  #include "analysis.h"
+ #include "graph.h"
+ #include "list.h"
+ #include "node.h"
+ #include "output.h"
  
  /* Analyze the keys and output the results.
***************
*** 25,29 ****
  do_analysis(struct graph *graph, char *outputdir)
  {
! 	struct graphlist	*graph_list;
  
  	graph_list = NULL;
--- 31,35 ----
  do_analysis(struct graph *graph, char *outputdir)
  {
! 	struct list	*graph_list;
  
  	graph_list = NULL;
***************
*** 39,65 ****
  analysis_nodes(struct graph *graph)
  {
! 	struct nodelink *node_link;
  
  	LIST_FOREACH(node_link, graph->node_list, list)
! 		output_file(node_link->node, graph);
  
  	return;
  }
  
! struct graphlist *
  analysis_seperate_nodes(struct graph *graph)
  {
! 	struct aliaslist	*alias_list;
! 	struct graphlist	*graph_list;
! 	struct nodelink		*node_link1;
! 	struct nodelink		*node_link2;
! 	struct nodelist		*node_list;
! 	struct nodelist		*node_list_msd1;
! 	struct nodelist		*node_list_msd2;
  
  	/* Duplicate the graphs alias and node lists so as to not modify the original copies.
  	 */
! 	alias_list = aliaslist_duplicate(graph->alias_list);
! 	node_list = nodelist_duplicate(graph->node_list);
  
  	/* Create the list, to add the msd sorted graphs to.
--- 45,71 ----
  analysis_nodes(struct graph *graph)
  {
! 	struct listlink *node_link;
  
  	LIST_FOREACH(node_link, graph->node_list, list)
! 		output_file(node_link->object, graph);
  
  	return;
  }
  
! struct list *
  analysis_seperate_nodes(struct graph *graph)
  {
! 	struct list	*alias_list;
! 	struct list	*graph_list;
! 	struct listlink		*node_link1;
! 	struct listlink		*node_link2;
! 	struct list		*node_list;
! 	struct list		*node_list_msd1;
! 	struct list		*node_list_msd2;
  
  	/* Duplicate the graphs alias and node lists so as to not modify the original copies.
  	 */
! 	alias_list = list_duplicate(graph->alias_list);
! 	node_list = list_duplicate(graph->node_list);
  
  	/* Create the list, to add the msd sorted graphs to.
***************
*** 73,102 ****
  		/* Create two new node lists.
  		 */
! 		if(((node_list_msd1 = nodelist_new()) == NULL) ||
! 		   ((node_list_msd2 = nodelist_new()) == NULL))
  			return NULL;
  
  		/* Add the first node from the node list to our msd sorted node list. And remove it from the non msd sorted node list.
   		 */
! 		nodelist_add_msd(node_list_msd1, LIST_FIRST(node_list)->node);
! 		nodelist_remove(node_list, LIST_FIRST(node_list)->node);
  
  		/* Add nodes that link to nodes in list2 to list1 then clone list1 onto list2 and repeat until no updates occur.
  		 */
! 		while(nodelist_size(node_list_msd1) != nodelist_size(node_list_msd2))
  		{
  			/* Duplicate nodelist1 onto nodelist2.
  			 */
! 			nodelist_free(node_list_msd2);
! 			if((node_list_msd2 = nodelist_duplicate(node_list_msd1)) == NULL)
  				return NULL;
! 			/* Iterate through nodelist2 adding nodes to nodelist1.
  			 */
  			LIST_FOREACH(node_link1, node_list_msd2, list)
! 				LIST_FOREACH(node_link2, ((struct node *) node_link1->node)->links, list)
! 					if(node_distance(node_link2->node, node_link1->node))
  					{
! 						nodelist_add_msd(node_list_msd1, node_link2->node);
! 						nodelist_remove(node_list, node_link2->node);
  					}
  		}
--- 79,108 ----
  		/* Create two new node lists.
  		 */
! 		if(((node_list_msd1 = list_new(node_compare_msd)) == NULL) ||
! 		   ((node_list_msd2 = list_new(node_compare_msd)) == NULL))
  			return NULL;
  
  		/* Add the first node from the node list to our msd sorted node list. And remove it from the non msd sorted node list.
   		 */
! 		list_add_msd(node_list_msd1, LIST_FIRST(node_list)->object);
! 		list_remove(node_list, LIST_FIRST(node_list)->object);
  
  		/* Add nodes that link to nodes in list2 to list1 then clone list1 onto list2 and repeat until no updates occur.
  		 */
! 		while(list_size(node_list_msd1) != list_size(node_list_msd2))
  		{
  			/* Duplicate nodelist1 onto nodelist2.
  			 */
! 			list_free(node_list_msd2);
! 			if((node_list_msd2 = list_duplicate(node_list_msd1)) == NULL)
  				return NULL;
! 			/* Iterate through list2 adding nodes to nodelist1.
  			 */
  			LIST_FOREACH(node_link1, node_list_msd2, list)
! 				LIST_FOREACH(node_link2, ((struct node *) node_link1->object)->links, list)
! 					if(node_distance(node_link2->object, node_link1->object))
  					{
! 						list_add_msd(node_list_msd1, node_link2->object);
! 						list_remove(node_list, node_link2->object);
  					}
  		}
***************
*** 108,116 ****
  		/* Free the 2nd nodelist so as to not leak memory.
  		 */
! 		nodelist_free(node_list_msd2);
  	}
  	/* Free the copy of the node_list.
  	 */
! 	nodelist_free(node_list);
  
  	return graph_list;	
--- 114,122 ----
  		/* Free the 2nd nodelist so as to not leak memory.
  		 */
! 		list_free(node_list_msd2);
  	}
  	/* Free the copy of the node_list.
  	 */
! 	list_free(node_list);
  
  	return graph_list;