antlr3-hasCycle (3) - Linux Manuals
NAME
ANTLR3_TOPO_struct -
A topological sort system that given a set of dependencies of a node m on node n, can sort them in dependency order.
SYNOPSIS
#include <antlr3collections.h>
Data Fields
void(* addEdge )(struct ANTLR3_TOPO_struct *topo, ANTLR3_UINT32 edge, ANTLR3_UINT32 dependency)
A method that adds an edge from one node to another.
pANTLR3_UINT32 cycle
A vector used to detect cycles in the edge dependecies.
ANTLR3_UINT32 cycleMark
A watermark used to accumulate potential cycles in the cycle array.
pANTLR3_BITSET * edges
A vector of vectors of edges, built by calling the addEdge method() to indicate that node number n depends on node number m.
void(* free )(struct ANTLR3_TOPO_struct *topo)
A method to free this structure and any associated memory.
ANTLR3_BOOLEAN hasCycle
A flag that indicates the algorithm found a cycle in the edges such as 9->8->1->9 If this flag is set after you have called one of the sort routines then the detected cycle will be contained in the cycle array and cycleLimit will point to the one after the last entry in the cycle.
ANTLR3_UINT32 limit
One more than the largest node index that is contained in edges/sorted.
pANTLR3_UINT32 sorted
A vector used to build up the sorted output order.
pANTLR3_UINT32(* sortToArray )(struct ANTLR3_TOPO_struct *topo)
A method that returns a pointer to an array of sorted node indexes.
void(* sortVector )(struct ANTLR3_TOPO_struct *topo, pANTLR3_VECTOR v)
A method that sorts the supplied ANTLR3_VECTOR in place based on the previously supplied edge data.
pANTLR3_BITSET visited
The set of visited nodes as determined by a set entry in the bitmap.
Detailed Description
A topological sort system that given a set of dependencies of a node m on node n, can sort them in dependency order.
This is a generally useful utility object that does not care what the things are it is sorting. Generally the set to be sorted will be numeric indexes into some other structure such as an ANTLR3_VECTOR. I have provided a sort method that given ANTLR3_VECTOR as an input will sort the vector entries in place, as well as a sort method that just returns an array of the sorted noded indexes, in case you are not sorting ANTLR3_VECTORS but some set of your own device.
Of the two main algorithms that could be used, I chose to use the depth first search for unvisited nodes as a) This runs in linear time, and b) it is what we used in the ANTLR Tool to perform a topological sort of the input grammar files based on their dependencies.
Field Documentation
void(* ANTLR3_TOPO_struct::addEdge)(struct ANTLR3_TOPO_struct *topo, ANTLR3_UINT32 edge, ANTLR3_UINT32 dependency)
A method that adds an edge from one node to another. An edge of n -> m indicates that node n is dependent on node m. Note that while building these edges, it is perfectly OK to add nodes out of sequence. So, if you have edges:
3 -> 0 2 -> 1 1 -> 3
The you can add them in that order and so add node 3 before nodes 2 and 1
Referenced by antlr3TopoNew().
pANTLR3_UINT32 ANTLR3_TOPO_struct::cycle
A vector used to detect cycles in the edge dependecies. It is used as a stack and each time we descend a node to one of its edges we add the node into this stack. If we find a node that we have already visited in the stack, then it means there wasa cycle such as 9->8->1->9 as the only way a node can be on the stack is if we are currently descnding from it as we remove it from the stack as we exit from descending its dependencies
Referenced by antlr3TopoNew(), DFS(), freeTopo(), and sortToArray().
ANTLR3_UINT32 ANTLR3_TOPO_struct::cycleMark
A watermark used to accumulate potential cycles in the cycle array. This should be zero when we are done. Check hasCycle after calling one of the sort methods and if it is ANTLR3_TRUE then you can find the cycle in cycle[0]...cycle[cycleMark-1]
Referenced by antlr3TopoNew(), and DFS().
pANTLR3_BITSET* ANTLR3_TOPO_struct::edges
A vector of vectors of edges, built by calling the addEdge method() to indicate that node number n depends on node number m. Each entry in the vector contains a bitset, which has a bit index set for each node upon which the entry node depends.
Referenced by addEdge(), antlr3TopoNew(), DFS(), freeTopo(), and sortToArray().
void(* ANTLR3_TOPO_struct::free)(struct ANTLR3_TOPO_struct *topo)
A method to free this structure and any associated memory.
Referenced by antlr3TopoNew().
ANTLR3_BOOLEAN ANTLR3_TOPO_struct::hasCycle
A flag that indicates the algorithm found a cycle in the edges such as 9->8->1->9 If this flag is set after you have called one of the sort routines then the detected cycle will be contained in the cycle array and cycleLimit will point to the one after the last entry in the cycle.
Referenced by antlr3TopoNew(), DFS(), sortToArray(), and sortVector().
ANTLR3_UINT32 ANTLR3_TOPO_struct::limit
One more than the largest node index that is contained in edges/sorted.
Referenced by addEdge(), antlr3TopoNew(), DFS(), freeTopo(), sortToArray(), and sortVector().
pANTLR3_UINT32 ANTLR3_TOPO_struct::sorted
A vector used to build up the sorted output order. Note that as the vector contains UINT32 then the maximum node index is 'limited' to 2^32, as nodes should be zero based.
Referenced by antlr3TopoNew(), DFS(), freeTopo(), sortToArray(), and sortVector().
pANTLR3_UINT32(* ANTLR3_TOPO_struct::sortToArray)(struct ANTLR3_TOPO_struct *topo)
A method that returns a pointer to an array of sorted node indexes. The array is sorted in topological sorted order. Note that the array is only as large as the largest node index you created an edge for. This means that if you had an input of 32 nodes, but that largest node with an edge was 16, then the returned array will be the sorted order of the first 16 nodes and the last 16 nodes of your array are basically fine as they are as they had no dependencies and do not need any particular sort order.
NB: If the structure that contains the array is freed, then the sorted array will be freed too so you should use the value of limit to make a long term copy of this array if you do not want to keep the topo structure around as well.
Referenced by antlr3TopoNew(), and sortVector().
void(* ANTLR3_TOPO_struct::sortVector)(struct ANTLR3_TOPO_struct *topo, pANTLR3_VECTOR v)
A method that sorts the supplied ANTLR3_VECTOR in place based on the previously supplied edge data.
Referenced by antlr3TopoNew().
pANTLR3_BITSET ANTLR3_TOPO_struct::visited
The set of visited nodes as determined by a set entry in the bitmap.
Referenced by antlr3TopoNew(), DFS(), freeTopo(), and sortToArray().
Author
Generated automatically by Doxygen for ANTLR3C from the source code.