link.c

circuit calculation program

#include "graph.h"
#include "types.h"


typedef struct link_head {
	/* next link_head in the same network */
	struct link_head *next;       
	
	/* link list */
	struct link_def *link;            
	
	/* mapping: node id<-> matrix index */
	int index;                        
	
} link_head_t;

link_head_t *link_head;

#define NODEID(p)      ((p - link_head) )
#define INDEX(node_id) (link_head[ node_id ].index)

/* network link head list */
link_head_t *network;
link_head_t *network_tail;
int network_nodes;
/*
 *     0 xxx3xxx     the matrix is symmetric, so only the right upper half 
 *     1  xx3xxx     triangle is stored as shown left.
 *     2   x3xxx 
 *     3    3333     Take the 3rd node as the example, the nodes connecting      
 *     4     xxx     to 3 are stored in those positions marked by a '3'
 *     5      xx
 *     6       x
 */	
int link_add (int pin_from, int pin_to )
{
	link_t *p, *q, *r;
	int node_to;
	int node_from;
	
	p = (link_t*) malloc (sizeof (link_t));
	if (!p) {
		error (__FILE__, __LINE__, ENO_MEM);
		
		return ENO_MEM;
	}
	node_to	= NODE (pin_to);
	node_from = NODE (pin_from);
	
	assert (node_to != node_from);
	assert (link_head);

	/* add to the lower triangle of the matrix */
	if (!link_head[ node_to ].link 
	    || (link_head[ node_to ].link 
	        &&link_head[ node_to ].index > link_head[ node_from ].index)) {
      	    	
		p->node_id = node_to;
		p->pin_from = pin_from;
		p->pin_to = pin_to;
	} else { /* save to the symmetric place  */
		p->node_id = node_from;
		p->pin_from = pin_to;
		p->pin_to = pin_from;
		 /* permute node_to and node_from */
		node_from = node_to;
		node_to = p->node_id;
	}

	/* make indexing, node_id is too big when sub-network is small */	    	
	if (!link_head[ node_from ].link 
	    && !link_head[ node_from ].index ) {
	    	link_head[ node_from ].index = network_nodes++;		
		/* a new link head, add to the link head list */
		if (network) {
			assert (network_tail);
			network_tail->next = link_head + node_from;
		} else
			network = link_head + node_from;
		
		network_tail = link_head + node_from;	    	
	}
	if (!link_head[ node_to ].index ) {
	    	link_head[ node_to ].index = network_nodes++;	
	    	
	    	network_tail->next = link_head + node_to;
		network_tail = link_head + node_to;	    		    		
	 }   	

	/* add to the link list of link_head[ node_from ] */
	if (!(q = link_head[ node_from ].link) ){
		link_head[ node_from ].link = p;
		p->next = NULL;
		

	} else { /* in ascending order of node_to */
		r = NULL;
		do {
			if (q->node_id == node_to ) {
				/* a loop between node_to and node_from is seen */
				voltage_eq_2_link (pin_from, pin_to,
					q->pin_from, q->pin_to );			
				free (p);
				return SUCCESS;
			}

			if (q->node_id > node_to ) break;
			r = q;
		} while (q = q->next);

		p->next = q;
		if (!r) link_head[ node_from ].link = p;
		else r->next = p;
	}

	return SUCCESS;
}


/* for a link_head, the list "link" is in the ascending order of node_tp */
link_t *link_state (int node_from, int node_to )
{
	int n;
	link_t *p;

	/* switch to the symmetric element if necessary */
	assert (link_head);
	
	if (INDEX (node_to) < INDEX (node_from) ) {
		n = node_from;
		node_from = node_to;
		node_to = n;
	}

	p = link_head[ node_from ].link;
	while (p && p->node_id < node_to ) p = p->next;

	if (p && p->node_id == node_to ) return p;

	return NULL;
}
/* construct a neighbor array for node node_id, return the number of neighbors 
 * the node whose index is less than that of node_id is skipped 
 * the function goes to the right of the matrix.
 *
 * we are only interested in un-traverseover-ed neighbors. 
 * and we always process in the ascending order of node index 
 * so any neighbor whose index is smaller is skipped
 */
int link_neighbor ( int node_id, int *array )
{
	link_t *p;
	link_head_t *q;
	int i,j;
	
	assert (link_head);
	p = link_head[ node_id ].link;
	
	/* the matrix is a triangle, scan horizontally first */
	j = 0;
	while (p) { 
		assert (link_head);
	
		/* record the node from which this node is arrived */
		array[ INDEX (p->node_id) ] = node_id; 
		j++;
		
		p = p->next;		
	}
	return j;
}	
/*
 * set up the link list for KVL 
 *      An : n-hop adj matrix 
 * start_id: node_id for the starting node
 * end_idx : node_id for the last node
 *    path : for output
 *     return the length of the link
 */
static int link_build_path (int *An, int start_id, int end_id, link_t **path )
{
	int i,k;
	link_t *p;
	
	assert (link_head);
   		
	k = 0;
	do {
		p = link_state (start_id, (i = An[ INDEX (start_id) ]) );
		*path++ = p;
		k++;

		start_id = i;
		
		assert (i!=-1);
	} while (start_id != end_id );	
	
	return k; 
}	
/*
 * convert node index into link_head_t * so that node_id can be found by NODEID()
 */
inline link_head_t * link_head_p ( int index )
{
	link_head_t *p;	
	/* convert index i to node_id */
	p = network;	
	while (p && p->index < index ) {p = p->next;}
	
	assert (p && p->index == index );
	return p;
}

int link_extend_1_hop_horz ( int i, int *An)
{
	int node_to;
	int node_via;
	int j = 0;
				
	link_head_t *p;
	link_t *q;

	p = link_head_p (i);
	node_via = NODEID (p);
		
	q = p->link;

	/* all nodes in q is nodes reachable by 1-hop from node_via */
	while (q) {
		int m;
			
		assert (link_head); /* node_to valid? */
		m = INDEX (q->node_id);

		if (An[ m ] == -1){                /* new reachable node */
			An[ m ] = node_via;
			j++;
		} else {   /* loop found. a same node is reached from more than 1 paths */
		}
			
		q = q->next;
	}
		
	return j;
}
/*
 * when expanding path starting with source, we try source's neighbors one by one
 * so, we need trying all neigbors with index bigger than src
 */
int link_extend_1_hop_vert( int i, int k,int *An)
{
	int node_to;
	int node_via;
	int j = 0;
				
	link_head_t *p;
	link_t *q;

	p = link_head_p (i);
	node_via = NODEID (p);

	while (p && p->index < k ) {		
		q = p->link;

		/* all nodes in q is nodes reachable by 1-hop from node_via */
		while (q && INDEX (q->node_id) < k ) q = q->next;
		
		if (q && INDEX (q->node_id) == k ) {
			int m;
			
			assert (link_head); /* node_to valid? */
			m = INDEX (q->node_id);

			if (An[ m ] == -1){                /* new reachable node */
				An[ m ] = node_via;
				j++;
			}
			
			q = q->next;
		}
		p = p->next;
	}	
	return j;
}
/* An+1 =  An * (adj matrix) is the n+1'th arrival matrix 
 * the n'th element of An and A is the endpoint node_id in the 
 * path to n'node of the network
 *
 * returns the number of new nodes reached, if 0 is returned
 * then no more loops left
 */
int link_mult (int skip, int *An)
{
	int i,j;
	
	assert (link_head );	


	j = 0;
	for (i = skip; i < network_nodes; i ++ ) {

		if (An[ i ] == -1 ) continue; /* unreachable */
		
		j += link_extend_1_hop_horz (i, An);
		j += link_extend_1_hop_vert (skip, i, An);
	}

	return j;
}

/* build path from VCC to GND */
void link_circuit_with_source ( int *An, int *A, int n_neighbors, int gnd_id, int src_id, link_t **path )
{
	int i;
	 /* scan for paths goes to gnd, each neighbor is used once */
 	for (i = 0; i < n_neighbors; i ++  ) {
   	   int j,k;     /* from the i'th neighbor */
   	   
   	   memset (An, -1, network_nodes * sizeof (int));
   	   for (j = k = 0; k < i; j++  ) if (A[j]!=-1) k++;

   	   link_extend_1_hop_horz ( j, An);	
	   link_extend_1_hop_vert (INDEX (src_id), j, An);	
	   /* n_neighbors paths are expected to be seen */
	   
	   do{

	   	/* if reaches GND, output this circuit */
		if (An[ link_head[ gnd_id ].index ] != -1) {
			
			/* open path: starts with VCC, stops at GND*/
			k = link_build_path (An, gnd_id, src_id, path );
			
			voltage_eq_for_circuit (path, k);
			break;
		}
		
		
	    } while (link_mult ( INDEX (src_id), An));
	}
}


/* build path for a loop */
int link_circuit_without_source( int *An, int *A,int src_id, int n_neighbors, link_t **path )
{
	int i, n_loops;
	/* (node_id[2*i],node_id[2*i+1]) is the in/out node for i'th loop */
	int *node_id; 

	assert (link_head);	 
	TRACE();
	 /* look for loops. but we reject two paths with the same in/out node 
	  * so maximum loops through a neighbor node is n_neighbors-1
	  */
 	node_id = (int *) malloc ((n_loops = n_neighbors-1) * sizeof (int));
 	if (!node_id) {
 		error (__FILE__,__LINE__,ENO_MEM);
 		return ENO_MEM;
 	}
	memset (node_id, 0 ,n_loops * sizeof (int));        
	/* 
	 * begin with 2-hop away reachable nodes
	 * if no more nodes added in, return
	 * NOTE: 2-hop
	 */
	memcpy (An, A,network_nodes * sizeof (int));	 	 
       	if (!link_mult (INDEX (src_id), An) ) { 
       	/* all left nodes are neighbors, check paths between neighbors */
     		link_head_t *p = link_head_p (INDEX (src_id)+1);		
		while (p) {
			link_t *q = p->link;
			
			while (q) {
				int j = 0;				
				

				path[ 1 ] = q;				
				path[ 0 ] = link_state (src_id, q->node_id);
				path[ 2 ] = link_state (src_id, NODE (q->pin_from));				
				
				voltage_eq_for_circuit (path, 3);	
				
				q = q->next;
			}
			
			p = p->next;
		}
		return 0;				
	}
	/* comment out direct neigbors, when any one of them, say x,
       	 *  turned again by link_mult,then a path reachs x,then a loop found
      	 */
       	for (i = 0; i < network_nodes; i ++ ) 
        		if (A[i] != -1) An[ i ] = -1;	

	/* when new nodes are appended, more loops are ahead */    
	while (link_mult (INDEX (src_id), An)) { 
	

		/* A loop is:
	 	 *    commented out direct neighbor was reached by a new path
	 	 */		
        	for (i = 0; i < network_nodes; i ++ ) {
        		if (A[i] != -1 && An[ i ] != -1 ) {
        			
        		int j,k;	
        		/* An[i] is last node_id in the path to i'th node 
        		 * go back along the path  til the 2'nd node in the past
        		 */
        		j = i;
			while (A[ j ] == -1) {
        	 		assert (link_head);

        	 		j = link_head[ An[ j ] ].index;
				 break;
			}
        		/* Now, An[i] is the last but 1 node in the path
        		 * while A[j] is the 2nd node.
        	 	 * we accpet paths in/out throught 1 pair neighbors only once
        	 	 */				        	 	
			for (k = n_neighbors-2; k > n_loops; k--){
				
				if ((node_id[2*k] == i && node_id[2*k+1] == j)
				    ||(node_id[2*k] == j && node_id[2*k+1] == i))
				    
				    goto next;  /* reject */
			}
			/* save in/out infor for the new path */
			n_loops--;
			node_id[ 2*k ] = i;
			node_id[ 2*k + 1 ] = j;
			
			/* output the path*/
			assert (An[ j ] == src_id ); /*refer to link_neighbor */
			An[ INDEX (src_id) ] = NODEID (link_head_p(i)); /* make a loop */
			
			/* loop path: starts and stops at the same node*/
			j = link_build_path (An,src_id, src_id , path);
			
			voltage_eq_for_circuit (path, j); 
			
			An[ INDEX (src_id) ] =
			An[ i ] = -1;  /* commented it out again.... */
		    }
next:;       
	    	}	 
	}
	
	/* the circuit is bad */
	if (n_loops) 
		warning (__FILE__,__LINE__,"network malformed!");
	
	free (node_id);
	
	return n_loops;  /* none zero means, loops found are less than expected */
}
	
	
/* allocate mem for link_head*/
int link_init()
{
	link_head = (link_head_t*) malloc (sizeof (link_head_t) * n_nodes);
	
	if (link_head) 
		memset (link_head, 0, sizeof (link_head_t) * n_nodes);
	
	return !!link_head;
}

/* find circuit in a network so that Kitchhoff Voltage Law can be applied */

int link_circuit ()
{
	/* because network partition starts with a VCC, so the 1st
	 * row of the adj matrix must be a VCC.
	 *  
	 * try to find circuit from VCC to GND 
	 *
	 * 1. which row is of GND. this can be done in a better way
	 */
	 int gnd_id;
	 
	 /* A: neighbor array, An: n-step arrival array */
	 int *A,*An;
	 int n_neighbors, n_loops;
	 int i,j;
	 
	 link_head_t *p = network;
	 link_t **path;
	 	 
	 while(p && !CHECK_NODEFLAG (gnd_id=NODEID (p), GND)) p = p->next;
	 
	 if (!p) {
	 	error (__FILE__, __LINE__, ENO_GDN );
	 	return ENO_GND;  /* GND not found, can not continue....*/
	 }
	/* 2. construct arrival array. data in the n'th column means
	 *  the last node of path leading to node n
	 */
	 A = (int *) malloc (2*network_nodes * sizeof (int) + network_nodes * sizeof (link_t *));
	 if (!A) {
	 	error (__FILE__, __LINE__, ENO_MEM );
	 	return ENO_MEM;
	 }
	 An = A + network_nodes;
	 path = (link_t **)(An + network_nodes);
	 
	 p = network;
	 
	 while (p)  {
	 	if (!CHECK_NODEFLAG (NODEID (p), GND) ) {
	 		memset (A, -1, network_nodes * sizeof (int));  /* -1 means unreachable */	 	
	 		
	 		n_neighbors = link_neighbor (NODEID (p), A);
	 		if (!n_neighbors) goto skip;
	 		
			printf ("For node <%d>\n", NODEID (p));	
   			for (i = 0;i < network_nodes; i++ )
	   			printf ("%x ", A[ i ]);
		   	printf ("\n");	
	 	
	 		if (CHECK_NODEFLAG (NODEID (p), CVS) ) {
	 			link_circuit_with_source(An, A, n_neighbors, gnd_id,NODEID (p),path);
			else {
 	 			link_circuit_without_source(An, A, NODEID (p), n_neighbors, path);
			} 
		}
skip:		
		p = p->next;	 			
	}	   
	free (A);
}

void dump_link()
{
	int i,j=0;
	link_t *p;
	
	for (i = 0; i < n_nodes; i ++ )
		if (p = link_head[i].link) {
			printf ("\n Node:<%d>",i);
			
			while (p) {
				printf ("\n\tfrom:%d via:%d to:%d",
					p->pin_from,p->pin_to, p->node_id );
					
				p = p->next;
				j ++;
			}		
		}	
	printf ("\nTotalling %d edges.\n",j );
}	

void dump_network()
{
	link_head_t *p = network;
	
	while (p) {
		link_t *q = p->link;
		
		printf ("\n Node:<%d>(%d)",p->index, NODEID(p) );
		while (q) {
			printf ("\n\tfrom:%d via:%d to:%d",
				q->pin_from,q->pin_to, q->node_id );
			q = q->next;
		}
		
		p = p->next;
	}
	printf ("\n");
}


/*
 * destroy network
 */
int link_reset ()
{
	link_head_t *p = network;
	
	while (p) {
		link_t *q = p->link;
		
		while (q) {
			link_t *r = q;
			q = q->next;
			
			free (r);
		}
		
		p->link = NULL;
		p->index = 0;
		
		p = p->next;
	}	
	network = network_tail = NULL;
	network_nodes = 0;	
}	

/*
 * calculate volatge for each link
 * NOTE: network starts with a VCC
 */

int link_voltage ()
{
	link_head_t *p = network;
	
	while (p) {
		link_t *q = p->link;
		
		while (q) {
			voltage_link (q, NODEID (p));
			q = q->next;
			
		}

		p = p->next;
	}			
}