LINUX.ORG.RU

XML - для дерева, для графа?


0

0

Добрый день.

XML используют для представления дерева, разбираемого регеспами. А что можно для разбора ими же использовать для построения графа? Есть готовая технология, или что-то академическое?

anonymous

Ответ на: комментарий от gaa

матрица - это математическая абстракция. некоторые матрицы, например Permutation matrix, вообще грех реализовывать в виде матриц :)

Pi ★★★★★
()
Ответ на: комментарий от Pi

>Incidence matrix - академичнее некуда

Про неё пишут, что она очень большая при большом количестве рёбер. Альтернативы нет? Как её представить в строке? В виде XML? Представление структуры меня волнует больше, так как её обрабатывать придётся именно на уровне представления.

anonymous
()

мысль: дерево -- это граф без циклов. То есть, граф -- это дерево + возможный цикл. То есть, если добавить в дерево ссылку, оно становится графом (как в файловой системе симлинки). То есть, хранить тот же XML, только с "симлинками"-циклами.

А так вообще ещё можно конечные автоматы (или кусочно-линейные) использовать.

anonymous
()
Ответ на: комментарий от anonymous

>мысль: дерево -- это граф без циклов. То есть, граф -- это дерево + возможный цикл. То есть, если добавить в дерево ссылку, оно становится графом (как в файловой системе симлинки). То есть, хранить тот же XML, только с "симлинками"-циклами.

Обрабатывать-то это как?

>А так вообще ещё можно конечные автоматы (или кусочно-линейные) использовать.

Регеспы и используют конечные автоматы, грех их не использовать, если возможно.

anonymous
()
Ответ на: комментарий от anonymous

>Обрабатывать-то это как?

как тот же XML. То есть, в любой XML, который представляет дерево (узлы дерева соответствуют остову графа) добавляем рёбра до полного графа (в XML добавляем атрибут, который представляет "цикл" (если атрибут указан -- цикл между вершинами). Получается произвольный граф с циклами.

Например, дерево в ФС без симлинков = дерево в XML. Дерево ФС+симлинки = граф = тот же XML + перечень "симлинков" (рёбер, после которых появляются циклы). "Симлинки" можно добавить опциональным атрибутом в узлы XML-дерева.

Например, строим минимальное дерево, остов.
http://www.intuit.ru/department/ds/discrmath/11/

Остов + ребро1 = цикл1. Цикл1+ребро2+..реброN = исходный граф.

То есть, строишь остов, запихиваешь в XML (Вида
<вершина id="i">
<соседняя id="j"/>
<соседняя id="k"/>
<соседняя id="l"/>
</вершина>
). Потом "добавляешь рёбра" до цикла:
<вершина id="j">
<соседняя id="i"/>
</вершина>

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

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.