Re: YAML declarativeness

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.

But if the condition is relaxed, the description itself is just a set
of trees. You can build a tree for each edge in the graph, and you
just list all the edges to produce a forest of trees with the desired
property. I assume this is not what you meant.

Anyway, this isn't very interesting for the purpose of creating YAML
representations, either way you go it can be represented using YAML's
structures and aliases. To break YAMLs graphs, you'd need something
that needs to be referenced beforehand, but needs to reference what's
referencing it so that neither can exist before the other. Whenever
this happens it forms a cycle, which can be resolved by placing it in
the tree and producing a back edge with an alias. The easiest way to
produce this tree without problem is to create a depth-first spanning
tree (and the idea of such a tree is enough to dispel any notion of a
graph that cannot be represented in YAML), representing all non-tree
edges using aliases. If the graph is not (strongly) connected we may
have disconnected components at the end, which we can really just
place after, or do whatever with.

Devin Jeanpierre

On Tue, Feb 9, 2010 at 9:59 PM, William Spitzak <[email protected]> wrote:
> You are right I think. Nesting of lists into a tree can be used for
> forward references, while anchor/tag used for backward ones. I missed
> this because I was using anchor/tag for all connections.
>
> 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? I'm thinking this is true but not so sure of my graph
> theory.
>
> Clark C. Evans wrote:
>>
>> On Feb 8, 2010, at 13:36, William Spitzak <[email protected]> wrote:
>>
>>>
>>>
>>> Clark C. Evans wrote:
>>>> On Sun, 07 Feb 2010 16:48 +0100, "Roald de Vries" <[email protected]>
>>>> wrote:
>>>>> Why is this not allowed in YAML:
>>>>>
>>>>>     - *id001
>>>>> - &id001 some string
>>>> We had a requirement that YAML shouldn't require processors to load
>>>> the entire document before linking and returning the result.  If you
>>>> permitted this, it'd complicate or rule-out any sort of streaming.
>>>
>>> So yaml cannot be used to store an arbitrary directed graph (ie with a
>>> loop)? It is limited to only directed acyclic graphs?
>>
>> --- &cyclic
>> - *cyclic # graphs are permitted
>> ...
>>
>>
>>> PS: In our program we certainly are allowing forward references,
>>> despite the fact that the data is a DAG, as the order of the items in
>>> the list is being used for other purposes (the stacking order in the
>>> display). I am also preserving the anchor/tag values in our data,
>>> which is also against the yaml spec, though...
>>>
>
> ------------------------------------------------------------------------------
> SOLARIS 10 is the OS for Data Centers - provides features such as DTrace,
> Predictive Self Healing and Award Winning ZFS. Get Solaris 10 NOW
> http://p.sf.net/sfu/solaris-dev2dev
> _______________________________________________
> Yaml-core mailing list
> [email protected]
> https://lists.sourceforge.net/lists/listinfo/yaml-core
>

------------------------------------------------------------------------------
SOLARIS 10 is the OS for Data Centers - provides features such as DTrace,
Predictive Self Healing and Award Winning ZFS. Get Solaris 10 NOW
http://p.sf.net/sfu/solaris-dev2dev