Как бы вы представили график (вид, связанный с проблемой коммивояжера) в Haskell?

Question

Довольно просто представить дерево в haskell:

data Tree a = Node Tree a Tree | Leaf a

, но это потому, что ему не нужно понятие «указатель» императивного стиля, потому что у каждого узла / листа есть один и только одинродитель.Я думаю, я мог бы представить это как список списков Maybe Int s ... чтобы создать таблицу с Nothing для тех узлов без пути между и Just n для тех, которые делают ... но это кажется действительно уродливыми громоздкий.

Answer 1

Вы можете использовать такой тип, как

type Graph a = [Node a]
data Node a = Node a [Node a]

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

Answer 2

Отказ от ответственности: ниже приведено в основном бессмысленное упражнение в технике «завязывания узла».Fgl - это путь, если вы действительно хотите использовать свои графики.Однако, если вам интересно, как можно функционально представлять циклические структуры данных, читайте дальше.

Довольно просто представить граф в Haskell!

-- a directed graph

data Vertex a b = Vertex { vdata :: a, edges :: [Edge a b] }
data Edge   a b = Edge   { edata :: b, src :: Vertex a b, dst :: Vertex a b }

-- My graph, with vertices labeled with strings, and edges unlabeled

type Myvertex = Vertex String ()
type Myedge   = Edge   String ()

-- A couple of helpers for brevity

e :: Myvertex -> Myvertex -> Myedge
e = Edge ()

v :: String -> [Myedge] -> Myvertex
v = Vertex

-- This is a full 5-graph

mygraph5 = map vv [ "one", "two", "three", "four", "five" ] where
    vv s = let vk = v s (zipWith e (repeat vk) mygraph5) in vk

Это циклический, конечный, рекурсивная, чисто функциональная структура данных.Не очень эффективный или красивый, но смотрите, ма, никаких указателей!Вот упражнение: включите входящие ребра в вершину

data Vertex a b = Vertex {vdata::a, outedges::[Edge a b], inedges::[Edge a b]}

Легко построить полный граф, который имеет две (неразличимые) копии каждого ребра:

mygraph5 = map vv [ "one", "two", "three", "four", "five" ] where
    vv s = 
       let vks = repeat vk
           vk = v s (zipWith e vks mygraph5) 
                    (zipWith e mygraph5 vks)
       in vk

, но попробуйте построитьтот, у которого есть одна копия каждого!(Представьте, что в e v1 v2 участвуют дорогостоящие вычисления).

Answer 3

Самый простой способ - дать вершинам в графе уникальные имена (которые могут быть простыми, как Ints) и использовать либо обычную матрицу смежности, либо подходы со списком соседей, т. Е. Если имена Ints, либо использовать массив (Int , Int) Bool или массив Int [Int].

Answer 4

Методы завязывания узлов, которые обрисовали в общих чертах другие, могут работать, но это немного болезненно, особенно когда вы пытаетесь построить график на лету.Я думаю, что подход, который вы описываете, немного более практичен.Я бы использовал массив / вектор типов узлов, где каждый тип узла содержит список / массив / вектор соседей (в дополнение к любым другим необходимым данным), представленный в виде целых чисел соответствующего размера, где int - это индекс в узлемассив.Я, вероятно, не использовал бы Maybe Int s.С Int вы все равно можете использовать -1 или любое другое подходящее значение в качестве неинициализированного значения по умолчанию.После того, как вы заполнили все списки соседей и знаете, что они являются хорошими значениями, вам все равно не понадобится механизм отказа, предоставляемый Maybe, что, как вы заметили, накладывает накладные расходы и создает неудобства.Но ваш шаблон использования Maybe будет правильным, если вам нужно полностью использовать все возможные значения, которые может содержать тип указателя узла.

Answer 5

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

Также вы можете представить свой график с помощью матрицы смежности.

Или вы можете хранить карты между каждым узлом и входящими и исходящими ребрами.

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