Proposal for Requiring Save/Restore of Sets and Tags

[Carl Ollivier-Gooch]

On 10/20/2010 06:43 AM, Jason Kraftcheck wrote:
> On 10/05/2010 10:35 AM, Carl Ollivier-Gooch wrote:
>
>> These are things that one generally creates from a (undirected cyclic)
>> graph of the individual entities (of a given type) in the mesh.  So the
>> only way I'm seeing a graph of sets here is if you create sets with
>> exactly one entity apiece and string them together into a graph.
>>
>
> While our current use of tests is limited to tree-like graphs (geometric
> topology, spatial subdivision trees, etc.) I'm hesitant to agree with the
> premise that it will never be a useful capability to be able to construct
> more general graphs of groups of entities.

It's possible that it's a useful capability, but it's semantically 
incompatible with either of the two mechanisms we currently have 
(subset/set membership and parent/child).  Semantically, the only way to 
have a cycle there is something as silly as set A is an improper subset 
of B is an improper subset of A --- with A and B necessarily identical 
sets.  Parent-child relationships can't semantically have cycles at all.

So anything that's got cycles will fail to have a set-theoretic meaning 
that's compatible with what we currently have in the data model. 
Allowing cycles would necessarily change the semantics of one of those 
two relationships, and I'm not prepared to do that because we -might- 
-someday- identify a use case for it.

> Of course, if one really wanted to construct graphs of iBase_EntityHandle
> type entities, thandle-type tags might be a better choice.  But it wouldn't
> use a lot more memory to use sets in MOAB.
>
>> I don't dispute that a general graph capability --- which isn't what our
>> current data model supports --- would support this.
>>
>> But why would anyone ever do this this way?  I mean, using iMesh sets to
>> represent this graph is going to super-expensive because of the overhead
>> of having a graph of -sets- instead of a graph of entities (unless
>> there's some ultra-light-weight way to represent sets that I can't
>> imagine).  And the traversal isn't going to be any easier than
>> representing the set in some other way, and is again going to be
>> significantly more expensive.  So you'll have to come up with some other
>> example to convince me there's a realistic use case here.
>>
>
> Well, as I said above, we do use sets for some graphs now.  It is actually
> much cheaper if one is creating graphs from groups of entities.  But our
> spatial search trees perform quite well constructed from sets and in that
> case the non-leaf nodes don't have any entities.  Our data model doesn't
> really have anything else suitable to use for such graph nodes.

Whether it's cheaper to use sets or some other, non-iMesh method to 
create the graph is going to depend heavily on the set implementation, I 
suspect.  I'm sure my implementation of sets would use more memory for 
this than a purpose-built ADT (and frankly I'm surprised it's possible 
to beat the purpose-built ADT with any set implementation).  Not saying 
that creating the graph this way is a bad thing, or that it doesn't make 
like easier for an app programmer...

> But there very well could be in the future.  We didn't imagine using sets
> for spatial search trees when initially considering the data model.

If and when a use case arises, we should discuss it then, IMO, rather 
than breaking well-defined semantics for a possibility.

>>> I agree that embedding these types of graphs into a data model that
>>> seems more geared to directed graphs is a stretch. But, in my view, we
>>> should keep the possibility of embedding general graphs in the data
>>> model, even if accessing those types of graphs is somewhat unnatural.
>>
>> If we're going to embed general graphs of entities in the data model,
>> let's do that, instead of distorting a set data model with well-defined
>> semantics to cover something it wasn't originally intended to (or at
>> least, that I don't recall us ever discussing as an original intent). If
>> nothing else, we can surely implement general graphs of entities in a
>> much lighter-weight way than general graphs of sets, because we lose the
>> set overhead.
>
> I don't have a strong opinion about this.  But I am adamantly opposed to
> requiring implementations to check for and refuse to create cyclic graphs.
> We do some stuff involving very large graphs (e.g. millions of sets).  The
> performance penalty would be significant.  And we already correctly handle
> cyclic graphs in queries.

My memory is that we had already agreed that an implementation is free 
to skip expensive (and even cheap) checks when compiled in release mode, 
though it should do all checks in debug mode.  The latter is very 
important to help developers debug code, but once it's working (i.e., 
nothing stupid being done by accident), a lot of those checks are 
unnecessary, so turning them off for release code is no problem. 
Conditionally-defined macros will do this.  As Mark said, there are 
run-time configurable methods for this, too, though I suspect they add a 
small amount of overhead in practice.

Carl

-- 
------------------------------------------------------------------------
Dr. Carl Ollivier-Gooch, P.Eng.                   Voice: +1-604-822-1854
Professor                                           Fax: +1-604-822-2403
Department of Mechanical Engineering             email: cfog at mech.ubc.ca
University of British Columbia              http://www.mech.ubc.ca/~cfog
Vancouver, BC  V6T 1Z4                  http://tetra.mech.ubc.ca/ANSLab/
------------------------------------------------------------------------