-- Вершина -> Граф в виде списка вершин -> Список исключаемых вершин ->
-- Результирующий список смежных вершин
leafs::Int->[Int]->[Int]->[Int]
leafs n g notE = [ x | x <- g, haveEdge x n, notElem x notE ]
Haskell - графы и деревья
Добрый день!
Вынужден обратиться за помощью к более опытным людям, чем я.
Haskell изучаю не так давно, кое что умею, но многое все равно пока остается непонятым...так вот. Есть две задачи, в решении которых мне нужна помощь:
1)
Неориентированный граф с конечным числом вершин представлен парой из количества вершин и функции типа Int -> Int -> Bool, которая выдает True, если аргументы представляют собой номера вершин, соединенных ребром. Функция заведомо коммутативная, то есть если вершина a связана с вершиной b, то и вершина b связана с вершиной a.
type Graph = (Int, Int -> Int -> Bool)
требуется написать функцию
point :: Int -> Graph -> Bool
Проверяет, является ли вершина с заданным номером точкой сочленения в графе.
видел алгоритм поиска точки сочленения на Си, но реализовать его на Хаскеле не получилось пока(
2)
Бесконечное двоичное дерево задано следующим описанием типа:
type Tree a = Node (Tree a) Int (Tree a).
Определить следующую функцию "индексации" дерева:
index :: Tree a -> Int -> Int -> a
index t i j = ...
которая выдает содержимое узла дерева с "координатами" [i, j], находя j-й узел на i-м уровне дерева. Уровни и узлы на каждом уровне нумеруются с нуля. В качестве тестового примера построить дерево, в узлах которого расположены все натуральные числа в порядке "естественного" обхода в ширину сверху вниз (и определить функцию для построения такого дерева).
В задаче требуется определить дополнительную функцию для решения следующих задач. Эта дополнительная функция может использовать функцию индексации, а может и нет, но функция индексации все равно должна в программе присутствовать.
addParent :: (Num a) => Tree a -> Tree a
Определить функцию, которая добавляет к значению каждого узла, кроме корня, значение, хранящееся в его непосредственном предке.
тут проблемы начинаются в самом начале, не знаю как создать такое дерево.
Очень надеюсь на Вашу помощь)
Вынужден обратиться за помощью к более опытным людям, чем я.
Haskell изучаю не так давно, кое что умею, но многое все равно пока остается непонятым...так вот. Есть две задачи, в решении которых мне нужна помощь:
1)
Неориентированный граф с конечным числом вершин представлен парой из количества вершин и функции типа Int -> Int -> Bool, которая выдает True, если аргументы представляют собой номера вершин, соединенных ребром. Функция заведомо коммутативная, то есть если вершина a связана с вершиной b, то и вершина b связана с вершиной a.
type Graph = (Int, Int -> Int -> Bool)
требуется написать функцию
point :: Int -> Graph -> Bool
Проверяет, является ли вершина с заданным номером точкой сочленения в графе.
видел алгоритм поиска точки сочленения на Си, но реализовать его на Хаскеле не получилось пока(
2)
Бесконечное двоичное дерево задано следующим описанием типа:
type Tree a = Node (Tree a) Int (Tree a).
Определить следующую функцию "индексации" дерева:
index :: Tree a -> Int -> Int -> a
index t i j = ...
которая выдает содержимое узла дерева с "координатами" [i, j], находя j-й узел на i-м уровне дерева. Уровни и узлы на каждом уровне нумеруются с нуля. В качестве тестового примера построить дерево, в узлах которого расположены все натуральные числа в порядке "естественного" обхода в ширину сверху вниз (и определить функцию для построения такого дерева).
В задаче требуется определить дополнительную функцию для решения следующих задач. Эта дополнительная функция может использовать функцию индексации, а может и нет, но функция индексации все равно должна в программе присутствовать.
addParent :: (Num a) => Tree a -> Tree a
Определить функцию, которая добавляет к значению каждого узла, кроме корня, значение, хранящееся в его непосредственном предке.
тут проблемы начинаются в самом начале, не знаю как создать такое дерево.
Очень надеюсь на Вашу помощь)
так, вторая задача решена.
с первой все ещё проблемы
с первой все ещё проблемы
Пусть определен список вершин listV::[Int] и предикат определяющий их
смежность haveEdge::Int->Int->Bool .
Исходя из этих условий построим вспомогательные функции.
Функция определения списка смежных вершин, мы добавим к ней еще
проверку на не вхождение вершины в заданных список. Это нам нужно
будет для реализации алгоритма поиска в глубину.
Тогда у нас получиться определить функцию проходящую по всем
вершинам графа и возвращающую список достигнутых вершин из
заданной (поиск в глубь).
В vis у нас будут храниться посещенные вершины, что бы не пробегать по
ним несколько раз. foldr осуществляет свертку по смежным вершинам с
рекурсивным вызовом поиска. В g список вершин на которых происходит
поиск.
Еще один момент. Корень должен иметь как минимум двух потомков что бы
быть точкой сочленения.
То есть в начале для точки проверяем есть ли у нее хотя бы 2 смежных
вершины, если нет, то это точка сочленения. Если есть, то строим список
listV2 (без искомой точки) и запускаем на нем dfs с произвольной точки.
Если мы получаем на выходе не связный граф - длина списка меньше
заданного (listV2) то искомая точка - точка сочленения.
Опять таки это если исходный граф связный. Для не связного графа
определение точки сочленения будет отличаться. Да и код конечно
корявенький.
Если б у вас можно было определить свои структуры данных описывающие
граф, то можно было б посомтреть как реализовано dfs в исходниках
самого Haskell`а (packages/base/Data/Graph.hs) или ознакомиться с статьей
Structuring Depth-First
Search Algorithms in Haskell.
смежность haveEdge::Int->Int->Bool .
Исходя из этих условий построим вспомогательные функции.
Функция определения списка смежных вершин, мы добавим к ней еще
проверку на не вхождение вершины в заданных список. Это нам нужно
будет для реализации алгоритма поиска в глубину.
Код:
Тогда у нас получиться определить функцию проходящую по всем
вершинам графа и возвращающую список достигнутых вершин из
заданной (поиск в глубь).
Код:
dfs::[Int]->Int->[Int]->[Int]
dfs g i vis = if (elem i vis) then vis
else case adj of
[] -> (i:vis)
_ -> foldr (dfs g) (i:vis) adj
where adj = leafs i g vis
dfs g i vis = if (elem i vis) then vis
else case adj of
[] -> (i:vis)
_ -> foldr (dfs g) (i:vis) adj
where adj = leafs i g vis
В vis у нас будут храниться посещенные вершины, что бы не пробегать по
ним несколько раз. foldr осуществляет свертку по смежным вершинам с
рекурсивным вызовом поиска. В g список вершин на которых происходит
поиск.
Еще один момент. Корень должен иметь как минимум двух потомков что бы
быть точкой сочленения.
То есть в начале для точки проверяем есть ли у нее хотя бы 2 смежных
вершины, если нет, то это точка сочленения. Если есть, то строим список
listV2 (без искомой точки) и запускаем на нем dfs с произвольной точки.
Если мы получаем на выходе не связный граф - длина списка меньше
заданного (listV2) то искомая точка - точка сочленения.
Код:
point x = if (length (leafs x listV []) < 2) then True
else ( (length (bfs listV2 x [])) == (length listV2))
where listV2 = [n | n <- listV, n /= x]
else ( (length (bfs listV2 x [])) == (length listV2))
where listV2 = [n | n <- listV, n /= x]
Опять таки это если исходный граф связный. Для не связного графа
определение точки сочленения будет отличаться. Да и код конечно
корявенький.
Если б у вас можно было определить свои структуры данных описывающие
граф, то можно было б посомтреть как реализовано dfs в исходниках
самого Haskell`а (packages/base/Data/Graph.hs) или ознакомиться с статьей
Structuring Depth-First
Search Algorithms in Haskell.
Я буду благодарна за помощь, если кто-то сможет написать решение данной задачи!
Условие следующее:
Нужно написать на хаскеле приложение - для двух вершин А и В найти все пути между ними, которые не пересекаются(пути не должны иметь общих вершин, кроме концов А и В). Заранее большое спасибо за решение! И ,будьте добры, написать комментарии к задаче и оператором. Мы начали изучать его буквально недавно, многие еще неизвестно.
Буду ждать ответа.
Условие следующее:
Нужно написать на хаскеле приложение - для двух вершин А и В найти все пути между ними, которые не пересекаются(пути не должны иметь общих вершин, кроме концов А и В). Заранее большое спасибо за решение! И ,будьте добры, написать комментарии к задаче и оператором. Мы начали изучать его буквально недавно, многие еще неизвестно.
Буду ждать ответа.