programmnig advise needed

Magnus Lycka lycka at carmen.se
Fri Jun 10 14:10:05 CEST 2005


mitsura at skynet.be wrote:
> Hi,
> 
> I am writing a Python program that needs to read XML files and contruct
> a tree object from the XML file (using wxTree).
> The XML however is not an hiearchical XML file. It contains <elements>
> and <association> tags. The <assiociation> tags link the elements
> together.

Are you sure that you get a tree? As I understand your description,
the XML format could well be used to describe arbitrary directed
graphs, even cyclic ones. This might not be a problem unless someone
tries to expand the entire tree...but you should probably have
some kind of cycle check, or disallow "expand all" in the GUI and
make sure you don't create the nodes before they are expanded.

If you really just permit trees, it's fairly simple, because a
node should just appear as a <Name> in an association once. You
can put those in a set, and check that they aren't already in the
set before you accept the content in a new association. Something
like the following semi-pseudo-code:

nodes = set()

for name, parent in associations:
     if name in nodes:
         raise KeyError, ("%s is already in the tree. "
            "Can't put it under %s." % (name, parent)
     nodes.add(name)
     whatever...

If you want to allow arbitrary directed acyclic graphs (DAGs),
you have to work a little more. E.g. if you want to allow things
like:

A
.B
..C
...D
...E
.F
..C
...D
...E

(I know that you said a tree, but I've certainly met clever and
well educated people before who called DAGs trees...)

For DAGs, you might traverse the tree to make sure there are
no cycles, but there are probably better solutions as well. As
I said, if it's really trees you want, this is not a problem.

Actually, another risk is that your document describes several
disjunct structures... Oh well, that's another issue, and you
can always argue how defensive your code needs to be. It obviously
depends on how well you trust your input and the implications
of problems. Anyway, assuming cycle checks, it's easy to find
roots: They are the keys in the dictionary that don't occur as
values. If there's just one, you just have one tree.

To summarize: If you want to describe a tree structure in XML,
it's probably a good idea to use the natural hierarchy of XML
tags to do this. That way the file can't convey a non-tree
structure. If you need to use a construct like you describe
in your XML, this suggests that you need to convey non-tree
structures, and then you probably need to handle those as well.



More information about the Python-list mailing list