Fast search method for enabling a computer to find elementary loops in a graph

摘要

A method for operating a computer to find elementary loops in a strongly connected component of a graph. In the basic method, the computer identifies a starting vertex from the vertices of the strongly connected component that have not been examined as a possible starting vertex for an elementary loop and which are not contained in any elementary loop discovered thus far. The vertices of the strongly connected component are then searched for a path starting and ending on the identified vertex. If the search finds a path starting and ending of the identified vertex, the path is recorded as an elementary loop. This process is repeated until no starting vertex can be identified. To improve the efficiency of the search process, the computer identifies vertices that are the starting vertex for a paths that are shared by more than one elementary loop. The shared paths are stored separately and used to avoid searching the vertices of the path more than once.