На этом шаге мы приведем текст библиотеки и тестовые примеры, использующие перечисленные ранее функции.
Приведем текст библиотеки, содержащий описанные на предыдущем шаге функции.
Раскрыть/скрыть текст библиотеки.
-- Библиотека функций для работы с графами, представленными -- в виде списка рёбер (дуг). -- Список рёбер (дуг) моделируется списком пар -- -- [(x ,y ),(x ,y ),...,(x ,y )], -- 1 1 2 2 j j -- -- каждая из которых описывает дугу, соединяющую вершины -- x и y , x и y ,..., x и y . -- 1 1 2 2 j j -- -- Ребро (x,y) моделируется двумя дугами (x,y) и (y,x). -- Изолированная вершина x моделируется парой (x,"FALSE"). -- -- Автор программы (на языке LISP): М.В.Швецкий -- Переписано на язык Haskell: И.А.Кудрявцева (22.01.2010) ---------------------------------------------------------- module LibGrp_1 (addArc,listNode,neighb,neighb_1,deleteNode,addList,srchNode, delArc,istoks,stoks,memberList,oneRange,listSet,equalSet,str2num) where import Char ----------------------------------------------------------- -- Добавление дуги (x,y) в граф Graph, заданный списком дуг ------------------------------------------------------------------- addArc:: String -> String -> [(String,String)] -> [(String,String)] addArc x y graph | (memberList (x,y) graph) = graph | True = (x,y) : graph ----------------------------------------------------------- -- Построение списка, содержащего все вершины графа Graph, -- заданного списком рёбер (дуг) ---------------------------------------- listNode:: [(String,String)] -> [String] listNode graph | null graph = [] | True = listSet (oneRange graph) ---------------------------------------------------------- -- Построение списка вершин, смежных вершине x, в неориен- -- тированном графе Graph, заданном списком рёбер ------------------------------------------------- neighb:: String -> [(String,String)] -> [String] neighb x graph | null graph = [] | fst (head graph)==x && snd (head graph)=="FALSE" = [] | fst (head graph)==x = snd (head graph) : neighb x (tail graph) | snd (head graph)==x = fst (head graph) : neighb x (tail graph) | True = neighb x (tail graph) ------------------------------------------------------------ -- Построение списка вершин, смежных вершине x, в ориентиро- -- ванном графе Graph, заданном списком дуг -------------------------------------------------- neighb_1:: String -> [(String,String)] -> [String] neighb_1 x graph | null graph = [] | fst (head graph)==x && snd (head graph)=="FALSE" = [] | fst (head graph)==x = snd (head graph) : neighb_1 x (tail graph) | True = neighb_1 x (tail graph) ---------------------------------------------------------------- -- Удаление вершины x из графа Graph, заданного списком рёбер ------------------------------------------------------------- deleteNode:: String -> [(String,String)] -> [(String,String)] deleteNode x graph | null graph = [] | fst (head graph)==x || snd (head graph)==x = deleteNode x (tail graph) | True = head graph : deleteNode x (tail graph) ---------------------------------------------------------------- -- Добавление в граф Graph дуг, соединяющих вершину Node с -- вершинами, находящимися в списке LST ---------------------------------------------------- addList:: String -> [String] -> [(String,String)] -> [(String,String)] addList node lst graph | null lst = graph | True = addList node (tail lst) (addArc node (head lst) graph) ---------------------------------------------------------- -- Поиск в графе Graph, заданном списком рёбер, вершины, -- имеющей смежные вершины, содержащиеся в списке LST; -- NodeLST - список всех вершин графа Graph -------------------------------------------------------------- srchNode:: [String] -> [String] -> [(String,String)] -> String srchNode lst nodeLst graph | null lst = "" | equalSet (listSet (neighb (head nodeLst) graph)) lst = head nodeLst | True = srchNode lst (tail nodeLst) graph ------------------------------------------------------- -- Удаление дуги (x,y) из ориентированного графа Graph, -- заданного списком дуг. -- Исправлено: А.Ракитин (1 курс, фак. ИТ), 31.05.2006 ------------------------------------------------------------------- delArc:: String -> String -> [(String,String)] -> [(String,String)] delArc x y graph | null graph = [] | not (fst (head graph)==x && snd (head graph)==y) = head graph : delArc x y (tail graph) | (not (elem x (tail (istoks graph)) || elem x (tail (stoks graph)))) && (not (elem y (tail (istoks graph)) || elem y (tail (stoks graph)))) = (x,"FALSE"): (y,"FALSE"): delArc x y (tail graph) | (elem x (tail (istoks graph)) || elem x (tail (stoks graph))) && (not (elem y (tail (istoks graph)) || elem y (tail (stoks graph)))) = (y,"FALSE") : delArc x y (tail graph) | (not (elem x (tail (istoks graph)) || elem x (tail (stoks graph)))) && (elem y (tail (istoks graph)) || elem y (tail (stoks graph))) = (x,"FALSE") : delArc x y (tail graph) | True = delArc x y (tail graph) --------------------------------------------------------------- -- Функция возвращает список вершин-"источников" по графу Graph --------------------------------------------------------------- istoks:: [(String,String)] -> [String] istoks graph | null graph = [] | True = fst (head graph) : istoks (tail graph) ----------------------------------------------------------- -- Функция возвращает список вершин-"стоков" по графу Graph ----------------------------------------------------------- stoks:: [(String,String)] -> [String] stoks graph | null graph = [] | True = snd (head graph) : stoks (tail graph) ---------------------------------------------------------------- -- Вспомогательные функции библиотеки: ------------------------------------------------------------- -- Предикат, возвращающий T, если точечная пара Pair входит в -- список пар строк LST и NIL - в противном случае --------------------------------------------------------- memberList:: (String,String) -> [(String,String)] -> Bool memberList (x,y) lst | lst==[] = False | y=="FALSE" && not (assoc x lst (==)==[]) = True | [(x,y)]==assoc x lst (==) = True | True = memberList (x,y) (tail lst) ------------------------------------------------------------- -- Функция, выполняющая линейный поиск в ассоциативном списке -- alist пары, для которой при сравнении её fst-элемента с -- ключом key по тесту test признак не равен False. -- Если пара элементов, удовлетворяющая тесту, найдена, то -- возвращается список из этой пары; иначе - пустой список ---------------------------------------------------------- assoc:: String -> [(String,String)] -> (String -> String -> Bool) -> [(String,String)] assoc key alist test | null alist = [] | test (fst (head alist)) key = [head alist] | True = assoc key (tail alist) test --------------------------------------------------------------- -- Построение одноуровневого списка из списка пар строк ------------------------------------------------------- oneRange:: [(String,String)] -> [String] oneRange lst | null lst = [] | True = [fst (head lst),snd (head lst)] ++ oneRange (tail lst) ------------------------------------------------------- -- Преобразование одноуровневого списка LST в множество -- (удаление из списка повторяющихся элементов) ----------------------------------------------- listSet:: [String] -> [String] listSet lst | null lst = [] | elem (head lst) (tail lst) = listSet (tail lst) | True = head lst : listSet (tail lst) -------------------------------------------------------------- -- Предикат проверяет равенство двух одноуровневых списков без -- повторяющихся элементов LST1 и LST2 -------------------------------------- equalSet:: [String] -> [String] -> Bool equalSet lst1 lst2 | null lst1 = null lst2 | elem (head lst1) lst2 = equalSet (tail lst1) (filter ((head lst1)/=) lst2) | True = False --------------------------------------------------- -- Функция, преобразующая строку цифр в целое число --------------------------------------------------- str2num:: String -> Int str2num str | str=="" = error "Ошибка!" | head str=='-' = 0-sum (str2num1 (reverse (tail str)) ((length str)-1) 1) | True = sum (str2num1 (reverse str) (length str) 1) ----------------------------------------------------- str2num1:: String -> Int -> Int -> [Int] str2num1 str n m | n==1 = [(digitToInt (head str))*m] | True = (digitToInt (head str))*m : str2num1 (tail str) (n-1) (m*10)
Ряд тестовых примеров.
Раскрыть/скрыть текст примеров.
-- Неудачные тестовые примеры функций библиотеки LibGrp_1.hs -- по работе с графовой структурой данных ----------------------------------------- import LibGrp_1 test = testAddArc && testListNode && testNeighb && testNeighb_1 && testDeleteNode && testAddList && testSrchNode && testDelArc && testIstoks && testStoks && testMemberList && testOneRange && testListSet && testEqualSet && testStr2num --------------------------------------------------- testAddArc = addArc "3" "4" [] == [("3","4")] && addArc "3" "FALSE" [] == [("3","FALSE")] && addArc "3" "4" [("5","4"),("3","5"),("6","7")] == [("3","4"),("5","4"),("3","5"),("6","7")] && addArc "3" "4" [("5","4"),("3","4"),("6","7")] == [("5","4"),("3","4"),("6","7")] && addArc "3" "FALSE" [("1","2"),("3","4")] == [("1","2"),("3","4")] && addArc "3" "4" [("1","2"),("3","4")] == [("1","2"),("3","4")] && addArc "3" "6" [("3","5"),("3","6")] == [("3","5"),("3","6")] && addArc "4" "3" (addArc "3" "4" []) == [("4","3"),("3","4")] ----------------------------------------------- testListNode = listNode [("3","2"),("3","4")] == ["2","3","4"] && listNode [("1","2"),("5","4")] == ["1","2","5","4"] && listNode [("1","2"),("3","4"),("5","6")] == ["1","2","3","4","5","6"] --------------------------------------------------------- testNeighb = neighb "1" [("1","2"),("1","3"),("2","3"), ("5","FALSE")] == ["2","3"] && neighb "2" [("1","2"),("1","3"),("2","3"), ("5","FALSE")] == ["1","3"] && neighb "3" [("1","2"),("1","3"),("2","3"), ("5","FALSE")] == ["1","2"] && neighb "5" [("1","2"),("1","3"),("2","3"), ("5","FALSE")] == [] && neighb "1" [("1","1")] == ["1"] && neighb "1" [("1","1"),("1","3")] == ["1","3"] && neighb "1" [("1","2"),("2","1"),("1","3"), ("3","1"),("2","3"),("3","2"), ("5","FALSE")] == ["2","2","3","3"] && neighb "2" [("1","2"),("2","1"),("1","3"), ("3","1"),("2","3"),("3","2"), ("5","FALSE")] == ["1","1","3","3"] -------------------------------------------------------------- testNeighb_1 = neighb_1 "1" [("1","2"),("1","3"),("2","3"), ("5","FALSE")] == ["2","3"] && neighb_1 "2" [("1","2"),("1","3"),("2","3"), ("5","FALSE")] == ["3"] && neighb_1 "3" [("1","2"),("1","3"),("2","3"), ("5","FALSE")] == [] && neighb_1 "5" [("1","2"),("1","3"),("2","3"), ("5","FALSE")] == [] ------------------------------------------------------- testDeleteNode = deleteNode "2" [("3","1"),("3","2"), ("2","4")] == [("3","1")] && deleteNode "3" [("3","1"),("3","2"), ("2","3")] == [] ------------------------------------------------- testAddList = addList "3" ["5","6","7"] [("2","3"),("1","6"),("5","4")] == [("3","7"),("3","6"),("3","5"),("2","3"), ("1","6"),("5","4")] && addList "3" ["5","6","7"] [("3","5"),("3","6")] == [("3","7"),("3","5"),("3","6")] ----------------------------------------------------- testSrchNode = srchNode ["2","3"] ["1","2","3","4"] [("4","2"),("2","1"),("4","3")] == "4" && srchNode ["2","3"] ["1","2","3","4"] [("2","4"),("2","1"),("3","4")] == "4" && srchNode ["2","3"] ["1","2","3","4"] [("4","2"),("2","1"),("3","4")] == "4" && srchNode ["3","2"] ["1","2","3"] [("3","2"),("2","1"),("3","1")] == "1" ---------------------------------------------------------------- testDelArc = delArc "3" "4" [("1","2"),("3","4"),("4","3")] == [("1","2"),("4","3")] && delArc "3" "4" [("3","4")] == [("3","FALSE"),("4","FALSE")] && delArc "3" "4" [("3","4"),("3","1")] == [("4","FALSE"),("3","1")] && delArc "2" "1" [("2","1"),("2","3"),("3","1")] == [("2","3"),("3","1")] && delArc "2" "1" [("2","1"),("4","3"),("3","1")] == [("2","FALSE"),("4","3"),("3","1")] && delArc "2" "1" [("2","1"),("4","3"),("3","5")] == [("2","FALSE"),("1","FALSE"),("4","3"), ("3","5")] && delArc "2" "1" [("2","1"),("2","3"),("3","4")] == [("1","FALSE"),("2","3"),("3","4")] && delArc "2" "1" [("2","1")] == [("2","FALSE"),("1","FALSE")] && delArc "3" "5" [("2","1"),("3","4")] == [("2","1"),("3","4")] && delArc "2" "4" [("2","1"),("3","4")] == [("2","1"),("3","4")] && delArc "2" "3" [("2","FALSE")] == [("2","FALSE")] && delArc "1" "3" [("1","FALSE"),("2","FALSE"), ("3","FALSE")] == [("1","FALSE"),("2","FALSE"),("3","FALSE")] ---------------------------------------------------------------- testIstoks = istoks [("1","2"),("3","4"),("4","3")] == ["1","3","4"] && istoks [("1","1"),("2","2")] == ["1","2"] -------------------------------------------------------- testStoks = stoks [("1","2"),("3","4"),("4","3")] == ["2","4","3"] && istoks [("1","1"),("2","2")] == ["1","2"] -------------------------------------------------------- -- Неудачные тестовые примеры (вспомогательные функции): ----------------------------------------------------------- testMemberList = memberList ("3","2") [("1","2"),("3","2"), ("1","4")] == True && memberList ("3","2") [("2","3"),("3","3"), ("3","2")] == True ----------------------------------------------------------- testListSet = listSet ["1","1","1","1","2","2","2","2","3"] == ["1","2","3"] ---------------------------------------------------------------- testOneRange = oneRange [("1","2"),("4","5"),("2","1")] == ["1","2","4","5","2","1"] && oneRange [("1","2"),("1","2"),("1","2")] == ["1","2","1","2","1","2"] ------------------------------------------------------- testEqualSet = equalSet ["5","4","3","2","1"] ["3","1","2","4","5"] == True && equalSet ["5","4","3","2","1"] ["3","1","2","4"] == False -------------------------------------------------------- testStr2num = str2num "1" == 1 && str2num "-1" == -1 && str2num "12" == 12 && str2num "-12" == -12 && str2num "123456789" == 123456789 && str2num "-123456789" == -123456789 && str2num "2147483647" == 2147483647 && str2num "-2147483647" == -2147483647
На следующем шаге мы рассмотрим ассоциативный список инцидентности.
