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

We discussed this at length at the F2F but I don't recall reaching agreement. I think the critical piece we need to agree on regarding the "starting from" question relates to the definition of acyclicity, i.e. to know whether the path leads back to the starting point we need to know what that starting point is.  I think in the diagrams in the proposal this if clear - the starting node is the course, which in turn as a prerequisite, which is a course, etc. The possible confusion and difficulty is, I believe, defining this in XML terms. For example, is the starting point (node) the immediate parent of the reference element as in the course example? I don't know if this meets all flexibility requirements, but it is certainly the simplest solution.

Jim

________________________________
From: public-sml-request@w3.org [mailto:public-sml-request@w3.org] On Behalf Of Sandy Gao
Sent: Monday, November 05, 2007 1:09 PM
To: public-sml@w3.org
Subject: 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<http://www.w3.org/XML/Schema/>
Member, W3C SML WG<http://www.w3.org/XML/SML/>
(1-905) 413-3255 T/L 313-3255