fb4ef5ddff422e6ddb8ee3695d73ab47f0f5d039
kent
  Tue May 27 10:44:56 2014 -0700
Adding Jim Kent copyright notices to a few files that needed it.
diff --git src/lib/diGraph.c src/lib/diGraph.c
index 4d80e9c..a76204e 100644
--- src/lib/diGraph.c
+++ src/lib/diGraph.c
@@ -1,738 +1,741 @@
-/* diGraph - Directed graph routines. */
+/* diGraph - Directed graph routines. 
+ * This file is copyright 2002 Jim Kent, but license is hereby
+ * granted for all use - public, private or commercial. */
+
 #include "common.h"
 #include "hash.h"
 #include "dlist.h"
 #include "diGraph.h"
 
 
 struct diGraph *dgNew()
 /* Return a new directed graph object. */
 {
 struct diGraph *dg;
 AllocVar(dg);
 dg->nodeHash = newHash(0);
 dg->edgeList = newDlList();
 return dg;
 }
 
 static void dgNodeFree(struct dgNode **pNode)
 /* Free a diGraph node. */
 {
 struct dgNode *node = *pNode;
 if (node == NULL)
     return;
 slFreeList(&node->nextList);
 slFreeList(&node->prevList);
 freez(pNode);
 }
 
 static void dgNodeFreeList(struct dgNode **pList)
 /* Free list of diGraph nodes. */
 {
 struct dgNode *el, *next;
 
 for (el = *pList; el != NULL; el = next)
     {
     next = el->next;
     dgNodeFree(&el);
     }
 *pList = NULL;
 }
 
 void dgFree(struct diGraph **pGraph)
 /* Free a directed graph. */
 {
 struct diGraph *dg = *pGraph;
 if (dg == NULL)
     return;
 freeHash(&dg->nodeHash);
 dgNodeFreeList(&dg->nodeList);
 freeDlListAndVals(&dg->edgeList);
 freez(pGraph);
 }
 
 
 struct dgNode *dgAddNode(struct diGraph *dg, char *name, void *val)
 /* Create new node in graph. It's legal (but not efficient) to add
  * a node with the same name and value twice.  It's not legal to
  * add a node with the same name and a different value.  
  * You can pass in NULL for the name in which case the 
  * hexadecimal representation of val will become the name. */
 {
 struct dgNode *node;
 struct hashEl *hel;
 struct hash *hash = dg->nodeHash;
 char nbuf[17];
 
 if (name == NULL)
     {
     sprintf(nbuf, "%p", val);
     name = nbuf;
     }
 hel = hashLookup(hash, name);
 if (hel != NULL)
     {
     node = hel->val;
     if (node->val != val)
 	{
 	errAbort("Trying to add node %s with a new value (old 0x%llx new 0x%llx)",
 	    name, ptrToLL(node->val), ptrToLL(val));
 	}
     return node;
     }
 AllocVar(node);
 hel = hashAdd(hash, name, node);
 node->name = hel->name;
 node->val = val;
 slAddHead(&dg->nodeList, node);
 return node;
 }
 
 struct dgNode *dgAddNumberedNode(struct diGraph *dg, int id, void *val)
 /* Create new node with a number instead of a name. */
 {
 char buf[16];
 sprintf(buf, "%d", id);
 return dgAddNode(dg, buf, val);
 }
 
 struct dgNode *dgFindNode(struct diGraph *dg, char *name)
 /* Find existing node in graph. Return NULL if not in graph. */
 {
 struct hashEl *hel;
 if ((hel = hashLookup(dg->nodeHash, name)) == NULL)
     return NULL;
 return hel->val;
 }
 
 struct dgNode *dgFindNumberedNode(struct diGraph *dg, int id)
 /* Find node given number. */
 {
 char buf[16];
 sprintf(buf, "%d", id);
 return dgFindNode(dg, buf);
 }
 
 
 void *dgNodeVal(struct dgNode *node)
 /* Return value associated with node. */
 {
 return node->val;
 }
 
 void *dgNodeName(struct dgNode *node)
 /* Return name associated with node. */
 {
 return node->name;
 }
 
 int dgNodeNumber(struct dgNode *node)
 /* Return number of node.  (Will likely return 0 if node
  * was added with a name rather than a number). */
 {
 return atoi(node->name);
 }
 
 struct dgNodeRef *dgFindNodeInRefList(struct dgNodeRef *refList, struct dgNode *node)
 /* Return reference to node if in list, or NULL if not. */
 {
 struct dgNodeRef *ref;
 for (ref = refList; ref != NULL; ref = ref->next)
     if (ref->node == node)
 	return ref;
 return NULL;
 }
 
 struct dgConnection *dgFindNodeInConList(struct dgConnection *conList, struct dgNode *node)
 /* Return connection to node if in list, or NULL if not. */
 {
 struct dgConnection *con;
 for (con = conList; con != NULL; con = con->next)
     if (con->node == node)
 	return con;
 return NULL;
 }
 
 
 struct dgEdge *dgConnect(struct diGraph *dg, struct dgNode *a, struct dgNode *b)
 /* Connect node a to node b.  Returns connecting edge. 
  * Not an error to reconnect.  However all connects can 
  * be broken with a single disconnect. */
 {
 return dgConnectWithVal(dg, a, b, NULL);
 }
 
 struct dgEdge *dgConnectWithVal(struct diGraph *dg, struct dgNode *a, 
      struct dgNode *b, void *val)
 /* Connect node a to node b and put val on edge.  An error to
  * reconnect with a different val. */
 {
 struct dgConnection *con;
 struct dgEdge *edge;
 struct dlNode *edgeOnList;
 
 /* Check to see if it's already there. */
 if ((con = dgFindNodeInConList(a->nextList, b)) != NULL)
     {
     edge =  con->edgeOnList->val;
     if (val != edge->val)
         warn("Trying to add new value to edge between %s and %s, ignoring",
 	   a->name, b->name);
     return edge;
     }
 /* Allocate edge and put on list. */
 AllocVar(edge);
 edge->a = a;
 edge->b = b;
 edge->val = val;
 edgeOnList = dlAddValTail(dg->edgeList, edge);
 
 /* Connect nodes to each other. */
 AllocVar(con);
 con->node = b;
 con->edgeOnList = edgeOnList;
 slAddHead(&a->nextList, con);
 AllocVar(con);
 con->node = a;
 con->edgeOnList = edgeOnList;
 slAddHead(&b->prevList, con);
 
 return edge;
 }
 
 static struct dlNode *dgRemoveFromConList(struct dgConnection **pConList, 
 	struct dgNode *node, struct dgConnection **retCon)
 /* Remove reference to node from list. */
 {
 struct dgConnection *newList = NULL;
 struct dgConnection *con, *next;
 struct dlNode *edgeOnList = NULL;
 
 for (con = *pConList; con != NULL; con = next)
     {
     next = con->next;
     if (con->node == node)
 	{
 	edgeOnList = con->edgeOnList;
 	if (retCon != NULL)
 	    *retCon = con;
 	else
 	    freeMem(con);
 	}
     else
 	{
 	slAddHead(&newList, con);
 	}
     }
 slReverse(&newList);
 *pConList = newList;
 return edgeOnList;
 }
 
 void dgDisconnect(struct diGraph *dg, struct dgNode *a, struct dgNode *b)
 /* Disconnect nodes a and b. */
 {
 struct dlNode *edgeInList;
 struct dgEdge *edge;
 
 dgRemoveFromConList(&a->nextList, b, NULL);
 edgeInList = dgRemoveFromConList(&b->prevList, a, NULL);
 if (edgeInList != NULL)
     {
     edge = edgeInList->val;
     dlRemove(edgeInList);
     freeMem(edgeInList);
     freeMem(edge);
     }
 }
 
 
 void dgClearVisitFlags(struct diGraph *dg)
 /* Clear out visit flags. */
 {
 struct dgNode *node;
 for (node = dg->nodeList; node != NULL; node = node->next)
     node->visited = FALSE;
 }
 
 void dgClearConnFlags(struct diGraph *dg)
 /* Clear out connect flags. */
 {
 struct dgNode *node;
 for (node = dg->nodeList; node != NULL; node = node->next)
     node->conn = FALSE;
 }
 
 static struct dgNode *rTarget;
 
 static boolean rPathExists(struct dgNode *a)
 /* Recursively find if path from a to b exists. */
 {
 struct dgConnection *ref;
 if (a == rTarget)
     return TRUE;
 a->visited = TRUE;
 
 for (ref = a->nextList; ref != NULL; ref = ref->next)
     {
     if (!ref->node->visited && rPathExists(ref->node))
 	return TRUE;
     }
 return FALSE;
 }
 
 boolean dgPathExists(struct diGraph *dg, struct dgNode *a, struct dgNode *b)
 /* Return TRUE if there's a path from a to b. */
 {
 rTarget = b;
 dgClearVisitFlags(dg);
 return rPathExists(a);
 }
 
 static int topoIx;
 
 static void rTopoSort(struct dgNode *node)
 {
 struct dgConnection *ref;
 node->visited = TRUE;
 for (ref = node->nextList; ref != NULL; ref = ref->next)
     {
     if (!ref->node->visited)
 	rTopoSort(ref->node);
     }
 node->topoOrder = ++topoIx;
 }
 
 void dgTopoSort(struct diGraph *dg)
 /* Fill in topological order of nodes. */
 {
 struct dgNode *node;
 
 topoIx = 0;
 dgClearVisitFlags(dg);
 for (node = dg->nodeList; node != NULL; node = node->next)
     {
     if (!node->visited)
 	rTopoSort(node);
     }
 }
 
 static boolean  rHasCycles(struct dgNode *node)
 /* Recursively see if has cycles by looking for
  * backwards topoOrder. */
 {
 struct dgConnection *ref;
 struct dgNode *child;
 
 node->visited = TRUE;
 for (ref = node->nextList; ref != NULL; ref = ref->next)
     {
     child = ref->node;
     if (child->topoOrder > node->topoOrder)
 	return TRUE;
     if (!child->visited)
 	if (rHasCycles(child))
 	    return TRUE;
     }
 return FALSE;
 }
 
 boolean dgHasCycles(struct diGraph *dg)
 /* Return TRUE if directed graph has cycles. */
 {
 struct dgNode *node;
 
 dgTopoSort(dg);
 dgClearVisitFlags(dg);
 for (node = dg->nodeList; node != NULL; node = node->next)
     {
     if (!node->visited)
 	if (rHasCycles(node))
 	    return TRUE;
     }
 return FALSE;
 }
 
 struct dgNodeRef *rRefList;
 bool rMustHaveVal;			/* Set to TRUE if rFindConnected only to
                                          * consider nodes with values in connections. */
 
 static void rFindConnected(struct dgNode *a)
 /* Find all things connected to a directly or not that haven't
  * already been visited and put them on rRefList. */
 {
 if (!a->conn && (!rMustHaveVal || a->val))
     {
     struct dgNodeRef *ref;
     struct dgConnection *con;
     AllocVar(ref);
     ref->node = a;
     slAddHead(&rRefList, ref);
     a->conn = TRUE;
     for (con = a->nextList; con != NULL; con = con->next)
 	rFindConnected(con->node);
     for (con = a->prevList; con != NULL; con = con->next)
 	rFindConnected(con->node);
     }
 }
 
 struct dgNodeRef *dgFindNextConnected(struct diGraph *dg)
 /* Return list of nodes that make up next connected component,
  * or NULL if no more components.  slFreeList this when
  * done.  Call "dgClearConnFlags" before first call to this.
  * Do not call dgFindConnectedToNode between dgFindFirstConnected 
  * and this as they use the same flag variables to keep track of
  * what vertices are used. */
 {
 struct dgNode *a;
 
 for (a=dg->nodeList; a != NULL; a = a->next)
     {
     if (!a->conn)
 	break;
     }
 if (a == NULL)
     return NULL;
 rRefList = NULL;
 rMustHaveVal = FALSE;
 rFindConnected(a);
 return rRefList;
 }
 
 struct dgNodeRef *dgFindNextConnectedWithVals(struct diGraph *dg)
 /* Like dgFindConnected, but only considers graph nodes that
  * have a val attached. */
 {
 struct dgNode *a;
 
 for (a=dg->nodeList; a != NULL; a = a->next)
     {
     if (!a->conn && a->val != NULL)
 	break;
     }
 if (a == NULL)
     return NULL;
 rRefList = NULL;
 rMustHaveVal = TRUE;
 rFindConnected(a);
 return rRefList;
 }
 
 
 static int connectedComponents(struct diGraph *dg)
 /* Count number of connected components and set component field
  * of each node to reflect which component it is in. */
 {
 struct dgNodeRef *ref;
 int conCount = 0;
 struct dgNode *a = dg->nodeList;
 
 dgClearConnFlags(dg);
 for (;;)
     {
     for (; a != NULL; a = a->next)
 	{
 	if (!a->conn && (!rMustHaveVal || a->val))
 	    break;
 	}
     if (a == NULL)
 	break;
     rRefList = NULL;
     rFindConnected(a);
     ++conCount;
     for (ref = rRefList; ref != NULL; ref = ref->next)
 	{
 	ref->node->component = conCount;
 	}
     slFreeList(&rRefList);
     }
 return conCount;
 }
 
 int dgConnectedComponents(struct diGraph *dg)
 /* Count number of connected components and set component field
  * of each node to reflect which component it is in. */
 {
 rMustHaveVal = FALSE;
 return connectedComponents(dg);
 }
 
 int dgConnectedComponentsWithVals(struct diGraph *dg)
 /* Count number of connected components and set component field
  * of each node to reflect which component it is in. Only
  * consider components with values. */
 {
 rMustHaveVal = TRUE;
 return connectedComponents(dg);
 }
 
 struct dgNodeRef *dgFindNewConnected(struct diGraph *dg, struct dgNode *a)
 /* Find a connected component guaranteed not to be covered before 
  * including a. */
 {
 rRefList = NULL;
 rMustHaveVal = FALSE;
 rFindConnected(a);
 return rRefList;
 }
 
 struct dgNodeRef *dgFindNewConnectedWithVals(struct diGraph *dg, struct dgNode *a)
 /* Find a connected component guaranteed not to be covered before 
  * that includes a.  Connected components must have values*/
 {
 rRefList = NULL;
 rMustHaveVal = TRUE;
 rFindConnected(a);
 return rRefList;
 }
 
 
 struct dgNodeRef *dgFindConnectedToNode(struct diGraph *dg, struct dgNode *a)
 /* Return reference list of all nodes connected to a, including a.
  * slFreeList this list when done. */
 {
 dgClearConnFlags(dg);
 return dgFindNewConnected(dg, a);
 }
 
 struct dgEdge *dgDirectlyFollows(struct diGraph *dg, struct dgNode *a, struct dgNode *b)
 /* Return TRUE if b directly follows a. */
 {
 struct dgConnection *con = dgFindNodeInConList(a->nextList, b);
 if (con == NULL)
     return NULL;
 return con->edgeOnList->val;
 }
 
 struct dgNodeRef *dgFindPath(struct diGraph *dg, struct dgNode *a, struct dgNode *b)
 /* Find shortest path from a to b.  Return NULL if can't be found. */
 {
 struct dgNodeRef *refList  = NULL, *ref;
 struct dgConnection *con;
 struct dgNode *node, *nNode;
 struct dlList *fifo;
 struct dlNode *ffNode;
 struct dgNode endNode;
 int fifoSize = 1;
 
 /* Do some quick and easy tests first to return if have no way out
  * of node A, or if B directly follows A. */
 if (a->nextList == NULL)
     return NULL;
 if (a == b)
     {
     AllocVar(ref);
     ref->node = a;
     return ref;
     }
 if ((con = dgFindNodeInConList(a->nextList, b)) != NULL)
     {
     AllocVar(refList);
     refList->node = a;
     node = con->node;
     AllocVar(ref);
     ref->node = node;
     slAddTail(&refList, ref);
     return refList;
     }
 
 /* Set up for breadth first traversal.  Will use a doubly linked
  * list as a fifo. */
 for (node = dg->nodeList; node != NULL; node = node->next)
     node->tempEntry = NULL;
 fifo = newDlList();
 dlAddValTail(fifo, a);
 a->tempEntry = &endNode;
 
 while ((ffNode = dlPopHead(fifo)) != NULL)
     {
     --fifoSize;
     node = ffNode->val;
     freeMem(ffNode);
     for (con = node->nextList; con != NULL; con = con->next)
 	{
 	nNode = con->node;
 	if (nNode->tempEntry == NULL)
 	    {
 	    nNode->tempEntry = node;
 	    if (nNode == b)
 		{
 		while (nNode != &endNode && nNode != NULL)
 		    {
 		    AllocVar(ref);
 		    ref->node = nNode;
 		    slAddHead(&refList, ref);
 		    nNode = nNode->tempEntry;
 		    }
 		break;
 		}
 	    else
 		{
 		dlAddValTail(fifo, nNode);
 		++fifoSize;
 		if (fifoSize > 100000)
 		    errAbort("Internal error in dgFindPath");
 		}
 	    }
 	}
     }
 freeDlList(&fifo);
 return refList;
 }
 
 static int cmpPriority(const void *va, const void *vb)
 /* Sort smallest offset into needle first. */
 {
 const struct dgNode *a = *((struct dgNode **)va);
 const struct dgNode *b = *((struct dgNode **)vb);
 return (a->priority - b->priority);
 }
 
 boolean dgParentsAllVisited(struct dgNode *node)
 /* Return TRUE if all parents of node have  been visited. */
 {
 struct dgConnection *con;
 for (con = node->prevList; con != NULL; con = con->next)
     {
     if (con->node->visited == FALSE)
 	return FALSE;
     }
 return TRUE;
 }
 
 struct dgNodeRef *dgConstrainedPriorityOrder(struct diGraph *dg)
 /* Return traversal of graph in priority order subject to
  * constraint that all parents must be output before
  * their children regardless of node priority. 
  * Graph must be cycle free. */
 {
 struct dlList *sortedList = newDlList();
 struct dgNode *graphNode;
 struct dlNode *listNode;
 struct dgNodeRef *refList = NULL, *ref;
 
 if (dgHasCycles(dg))
     errAbort("Call to dgConstrainedPriorityOrder on graph with cycles.");
 
 /* Make up list sorted by priority. */
 for (graphNode = dg->nodeList; graphNode != NULL; graphNode = graphNode->next)
     {
     dlAddValTail(sortedList, graphNode);
     graphNode->visited = FALSE;
     }
 dlSort(sortedList, cmpPriority);
 
 /* Loop taking first member of list with no untraversed parents. */
 while (!dlEmpty(sortedList))
     {
     for (listNode = sortedList->head; listNode->next != NULL; listNode = listNode->next)
 	{
 	graphNode = listNode->val;
 	if (dgParentsAllVisited(graphNode))
 	    {
 	    dlRemove(listNode);
 	    freeMem(listNode);
 	    AllocVar(ref);
 	    ref->node = graphNode;
 	    slAddHead(&refList, ref);
 	    graphNode->visited = TRUE;
 	    break;
 	    }
 	}
     }
 freeDlList(&sortedList);
 slReverse(&refList);
 return refList;
 }
 
 struct dgEdgeRef *dgFindSubEdges(struct diGraph *dg, struct dgNodeRef *subGraph)
 /* Return list of edges in graph that connected together nodes in subGraph. */
 {
 struct hash *hash = newHash(0);
 struct dgNodeRef *nr;
 struct dgConnection *con;
 struct dgEdgeRef *erList = NULL, *er;
 struct dgNode *node;
 
 /* Build up hash of nodes in subGraph. */
 for (nr = subGraph; nr != NULL; nr = nr->next)
     {
     node = nr->node;
     hashAdd(hash, node->name, node);
     }
 
 for (nr = subGraph; nr != NULL; nr = nr->next)
     {
     node = nr->node;
     for (con = node->nextList; con != NULL; con = con->next)
 	{
 	if (hashLookup(hash, con->node->name))
 	    {
 	    AllocVar(er);
 	    er->edge = con->edgeOnList->val;
 	    slAddHead(&erList, er);
 	    }
 	}
     }
 freeHash(&hash);
 return erList;
 }
 
 void dgSwapEdges(struct diGraph *dg, struct dgEdgeRef *erList)
 /* Swap polarity of all edges in erList.  (Assumes you don't have
  * edges going both directions in graph.) */
 {
 struct dgEdgeRef *er;
 struct dgEdge *edge;
 struct dgNode *a, *b;
 struct dgConnection *con1, *con2;
 
 /* Remove edges from next and previous list of all
  * involved nodes and swap nodes in edge itself. */
 for (er = erList; er != NULL; er = er->next)
     {
     edge = er->edge;
     a = edge->a;
     b = edge->b;
     dgRemoveFromConList(&a->nextList, b, &con1);
     dgRemoveFromConList(&b->prevList, a, &con2);
     edge->a = b;
     edge->b = a;
     con1->node = a;
     slAddHead(&b->nextList, con1);
     con2->node = b;
     slAddHead(&a->prevList, con2);
     }
 }
 
 
 struct dgConnection *dgNextList(struct dgNode *node)
 /* Return list of nodes that follow node. */
 {
 return node->nextList;
 }
 
 struct dgConnection *dgPrevList(struct dgNode *node)
 /* Return list of nodes that precede node. */
 {
 return node->prevList;
 }
 
 void dgDumpGraph(struct diGraph *dg, FILE *out, boolean hideIsolated)
 /* Dump info on graph to output. */
 {
 struct dgNode *node;
 struct dgConnection *con;
 
 for (node = dg->nodeList; node != NULL; node = node->next)
     {
     if (hideIsolated  && node->nextList == NULL)
 	continue;
     fprintf(out, "%s:", node->name);
     for (con = node->nextList; con != NULL; con = con->next)
 	fprintf(out, " %s", con->node->name);
     fprintf(out, "\n");
     }
 }