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

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

В примере, предположите, что узел / идентификатор является типом xs:ID и что ссылка / касательно является типом 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>

Много средств разработки имеют поддержку идентификатора и IDREF также. Я использовал JAXB Java (Java Привязка XML. Это поддерживает их через @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]

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

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