Process for determining the simple cycles of a finite directed graph

Claim 2

A machine-implemented method, carried out by means of a data processing system that includes a storage unit, of determining the simple cycles of a finite directed graph comprising the machine steps of, searching various paths of said graph until a vertex of the graph is reencountered, placing in said storage unit a representation of the path followed from the initial encounter of said vertex to the reencounter, said path comprising a cyclic path, re-searching said path until a vertex is reencountered which has at least one arc which has not yet been searched, searching a path commencing with said arc, said searching including the previously defined searching, placing and researching steps, and concatenating terminal subpaths of the cyclic paths placed in said storage unit to thereby form additional cyclic paths.

Claim 3

A method as in claim 1 wherein said searching further comprises, placing in storage in a trail thread list in said storage unit representations of the vertices of the graph after they are searched, removing said vertices from said list as said vertices are re-searched, marking said vertices which are removed from said list, and terminating said searching after all vertices have been searched.

Claim 4

A method as in claim 2 wherein said concatenating further comprises selecting from said storage unit cyclic paths CP1 which contain a vertex v when the vertex v is reencountered during said searching and is marked as no longer on the trail thread list, concatenating (a) the tails of such cyclic paths with respect to v with (b) the tail of the trail thread list with respect to the end vertices of the cyclic paths CP1 and with (c) v and The arc joining v to the trail thread list when the end vertices of the cyclic paths CP1 are on the trail thread list, and placing said concatenated paths in said storage unit.

Claim 5

A method as in claim 3 wherein said concatenating further comprises selecting from said storage unit cyclic paths CP2 which contain the end vertices of the cyclic paths CP1 when said end vertices are not on the trial thread list, concatenating (a) the tail of the trail thread list with respect to the end vertex of CP2 with (b) v and the arc joining v to the trial thread list, with (c) the tails of the cyclic paths CP1 with respect to v, and with (d) the tails of the cyclic paths CP2 with respect to the end vertices of the cyclic paths CP1, repeating said previous selecting and concatenating steps for other cyclic paths in said storage unit until paths CPn are found whose end vertices are on the trail thread list, concatenating the tails of said cyclic paths CPn with respect to the end vertices of the last concatenated cyclic paths with said last concatenated paths and with the tail of the trial thread list with respect to the end vertices of CPn and placing said concatenated paths in said storage unit.

Claim 6

A method as in claim 4 further including the steps of, eliminating from said graph all vertices on which no arcs terminate and the arcs originating thereon, and eliminating from said graph all vertices on which no arcs originate and the arcs terminating thereon.

Claim 7

In a data processing system that includes a storage unit, a machine-implemented method, carried out by means of said system, of determining the simple cycles of a finite directed graph, the vertices and arcs of said graph being represented by a plurality of electrical signals stored in said unit, comprising the machine steps of: a. removing from said storage unit those vertices of the graph on which no arcs originate or terminate and the arcs terminating and originating respectively thereon, b. selecting one of the remaining vertices in said storage unit, c. searching one of the paths emanating from said selected vertex, said searching including the steps of marking each vertex and arc encountered and placing in storage in a trial thread list in said storage unit a representation of each vertex encountered, the contents of said list representing a path from said selected vertex to the vertex currently being examined, d. placing in said storage unit in a cyclic path list a representation of any encountered vertex and of the tail of the trail thread path with respect to said vertex when said encountered vertex is marked and is in said storage unit in said trail thread list, e. concatenating terminal subpaths of cyclic paths in said storage unit in said cyclic path list, where at least one of said subpaths comprises a particular encountered vertex and when said particular vertex is marked and is absent from said trail thread list, to thereby form paths which originate at said particular vertex and terminate at vertices on said trial thread path, f. concatenating each such path formed in step (e) to the tails of said trail thread path with respect to the vertices on which the paths obtained in step (e) terminate to thereby obtain cyclic paths, g. placing the cyclic paths obtained in step (f) in said storage unit in said cyclic path list, h. reversing the direction of said searching to thereby re-search said trial thread list each vertex re-searched, i. searching a path originating on a reencountered branch vertex when said path originating on said branch vertex commences on an unmarked arc, said searching including steps (c) through (h), j. selecting an unmarked vertex as the starting point of a new trial thread path, if no branch vertices are encountered during said re-searching, and proceeding through steps (c) through (i) and k. tErminating said method when all vertices have been searched.

Claim 8

In a data processing system that includes a storage unit, a machine-implemented method, carried out by means of said system, of determining the simple cycles of a finite directed graph, the vertices and arcs of said graph being represented by a plurality of electrical signals stored in said unit, comprising the machine steps of: a. removing from said storage unit those vertices of the graph on which no arcs originate or terminate and the arcs terminating and originating respectively thereon, b. selecting one of the remaining vertices in said storage unit, c. searching one of the paths emanating from said selected vertex, said searching including the steps of marking each vertex and arc encountered and placing in storage in a trial thread list in said storage unit a representation of each vertex encountered, the contents of said list representing a path from said selected vertex to the vertex currently being examined, d. placing in said storage unit in a cyclic path list a representation of any encountered vertex and of the tail of the trail thread path with respect to said vertex when said encountered vertex is marked and is in said storage unit in said trail thread list, e. concatenating terminal subpaths of cyclic paths in said storage unit in said cyclic path list, where at least one of said subpaths comprises a particular encountered vertex and when said particular vertex is marked and is absent from said trail thread list, to thereby form paths which originate at said particular vertex and terminate at vertices on said trial thread path, f. concatenating each such path formed in step (e) to the tails of said trail thread path with respect to the vertices on which the paths obtained in step (e) terminate to thereby obtain cyclic paths, g. placing the cyclic paths obtained in step (f) in said storage unit in said cyclic path list, h. reversing the direction of said searching to thereby re-search said trial thread list each vertex re-searched, i. searching a path originating on a reencountered branch vertex when said path originating on said branch vertex commences on an unmarked arc, said searching including steps (c) through (h), j. selecting an unmarked vertex as the starting point of a new trial thread path, if no branch vertices are encountered during said re-searching, and proceeding through steps (c) through (i) and k. tErminating said method when all vertices have been searched.

Claim 9

In a data processing system, a machine-implemented method, carried out by means of said system, of determining the simple cycles of a directed graph, the vertices and arcs of said graph being represented by a plurality of stored electrical signals, comprising the machine steps of, a. examining a path of said graph, said examining including maintaining a record of the arcs and vertices examined, b. placing in storage in a cyclic path list the tail of said record with respect to a particular vertex plus said vertex when said vertex is present in said record and is reencountered during said examining, c. reexamining the arcs and vertices in said record and removing same therefrom until reencountering a vertex which contains arcs not previously examined, d. examining a path commencing with one of said unexamined arcs including steps (a) through (c), e. placing all cyclic paths which are in the cyclic path list and which contain a vertex v in storage in a work list, when said vertex v is reencountered during said examining and has once been but is no longer on said record, f. establishing a list where examined cycle tails can be stored, g. removing one cyclic path from the work list and determining its tail with respect to v, h. returning to step (g) if said cycle tail is in the list of examined cycle tails or contains no noninitial vertices, otherwise adding said cycle tail to said list of examined cycle tails, i. returning to step (g) if said cycle tail contains any vertices found on a path P which comprises a concatenation of previously examined cycle tails and the vertex v, j. concatenating (1) the tail of the record with respect to the end of said cycle tail with (2) the path P, and with (3) said cycle tail to form a cyclic path when said cycle tail end is present in said record, k. placing said cyclic path in the cyclic path list and returning to step (g), l. placing the path P, the list of examined cycle tails and the work list on top of a stack in storage, concatenating said cycle tail with the path P to form a new path P and setting said cycle tail end v when said cycle tail end is not present in said record and returning to step (e), m. removing the top value of P, the top list of examined cycle tails and the top work list from the stack when the current work list is found to be empty and when the stack contains at least one value of P, n. returning to step (a) when the current work list is found to be empty and when the stack contains no values of P, and o. terminating the method when all vertices have been examined.

Claim 10

In a data processing system, a machine-implemented method, carried out by means of said system, of determining the simple cycles of a directed graph, the vertices and arcs of said graph being represented by a plurality of stored electrical signals, comprising the machine steps of, a. examining a path of said graph, said examining including maintaining a record of the arcs and vertices examined, b. placing in storage in a cyclic path list the tail of said record with respect to a particular vertex plus said vertex when said vertex is present in said record and is reencountered during said examining, c. reexamining the arcs and vertices in said record and removing same therefrom until reencountering a vertex which contains arcs not previously examined, d. examining a path commencing with one of said unexamined arcs including steps (a) through (c), e. placing all cyclic paths which are in the cyclic path list and which contain a vertex v in storage in a work list, when said vertex v is reencountered during said examining and has once been but is no longer on said record, f. establishing a list where examined cycle tails can be stored, g. removing one cyclic path from the work list and determining its tail with respect to v, h. returning to step (g) if said cycle tail is in the list of examined cycle tails or contains no noninitial vertices, otherwise adding said cycle tail to said list of examined cycle tails, i. returning to step (g) if said cycle tail contains any vertices found on a path P which comprises a concatenation of previously examined cycle tails and the vertex v, j. concatenating (1) the tail of the record with respect to the end of said cycle tail with (2) the path P, and with (3) said cycle tail to form a cyclic path when said cycle tail end is present in said record, k. placing said cyclic path in the cyclic path list and returning to step (g), l. placing the path P, the list of examined cycle tails and the work list on top of a stack in storage, concatenating said cycle tail with the path P to form a new path P and setting said cycle tail end v when said cycle tail end is not present in said record and returning to step (e), m. removing the top value of P, the top list of examined cycle tails and the top work list from the stack when the current work list is found to be empty and when the stack contains at least one value of P, n. returning to step (a) when the current work list is found to be empty and when the stack contains no values of P, and o. terminating the method when all vertices have been examined.

Claim 11

A method as in claim 7 further comprising the steps of, removing from said graph all vertices on which no arcs terminate and the arcs originating thereon, and removing from said graph all vertices on which no arcs originate and the arcs terminating thereon.