Hi Again, Below (at the bottom) is the initial reply to my previously posted question on the matter of sorting the out edges of an XSD graph of element dependencies sent by Doug Gregor (and also from Jeremy Seik). I repost their response so everyone can be on the same page regarding what the big deal is: (Me) The problem with this solution is that it is easy to imagine a scenario in which the sub-elements, A B C, are also the children of some other type, ElementY, but in some other order: <ElementY> </C> </B> </A> </ElementY> And using the suggestion below will create a non-directed graph due to the bidirectional edges A->B and B->A or B->C and C->B :( And topological sort won't work when that's the case, as everybody knows. So the assumption that the elements A, B and C will always be found in the same order in an XSD content model, is, to say the least, a weak assumption that can only safely hold true for small, highly controlled schemas. But for large schemas, or schemas I have no control over, that reuse common elements in various orders, all bets are off when the suggested fix will break. So I am a wary of *just* creating extra edges as suggested. I would prefer a more complete solution whereby the edges: ElementY->A ElementY->B ElementY->C Can be ordered somehow using a property or modifying the topological sort algorithm to do this, but right now it's not clear to me where to start. So this is really my question here, how to properly solve this problem in a way that accommodates all possible orderings of the child elements. The only safe assumption is that the parent type (such a ElementX) is unique and that is what makes the edges to its children unique. And also, I'm not concerned about multiple occurrences of child elements (such as two elements of B under ElementX) since those edges can be counted and don't affect the working of the sort. Thanks for any help here, Elisha Berns (Greg) Okay, so we have dependencies in the graph that aren't strictly hierarchical. The easiest answer is to add edges A->B and B->C, because that would illustrate the true dependencies in the example.
And therein lies my question, how do I add to the edge data the information that signifies a fixed, sequential order among vertices, when required, that is not to be broken by the sort? For the example above the edges are:
ElementX -> A (1) ElementX -> B (2) ElementX -> C (3)
Unfortunately, I don't know of a good way to do this. topological_sort can only be based on the link structure of the graph. However, we might be able to be a little sneaky by putting the edges into the graph in the reverse order of the dependencies. So when enumerating the out_edges of ElementX, we want to get the edges for C, B, and A, in that order. Then when the depth_first_search instead topological_sort runs, it should give the right ordering. Doug Elisha Berns e.berns@computer.org tel. (310) 556 - 8332 fax (310) 556 - 2839