lib/diGraph.c File Reference

#include "common.h"
#include "hash.h"
#include "dlist.h"
#include "diGraph.h"

Include dependency graph for diGraph.c:

Go to the source code of this file.

Functions
diGraph *	dgNew ()
static void	dgNodeFree (struct dgNode **pNode)
static void	dgNodeFreeList (struct dgNode **pList)
void	dgFree (struct diGraph **pGraph)
dgNode *	dgAddNode (struct diGraph *dg, char *name, void *val)
dgNode *	dgAddNumberedNode (struct diGraph *dg, int id, void *val)
dgNode *	dgFindNode (struct diGraph *dg, char *name)
dgNode *	dgFindNumberedNode (struct diGraph *dg, int id)
void *	dgNodeVal (struct dgNode *node)
void *	dgNodeName (struct dgNode *node)
int	dgNodeNumber (struct dgNode *node)
dgNodeRef *	dgFindNodeInRefList (struct dgNodeRef *refList, struct dgNode *node)
dgConnection *	dgFindNodeInConList (struct dgConnection *conList, struct dgNode *node)
dgEdge *	dgConnect (struct diGraph *dg, struct dgNode *a, struct dgNode *b)
dgEdge *	dgConnectWithVal (struct diGraph *dg, struct dgNode *a, struct dgNode *b, void *val)
static struct dlNode *	dgRemoveFromConList (struct dgConnection **pConList, struct dgNode *node, struct dgConnection **retCon)
void	dgDisconnect (struct diGraph *dg, struct dgNode *a, struct dgNode *b)
void	dgClearVisitFlags (struct diGraph *dg)
void	dgClearConnFlags (struct diGraph *dg)
static boolean	rPathExists (struct dgNode *a)
boolean	dgPathExists (struct diGraph *dg, struct dgNode *a, struct dgNode *b)
static void	rTopoSort (struct dgNode *node)
void	dgTopoSort (struct diGraph *dg)
static boolean	rHasCycles (struct dgNode *node)
boolean	dgHasCycles (struct diGraph *dg)
static void	rFindConnected (struct dgNode *a)
dgNodeRef *	dgFindNextConnected (struct diGraph *dg)
dgNodeRef *	dgFindNextConnectedWithVals (struct diGraph *dg)
static int	connectedComponents (struct diGraph *dg)
int	dgConnectedComponents (struct diGraph *dg)
int	dgConnectedComponentsWithVals (struct diGraph *dg)
dgNodeRef *	dgFindNewConnected (struct diGraph *dg, struct dgNode *a)
dgNodeRef *	dgFindNewConnectedWithVals (struct diGraph *dg, struct dgNode *a)
dgNodeRef *	dgFindConnectedToNode (struct diGraph *dg, struct dgNode *a)
dgEdge *	dgDirectlyFollows (struct diGraph *dg, struct dgNode *a, struct dgNode *b)
dgNodeRef *	dgFindPath (struct diGraph *dg, struct dgNode *a, struct dgNode *b)
static int	cmpPriority (const void *va, const void *vb)
boolean	dgParentsAllVisited (struct dgNode *node)
dgNodeRef *	dgConstrainedPriorityOrder (struct diGraph *dg)
dgEdgeRef *	dgFindSubEdges (struct diGraph *dg, struct dgNodeRef *subGraph)
void	dgSwapEdges (struct diGraph *dg, struct dgEdgeRef *erList)
dgConnection *	dgNextList (struct dgNode *node)
dgConnection *	dgPrevList (struct dgNode *node)
void	dgDumpGraph (struct diGraph *dg, FILE *out, boolean hideIsolated)
Variables
static char const	rcsid [] = "$Id: diGraph.c,v 1.9 2005/08/17 03:01:29 galt Exp $"
static struct dgNode *	rTarget
static int	topoIx
dgNodeRef *	rRefList
bool	rMustHaveVal

---

Function Documentation

static int cmpPriority	(	const void *	va,
		const void *	vb
	)			[static]

Definition at line 584 of file diGraph.c.

References dgNode::priority.

Referenced by dgConstrainedPriorityOrder().

{
const struct dgNode *a = *((struct dgNode **)va);
const struct dgNode *b = *((struct dgNode **)vb);
return (a->priority - b->priority);
}

Here is the caller graph for this function:

static int connectedComponents

(

struct diGraph *

dg

)

[static]

Definition at line 423 of file diGraph.c.

References dgNode::component, dgNode::conn, dgClearConnFlags(), dgNodeRef::next, dgNode::next, dgNodeRef::node, diGraph::nodeList, rFindConnected(), rMustHaveVal, rRefList, slFreeList(), and dgNode::val.

Referenced by dgConnectedComponents(), and dgConnectedComponentsWithVals().

{
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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

struct dgNode* dgAddNode	(	struct diGraph *	dg,
		char *	name,
		void *	val
	)			[read]

Definition at line 56 of file diGraph.c.

References AllocVar, errAbort(), hashAdd(), hashLookup(), hashEl::name, dgNode::name, diGraph::nodeHash, diGraph::nodeList, ptrToLL, slAddHead, dgNode::val, and hashEl::val.

Referenced by dgAddNumberedNode().

{
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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

struct dgNode* dgAddNumberedNode	(	struct diGraph *	dg,
		int	id,
		void *	val
	)			[read]

Definition at line 92 of file diGraph.c.

References dgAddNode().

{
char buf[16];
sprintf(buf, "%d", id);
return dgAddNode(dg, buf, val);
}

Here is the call graph for this function:

void dgClearConnFlags

(

struct diGraph *

dg

)

Definition at line 259 of file diGraph.c.

References dgNode::conn, FALSE, dgNode::next, and diGraph::nodeList.

Referenced by connectedComponents(), and dgFindConnectedToNode().

{
struct dgNode *node;
for (node = dg->nodeList; node != NULL; node = node->next)
    node->conn = FALSE;
}

Here is the caller graph for this function:

void dgClearVisitFlags

(

struct diGraph *

dg

)

Definition at line 251 of file diGraph.c.

References FALSE, dgNode::next, diGraph::nodeList, and dgNode::visited.

Referenced by dgHasCycles(), dgPathExists(), and dgTopoSort().

{
struct dgNode *node;
for (node = dg->nodeList; node != NULL; node = node->next)
    node->visited = FALSE;
}

Here is the caller graph for this function:

struct dgEdge* dgConnect	(	struct diGraph *	dg,
		struct dgNode *	a,
		struct dgNode *	b
	)			[read]

Definition at line 158 of file diGraph.c.

References dgEdge::a, dgEdge::b, and dgConnectWithVal().

{
return dgConnectWithVal(dg, a, b, NULL);
}

Here is the call graph for this function:

int dgConnectedComponents

(

struct diGraph *

dg

)

Definition at line 453 of file diGraph.c.

References connectedComponents(), FALSE, and rMustHaveVal.

{
rMustHaveVal = FALSE;
return connectedComponents(dg);
}

Here is the call graph for this function:

int dgConnectedComponentsWithVals

(

struct diGraph *

dg

)

Definition at line 461 of file diGraph.c.

References connectedComponents(), rMustHaveVal, and TRUE.

{
rMustHaveVal = TRUE;
return connectedComponents(dg);
}

Here is the call graph for this function:

struct dgEdge* dgConnectWithVal	(	struct diGraph *	dg,
		struct dgNode *	a,
		struct dgNode *	b,
		void *	val
	)			[read]

Definition at line 166 of file diGraph.c.

References dgEdge::a, AllocVar, dgEdge::b, dgFindNodeInConList(), dlAddValTail(), diGraph::edgeList, dgConnection::edgeOnList, dgNode::name, dgNode::nextList, dgConnection::node, dgNode::prevList, slAddHead, dgEdge::val, dlNode::val, and warn().

Referenced by dgConnect().

{
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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

struct dgNodeRef* dgConstrainedPriorityOrder

(

struct diGraph *

dg

)

[read]

Definition at line 604 of file diGraph.c.

References AllocVar, cmpPriority(), dgHasCycles(), dgParentsAllVisited(), dlAddValTail(), dlEmpty(), dlRemove(), dlSort(), errAbort(), FALSE, freeDlList(), freeMem(), dlList::head, newDlList(), dlNode::next, dgNode::next, diGraph::nodeList, slAddHead, slReverse(), TRUE, dlNode::val, and dgNode::visited.

{
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;
}

Here is the call graph for this function:

struct dgEdge* dgDirectlyFollows	(	struct diGraph *	dg,
		struct dgNode *	a,
		struct dgNode *	b
	)			[read]

Definition at line 499 of file diGraph.c.

References dgFindNodeInConList(), dgConnection::edgeOnList, dgNode::nextList, and dlNode::val.

{
struct dgConnection *con = dgFindNodeInConList(a->nextList, b);
if (con == NULL)
    return NULL;
return con->edgeOnList->val;
}

Here is the call graph for this function:

void dgDisconnect	(	struct diGraph *	dg,
		struct dgNode *	a,
		struct dgNode *	b
	)

Definition at line 233 of file diGraph.c.

References dgEdge::a, dgEdge::b, dgRemoveFromConList(), dlRemove(), freeMem(), dgNode::nextList, dgNode::prevList, and dlNode::val.

{
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);
    }
}

Here is the call graph for this function:

void dgDumpGraph	(	struct diGraph *	dg,
		FILE *	out,
		boolean	hideIsolated
	)

Definition at line 722 of file diGraph.c.

References dgNode::name, dgConnection::next, dgNode::next, dgNode::nextList, dgConnection::node, and diGraph::nodeList.

{
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");
    }
}

struct dgNodeRef* dgFindConnectedToNode	(	struct diGraph *	dg,
		struct dgNode *	a
	)			[read]

Definition at line 491 of file diGraph.c.

References dgClearConnFlags(), and dgFindNewConnected().

{
dgClearConnFlags(dg);
return dgFindNewConnected(dg, a);
}

Here is the call graph for this function:

struct dgNodeRef* dgFindNewConnected	(	struct diGraph *	dg,
		struct dgNode *	a
	)			[read]

Definition at line 470 of file diGraph.c.

References FALSE, rFindConnected(), rMustHaveVal, and rRefList.

Referenced by dgFindConnectedToNode().

{
rRefList = NULL;
rMustHaveVal = FALSE;
rFindConnected(a);
return rRefList;
}

Here is the call graph for this function:

Here is the caller graph for this function:

struct dgNodeRef* dgFindNewConnectedWithVals	(	struct diGraph *	dg,
		struct dgNode *	a
	)			[read]

Definition at line 480 of file diGraph.c.

References rFindConnected(), rMustHaveVal, rRefList, and TRUE.

{
rRefList = NULL;
rMustHaveVal = TRUE;
rFindConnected(a);
return rRefList;
}

Here is the call graph for this function:

struct dgNodeRef* dgFindNextConnected

(

struct diGraph *

dg

)

[read]

Definition at line 380 of file diGraph.c.

References dgNode::conn, FALSE, dgNode::next, diGraph::nodeList, rFindConnected(), rMustHaveVal, and rRefList.

{
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;
}

Here is the call graph for this function:

struct dgNodeRef* dgFindNextConnectedWithVals

(

struct diGraph *

dg

)

[read]

Definition at line 403 of file diGraph.c.

References dgNode::conn, dgNode::next, diGraph::nodeList, rFindConnected(), rMustHaveVal, rRefList, TRUE, and dgNode::val.

{
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;
}

Here is the call graph for this function:

struct dgNode* dgFindNode	(	struct diGraph *	dg,
		char *	name
	)			[read]

Definition at line 100 of file diGraph.c.

References hashLookup(), diGraph::nodeHash, and hashEl::val.

Referenced by dgFindNumberedNode().

{
struct hashEl *hel;
if ((hel = hashLookup(dg->nodeHash, name)) == NULL)
    return NULL;
return hel->val;
}

Here is the call graph for this function:

Here is the caller graph for this function:

struct dgConnection* dgFindNodeInConList	(	struct dgConnection *	conList,
		struct dgNode *	node
	)			[read]

Definition at line 147 of file diGraph.c.

References dgConnection::next, and dgConnection::node.

Referenced by dgConnectWithVal(), dgDirectlyFollows(), and dgFindPath().

{
struct dgConnection *con;
for (con = conList; con != NULL; con = con->next)
    if (con->node == node)
        return con;
return NULL;
}

Here is the caller graph for this function:

struct dgNodeRef* dgFindNodeInRefList	(	struct dgNodeRef *	refList,
		struct dgNode *	node
	)			[read]

Definition at line 137 of file diGraph.c.

References dgNodeRef::next, and dgNodeRef::node.

{
struct dgNodeRef *ref;
for (ref = refList; ref != NULL; ref = ref->next)
    if (ref->node == node)
        return ref;
return NULL;
}

struct dgNode* dgFindNumberedNode	(	struct diGraph *	dg,
		int	id
	)			[read]

Definition at line 109 of file diGraph.c.

References dgFindNode().

{
char buf[16];
sprintf(buf, "%d", id);
return dgFindNode(dg, buf);
}

Here is the call graph for this function:

struct dgNodeRef* dgFindPath	(	struct diGraph *	dg,
		struct dgNode *	a,
		struct dgNode *	b
	)			[read]

Definition at line 508 of file diGraph.c.

References AllocVar, dgFindNodeInConList(), dlAddValTail(), dlPopHead(), errAbort(), freeDlList(), freeMem(), newDlList(), dgConnection::next, dgNode::next, dgNode::nextList, dgConnection::node, diGraph::nodeList, slAddHead, slAddTail(), dgNode::tempEntry, and dlNode::val.

{
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;
}

Here is the call graph for this function:

struct dgEdgeRef* dgFindSubEdges	(	struct diGraph *	dg,
		struct dgNodeRef *	subGraph
	)			[read]

Definition at line 649 of file diGraph.c.

References AllocVar, dgConnection::edgeOnList, hashAdd(), hashLookup(), dgNode::name, newHash(), dgConnection::next, dgNodeRef::next, dgNode::nextList, dgConnection::node, dgNodeRef::node, slAddHead, and dlNode::val.

{
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;
}

Here is the call graph for this function:

void dgFree

(

struct diGraph **

pGraph

)

Definition at line 43 of file diGraph.c.

References dgNodeFreeList(), diGraph::edgeList, freeDlListAndVals(), freeHash(), freez(), diGraph::nodeHash, and diGraph::nodeList.

{
struct diGraph *dg = *pGraph;
if (dg == NULL)
    return;
freeHash(&dg->nodeHash);
dgNodeFreeList(&dg->nodeList);
freeDlListAndVals(&dg->edgeList);
freez(pGraph);
}

Here is the call graph for this function:

boolean dgHasCycles

(

struct diGraph *

dg

)

Definition at line 341 of file diGraph.c.

References dgClearVisitFlags(), dgTopoSort(), FALSE, dgNode::next, diGraph::nodeList, rHasCycles(), TRUE, and dgNode::visited.

Referenced by dgConstrainedPriorityOrder().

{
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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

struct diGraph* dgNew

(

)

[read]

Definition at line 9 of file diGraph.c.

References AllocVar, diGraph::edgeList, newDlList(), newHash(), and diGraph::nodeHash.

{
struct diGraph *dg;
AllocVar(dg);
dg->nodeHash = newHash(0);
dg->edgeList = newDlList();
return dg;
}

Here is the call graph for this function:

struct dgConnection* dgNextList

(

struct dgNode *

node

)

[read]

Definition at line 710 of file diGraph.c.

References dgNode::nextList, and dgConnection::node.

{
return node->nextList;
}

static void dgNodeFree

(

struct dgNode **

pNode

)

[static]

Definition at line 19 of file diGraph.c.

References freez(), dgNode::nextList, dgNode::prevList, and slFreeList().

Referenced by dgNodeFreeList().

{
struct dgNode *node = *pNode;
if (node == NULL)
    return;
slFreeList(&node->nextList);
slFreeList(&node->prevList);
freez(pNode);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void dgNodeFreeList

(

struct dgNode **

pList

)

[static]

Definition at line 30 of file diGraph.c.

References dgNodeFree(), and dgNode::next.

Referenced by dgFree().

{
struct dgNode *el, *next;

for (el = *pList; el != NULL; el = next)
    {
    next = el->next;
    dgNodeFree(&el);
    }
*pList = NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void* dgNodeName

(

struct dgNode *

node

)

Definition at line 124 of file diGraph.c.

References dgNode::name.

{
return node->name;
}

int dgNodeNumber

(

struct dgNode *

node

)

Definition at line 130 of file diGraph.c.

References dgNode::name.

{
return atoi(node->name);
}

void* dgNodeVal

(

struct dgNode *

node

)

Definition at line 118 of file diGraph.c.

References dgNode::val.

{
return node->val;
}

boolean dgParentsAllVisited

(

struct dgNode *

node

)

Definition at line 592 of file diGraph.c.

References FALSE, dgConnection::next, dgConnection::node, dgNode::prevList, TRUE, and dgNode::visited.

Referenced by dgConstrainedPriorityOrder().

{
struct dgConnection *con;
for (con = node->prevList; con != NULL; con = con->next)
    {
    if (con->node->visited == FALSE)
        return FALSE;
    }
return TRUE;
}

Here is the caller graph for this function:

boolean dgPathExists	(	struct diGraph *	dg,
		struct dgNode *	a,
		struct dgNode *	b
	)

Definition at line 285 of file diGraph.c.

References dgClearVisitFlags(), rPathExists(), and rTarget.

{
rTarget = b;
dgClearVisitFlags(dg);
return rPathExists(a);
}

Here is the call graph for this function:

struct dgConnection* dgPrevList

(

struct dgNode *

node

)

[read]

Definition at line 716 of file diGraph.c.

References dgConnection::node, and dgNode::prevList.

{
return node->prevList;
}

static struct dlNode* dgRemoveFromConList	(	struct dgConnection **	pConList,
		struct dgNode *	node,
		struct dgConnection **	retCon
	)			[static, read]

Definition at line 204 of file diGraph.c.

References dgConnection::edgeOnList, freeMem(), dlNode::next, dgConnection::next, dgConnection::node, and slAddHead.

Referenced by dgDisconnect(), and dgSwapEdges().

{
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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void dgSwapEdges	(	struct diGraph *	dg,
		struct dgEdgeRef *	erList
	)

Definition at line 682 of file diGraph.c.

References dgEdge::a, dgEdge::b, dgRemoveFromConList(), dgEdgeRef::edge, dgEdgeRef::next, dgNode::nextList, dgConnection::node, dgNode::prevList, and slAddHead.

{
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);
    }
}

Here is the call graph for this function:

void dgTopoSort

(

struct diGraph *

dg

)

Definition at line 307 of file diGraph.c.

References dgClearVisitFlags(), dgNode::next, diGraph::nodeList, rTopoSort(), topoIx, and dgNode::visited.

Referenced by dgHasCycles().

{
struct dgNode *node;

topoIx = 0;
dgClearVisitFlags(dg);
for (node = dg->nodeList; node != NULL; node = node->next)
    {
    if (!node->visited)
        rTopoSort(node);
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void rFindConnected

(

struct dgNode *

a

)

[static]

Definition at line 361 of file diGraph.c.

References AllocVar, dgNode::conn, dgConnection::next, dgNode::nextList, dgConnection::node, dgNodeRef::node, dgNode::prevList, rMustHaveVal, rRefList, slAddHead, TRUE, and dgNode::val.

Referenced by connectedComponents(), dgFindNewConnected(), dgFindNewConnectedWithVals(), dgFindNextConnected(), and dgFindNextConnectedWithVals().

{
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);
    }
}

Here is the caller graph for this function:

static boolean rHasCycles

(

struct dgNode *

node

)

[static]

Definition at line 321 of file diGraph.c.

References FALSE, dgConnection::next, dgNode::nextList, dgConnection::node, dgNode::topoOrder, TRUE, and dgNode::visited.

Referenced by dgHasCycles().

{
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;
}

Here is the caller graph for this function:

static boolean rPathExists

(

struct dgNode *

a

)

[static]

Definition at line 269 of file diGraph.c.

References FALSE, dgConnection::next, dgNode::nextList, dgConnection::node, rTarget, TRUE, and dgNode::visited.

Referenced by dgPathExists().

{
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;
}

Here is the caller graph for this function:

static void rTopoSort

(

struct dgNode *

node

)

[static]

Definition at line 295 of file diGraph.c.

References dgConnection::next, dgNode::nextList, dgConnection::node, topoIx, dgNode::topoOrder, TRUE, and dgNode::visited.

Referenced by dgTopoSort().

{
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;
}

Here is the caller graph for this function:

---

Variable Documentation

char const rcsid[] = "$Id: diGraph.c,v 1.9 2005/08/17 03:01:29 galt Exp $" [static]

Definition at line 7 of file diGraph.c.

bool rMustHaveVal

Definition at line 358 of file diGraph.c.

Referenced by connectedComponents(), dgConnectedComponents(), dgConnectedComponentsWithVals(), dgFindNewConnected(), dgFindNewConnectedWithVals(), dgFindNextConnected(), dgFindNextConnectedWithVals(), and rFindConnected().

struct dgNodeRef* rRefList

Definition at line 357 of file diGraph.c.

Referenced by connectedComponents(), dgFindNewConnected(), dgFindNewConnectedWithVals(), dgFindNextConnected(), dgFindNextConnectedWithVals(), and rFindConnected().

struct dgNode* rTarget [static]

Definition at line 267 of file diGraph.c.

Referenced by dgPathExists(), and rPathExists().

int topoIx [static]

Definition at line 293 of file diGraph.c.

Referenced by dgTopoSort(), and rTopoSort().

---