/* diGraph - Directed graph routines. */ #ifndef DIGRAPH_H #define DIGRAPH_H #ifndef DLIST_H #include "dlist.h" #endif struct diGraph /* A directed graph. */ { struct dgNode *nodeList; struct hash *nodeHash; struct dlList *edgeList; }; struct dgNode /* A node on a directed graph */ { struct dgNode *next; /* Next in master node list. */ char *name; /* Name of node (allocated in hash). */ void *val; /* Value of node. */ struct dgConnection *nextList; /* Ways out of node. */ struct dgConnection *prevList; /* Ways into node. */ int topoOrder; /* Topographical order after call to dgTopoSort. */ int component; /* Connected component number after call to dgConnectedComponents. */ int priority; /* Node priority. */ struct dgNode *tempEntry; /* Way in for breadth first search */ bool visited; /* Visit order in depth first traversal. */ bool conn; /* Flag for connection algorithms. */ bool flagA; /* Flag used in rangeGraph algorithms. */ bool flagB; /* Currently unused flag. */ }; struct dgEdge /* An edge on graph */ { void *val; /* Value of edge. */ struct dgNode *a; /* Node on incoming side. */ struct dgNode *b; /* Node on outgoing side. */ bool unflippable; /* True if can't flip this edge (specialized ooGreedy thing really) */ }; struct dgConnection /* Connects one node to another. Linked to edge. */ { struct dgConnection *next; /* Next in list. */ struct dgNode *node; /* Node this connects to. */ struct dlNode *edgeOnList; /* Associated edge. */ }; struct dgNodeRef /* A reference to a node. */ { struct dgNodeRef *next; /* Next in list. */ struct dgNode *node; /* Pointer to node. */ }; struct dgEdgeRef /* A reference to an edge. */ { struct dgEdgeRef *next; /* Next in list. */ struct dgEdge *edge; /* Reference to edge. */ }; struct diGraph *dgNew(); /* Return a new directed graph object. */ void dgFree(struct diGraph **pGraph); /* Free a directed graph. */ struct dgNode *dgAddNode(struct diGraph *dg, char *name, void *val); /* Create new node in graph. */ struct dgNode *dgAddNumberedNode(struct diGraph *dg, int id, void *val); /* Create new node with a number instead of a name. */ struct dgNode *dgFindNode(struct diGraph *dg, char *name); /* Find existing node in graph. */ struct dgNode *dgFindNumberedNode(struct diGraph *dg, int id); /* Find node given number. */ void *dgNodeVal(struct dgNode *node); /* Return value associated with node. */ void *dgNodeName(struct dgNode *node); /* Return name associated with node. */ int dgNodeNumber(struct dgNode *node); /* Return number of node. (Will likely return 0 if node * was added with a name rather than a number). */ struct dgEdge *dgConnect(struct diGraph *dg, struct dgNode *a, struct dgNode *b); /* Connect node a to node b. Returns connecting edge. */ 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. */ struct dgEdge *dgConnectUnflippable(struct diGraph *dg, struct dgNode *a, struct dgNode *b, void *val); /* Connect a to b with an edge than can't be flipped. */ void dgDisconnect(struct diGraph *dg, struct dgNode *a, struct dgNode *b); /* Disconnect nodes a and b. */ struct dgEdge *dgDirectlyFollows(struct diGraph *dg, struct dgNode *a, struct dgNode *b); /* Return TRUE if b directly follows a. */ boolean dgPathExists(struct diGraph *dg, struct dgNode *a, struct dgNode *b); /* Return TRUE if there's a path from a to b. */ 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 *dgFindConnectedToNode(struct diGraph *dg, struct dgNode *a); /* Return reference list of all nodes connected to a, including a. * slFreeList this list when done. */ struct dgNodeRef *dgFindNewConnected(struct diGraph *dg, struct dgNode *a); /* Find a connected component guaranteed not to be covered before * that includes a. */ struct dgNodeRef *dgFindNewFlippableConnected(struct diGraph *dg, struct dgNode *a); /* Find a connected component guaranteed not to be covered before * that includes a. Connected components must be connected by flippable * edges. */ 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 dgNodeRef *dgFindNextFlippableConnected(struct diGraph *dg); /* Like dgFindConnected, but only considers graph nodes that * are conencted by a flippable edge. */ int dgConnectedComponents(struct diGraph *dg); /* Count number of connected components and set component field * of each node to reflect which component it is in. */ int dgConnectedFlippableComponents(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 connected by flippable edges. */ void dgTopoSort(struct diGraph *dg); /* Fill in topological order of nodes. */ boolean dgHasCycles(struct diGraph *dg); /* Return TRUE if directed graph has cycles. */ boolean dgParentsAllVisited(struct dgNode *node); /* Return TRUE if all parents of node have been visited. */ 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. */ boolean dgRangesConsistent(struct diGraph *rangeGraph, boolean (*findEdgeRange)(struct dgEdge *edge, int *retMin, int *retMax) ); /* Return TRUE if graph with a range of allowable distances associated * with each edge is internally consistent. */ boolean dgAddedRangeConsistent(struct diGraph *rangeGraph, struct dgNode *a, struct dgNode *b, int abMin, int abMax, boolean (*findEdgeRange)(struct dgEdge *edge, int *retMin, int *retMax) ); /* Return TRUE if graph with a range of allowable distances associated * with each edge would be internally consistent if add edge from a to b * with given min/max values. */ struct dgEdgeRef *dgFindSubEdges(struct diGraph *dg, struct dgNodeRef *subGraph, boolean onlyFlippable); /* Return list of edges in graph that connected together nodes in subGraph. * Optionally return only flippable edges. */ 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.) */ void dgClearConnFlags(struct diGraph *dg); /* Clear out conn flags. */ void dgClearVisitFlags(struct diGraph *dg); /* Clear out visit order flags. */ struct dgNodeRef *dgFindNodeInRefList(struct dgNodeRef *refList, struct dgNode *node); /* Return reference to node if in list, or NULL if not. */ struct dgConnection *dgFindNodeInConList(struct dgConnection *conList, struct dgNode *node); /* Return connection to node if in list, or NULL if not. */ struct dgConnection *dgNextList(struct dgNode *node); /* Return list of connections out of this node. Don't free (or rearrange) * this list please. */ struct dgConnection *dgPrevList(struct dgNode *node); /* Return list of connections into this node. Don't free (or rearrange) * this list please. */ void dgDumpGraph(struct diGraph *dg, FILE *out, boolean hideIsolated); /* Dump info on graph to output. */ #endif /* DIGRAPH_H */