Найти расстояние в графах между узлами

Question

Я получил список в моей руке такой:

[(1,2),(1,4),(2,4),(3,9),(4,7),(7,9)] 

Я должен реализовать функцию, которая принимает: а список существующих отношений, а пар новых REALITON , a расстояние n.

Функция должна работать следующим образом: она принимает все параметры, вычисляет расстояние между узлами, которое задано в новом соотношении, если расстояние < = до расстояния n, функция возвращает список, включая новое отношение.

напр:

list = [(1,2),(1,4),(2,4),(3,9),(4,7),(7,9)] 

new_relation = [(1,3)] 

distance_n = 4 

Она возвращает [(1,2), (1,3), (1,4), (2,4), (3,9), (4,7), (7,9)]

Если расстояние было 3 было бы вернуть первоначальный список

[(1,2),(1,4),(2,4),(3,9),(4,7),(7,9)] 

Как я могу это сделать? У меня проблемы с графиками. Примечание: оно должно быть реализовано в Haskell.

Answer 1

Как всегда в Haskell, мы начинаем с объявления наших типов. Вот я просто хочу сказать, что Graph список Edge с, и Edge является кортежем Node с, которые только Int s

type Node = Int 
type Edge = (Int, Int) 
type Graph = [Edge] 

Тогда мы можем объявить наши функции типов. Во-первых, мы имеем функцию, которая решает конкретную проблему,

addNode :: Graph -> Edge -> Int -> Graph 
addNode graph newEdge maxDistance = undefined 

Но мы знаем из постановки задачи, что мы собираемся нужен помощник, а именно функцию, которая вычисляет расстояние между двумя узлами (которые могут быть определены, если узлы не подключены). Так как это не всегда имеет действительное значение для возвращения, мы будем обернуть его в Maybe и вернуть Nothing когда узлы не подключены

distance :: Graph -> Node -> Node -> Maybe Int 
distance graph fromNode toNode = undefined 

С этой вспомогательной функцией, теперь мы можем реализовать addNode довольно просто

addNode graph newEdge@(fromNode, toNode) maxDistance = 
    case distance graph fromNode toNode of 
     Nothing -> graph 
     Just d -> 
      if d <= maxDistance 
       then newEdge : graph 
       else graph 

Но похоже, что вы хотите сохранить график сортируется, так что если вы импортируете Data.List вы можете просто бросить в sort

addNode graph newEdge@(fromNode, toNode) maxDistance = 
    case distance graph fromNode toNode of 
     Nothing -> graph 
     Just d -> 
      if d <= maxDistance 
       then sort $ newEdge : graph 
       else graph 

Теперь все, что вам нужно сделать, это реализовать distance, и все будет готово.

Answer 2

У обоих the containers package и the graphs package есть похожие списки, похожие на ваши.

A Very General Method of Computing Shortest Paths содержит функциональную реализацию алгоритма Джикстры для нахождения расстояний на графе, но он работает на матрице смежности. Либо сделайте изменение представления, либо измените алгоритм работы над списками смежности.

Как только у вас есть функция distance :: Graph -> Vertex -> Vertex -> Distance, а функция addEdge :: Edge -> Graph -> Graph, вы золотые. addEdge должно быть относительно легко писать независимо от представления, но в целом добавление ребра означает, что вам нужно отбрасывать любые предыдущие, кэшированные вычисления расстояния.