Haskell. Представление графа.

[Pulseofmalstrem]

Доброе время суток.

Задаваясь вопросом о графах, я не сумел найти адекватное представление оных для случая, когда имена вершин не имеют значения.
То есть, если работать с именами можно и нужно - то годится такой вариант:

Используется синтаксис Haskell

data Grath name vortex = Net [(name, vortex)] [([name], name)]

Когда граф - список пар имя-вершина и список всех возможных переходов и всех вершин (вместо списков можно использовать любые хранилища данных).
Однако иногда хочется, чтобы граф определялся как дерево (а не заменять имена на номера):

Используется синтаксис Haskell

data Tree a = Node a [Tree a]

То есть акцент делается на взаимосвязях, а имена опускаются. Но так не удобно работать с циклами (а они вообще вроде-бы так не представимы (поправьте если я не прав)). И вот тут возникает проблема.
Пока самое лучшее, что я смог придумать - выделение в графе элементарных циклов (внутри которых нет других циклов) и абстракция оных в единый элемент:

Используется синтаксис Haskell

data Grath a = Singleton a [Grath a] | Cycle Представление кругового списка над (Grath a) 

Однако и тут не все так гладко, так как идея сырая и возникает проблема с представлением элементарных циклов со смежными гранями.

[Mysterious Light]

Как Вы определяете понятие графа у себя в голове?
Можно, скажем, задавать граф списком всех вершин и функцией, которая сопоставляет вершине смежные:

Используется синтаксис Haskell

data Graph a = Graph {
  vertices :: [a],
  neighbours :: a -> [a] -- или: Data.Map a [a]
}

Если хочется исключить возможность маркировать вершины именами (т.е. снять ограничение Eq a), то придётся отказаться от функций вроде neighbours :: Graph a -> a -> [a], а как тогда работать с таким графом?

Кстати, о деревьях: дерево-как-граф допускает использование любой из своих $n$ вершин как корня, но все эти $n$ представлений будут различаться, если записывать их в соответствии с приведённым Вами типом.

[arseniiv]

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