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

Question

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

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

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

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

Answer 1

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

• an adjacency list representation
• an adjacency matrix representation

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

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

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

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

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

Answer 2

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

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

Answer 3

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

Answer 4

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

Обычно отношения в 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 тоже. Я использовал JAXB (Java XML в Java Binding. Он поддерживает их через @XmlID и @XmlIDREF аннотации. Вы можете построить свой график, используя простые объекты Java, а затем использовать JAXB для обработки фактической сериализации XML.

Answer 6

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

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

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

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