Patent ID: 7764629

Claim:
A method in a computer system with multiple processors and memory for identifying connected nodes in a graph, the method comprising: providing in the memory a graph having nodes and edges connecting the nodes of the graph; identifying subgraphs of nodes by performing at each of the processors in parallel the following: selecting by the processor for visiting an unvisited node of the graph and marking it as a root node; searching by the processor for nodes that are connected to the root node; when an unvisited connected node is found, visiting by the processor the unvisited found node and indicating that the unvisited found node is connected to the root node such that the root node and the nodes indicated as connected to the root node form a subgraph of nodes; when a visited connected node is found, when the visited found node is indicated as connected to a different root node, indicating by the processor a mapping between the root node and the different root node, the mapping indicating that the subgraph of the root node is connected to the subgraph of the different root node; and after the subgraphs are identified, applying by a processor an algorithm to the identified subgraphs and mappings, wherein the subgraphs represent hyper-nodes and the mappings represent hyper-edges between the hyper-nodes, to identify groups of connected nodes, wherein a group of nodes is connected if there exists a path of edges from each node in the group to every other node in the group and there is no edge from a node in the group to a node that is not in the group.