Comment sérialiser une structure de graphe?

Question

Les fichiers plats et les bases de données relationnelles nous donnent un mécanisme pour sérialiser les données structurées. XML est superbe 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 à travers des bords résistifs.

Alors, quel est le meilleur moyen de sérialiser une structure de graphe? 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 web complexe d'objets: cela fonctionne habituellement mais peut facilement devenir laid.

Je connais la langue des points utilisée 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'adorerais avoir des références à des articles traitant de cela.

Answer 1

Comment représentez-vous votre graphique en mémoire?
Fondamentalement, vous avez deux (bonnes) Options:

• an adjacency list representation
• an adjacency matrix representation

dans lequel la représentation de la liste de contiguïté est préférable d'utiliser un graphique clairsemée et une représentation matricielle pour les graphiques denses .

Si vous utilisiez ces représentations, vous pouvez sérialiser ces représentations à la place.

Si cela doit être lisible par l'utilisateur, vous pouvez toujours choisir de créer votre propre algorithme de sérialisation.Par exemple, vous pouvez écrire sur la représentation matricielle comme vous le feriez avec une matrice « normale »: il suffit d'imprimer les colonnes et les lignes, et toutes les données comme si:

1 2 3 
1 #t #f #f 
2 #f #f #t 
3 #f #t #f 

(c'est un non représentation optimisée, non pondérée, mais peut être utilisée pour les graphes orientés)

Answer 2

XML est très verbeux. Chaque fois que je le fais, je roule le mien. Voici un exemple de graphe acyclique dirigé sur 3 nœuds. Il est assez compact et fait tout ce qu'il faut pour faire:

0: foo 
1: bar 
2: bat 
---- 
0 1 
0 2 
1 2 

Answer 3

Sur une note moins académique, plus pratique, nous utilisons CubicTestXstream (Java) pour sérialiser des tests et à partir de xml. Xstream gère les relations d'objet à structure graphique, de sorte que vous pourriez apprendre une chose ou deux en regardant sa source et le xml résultant. Vous avez raison à propos de la partie moche cependant, les fichiers XML générés ne sont pas beaux.

Answer 4

Un exemple que vous connaissez peut-être est la sérialisation Java. Ceci sérialise effectivement par le graphe, avec chaque instance d'objet étant un noeud, et chaque référence étant un bord. L'algorithme utilisé est récursif, mais ignore les doublons. Ainsi, le code pseudo serait:

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 façon est bien sûr que la liste des noeuds et des arêtes, ce qui peut être fait en XML, ou dans tout autre format de sérialisation préféré, ou comme une matrice de contiguïté.

Answer 5

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 les graphiques au format XML, vous devez utiliser les types de schéma xs:ID et xs:IDREF.

Dans un exemple, supposons que node/@ id est un type xs: ID et que link/@ ref est un type xs: IDREF. Le code 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 ont un soutien pour l'identification et IDREF aussi. Je l'ai utilisé JAXB Java (Java de XML Binding. Il prend en charge ces à travers les @XmlID et les @XmlIDREF annotations. Vous pouvez construire votre graphique en utilisant des objets Java simples et utiliser JAXB pour gérer la sérialisation réelle au format XML.

Answer 6

listes de contiguïté et contiguïté Les matrices sont les deux façons courantes de représenter les graphes en mémoire.La première décision à prendre lorsque vous choisissez entre ces deux éléments est ce que vous voulez optimiser.Les listes d'adjacences sont très rapides si vous devez, par exemple, obtenir la liste d'un D'un autre côté, si vous faites beaucoup de tests pour l'existence d'arêtes ou si vous avez une représentation graphique d'une chaîne markov, alors vous préférerez probablement une matrice d'adjacence

La question suivante d considérer est combien vous avez besoin pour entrer dans la mémoire. Dans la plupart des cas, lorsque le nombre d'arêtes dans le graphe est beaucoup plus petit que le nombre total d'arêtes possibles, une liste d'adjacence va être plus efficace, car il suffit de stocker les arêtes qui existent réellement. Un bon moyen est de représenter la matrice d'adjacence en format de lignes clairsemées compressées dans lequel vous gardez un vecteur des entrées non nulles de haut en bas à gauche, un vecteur correspondant indiquant les colonnes dans lesquelles 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é par:

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] 

rangée clairsemée comprimé est effectivement une liste d'adjacence (les indices de colonnes fonctionnent de la même manière), mais le format se prête un peu plus propre aux opérations de la matrice.