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

Question

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

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

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

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

Answer 1

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

• представление списка смежности
• представление матрицы смежности

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

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

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

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

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

Answer 2

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

В примере предположим, что node / @ id является типом xs: ID, а ссылка / @ 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.

Answer 3

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

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

Answer 4

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

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

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

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

Answer 5

Один пример, который вам может быть знаком, - сериализация 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, или в любом другом предпочтительном формате сериализации, или как матрица смежности.

Answer 6

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