OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.


Help: OASIS Mailing Lists Help | MarkMail Help



   Re: [xml-dev] graphs and trees

[ Lists Home | Date Index | Thread Index ]

[Simon St.Laurent]
> (Tom Passin had it slightly easier, I think, as he was mostly moving from
> trees to graphs, but the shift was still noticeable.)

Yes, but it was really hard to re-create a pseudo-tree for display purposes,
once the graph was constructed.  Going into Extreme, I still had a bug in
that part that I have now been able to correct.

> Overall, my suspicion is that graph serialization is far more
> challenging than tree serialization, as the worst complication in tree
> serialization is the need to add (sometimes arbitrary) order to the
> parts of the tree which aren't considered ordered.

There are a lot of issues, partly because people have different purposes for
doing so.  Also, a graph can have different type of substructures.  Some of
them might be more-or-less hierarchical and some not.  For example, if you
have a graph that includes a taxonomy,  you will probably be able to pull
out a tree for the taxonomy part (assuming that the taxonomy really is a
tree!), because you can traverse down the class-subclass or whatever
relationships.  But other parts of the graph may not resemble hierarchies
that much, and you may have other reasons for serializing them.

> Graph serialization
> offers far more choices about different ways of representing connections
> as well as the general problem of unrolling circular connections into a
> straight-line sequence of bits.

Graph algorithms tend to "mark" each node as it is traversed.  This is well
and good, but finding a good starting point can be the hardest part.

For other purposes, getting the neighborhood around a node is more useful
that forcing the graph into a serialization or tree.  It just depends on
what you want to do.


Tom P


News | XML in Industry | Calendar | XML Registry
Marketplace | Resources | MyXML.org | Sponsors | Privacy Statement

Copyright 2001 XML.org. This site is hosted by OASIS