Comment sérialiser une structure graphique ?
https://stackoverflow.com/questions/51783
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Les fichiers plats et les bases de données relationnelles nous offrent un mécanisme pour sérialiser les données structurées.XML est idéal pour sérialiser des données arborescentes non structurées.
Mais de nombreux problèmes sont mieux représentés par des graphiques.Un programme de simulation thermique fonctionnera, par exemple, avec des nœuds de température connectés les uns aux autres via des bords résistifs.
Alors, quelle est la meilleure façon de sérialiser une structure graphique ?Je sais que XML peut, dans une certaine mesure, le faire --- de la même manière qu'une base de données relationnelle peut sérialiser un réseau complexe d'objets :cela fonctionne généralement mais peut facilement devenir moche.
Je connais le langage de points utilisé par le programme graphviz, mais je ne suis pas sûr que ce soit la meilleure façon de le faire.Cette question est probablement le genre de chose sur laquelle le monde universitaire pourrait travailler et j'aimerais avoir des références à des articles qui en discutent.
La solution
Comment représentez-vous votre graphique en mémoire?
En gros, vous avez deux (bonnes) options :
dans lequel la représentation de liste de contiguïté est mieux utilisée pour un graphe clairsemé et une représentation matricielle pour les graphes denses.
Si vous avez utilisé de telles représentations, vous pouvez plutôt sérialiser ces représentations.
Si ça doit être lisible par l'homme vous pouvez toujours opter pour la création de votre propre algorithme de sérialisation.Par exemple, vous pouvez écrire la représentation matricielle comme vous le feriez avec n'importe quelle matrice "normale":imprimez simplement les colonnes et les lignes, ainsi que toutes les données qu'elles contiennent, comme ceci :
1 2 3
1 #t #f #f
2 #f #f #t
3 #f #t #f
(il s'agit d'une représentation non optimisée et non pondérée, mais peut être utilisée pour des graphiques orientés)
Autres conseils
Généralement, les relations en XML sont représentées par la relation parent/enfant.XML peut gérer les données graphiques, mais pas de cette manière.Pour gérer des graphiques en XML, vous devez utiliser le xs:ID et xs : IDREF types de schéma.
Dans un exemple, supposons que node/@id est un type xs:ID et que link/@ref est un type xs:IDREF.Le XML suivant montre le cycle de trois nœuds 1 -> 2 -> 3 -> 1.
<data>
<node id="1">
<link ref="2"/>
</node>
<node id="2">
<link ref="3"/>
</node>
<node id="3">
<link ref="1"/>
</node>
</data>
De nombreux outils de développement prennent également en charge ID et IDREF.J'ai utilisé JAXB (Java XML Binding.Il les soutient à travers le @XmlID et le @XmlIDREF annotations.Vous pouvez créer votre graphique à l'aide d'objets Java simples, puis utiliser JAXB pour gérer la sérialisation réelle au format XML.
XML est très verbeux.Chaque fois que je le fais, je roule le mien.Voici un exemple de graphe acyclique dirigé à 3 nœuds.Il est assez compact et fait tout ce dont j'ai besoin :
0: foo
1: bar
2: bat
----
0 1
0 2
1 2
Un exemple que vous connaissez peut-être est la sérialisation Java.Cela sérialise efficacement par graphique, chaque instance d'objet étant un nœud et chaque référence étant un bord.L'algorithme utilisé est récursif, mais ignore les doublons.Le pseudo-code serait donc :
serialize(x):
done - a set of serialized objects
if(serialized(x, done)) then return
otherwise:
record properties of x
record x as serialized in done
for each neighbour/child of x: serialize(child)
Une autre méthode consiste bien sûr à créer une liste de nœuds et d'arêtes, qui peut être réalisée au format XML, ou dans tout autre format de sérialisation préféré, ou sous forme de matrice de contiguïté.
Les listes de contiguïté et les matrices de contiguïté sont les deux manières courantes de représenter des graphiques en mémoire.La première décision que vous devez prendre lorsque vous décidez entre ces deux est ce que vous souhaitez optimiser.Les listes de contiguïté sont très rapides si vous avez besoin, par exemple, d'obtenir la liste des voisins d'un sommet.D'un autre côté, si vous effectuez de nombreux tests sur l'existence des bords ou si vous disposez d'une représentation graphique d'une chaîne de Markov, vous préférerez probablement une matrice de contiguïté.
La prochaine question que vous devez considérer est de savoir quelle quantité de mémoire vous devez conserver.Dans la plupart des cas, lorsque le nombre d'arêtes dans le graphique est bien inférieur au nombre total d'arêtes possibles, une liste de contiguïté sera plus efficace, car il vous suffit de stocker les arêtes qui existent réellement.Un juste milieu consiste à représenter la matrice de contiguïté sous forme de lignes clairsemées compressées dans laquelle vous conservez un vecteur des entrées non nulles du coin supérieur gauche au coin inférieur droit, un vecteur correspondant indiquant dans quelles colonnes les entrées non nulles peuvent être trouvées, et un troisième vecteur indiquant le début de chaque ligne dans le vecteur d'entrée de colonne.
[[0.0, 0.0, 0.3, 0.1]
[0.1, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[0.5, 0.2, 0.0, 0.3]]
peut être représenté comme suit :
vals: [0.3, 0.1, 0.1, 0.5, 0.2, 0.3]
cols: [2, 3, 0, 0, 1, 4]
rows: [0, 2, null, 4]
La ligne clairsemée compressée est en fait une liste de contiguïté (les indices de colonne fonctionnent de la même manière), mais le format se prête un peu plus proprement aux opérations matricielles.
Sur une note moins académique et plus pratique, Test Cubique nous utilisons Xstream (Java) pour sérialiser les tests vers et depuis XML.Xstream gère les relations d'objet structurées sous forme de graphiques, vous pouvez donc apprendre une ou deux choses en regardant sa source et le fichier XML résultant.Vous avez raison à propos du laid Cependant, les fichiers XML générés ne sont pas jolis.
