inc/diGraph.h File Reference

#include "dlist.h"

Include dependency graph for diGraph.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	diGraph
struct	dgNode
struct	dgEdge
struct	dgConnection
struct	dgNodeRef
struct	dgEdgeRef
Functions
diGraph *	dgNew ()
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)
dgEdge *	dgConnect (struct diGraph *dg, struct dgNode *a, struct dgNode *b)
dgEdge *	dgConnectWithVal (struct diGraph *dg, struct dgNode *a, struct dgNode *b, void *val)
void	dgDisconnect (struct diGraph *dg, struct dgNode *a, struct dgNode *b)
dgEdge *	dgDirectlyFollows (struct diGraph *dg, struct dgNode *a, struct dgNode *b)
boolean	dgPathExists (struct diGraph *dg, struct dgNode *a, struct dgNode *b)
dgNodeRef *	dgFindPath (struct diGraph *dg, struct dgNode *a, struct dgNode *b)
dgNodeRef *	dgFindConnectedToNode (struct diGraph *dg, struct dgNode *a)
dgNodeRef *	dgFindNewConnected (struct diGraph *dg, struct dgNode *a)
dgNodeRef *	dgFindNewConnectedWithVals (struct diGraph *dg, struct dgNode *a)
dgNodeRef *	dgFindNextConnected (struct diGraph *dg)
dgNodeRef *	dgFindNextConnectedWithVals (struct diGraph *dg)
int	dgConnectedComponents (struct diGraph *dg)
int	dgConnectedComponentsWithVals (struct diGraph *dg)
void	dgTopoSort (struct diGraph *dg)
boolean	dgHasCycles (struct diGraph *dg)
boolean	dgParentsAllVisited (struct dgNode *node)
dgNodeRef *	dgConstrainedPriorityOrder (struct diGraph *dg)
boolean	dgRangesConsistent (struct diGraph *rangeGraph, boolean(*findEdgeRange)(struct dgEdge *edge, int *retMin, int *retMax))
boolean	dgAddedRangeConsistent (struct diGraph *rangeGraph, struct dgNode *a, struct dgNode *b, int abMin, int abMax, boolean(*findEdgeRange)(struct dgEdge *edge, int *retMin, int *retMax))
dgEdgeRef *	dgFindSubEdges (struct diGraph *dg, struct dgNodeRef *subGraph)
void	dgSwapEdges (struct diGraph *dg, struct dgEdgeRef *erList)
void	dgClearConnFlags (struct diGraph *dg)
void	dgClearVisitFlags (struct diGraph *dg)
dgNodeRef *	dgFindNodeInRefList (struct dgNodeRef *refList, struct dgNode *node)
dgConnection *	dgFindNodeInConList (struct dgConnection *conList, struct dgNode *node)
dgConnection *	dgNextList (struct dgNode *node)
dgConnection *	dgPrevList (struct dgNode *node)
void	dgDumpGraph (struct diGraph *dg, FILE *out, boolean hideIsolated)

---

Function Documentation

boolean dgAddedRangeConsistent	(	struct diGraph *	rangeGraph,
		struct dgNode *	a,
		struct dgNode *	b,
		int	abMin,
		int	abMax,
		boolean(*)(struct dgEdge *edge, int *retMin, int *retMax)	findEdgeRange
	)

Definition at line 197 of file dgRange.c.

References bfCheckGraph(), bfGraphFree(), and bfGraphFromRangeGraph().

Referenced by dgRangesConsistent().

{
struct bfGraph *bfGraph;
boolean ok; 

bfGraph = bfGraphFromRangeGraph(rangeGraph, findEdgeRange, a, b, abMin, abMax);
ok = bfCheckGraph(bfGraph);
bfGraphFree(&bfGraph);
return ok;
}

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(), dgNode::name, hashEl::name, diGraph::nodeHash, diGraph::nodeList, ptrToLL, slAddHead, hashEl::val, and dgNode::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, dlNode::val, dgEdge::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(), dgNode::next, dlNode::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, dgNode::next, dgConnection::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(), dgNode::next, dgConnection::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(), dgNodeRef::next, dgConnection::next, dgNode::nextList, dgNodeRef::node, dgConnection::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;
}

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

boolean dgRangesConsistent	(	struct diGraph *	rangeGraph,
		boolean(*)(struct dgEdge *edge, int *retMin, int *retMax)	findEdgeRange
	)

Definition at line 213 of file dgRange.c.

References dgAddedRangeConsistent().

{
return dgAddedRangeConsistent(rangeGraph, NULL, NULL, 0, 0, findEdgeRange);
}

Here is the call 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:

---