CODEWITHSUNDEEP
xmlgraph
P basak
P basak

Reputation: 5004

Representing a graph in XML

Hi what will the best possible way to represent a graph in XML, where a node can be the child of a parent node and may be the parent of another child node. It can refer to itself, and multiple nodes can have same parent. And a node can have multiple parents. All nodes are from same class. I want to build it efficiently, so that if I can learn about a child node from a parent node I can go to the specific child tag without having to iterate all the nodes. Is it possible? for example here is an overview,

A->B,C,D

B->C,D

it may look like 

<Node name=A>
 <childNode name=B>
 <childNode name=C>
 <childNode name=D>
</Node>

<Node name=B>
 <childNode name=C>
 <childNode name=D>
</Node>

So are there any better approaches than this? Whenever I get a child from A i.e. B, than I will have to basically iterate through all Nodes and match there name attribute with B to find the Node that represents B. Can I somehow do it faster?

Upvotes: 2

Views: 10089

Answers (3)

Quang Van
Quang Van

Reputation: 12095

Take a look at RDF/XML.

RDF is a simple data model for the semantic web (linked-data) consisting of triples (Subject, Predicate, Object). It can represent graphs and is serializable in a number of formats including xml, json (json-ld) and turtle.

Upvotes: 0

Tony
Tony

Reputation: 10327

Since you have a graph, and not a tree as you first thought, why not use GraphML?

GraphML is a comprehensive and easy-to-use file format for graphs. It consists of a language core to describe the structural properties of a graph and a flexible extension mechanism to add application-specific data.

Unlike many other file formats for graphs, GraphML does not use a custom syntax. Instead, it is based on XML and hence ideally suited as a common denominator for all kinds of services generating, archiving, or processing graphs.

Upvotes: 8

S&#225;T
S&#225;T

Reputation: 3692

Well, I can't say I fully understand your problem, but I think you're trying to rebuild a (directed) graph in a high level language from an XML file, right? It'd help to know what kind of representation you have in the high level language. Or the language, actually. Assuming C++, and an adjacency list:

I'd first create a map<string, Node*>, mapping the names to the nodes. My XML would look like this:

<edge from='A' to='B' />
<edge from='A' to='C' />
<edge from='A' to='D' />
<edge from='B' to='C' />
<edge from='B' to='D' />

This is rather compact, and I can parse it with a SAX parser, which is always nice. As I read the edges sequentially, I check to see if I have the nodes in my map already: if not, I store them:

if(mapping.find(from) == map.end()) map.insert(make_pair(from, new Node()));
if(mapping.find(to) == map.end()) map.insert(make_pair(to, new Node()));

Once both end nodes are in the map, we can add the edge by:

mapping[from]->add_egde_to(mapping[to]);

Once the parsing is complete, you have the nodes in the map, nicely ordered by name.

Anyhow, you may want to look at Wikipedia's summary about graph representations, that may give you ideas.

Upvotes: 0

Related Questions