Re: [Bug 4639] Allow cycle checking on element graphs as well as document graphs

Haven't had a chance to digest all the discussions around this issue. A 
quick question about Ginny's proposal below.

To define a graph, we need 4 things (there are other more normative graph 
theory definitions; "4" helps in this discussion)
- The set of all nodes
- The set of all arcs
- For a given arc, which node does it start from
- For a given arc, which node does it end at

> Consider a directed graph whose arcs are SML references of a given 
complexType
> (and any derived types)

Now we have all the arcs

> and whose nodes are the set of elements pointed to by
> any of these SML references.

Now we have all the nodes. This also implicitly answers the "ending at" 
node question.

What's left to answer is the "starting from" node for the arcs. How is it 
determined? Any node that contains the arc? What if there are more than 
one (e.g. both the parent and the grandparent are nodes)?

I think identifying the relationship between an arc and its starting node 
is the key issue here. This is also where proposals differ from one 
another.

Also note that because nodes are limited to only those being pointed to, 
then it's possible that there are arcs without a starting node. This is OK 
for our discussion around cyclicity, but would hurt graph theorists' brain 
cells.

Thanks,
Sandy Gao
XML Technologies, IBM Canada
Editor, W3C XML Schema WG
Member, W3C SML WG
(1-905) 413-3255 T/L 313-3255