1

Topic: Search of loops in dependences

There is a sequence of entities - A, B, a C, D, E, F..... Any essence can comprise the link to any other of this sequence, except itself. Mandatory there is an essence which does not depend from any another. A question two 1) whether How to find is loops in dependences? That is to eliminate cases when In depends from With, With depends from D and And, and D depends from F and B? 2) How to sort this sequence by a principle of dependences? That is the first should stand what on anybody what depend only on the first and so on do not depend, further? However, on the second at me the decision was invented. To enter number for each essence - coefficient of dependences. At what on anybody do not depend - it is equal to zero, and at what  - from it is equal (a maximum of coefficient of children + 1). And by this number and to sort. This approach will work? There are no reefs? And here on the first something of anything optimal was not invented, except a heap of searches.

2

Re: Search of loops in dependences

Hello, SergeyOsipov, you wrote: SO> 1) whether How to find is loops in dependences? That is to eliminate cases when In depends from With, With depends from D and And, and D depends from F and B? The decision in a forehead. For each node to construct a tree of dependences. If in this tree there will be a start node the loop is available. If a start node did not reach, but the tree turned out too long the loop for certain is, only the start node does not participate in it.

3

Re: Search of loops in dependences

Hello, Mihas, you wrote: SO>> 1) whether How to find is loops in dependences? That is to eliminate cases when In depends from With, With depends from D and And, and D depends from F and B? M> the Decision in a forehead. M> for each node to construct a tree of dependences. M> if in this tree there will be a start node the loop is available. M> if a start node did not reach, but the tree turned out too long the loop for certain is, only the start node does not participate in it. But if to construct such tree for each node for certain there will be a tree where the start node repeats. So after all? Or not? Simply term "too long" is blurred enough.

4

Re: Search of loops in dependences

Hello, SergeyOsipov, you wrote: SO> But if to construct such tree for each node for certain there will be a tree where the start node repeats. So after all? Or not? I will explain. The tree needs to be built separately for each node. And to supervise its appearance only in this tree. In adjacent trees to climb not what for. SO> Simply term "too long" is blurred enough. Here it is necessary to think. The internal voice prompts: if we have all N sites depth of a tree should not exceed N. If it is more, somewhere went on the second circle.

5

Re: Search of loops in dependences

Hello, SergeyOsipov, you wrote: SO> There is a sequence of entities - A, B, a C, D, E, F..... SO> Any essence can comprise the link to any other of this sequence, except itself. SO> mandatory there is an essence which does not depend from any another. SO> a question two SO> 1) whether How to find is loops in dependences? That is to eliminate cases when In depends from With, With depends from D and And, and D depends from F and B? SO> 2) How to sort this sequence by a principle of dependences? That is the first should stand what on anybody what depend only on the first and so on do not depend, further? SO> However, on the second at me the decision was invented. To enter number for each essence - coefficient of dependences. At what on anybody do not depend - it is equal to zero, and at what  - from it is equal (a maximum of coefficient of children + 1). And by this number and to sort. This approach will work? There are no reefs? Will work. SO> and here on the first something of anything optimal was not invented, except a heap of searches. Actually the decision of a question 2 will work and for 1 too and on the contrary. More in detail 1) peaks (column) without proceeding dependences are selected. If those are not present - means there are cycles. The selected peaks it is added in resultant sequence, supposing that all of them are equal (or sorting to any sign) 2) their column the edges entering into selected peaks is deleted. 3)  1) if enough to define, whether is cycles are will already work. If it is necessary to define, what nodes enter into cycles, it is necessary to operate more difficult. Z.Y.hardly algorithm is optimal, but is simple.

6

Re: Search of loops in dependences

Hello, SergeyOsipov, you wrote: SO> There is a sequence of entities - A, B, a C, D, E, F..... SO> Any essence can comprise the link to any other of this sequence, except itself. SO> mandatory there is an essence which does not depend from any another. SO> a question two SO> 1) whether How to find is loops in dependences? That is to eliminate cases when In depends from With, With depends from D and And, and D depends from F and B? Check of the graph on acyclicity SO> 2) How to sort this sequence by a principle of dependences? That is the first should stand what on anybody what depend only on the first and so on do not depend, further? Width-first search

7

Re: Search of loops in dependences

Hello, samius, you wrote: S> Actually the decision of a question 2 will work and for 1 too and on the contrary. S> is more detailed S> 1) peaks (column) without proceeding dependences are selected. If those are not present - means there are cycles. The selected peaks it is added in resultant sequence, supposing that all of them are equal (or sorting to any sign) S> 2) their column the edges entering into selected peaks is deleted. S> 3)  1) S> if enough to define, whether is cycles are will already work. Interesting. It is necessary to consider. And to which moment of such simplification of the graph come confidence, what cycles are? The graph does not become simpler any more, and dependences remained?

8

Re: Search of loops in dependences

Hello, SergeyOsipov, you wrote: SO> Hello, samius, you wrote: S>> If enough to define, whether there are cycles are will already work. SO> it is interesting. It is necessary to consider. And to which moment of such simplification of the graph come confidence, what cycles are? The graph does not become simpler any more, and dependences remained? When raw peaks still remained, but among them there is no with 0th level of an outcome (without dependences) - the cycle means.

9

Re: Search of loops in dependences

Hello, SergeyOsipov, you wrote: SO> However, on the second at me the decision was invented. To enter number for each essence - coefficient of dependences. At what on anybody do not depend - it is equal to zero, and at what  - from it is equal (a maximum of coefficient of children + 1). And by this number and to sort. This approach will work? There are no reefs? A / \B \/\C E / / \D F G At B the coefficient of dependences turns out more than at E that, , . SO> and here on the first something of anything optimal was not invented, except a heap of searches. We get set of raw nodes, and initially we put all nodes there. In each node we get a sign that it is already processed, and set of nodes on which it depends. While the set of raw nodes does not become empty: * we take therefrom the first node * the search algorithm of dependences is applied to a node to it. Algorithm recursive: * for all nodes on which the given node depends directly: ** if the node is not processed yet, this algorithm ** recursively is applied this node is brought in set of own dependences and its dependences * we mark a node as processed, and it is deleted it from "global" set of raw nodes When we something put into the list of dependences, we check, whether we there brought ourselves. If yes, means in a dependence graph there was a cycle, are under abnormal condition completed. If operations of adding/removal of a node in set of dependences and join of two sets have complexity O (1), this algorithm has complexity O (N) that is rather quite good. Naturally, I did not debug this algorithm, and is direct now from a head invented, so somewhere could and be mistaken