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

This is indeed the issue and, I think, the reason we entertained other
proposals for locating the sml:acyclic constraint. 
 
My reasoning is as follows (and I'm no graph theorist):
 
- if the SML reference is not constrained to be acyclic, we have no
issue since we are not going to try to detect cycles.
 
- if the SML reference is acyclic, then we can construct the graph as
Sandy points out. Assuming that there is a cycle back to the 'starting
node', then this node will already be part of the graph because one of
the SML references points to it. If there is no cycle back to the
starting node, then the 'starting node' will not have a reference to it
and, therefore, will not be part of the graph. This is ok since, in this
case, there is no cycle that includes this node.
 
Having said that, what exactly is a 'starting node' in a cycle? Starting
from any of the nodes in a cycle produces the same cycle.
 
In fact, I maintain that we cannot accurately determine which node
'starts' the cycle since we can't tell which ancestor node of the '1st'
SML reference we look at would be the correct one to choose. That's why
the graph must first be created with arcs and then the nodes are
discovered and added. 
 
So, there is a difference between creating a graph that completely
describes all arcs/nodes in the model versus creating graphs for the
sole purpose of detecting cycles. I'm hoping that we only need to do the
latter.
 
--
ginny

________________________________

From: public-sml-request@w3.org [mailto:public-sml-request@w3.org] On
Behalf Of Sandy Gao
Sent: Monday, November 05, 2007 10:09 AM
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