Proposal for Requiring Save/Restore of Sets and Tags

[Jason Kraftcheck]

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.

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.

> Finally, this definitely is outside either the subset/set member or
> parent-child relationships currently in the data model.
> 
> My understanding is that we set out to do two kinds of things with set
> relationships.
> 
> First, we wanted to be able to represent subsets. This our current data
> model does through adding sets to sets.  Whether those sets are subsets
> (with entities belonging to both) or members (with entity members of the
> subset not necessarily being entity members of the containing set) is up
> to the application to decide, and to handle appropriately afterwards.
> This has obvious applications in things like representing all entities
> that are a certain material (for instance) and the entities that are on
> the bdry of that material.
> 
> Second, we wanted to represent heirarchical relationships between
> collections of entities.  For example, a fine mesh in a multigrid
> heirarchy (stored in a set) would be the parent of a coarse mesh in that
> same heirarchy (another set).  Or an initial mesh in a refinement
> sequence (a set) would be the parent of a refined mesh in that same
> sequence (another set).  This usage corresponds to a directed graph.
> It's semantically plausible that there be more than one route from one
> node in the graph to another.  For instance, in multigrid
> semi-coarsening, one could have an initial fine mesh (A), two
> semi-coarsened meshes (in 2D; B_i and B_j), and fully coarsened mesh
> (C).  A is a parent of both B_i and B_j, and B_i and B_j are both
> parents of C.  This still isn't cyclic, of course.
> 
> Both of these relationships have, IMO, well-defined semantics that were
> agreed upon a long time ago.  (Maybe the "agreement" is overstated, but
> there's not been any objection to multiple write-ups of those semantics
> as I've stated them, which sounds like agreement to me.)  Both of these
> are also directed relationships and --- semantically --- acyclic.  As
> Mark M said, that's a tree.
> 
> And I still haven't seen anything that looks --- to me --- like a
> compelling use case for graphs of sets that are undirected and/or cyclic.
> 

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.

>> 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.

- jason