CODEWITHSUNDEEP
xmlgraphxml-serialization
Henrik P. Hessel
Henrik P. Hessel

Reputation: 36637

Serializing a dependency graph in XML

What would be your take on a xml file that contains certain elements, that reference n other elements. Background for this questions is a techtree (graph) serialized as a xml document. E.g. the tech "Cannons" prerequisite two other nodes (elements) "Iron" and "Gunpowder".

enter image description here Source: http://www.amazon.com/Programming-Game-Example-Mat-Buckland/dp/1556220782

Upvotes: 0

Views: 991

Answers (2)

forty-two
forty-two

Reputation: 12817

It's a directed graph. I'm sure there's lots of xml based representations for that, but graphml comes to mind:

<graphml>
<graph id="techtree" edgedefault="directed">
    <node id="gunpowder" />
    <node id="iron" />
    <node id="cannons" />
    <edge source="gunpowder" target="cannons" />
    <edge source="gunpowder" target="cannons" />
</graph>
</graphml>

Note that this is just from memory, there's probably loads of namespaces and other stuff needed.

Upvotes: 3

G_H
G_H

Reputation: 12019

By its very nature, XML introduces a tree structure into a document. If the relation between an element and its child nodes is considered to be an "allows you to create" definition, then you'll have a problem when you run into a situation where certain objects are referenced more than once. You'll end up having to specify them twice with no obvious way of telling they represent the same thing.

Let's take a look at the Iron from your example:

<iron>
    <cannons/>
    <guns/>
</iron>

No problem there, however, Wood will have...

<wood>
    <forge/>
    <arrows/>
    <guns/>
</wood>

The guns element appears here as well. The above representation is very simple, but maybe a lot more data will be associated with each element and you'll want to avoid repetition. You'll also get into trouble when your graph contains cycles, although I suppose that wouldn't be valid anyway given the semantics. Also note that wood is a direct requirement for guns, but guns also depend indirectly on wood via iron <- forge <- wood. This will become complicate to represent.

A number of things could be done. First of all, each element and the contained structure could be placed separately in the XML document, then referred in some way...

<guns itemId="1">
    <!-- embedded structure -->
</guns>
...
<iron>
    <item>1</item>
</iron>
<wood>
    <item>1</item>
</wood>

However, this leaves it up to you to programmatically resolve such references. The advantages of XML, being tools like parsers, XSLT and object binding, are partially lost.

Other options would be to link to elements via XLink, which seems like a natural fit here. Or use XInclude to define things only once, then include them in various places. Your "inlined" XML, with the inclusions resolved, will still have all the duplicate data. But at least it now no longer can become inconsistent.

But that's just one way of looking at it. Rather than trying to get the same directionality in the XML tree as in your graph, how about reversing things? Instead of an "allows you to create" relationship, you could make a "requires" relationship.

Going back to Iron:

<iron>
    <forge/>
</iron>

You'll now know that Iron requires a Forge. Guns:

<guns>
    <gunpowder/>
    <iron/>
    <wood/>
</guns>

But the problem remains the same: you can't just keep embedding one structure into the other, because at some point the same thing will be needed in more than one place. A Forge requires Wood, but so do Guns.

XML works for tree structures, but the moment your graph doesn't strictly adhere to such a structure, it becomes difficult to represent using XML. At least, difficult in the sense that you won't get any big advantages from it and will still need to program a lot yourself.

I don't know of any (de)serializable data representation that is a perfect fit for graphs of any kind. There's a software package called Graphviz which is intended specifically for graph rendering; it's open-source, so perhaps the documentation and/or code can deliver some good ideas.

Upvotes: 1

Related Questions