Como serializar uma estrutura gráfica?

StackOverflow https://stackoverflow.com/questions/51783

  •  09-06-2019
  •  | 
  •  

Pergunta

Arquivos simples e bancos de dados relacionais nos fornecem um mecanismo para serializar dados estruturados.XML é excelente para serializar dados não estruturados em forma de árvore.

Mas muitos problemas são melhor representados por gráficos.Um programa de simulação térmica irá, por exemplo, trabalhar com nós de temperatura conectados entre si através de arestas resistivas.

Então, qual é a melhor maneira de serializar uma estrutura gráfica?Eu sei que o XML pode, até certo ponto, fazer isso — da mesma forma que um banco de dados relacional pode serializar uma rede complexa de objetos:geralmente funciona, mas pode facilmente ficar feio.

Conheço a linguagem de pontos usada pelo programa Graphviz, mas não tenho certeza se essa é a melhor maneira de fazer isso.Esta questão é provavelmente o tipo de coisa em que a academia pode estar trabalhando e eu adoraria ter referências a quaisquer artigos que discutam isso.

Foi útil?

Solução

Como você representa seu gráfico na memória?
Basicamente você tem duas (boas) opções:

em que a representação da lista de adjacências é melhor usada para um grafo esparso e uma representação matricial para os grafos densos.

Se você usasse essas representações, poderia serializá-las.

Se tiver que ser legível por humanos você ainda pode optar por criar seu próprio algoritmo de serialização.Por exemplo, você poderia escrever a representação da matriz como faria com qualquer matriz "normal":basta imprimir as colunas e linhas e todos os dados contidos assim:

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

(esta é uma representação não otimizada e não ponderada, mas pode ser usada para gráficos direcionados)

Outras dicas

Normalmente, os relacionamentos em XML são mostrados pelo relacionamento pai/filho.XML pode lidar com dados gráficos, mas não dessa maneira.Para lidar com gráficos em XML você deve usar o xs:ID e xs:IDREF tipos de esquema.

Em um exemplo, suponha que node/@id seja um tipo xs:ID e que link/@ref seja um tipo xs:IDREF.O XML a seguir mostra o ciclo de três nós 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>

Muitas ferramentas de desenvolvimento também oferecem suporte para ID e IDREF.Eu usei o JAXB do Java (Java XML Binding.Ele os apoia através do @XmlID e a @XmlIDREF anotações.Você pode construir seu gráfico usando objetos Java simples e depois usar JAXB para lidar com a serialização real para XML.

XML é muito detalhado.Sempre que faço isso, eu faço o meu próprio.Aqui está um exemplo de um gráfico acíclico direcionado de 3 nós.É bastante compacto e faz tudo o que preciso:

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

Um exemplo que você deve estar familiarizado é a serialização Java.Isso serializa efetivamente por gráfico, com cada instância de objeto sendo um nó e cada referência sendo uma aresta.O algoritmo usado é recursivo, mas ignora duplicatas.Então o pseudocódigo seria:

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)

Outra forma, claro, é como uma lista de nós e arestas, que pode ser feita como XML, ou em qualquer outro formato de serialização preferido, ou como uma matriz de adjacência.

Listas de adjacências e matrizes de adjacência são as duas formas comuns de representar gráficos na memória.A primeira decisão que você precisa tomar ao decidir entre os dois é o que você deseja otimizar.As listas de adjacência são muito rápidas se você precisar, por exemplo, obter a lista dos vizinhos de um vértice.Por outro lado, se você estiver fazendo muitos testes para a existência de arestas ou tiver uma representação gráfica de uma cadeia de Markov, provavelmente preferirá uma matriz de adjacência.

A próxima questão que você precisa considerar é quanto você precisa caber na memória.Na maioria dos casos, onde o número de arestas no gráfico é muito menor que o número total de arestas possíveis, uma lista de adjacências será mais eficiente, pois você só precisa armazenar as arestas que realmente existem.Um meio termo é representar a matriz de adjacência em formato de linha esparsa compactada, no qual você mantém um vetor de entradas diferentes de zero do canto superior esquerdo para o canto inferior direito, um vetor correspondente indicando em quais colunas as entradas diferentes de zero podem ser encontradas e um terceiro vetor indicando o início de cada linha no vetor de entrada de coluna.

[[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]]

pode ser representado como:

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]

A linha esparsa compactada é efetivamente uma lista de adjacências (os índices das colunas funcionam da mesma maneira), mas o formato se presta de maneira um pouco mais limpa às operações de matriz.

Numa nota menos acadêmica e mais prática, em Teste Cúbico nós usamos Stream X (Java) para serializar testes de e para xml.O Xstream lida com relações de objetos estruturadas em grafos, então você pode aprender uma ou duas coisas olhando sua fonte e o xml resultante.Você está certo sobre o feio parte, porém, os arquivos xml gerados não parecem bonitos.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top