Patent ID: 8239404

Claim:
A computer-implemented method for identifying entries and exits while identifying strongly connected components in a graph, the method comprising: receiving a node of a graph data structure for which to identify strongly connected components, entries, and exits; setting an index of the received node to an incremented value that tracks a count of nodes identified in the graph data structure as the nodes are encountered; initializing a low link value of the received node to a number higher than a number of nodes in the graph data structure, wherein the low link value tracks a lowest index of other nodes that can be reached by following edges connected to the node; storing the received node along with any other nodes that may be part of a set of strongly connected components in a temporary storage facility; determining whether the received node has any descendants; upon determining that the received node has descendants, processing descendants of the received node to determine whether each descendant is itself a root of a set of strongly connected components; and if the node index is equal to the node low link value, identifying the node as a root of a set of strongly connected components; and removing nodes that were previously stored in the temporary storage facility until the received node is removed, wherein the removed nodes are a set of identified strongly connected components, wherein the preceding steps are performed by at least one processor.