[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: graphs and trees

• To: <xml-dev@l...>
• Subject: Re: graphs and trees
• From: "Thomas B. Passin" <tpassin@c...>
• Date: Sun, 10 Aug 2003 19:32:56 -0400
• References: <r02000000-1026-6A3ADE26CB7D11D7900C0003937A08C2@[192.168.124.11]>

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

Cheers,

Tom P

• References:
  • graphs and trees
    • From: "Simon St.Laurent" <simonstl@s...>

• Prev by Date: graphs and trees
• Next by Date: Re: Binary XML == "spawn of the devil" ?
• Previous by thread: graphs and trees
• Index(es):
  • Date
  • Thread