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

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

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

Иногда список всех ребёр оказывается в разы экономнее.

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

Семантические графы RDF вполне себе графы

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

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

А для операций над такими графами регеспов достаточно?

есть регекспы над XML деревьями, http://www.thaiopensource.com/trex/tutorial.html http://www.thaiopensource.com/trex/ http://xduce.sourceforge.net/papers.html

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

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

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

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

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

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

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

как тот же 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), конечно можно, но не совсем правильно. Матрицей инцидентности задать проще.

http://en.wikipedia.org/wiki/CDuce http://en.wikipedia.org/wiki/DOT_language