2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Haskell. Представление графа.
Сообщение13.08.2015, 21:30 


16/12/14
472
Доброе время суток.

Задаваясь вопросом о графах, я не сумел найти адекватное представление оных для случая, когда имена вершин не имеют значения.
То есть, если работать с именами можно и нужно - то годится такой вариант:
Используется синтаксис 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)

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

 Профиль  
                  
 
 Re: Haskell. Представление графа.
Сообщение15.08.2015, 09:30 
Аватара пользователя


29/05/11
227
Красноармейск, Донецкая обл.
Как Вы определяете понятие графа у себя в голове?
Можно, скажем, задавать граф списком всех вершин и функцией, которая сопоставляет вершине смежные:
Используется синтаксис Haskell
data Graph a = Graph {
  vertices :: [a],
  neighbours :: a -> [a] -- или: Data.Map a [a]
}

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

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

 Профиль  
                  
 
 Re: Haskell. Представление графа.
Сообщение15.08.2015, 20:15 
Заслуженный участник


27/04/09
28128
Ну и несвязный граф деревом не представить. Да и работать с древесным представлением может быть удобно только в специфических случаях. :-)

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group