Proposal for Requiring Save/Restore of Sets and Tags

[Carl Ollivier-Gooch]

On 10/05/2010 04:41 AM, Tim Tautges wrote:
> With the current definition of set parent/child relations, you can embed
> not only directed graphs in the data model, but also general graphs. In
> this case you'd use only one of the parent/child types of links, and two
> nodes in the graph linked by an edge would each have a parent link to
> the other. Granted you'd need to be careful when traversing these,
> because of the inherent cycles, but at least you'd be able to represent
> them, in a part of the data model that is already fairly natural for
> many of the other queries on graph nodes, and for representing other
> types of (i.e. directed) graphs.
>
> As to what you'd use them for, choose any application of undirected
> graphs on a mesh, e.g. maximal independent set, graph coloring, etc.

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.

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.

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.

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

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