On 10/21/2010 03:36 PM, Carl Ollivier-Gooch wrote:
I was referring to the case of requesting an -iterator- over faces that are also prisms. That's pretty clearly a malformed call. Retrieving the faces of a prism is equally clearly not.
And that is a request that an implementation cannot fulfill (sanely) regardless of whether or not the spec explicitly prohibits it.
Okay, I'll concede that one can construct a graph for which this test would be O(n) --- a graph that can be mapped onto a straight line.
Searching for cycles in a graph is O(n).
And for balanced trees, I guess the check is still O(log n), for total complexity of O(n log n). That still isn't great, but it's no worse than the complexity for constructing the tree itself.
And how do you verify that it is a tree as opposed to a more general graph in better than O(n)?
This isn't keeping interoperability. It is requiring implementations do interoperability checks for applications. If they want those checks then they can test with reference implementation.
Huh? If the spec says that X must happen, and all implementations but one do that, then an implementation that doesn't isn't interoperable with the others, in the sense that code written to exploit that feature of that implementation fails on the others. As you've all probably gathered, I'm in favor of narrowing down the possibilities of this sort of thing in the API; after all, we're advertising interoperability as a major selling point.
Yes, tautologically, if the spec mandates that implementations check this, then implementations are not conforming if they do not check it. However, your argument for adding this check is to ensure that all applications using the API do not use it in some way that not all implementations support. So what you're asking is that all implementations perform a very expensive check to do conformance testing for the application.
2. Change the current semantics, rendering the check irrelevant. If we're going to do this, we face the issue of supporting both directed and undirected graphs, presumably. Here the interoperability problem would be limited to a transition period when we have some implementations that don't fully support undirected and/or cyclic graphs. I think I could support cyclic directed graphs by removing a check. Undirected graphs could be really easy or could require significant re-write; I'm not sure without dissecting the code.
3. Don't mandate that implementations refuse to create cyclic graphs.
If this is made interoperable, in the sense of my last paragraph, how does it differ from 2 (leaving aside the directed/undirected issue)?
There are two separate issues. The first is whether or not to mandate the check. As I said way at the start of this thread: I am adamantly opposed to this because because the computational cost to great. The second is whether or not, if we do not mandate the check, which of the other two alternatives we choose: - implementations are allowed to chose between allowing cyclic graphs or returning an error code or the full-blown - all implementations must support cyclic graphs. I'd prefer the latter, but I am not in opposition to the former.
For what it's worth, I can imagine a use case for -undirected- cyclic graphs of sets of entities: lumped partitioning and related tasks. That's two changes in semantics, but we actually get a use case for our trouble this way.
Well, you could use the existing links for that. Just create parent links both ways and traverse only parent links. Of course, if you prohibit cycles then we need a different type of link. - jason