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

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

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

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

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

Ответ 1

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

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

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

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

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

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

Ответ 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.

Ответ 3

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

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

Ответ 4

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

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

Ответ 5

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

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

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

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

Ответ 6

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