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

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

Hi,

I got off to a wrong start my posting my question(s) privately, so in
everyone's best interest, and certainly my own, I'm just reposting my
question here in the hope that someone can comment on how to go about
solving the following graph problem:

Basically, just to define the context of the question, I need to
construct the order in which XML elements need to be serialized to an
XML document by reading/analysing an XSD schema document.  The parent
child relationships in the XSD, inside the type and element definitions
give me the basic graph object that I need and after a topological sort
it gives the basic order of dependencies within the XSD; however, that
being said, the order of elements within individual type definitions
(and element definitions also) is lost.  For example, if some complex
content model has 3 children in a fixed order:

<ElementX>
        </A>
        </B>
        </C>
</ElementX>

the results from the topological sort can give the A B C out of order as
C B A.  So I need to add some information that expresses the fixed,
sequential order of the of the content model for whatever element
requires it (in XSD lingo it's a <sequence> particle for complex
content).

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)

Elisha Berns
e.berns_at_[hidden]
tel. (310) 556 - 8332
fax (310) 556 - 2839