Proposal for Requiring Save/Restore of Sets and Tags

[Tim Tautges]

On 10/05/2010 08:15 AM, Mark Miller wrote:
> On Tue, 2010-10-05 at 04:41, 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.
>>
>> 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 you want to make an argument for general graphs, then why are the
> functions named 'Parent' and 'Child' -- which are much more suggestive
> of a very specific kind of graph, a tree in fact? Why not just name
> them...
>
> iMesh_addGraphEdge();
> iMesh_rmvGraphEdge();
> iMesh_getGraphOutEdges();
> iMesh_getGraphInEdges();
>

So, it's a balance between tailoring the data model and interface to the fully general case (or adding a different type 
of set relation to the data model), or fitting something that's a little outside the norm into the existing data model. 
  Since directed graphs are much more common, the data model conforms more to that usage.  The question is whether to 
restrict it to only that.  I'm arguing that we maybe shouldn't do that, unless we have a good reason.  I myself am on 
the fence about this, but lean towards wanting more generality if possible.

> Also, in general graphs, we tend to want/need to be able to associate
> data with vertices AND EDGEs of the graph. iMesh as designed can only do
> the vertex part of that (e.g. tags on sets).

Yeah, though you can accomplish this by representing the edge with a node in the graph.  This is basically what we're 
doing by using child sets to represent surfaces between volumes, linking them through parent/child relations.

>
> Next, I could be misunderstanding things but I don't think iMesh can
> support the concept of multiple graphs purposed for different types of
> traversals, can it (e.g. different collections of edges in the graph
> used for different purposes).
>

That's correct, though I don't know of any graph representations that can do this (without storing more information on 
the edges and filtering results of traversals).

> Finally, if a dataset contains a graph, we can't really avoid reading
> and instantiating that in the _load call and saving it in the _save call
> even if its unlikely any other client is going to know what to do with
> that data.
>

Sure, the semantics of graph traversal itself must be part of the data model; the use of that for whatever the 
application has in mind remains opaque.

> So, I think trying to make an argument general graphs, given the current
> design, is dubious at best.
>

Thus the being on the fence part, and the point of not wanting to add support for the more general case explicitly to 
the API.

- tim

> Mark
>
>
>
>>
>> - tim
>>
>> On 10/05/2010 12:56 AM, Carl Ollivier-Gooch wrote:
>>>
>>> To get a cycle, you've got to have this looping back on itself.
>>> Semantically, it makes sense, but it's (a) silly and (b) unlikely to
>>> occur except on purpose, in which case, why bother?
>>>
>>> Carl
>>>

-- 
================================================================
"You will keep in perfect peace him whose mind is
   steadfast, because he trusts in you."               Isaiah 26:3

              Tim Tautges            Argonne National Laboratory
          (tautges at mcs.anl.gov)      (telecommuting from UW-Madison)
          phone: (608) 263-8485      1500 Engineering Dr.
            fax: (608) 263-4499      Madison, WI 53706