[Boost-users] Re: BGL: Topological Sort plus ordered out edges

From: Elisha Berns (e.berns_at_[hidden])
Date: 2005-04-03 01:29:58

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_at_[hidden]
tel. (310) 556 - 8332
fax (310) 556 - 2839