1

Topic: The search algorithm of all cycles in the column

The directional graph is given, set structurally i.e. the peak can contain references to other peaks. It is necessary to find all cycles in the column. What it is possible to look at this subject?

2

Re: The search algorithm of all cycles in the column

N> the directional graph Is given, set structurally i.e. the peak can contain references to other peaks. N> it is necessary to find all cycles in the column. N> that it is possible to look at this subject? Probably, it is necessary to begin with determination of cyclomatic number and a fundamental cycle. And generally already repeatedly considered: http://rsdn.org/forum/alg/110876.flat the Author: __ Avatar __ Date: 07.10.02

3

Re: The search algorithm of all cycles in the column

Hello, nen777w, you wrote: N> the directional graph Is given, set structurally i.e. the peak can contain references to other peaks. N> it is necessary to find all cycles in the column. It is possible to begin with search of components of the strong connectivity, and then to solve the task for each of them. N> That it is possible to look at this subject? , Lejzerson, Rivest.

4

Re: The search algorithm of all cycles in the column

Hello, nen777w, you wrote: N> the directional graph Is given, set structurally i.e. the peak can contain references to other peaks. N> it is necessary to find all cycles in the column. N> that it is possible to look at this subject? 1. Search in . 2. I think, the wave algorithm approaches in which in a single step will "be colored"  in a certain color which corresponds to color of initial peak. On a trace. A step it is simply colored the adjacent peaks checking current color if it coincided, here it, a cycle and it is necessary simply  a route.

5

Re: The search algorithm of all cycles in the column

Hello, Kernan, you wrote: K> Search in . Yes, it is a primitive which will be anyway necessary. Depth-first search, strangely enough, is engaged not in search, and creation of wood and classification of arcs. Each time when it is met back edge, is a signal about cycle detection.

6

Re: The search algorithm of all cycles in the column

Hello, Qbit86, you wrote: Q> Hello, Kernan, you wrote: K>> Search in . Q> Yes, it is a primitive which will be anyway necessary. Depth-first search, strangely enough, is engaged not in search, and creation of wood and classification of arcs. Each time when it is met back edge, is a signal about cycle detection. For  it is necessary  from  to look and invent something. Besides, all naive algorithms have simply indecent algorithmic complexity at worst.

7

Re: The search algorithm of all cycles in the column

Hello, Kernan, you wrote: K> For  it is necessary  from  to look and invent something. Besides, all naive algorithms have simply indecent algorithmic complexity at worst. Under a primitive I meant basic procedure-brick. For example, the search of components of the strong connectivity offered above uses (twice) bypass in depth.

8

Re: The search algorithm of all cycles in the column

Hello, nen777w, you wrote: N> the directional graph Is given, set structurally i.e. the peak can contain references to other peaks. N> it is necessary to find all cycles in the column. N> that it is possible to look at this subject? Currently the most effective algorithm is the algorithm of Tiernan sm its article "An algorithm for finding a fundamental set of cycles of a graph" http://citeseerx.ist.psu.edu/viewdoc/do … p;type=pdf In the presence of the infinite storage on the computer, there is a probability not to live to that happy moment when all cycles even for the small graph with number of peaks ~100 Program implementation will be found is available in boost:: graph in tiernan_all_cycles.hpp