Référence à la hiérarchie des éléments XML

Question

Je suis à la recherche de représentations possibles pour ce qui peut être considéré comme un graphe de profondeur finie au format XML pour l'échange de données. Le point problématique est de savoir comment référencer les nœuds dans les balises de bordure. Deux stratégies que je vois sont a) utilisant des identifiants uniques ou b) utilisant des chemins.

ID uniques:

<graph id="g0"> 
    <node id="n0"/> 
    <node id="n1"/> 
    <edge from="n1" to="n0"/> 
</graph> 
<graph id="g1"> 
    <node id="n2"/> 
</graph> 
<edge from="n2" to="n1"/> 

chemins:

<graph id="0"> 
    <node id="0"/> 
    <node id="1"/> 
    <node id="2"/> 
    <edge from="1" to="0"/> 
    <edge from="2" to="1"/> 
</graph> 
<graph id="1"> 
    <node id="0"/> 
</graph> 
<edge from="1:0" to="0:2"/> 

Quelle est la procédure standard pour ce genre de choses? D'après ce que j'ai compris, l'approche de l'identificateur unique semble être plus répandue. Mon problème avec qui est quand les graphiques deviennent très grandes, il y a:

• nécessité d'une table de hachage vraiment grand que les cartes objets à leurs ID à des fins de lecture/écriture des bords de/vers des fichiers XML
• le fichier lui-même est plus grand que celui écrit en utilisant des chemins parce que vous ne pouvez pas omettre des composants de chemin redondants si le bord est interne au graphe.

Pensées?

Mise à jour 1:

Notez que ce ne est pas un graphique plat; ses un ou plusieurs graphiques interconnectés. Ils ont chacun des éléments indexés localement, mais les aplatir tous et garder une trace des bords à travers eux est un peu gênant.

mise à jour 1.1: Remarqué que des sous-graphes dans graphml, ils utilisent en effet les clés complexes qui permet de séparer ID nœud local de l'un mondial.

Mise à jour 2:

Oui, évidemment ce n'est pas un XML bien formé et les balises manquantes et toutes sortes de déclarations de schéma.

Answer 1

Il y a un schéma décrivant ce graphique: voir GraphML

Exemple:

<?xml version="1.0" encoding="UTF-8"?> 
<graphml xmlns="http://graphml.graphdrawing.org/xmlns" 
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" 
    xsi:schemaLocation="http://graphml.graphdrawing.org/xmlns 
    http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd"> 
    <graph id="G" edgedefault="undirected"> 
    <node id="n0"/> 
    <node id="n1"/> 
    <node id="n2"/> 
    <node id="n3"/> 
    <node id="n4"/> 
    <node id="n5"/> 
    <node id="n6"/> 
    <node id="n7"/> 
    <node id="n8"/> 
    <node id="n9"/> 
    <node id="n10"/> 
    <edge source="n0" target="n2"/> 
    <edge source="n1" target="n2"/> 
    <edge source="n2" target="n3"/> 
    <edge source="n3" target="n5"/> 
    <edge source="n3" target="n4"/> 
    <edge source="n4" target="n6"/> 
    <edge source="n6" target="n5"/> 
    <edge source="n5" target="n7"/> 
    <edge source="n6" target="n8"/> 
    <edge source="n8" target="n7"/> 
    <edge source="n8" target="n9"/> 
    <edge source="n8" target="n10"/> 
    </graph> 
</graphml> 

Answer 2

le fichier lui-même est plus grande que celle écrite en utilisant des chemins parce que vous ne pouvez pas omettez composants de chemin redondants si bord est interne au graphique.

Ce point est une optimisation prématurée. Les parseurs/rédacteurs XML ne vont pas s'étouffer avec les fichiers volumineux, et si la taille du stockage est un problème, XML se comprime généralement très bien avec ZIP.

nécessité d'une table de hachage vraiment grand que les cartes objets à leurs ID à des fins de lecture/écriture de bords/vers des fichiers XML

C'est une préoccupation de mise en œuvre.Vous pouvez certainement éviter d'avoir une grande table de hachage comme celle-ci si vous écrivez vos routines de lecture/écriture XML dans les classes de graphes, de nœuds et de bords elles-mêmes plutôt que d'essayer de maintenir le mappage dans une structure séparée. Les graphiques sont assez faciles à sérialiser et à désérialiser.

Les identifiants uniques sont probablement la voie à suivre. Si vous structurez les ID d'une manière similaire à la manière hiérarchique que vous avez proposée, elle sera également relativement lisible par l'homme, ce qui est l'un des objectifs de XML.