Как сериализовать структуру графа?

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

  •  09-06-2019
  •  | 
  •  

Вопрос

Плоские файлы и реляционные базы данных предоставляют нам механизм сериализации структурированных данных.XML превосходно подходит для сериализации неструктурированных древовидных данных.

Но многие проблемы лучше всего изображаются с помощью графиков.Например, программа теплового моделирования будет работать с температурными узлами, соединенными друг с другом через резистивные края.

Так как же лучше всего сериализовать структуру графа?Я знаю, что XML может в некоторой степени это сделать — точно так же, как реляционная база данных может сериализовать сложную сеть объектов:обычно это работает, но может легко стать некрасивым.

Я знаю о точечном языке, используемом программой Graphviz, но не уверен, что это лучший способ сделать это.Вероятно, над этим вопросом работают научные круги, и мне бы хотелось получить ссылки на любые статьи, обсуждающие этот вопрос.

Это было полезно?

Решение

Как вы представляете свой график в памяти?
По сути, у вас есть два (хороших) варианта:

в котором представление списка смежности лучше всего использовать для разреженного графа и матричное представление для плотных графов.

Если вы использовали такие представления, вы могли бы вместо этого сериализовать эти представления.

Если это должно быть человек читаемый вы все равно можете выбрать создание собственного алгоритма сериализации.Например, вы можете записать представление матрицы, как если бы вы делали это с любой «обычной» матрицей:просто распечатайте столбцы и строки и все данные в них следующим образом:

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

(это неоптимизированное, невзвешенное представление, но его можно использовать для ориентированных графов)

Другие советы

Обычно отношения в XML отображаются как отношения родитель/потомок.XML может обрабатывать данные графа, но не таким образом.Для обработки графиков в XML вам следует использовать хз:ИД и хз:ИДРЕФ типы схем.

В качестве примера предположим, что node/@id — это тип xs:ID, а link/@ref — это тип xs:IDREF.Следующий XML показывает цикл из трех узлов 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>

Многие инструменты разработки также поддерживают ID и IDREF.Я использовал Java JAXB (Java XML Binding.Он поддерживает их посредством @XmlID и @XmlIDREF аннотации.Вы можете построить свой график, используя простые объекты Java, а затем использовать JAXB для фактической сериализации в XML.

XML очень многословен.Всякий раз, когда я это делаю, я катаюсь сам.Вот пример ориентированного ациклического графа с 3 узлами.Он довольно компактен и делает все, что мне нужно:

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

Одним из примеров, который вам, возможно, знаком, является сериализация Java.Это эффективно сериализуется по графу, где каждый экземпляр объекта является узлом, а каждая ссылка — ребром.Используемый алгоритм является рекурсивным, но пропускает дубликаты.Таким образом, псевдокод будет:

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)

Другой способ, конечно, — это список узлов и ребер, который может быть выполнен в формате XML, в любом другом предпочтительном формате сериализации или в виде матрицы смежности.

Списки смежности и матрицы смежности — два распространенных способа представления графов в памяти.Первое решение, которое вам нужно принять при выборе между этими двумя, — это то, для чего вы хотите оптимизировать.Списки смежности работают очень быстро, если вам нужно, например, получить список соседей вершины.С другой стороны, если вы проводите много проверок на наличие ребер или имеете графическое представление цепи Маркова, то вы, вероятно, отдадите предпочтение матрице смежности.

Следующий вопрос, который вам нужно рассмотреть, — это то, сколько вам нужно уместить в памяти.В большинстве случаев, когда количество ребер в графе намного меньше общего числа возможных ребер, список смежности будет более эффективным, поскольку вам нужно хранить только те ребра, которые действительно существуют.Счастливой серединой является представление матрицы смежности в формате сжатых разреженных строк, в котором вы сохраняете вектор ненулевых записей сверху слева вниз справа, соответствующий вектор, указывающий, в каких столбцах можно найти ненулевые записи, и третий вектор, указывающий начало каждой строки в векторе входа в столбец.

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

можно представить как:

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]

Сжатая разреженная строка фактически представляет собой список смежности (индексы столбцов функционируют таким же образом), но этот формат немного более удобен для матричных операций.

На менее академической, но более практической ноте, в КубикТест мы используем Xstream (Java) для сериализации тестов в XML и обратно.Xstream обрабатывает объектные отношения, структурированные в виде графа, поэтому вы можете кое-что узнать, просматривая его исходный код и полученный XML-код.Вы правы насчет уродливый Однако сгенерированные XML-файлы выглядят некрасиво.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top