Tim's (putative) non-controversial issues with iRel 1 1 proposal

In my intent, the numbered statements below should be non-controversial and unambiguous. Thus, if there is any disagreement with any of the statements I've made, please point them out, and back them up with objective, not subjective, justification. The text in paragraphs following the numbered statements, if any, are my interpretations, and are of course subjective.

Also, the comments below apply to the whole of Seegyoung's modified iRel document, which is split up into 4 separate pages on this wiki. I haven't cited exactly where in that document the following things are stated; if you're wondering where I get something below, ask and I'll dig it up.

EntArr-based relations

1. EntArr-based relations incur a storage cost per model entity of O(N), where N is the number of mesh entities classified on that model entity. This is true because the entities on the EntArr side of a relation are passed back to the application in the form of a C-based array of entities, and by definition those arrays do not have state that the application can query. Thus, the only way to query relations from the mesh side is on individual entities. Furthermore, the retrieval cost for these relations is required to be O(1), which implies no searching.

  • Seegyoung: iRel_getEntEntArrRelation returns iBase_EntityIterator instead of extra c-array to
    - avoid extra memory allocation for temporary array in iRel
    - avoid invalidated entity handle in entity array during traversal due to entity addition/removal
    I don't think MOAB needs extra storage for the EntArr support on top of Set.

Contradiction 1

2. The document contradicts itself on whether entities on the Ent side of an Ent-EntArr relation are required to store relations. On the one hand, it is stated that the implementation is not guaranteed to store this information. On the other hand, queries from either side of the relation can be satisfied in O(1) time.

  • Seegyoung: In SCOREC S/W, reverse classification (model Ent to mesh EntArr) is not stored, instead we store only classification (mesh Ent to model Ent). This means we cannot support Ent-EntArr query in O(1) for reverse classification. I will correct the document if something still mismatch.

If the relation isn't stored on the Ent side, a search over entities on the EntArr side is required, which will have time complexity O(inf), where inf is the total number of mesh entities in the mesh database (assuming that's what's on the EntArr side).

Because applications cannot assume that these relations are stored on the Ent side, they need to assume the worst to avoid O(inf) scaling on every query from the Ent side of the relation. That will add a great deal of management responsibility on the application side, possibly (e.g. under mesh modification) amounting to a re-implementation of iRel in the application.

  • Seegyoung: Assuming all iRel implementation providers should support O(1) queries for all iRel_get* is absurd. For example, SCOREC chose not to store reverse classifications for some reasons but non-O(1) cost for reverse classification query doesn't cause trouble for applications since it's used rarely.

Proposed addition

3. The proposed addition to iRel will result in two non-interacting versions of an iRel interface, one that supports Ent, Both, and Set, and the other that supports Ent and EntArr.

By definition, EntArr-type relations cannot interact with Sets, and there is no functionality supported for switching between EntArr-based relations and other types. This will result in either non-interoperable solutions, or double the effort on the application side to work with iRel.

Adding (a, [l, m, n]) relation

4. In the discussion about adding the relation (a, [l, m, n]), another step must be added at the front, to check whether l is related to b, and removing it if so. Checking is guaranteed to be O(1); the cost of removing will depend on the implementation, but at best can be O(1) (because the implementation is not required to store the Ent->EntArr relation, there will be no cost for updating it).

Contradiction 2

5. There is a contradiction in what is returned when querying an Ent for the related EntArr. In one place it is stated that this communication is in the form of C arrays, which have no state, while in another it states that EntArr-based iterators are used (which do have state). Furthermore, these iterators are required to implement "no invalidation with entity removal" semantics. Since iRel does not have functions for deleting entities, this has the effect of either a) binding the implementation of iRel to that of iMesh, so that the iRel-based iterator can be updated upon entity deletion; or b) imposing extra constraints on the implementation of these iterators, such that they can be notified by the iMesh implementation when enities are deleted.

[Clarification: a subsequent read of Seegyoung's document seems to indicate that the iterators returned are implemented in the underlying interface (e.g. iMesh). But, as specified, iMesh does not have iterators over anything other than sets (with a special case of iterators over the root set). Thus, I don't see any way to support these iterators unless the underlying thing being iterated is an iMesh set, or unless we expand the functionality of an iterator.]

Classification/Reverse Classification use case

6. In the "Classification/Reverse Classification" use case, it is stated that the cost of constructing an iterator over the set of mesh entities classified on a model face is O(n). Strictly speaking, the cost is O(S(n)), or the cost of getting all entities in a set, which will vary by implementation. For example, in MOAB, this will be O(1), for both vector- and set-based sets. As stated, this seems to imply that querying the contents of a set in FMDB is always O(n). Similarly, for the use case as stated (but implemented using different calls to iRel), changing all of the entities classified on one model face to be classified on another model face will be O(S(n)), where S(n) is the complexity of querying or changing the total contents of a set. Again, the actual complexity depends on implementation; in MOAB, this will typically be O(1). Thus, the total cost for this use case, using v1.0 of iRel, will be 3*O(S(n)), assuming the cost of changing all contents is the same as retrieving all contents. For any
implementation using array-based sets, this will boil down to O(1).

Also, I will point out that for complexity analysis, strictly speaking, O(n) is the same as 3*O(n).

7. Again in the "Classification/Reverse Classification" use case, in the algorithm for v1.1, getting an iterator to reverse classification (i.e. to entities classified on a model entity) is not guaranteed to be O(1) (see point 2 above). If this operation is in fact O(1), and the setEntEntRelation in the WHILE loop of this use case is O(n) for the whole while loop, then there must be extra constraints on how relations are stored in the implementation. That is, I don't see a way to support both O(1) retrieval and O(1) deletion of individual entities from (whatever stores) the EntArr.

You might ask how MOAB can then do this operation with O(1) complexity; the answer is in how you describe the use case and its implementation. As stated, this use case describes classification of all faces on a different model face.

8. More detail is needed on the "Edge Swapping" use case. First of all, as stated, the longest edge is always swapped, which will be impossible if that edge bounds only one face classified on the model face. Next, the algorithm described for v1.0 is not credible; for example, you would not create a new classification set for every new edge resulting from swapping. Furthermore, it would be silly to call getEntEntRelation to get the classification of an edge, when by definition that edge is guaranteed to be classified on the model face you're iterating over. For some reason, those queries aren't required in the v1.1 algorithm.
  • Mark Beall: I think it would make sense to fix the use cases so that they are correct. Part of the reason they may be incorrect is that people don't understand what the proper iRel calls are and thus having the examples helps the documentation. For example, the edge classification should be checked at the top of the loop and skipped if the edge isn't classified on the model face.
9. The "Classification/Reverse Classification" and "Edge Swapping" use cases are redundant. In each, you're changing the classification of entities, either from one model entity to another, or by removing one and adding another. The iRel functions called in the v1.1 algorithms for both these use cases is the same.
  • Mark Beall: I think they are subtly different. In one case In the "Edge Swapping" use case the set of entities classified on the model face that I'm iterating over is changing while I'm iterating over it (some mesh faces are being deleted due to the swaps).