2014 dxdy logo

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

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




 
 Haskell. Определение графа.
Сообщение09.06.2015, 21:08 
В рамках свободного изучения Haskell, я добрался до создания типов данных, и мне подумалось попробовать определить, что такое граф самостоятельно. Прошу проверить мою идею.
Пусть A - тип данных, хранящийся внутри ячеек графа.
$Graf(A) =  Empty + Top(A) \\
Top(A) = A \times List(Top(A)) \\
Build = construcor \ Top(A) \\
into, ways = selectors \ Top(A) \\
isEmpty, isNonEmpty = predicates (A) \\
Empty, NonEmpty = parts(A) \\
$
Вроде бы тогда получается, что граф состоит из пустых ячеек и вершин. А вершины состоят из объектов типа А и списка вершин (в которые по моей задумке можно отправится из данной вершины). Функция $into$ позволяет узнать, что хранится внутри данной вершины, а функция $ways$ позволяет просмотреть список вершин, доступных к путешествию. Функции $Empty$ $NonEmpty$ позволяют понять пуста ли ячейка или нет. Вопрос в том, можно на основании такой структуры организовать граф? И стоит пробовать накидывать шаблонный модуль для функций, работающих с графом.

-- 09.06.2015, 21:28 --

sogoodweather
А зачем ребра? Я просто думал именно про это, ребра же нужны тогда когда мы храним в них какую-то информацию. А если в графе данные хранятся только в вершинах, то тогда не разумнее сделать примерно как в дереве? Ведь это упрощает жизнь, хотя конечно можно и так сказать (проблема в том, что я новичек в этом деле):
$
Graf (A) = Tops(A) + Ways() \\
Tops(A) = A \times List(Ways()) \\
Ways = Tops \times Tops $(я не совсем понимаю, что можно хранить в пути, что бы определяло его. По идее информацию о двух вершинах, которые он соединяет)

 
 
 
 Re: Haskell. Определение графа.
Сообщение10.06.2015, 02:28 
Pulseofmalstrem, а вы не могли бы функции нормально с типами вместе описать? И, раз речь о хаскеле, можно ведь было бы прямо код на нём и писать (или есть какая-то методическая причина?).

Если представлять граф как список вершин, каждая из которых сама является значением и списком вершин, то почему бы не просто написать
type Graph a = [Vertex a]
data Vertex a = Vertex { value :: a, linked :: [Vertex a] }

(или type Vertex a = (a, [Vertex a]), но…)
или, математически, $\mathrm{Graph}\,a = [\mathrm{Vertex}\,a]$, $\mathrm{Vertex}\,a = a\times[v]$, где $[a] = \mu\ell.\,1+a\times\ell$ считается известным. Зачем граф представлять суммой пустого и одной вершины, не понял.

Pulseofmalstrem в сообщении #1025406 писал(а):
Вопрос в том, можно на основании такой структуры организовать граф?
Некоторые алгоритмы такую структуру как раз любят, вроде бы. По крайней мере, самый обычный граф (не мультиграф, не взвешеный, не ещё какой-нибудь), как неор-, так и ор-, представим, т. к. тогда рёбра однозначно восстанавливаются по вершинам. Правда, сделать в таком представлении цикл — не на раз-два.

 
 
 [ Сообщений: 2 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group