Re: YAML declarativeness

If you'll recall, the original question was:

> Is it true that any arbitrary directed graph can be reduced to a set of
> trees and a set of links that only go from nodes back to their ancestors
> in those trees?

The YAML document you provide does not satisfy this property, because
your link is a child of C, the alias *d, but this reference is to a
child &d of B. So C has a link to a nephew/niece, not an ancestor!

As for the paragraph preceding the documents, I'm not sure what you
mean by "emit" etc., and I'm not sure how it resolves the dilemma, as
d is still not an ancestor of anybody (nor can it be).

Devin Jeanpierre

On Thu, Apr 29, 2010 at 9:09 PM, Oren Ben-Kiki <[email protected]> wrote:
> Interesting... but it I don't get it.
> It seems to me YAML can be used to serialize any cyclical structure,
> including the one you described:
>
> On Wed, 2010-02-10 at 01:00 -0500, Devin Jeanpierre wrote:
>> It is true for an undirected graph. It is not true for a directed
>> graph, unless the trees are allowed to not span as much of the graph
>> as they can. Supposing we want spanning trees, the following graph
>> works against us:
>>
>> a->b->d;a->c->d
>>
>> Our hand is forced in producing the first part of the spanning tree,
>> a->b; a->c . Either b or c can get d as a child, but at that point we
>> are forced to produce a cross edge that does not point to an ancestor,
>> but to the sibling's child.
>
> That's the part I don't get. You emit a->b first, then a->c second. Ok.
> You can now emit, say, b->d, and give an anchor to d. Now emit c->d, but
> use a reference to that anchor. What am I missing?
>
> You could also present it directly as a graph:
>
>  a:
>    data: ...
>    children:
>      b:
>        data: ...
>        children:
>          d: &d
>            data: ...
>            children: {}
>      c:
>        data: ...
>        children:
>          d: *d
>
> Or maybe (if you want to avoid repeating the name):
>
>  name: a
>  data : ...
>  children:
>    ? name: b
>      data: ...
>      children: &d
>        ? name: d
>          data: ...
>          children: {}
>    ? name: c
>      data: ...
>      children:
>        ? *d
>
> Or something along these lines.
>
> Have fun,
>
>    Oren Ben-Kiki
>
>
>

------------------------------------------------------------------------------