The DB translation maps A to 0, B to 1, ... , I to 8, J to 9. (I just did it by hand.)Originally Posted by Ackbeet
A = {B, C} means
data[0] = [1, 2]
So if you start with list of empty lists
[ [], [], [], [], [], [], [], [], [], [] ]
then you add A by doing
[ [1,2], [], [], [], [], [], [], [], [], [] ]
and likewise for D, C, F, G (all the others will remain empty in your examples).
My version 2 detects a cycle in all three cases. However, those are not all cycles that there are in db3.
The only thing that my version tries to make sure is that if there is a cycle, then at least one cycle gets detected.
It might be that undefined's implementation (of, I take it, basically the same algorithm) has a slight difference that makes it detect more cycles. Maybe you want to figure out what that difference happens to be?
But, basically, I think you are right: using the visited bit does in some cases prevent my implementation of the algorithm from detecting certain cycles. As in your db3.
I can easily see why this is the case with db3: after the first cycle A<-C<-F<-A has been found, the search for another cycle A<-C<-G<-A is abandoned too early beause the visited bit of A is tested before its marked bit is tested (the latter would lead to the detection of the second cycle).
You can see that undefined's handling of the visited and marked bits is a little different in his recurse() function.
P.S: I think, one would have to insert another test of the marked bit in the loop over all components in the current assembly before the visibility bit gets tested.
I have modified my code of version 2 slightly, that gives version 3, attached. Version 3 now also detects both cycles of DB3.
The change is in the condition of the following if-statement of checkAssemblies()
Code:for component in assembly.components: if component.marked or not component.visited: cycleFound |= checkAssembly(component, stack)
Unfortunately, this change was a bit hasty. It was not the most stupid thing that I have ever done in my life, but...
Anyway: what I really should have done is simply remove the statement that sets the visited bit prematurely after a cycle has been detected, because the depth-first traversal passing through that assembly is not completely finished at this point. That was the wrong thing to do for sure. So checkAssembly() now, in version 4, looks like this:
This example proves that sometimes simply dropping a line of code can do wonders for a program.Code:def checkAssembly(assembly, stack): if assembly.marked: dumpCycle(assembly, stack) return True # i.e. cycle found cycleFound = False assembly.marked = True stack.append(assembly) for component in assembly.components: if not component.visited: cycleFound |= checkAssembly(component, stack) stack.pop() assembly.marked = False assembly.visited = True return cycleFound
Version 4 also finds both cycles of DB3.
Hey guys,
Another approach:
All parts are assigned what's called an "assembly level." Level 0 is a raw part, level 1 is a simple assembly, and so on. The assigned assembly level for a part should always be higher, numerically, than any parts in its bill of materials.
So, query: if I just check that all constituent parts have a lower number than the part in consideration, will this prevent all possible cycles? I'm thinking it will.
I agree, your proposal will prevent cycles. A proof by induction seems readily available.
The only potential problem I see is if you later decide, for example, that a raw part is actually made of some other parts, so it needs to have its assembly level raised. Then you'll need to check all the assemblies that contain it, and possibly raise their levels too, which could be messy. But this probably wouldn't happen very often, or at all.
The existence of such a numbering scheme for a given database can easily be checked by topologically sorting the database. I'm not sure how one would detect "all" cycles in such a database doing a topological sort, however - I would have to actually code it...
It is certainly true that the database is cycle-free if and only if it is possible to assign numbers to the assemblies in such a way that the number assigned to an assembly is always greater than the number assigned to any of its components.So, query: if I just check that all constituent parts have a lower number than the part in consideration, will this prevent all possible cycles? I'm thinking it will.
(In essence this means that the database is cycle-free if and only if it can be mapped to a linear order of level-numbers by an order homomorphism: this idea of mapping the partial order "is a component of" to a linear order has already come up earlier in our discussion.)
We need to consider how having such numbers around (even though we don't need them for any other purpose than to keep the database cycle-free) impacts the basic operations:
1. Adding a new assembly having assemblies already in the database as components: To maintain the numbering scheme across this operation is trivial, since we can just assign the new assembly the largest number assigned to one of its components + 1.
2. Deleting a component from an existing assembly is also trivial to handle: just drop the component without adjusting the number assigned to the assembly thus modified. You might decide to do more work than that (by setting the level-number again to the maximum of the level-numbers of its components + 1, which would be advandageous for operation #3, below).
Since these first two operations cannot introduce cycles in a cycle-free database, having those level-numbers around didn't introduce much trouble maintaining them, but it also didn't provide any benefit at all.
Now for the one critical operation:
3. If existing assemblies are added as new components to an existing assembly, cycles may be created. Now, if we have those level-numbers around, we may be able to see, just by looking at the level-numbers that are currently assigned to the assembly about to be modified and all its components, that the modification does not introduce a cycle. So something like a depth-first search, rooted in that assembly, can be avoided.
However, it can also happen that a component gets added that has a higher level-number than the assembly to which it is to be added. In that case, the numbering scheme needs to be reorganized in a more fundamental way (as undefined has already indicated).
I think that in practical applications it is rather likely that a fundamental reorganization of the level-number assignment is not necessary even for the critical operation #3. So performance of this level-number assignment idea might be better on average than doing a complete cycle-testing by invocation of checkAssembly(assembly,[]) for the assembly about to be modified (on average, but maybe not in the worst case).
The question, as I see it, is about the complexity of the implementation. Again, one would have to actually code it to decide.
However, assigning the level-numbers to an entire database from scratch is surely going to require more effort than just checking the database for the existence of cycles.
Coding it is not really as bad as it seems, if we just reuse what we've already got. We can use the depth-first search to do the assigment of level numbers like this, I think:
Of course, if cycles have been found, the level-numbering of assemblies does not satisfy the condition that guarantees cycle-freeness of the database.Code:def renumberAssembly(assembly, stack): if assembly.marked: return [getCycle(assembly, stack)] cyclesFound = [] newLevel = -1 assembly.marked = True # assembly is on the stack stack.append(assembly) # should be stack.push(assembly), but it's Python... for component in assembly.components: if not component.visited: cyclesFound += renumberAssembly(component, stack) newLevel = max(newLevel, component.level) stack.pop() assembly.marked = False # assembly is no longer on the stack assembly.visited = True # depth-first search through assembly is complete assembly.level = newLevel + 1 return cyclesFound def renumberDb(db): cyclesFound = [] for assembly in db: if not assembly.visited: cyclesFound += renumberAssembly(assembly, []) for assembly in db: assembly.visited = False return cyclesFound
This version does not just print out the cycles but returns a list of cycles: because I always find functions that just dump out information to the console rather dubious in the first place. That's not what one wants to do anyway.
Warning: Version 5 attached is not really throughly tested. I just wanted to show how easy it is (or, rather, seems to me at the moment) to modify the existing version 4 to incorporate the assignment of level-numbers.
The advantage of having level numbers assigned is that in the case of the critical update operation #3 we can avoid actually invoking renumberAssembly(assembly, []) if the level of the assembly about to be modified is already greater than all the levels of its components, including the new ones.
  |
LinkBack URL
About LinkBacks
Typical mathematicians.
