На этом шаге мы приведем текст библиотеки и тестовые примеры, использующие перечисленные ранее функции.
Приведем текст библиотеки, содержащий описанные на предыдущем шаге функции.
Раскрыть/скрыть текст библиотеки.
-- Библиотека для работы с графами, представленными ассо- -- циативными списками смежности. -- Ассоциативные списки смежности моделируются ассоциати- -- вным списком точечных пар следующего вида: -- -- [(A ,[x ,x ,...,x ]),...,(A ,[y ,y ,...,y ])], -- 1 1 2 k n 1 2 j -- -- каждая из которых описывает дугу, соединяющую вершины -- -- A и x , A и x ,..., A и x ,..., -- 1 1 1 2 1 k -- -- A и y , A и y ,..., A и y . -- n 1 n 2 n j -- -- Автор программы (на языке LISP): М.В.Швецкий -- Переписано на язык Haskell: И.А.Кудрявцева (28.01.2010) ---------------------------------------------------------- module LibGrp_2 (pairLis,reKey,reData,assoc1,rAssoc,putAssoc1,addArc, deleteNode,deleteArc,walk,neighb2,oneRange,listSet,assoc) where import List ----------------------------------------------------------- -- Построение графа из списка вершин KEY и списка списков -- смежных вершин DATA с помощью добавления к существующему -- графу Graph -------------------------------------------------------------- pairLis:: [Integer] -> [[Integer]] -> [(Integer,[Integer])] -> [(Integer,[Integer])] pairLis key dta graph | null key = graph | null dta = graph | elem (head key) (reKey graph) = pairLis (tail key) (tail dta) (putAssoc1 (head key) (listSet (head dta ++ (assoc1 (head key) graph))) graph) | True = (head key,head dta) : pairLis (tail key) (tail dta) graph ----------------------------------------------------- -- Восстановление списка вершин графа Graph из -- ассоциативного списка инцидентности ------------------------------------------ reKey:: [(Integer,[Integer])] -> [Integer] reKey graph | null graph = [] | True = fst (head graph) : reKey (tail graph) ---------------------------------------------------------------- -- Восстановление списка списков смежных вершин графа -- Graph из ассоциативного списка инцидентности -------------------------------------------------- reData:: [(Integer,[Integer])] -> [[Integer]] reData graph | null graph = [] | True = snd (head graph) : reData (tail graph) ----------------------------------------------------------- -- Функция возвращает список вершин графа Graph, содержащий -- вершины, смежные вершине Node ------------------------------------------------------ assoc1:: Integer -> [(Integer,[Integer])] -> [Integer] assoc1 node graph | null graph = [] | fst (head graph)==node = snd (head graph) | True = assoc1 node (tail graph) ------------------------------------------------------------ -- Функция возвращает список из вершины графа Graph, имеющей -- заданный список смежных вершин LST -------------------------------------------------------- rAssoc:: [Integer] -> [(Integer,[Integer])] -> [Integer] rAssoc lst graph | null graph = [] | sort (snd (head graph))==sort lst = [fst (head graph)] | True = rAssoc lst (tail graph) --------------------------------------------------------- -- Изменение в графе Graph списка вершин, смежных вершине -- Key, на список Data ------------------------------------------------------------ putAssoc1:: Integer -> [Integer] -> [(Integer,[Integer])] -> [(Integer,[Integer])] putAssoc1 key dta graph | null graph = [] | fst (head graph)/=key = head graph : putAssoc1 key dta (tail graph) | True = (fst (head graph),dta) : putAssoc1 key dta (tail graph) ------------------------------------------------------------- -- Добавление в граф Graph дуги (x,y) ------------------------------------------------------- addArc:: Integer -> Integer -> [(Integer,[Integer])] -> [(Integer,[Integer])] addArc x y graph | null graph = [(x,[y])] | fst (head graph)==x && not (elem y (snd (head graph))) = putAssoc1 x (y : snd (head graph)) graph | fst (head graph)==x && elem y (snd (head graph)) = graph | True = head graph : addArc x y (tail graph) ---------------------------------------------------------------- -- Удаление вершины X из графа Graph ------------------------------------------------ deleteNode:: Integer -> [(Integer,[Integer])] -> [(Integer,[Integer])] deleteNode x graph | (null graph) = [] | fst (head graph)==x = deleteNode x (tail graph) | elem x (snd (head graph)) = (fst (head graph), filter (x/=) (snd (head graph))) : deleteNode x (tail graph) | True = head graph : deleteNode x (tail graph) ------------------------------------------------------------ -- Удаление дуги (X,Y) из графа Graph ---------------------------------------------------------- deleteArc:: Integer -> Integer -> [(Integer,[Integer])] -> [(Integer,[Integer])] deleteArc x y graph | null graph = [] | fst (head graph)==x && elem y (snd (head graph)) = (x,filter (y/=) (snd (head graph))) : deleteArc x y (tail graph) | True = head graph : deleteArc x y (tail graph) -------------------------------------------------------------- -- Построение списка, содержащего все вершины графа, заданного -- ассоциативным списком инцидентности Graph -------------------------------------------- walk:: [(Integer,[Integer])] -> [Integer] walk graph | null graph = [] | True = sort (listSet (oneRange graph)) --------------------------------------------------------- -- Функция возвращает всех "соседей" данной вершины X -- в графе Graph, представленном в виде ассоциативного -- списка инцидентности ------------------------------------------------------- neighb2:: Integer -> [(Integer,[Integer])] -> [Integer] neighb2 x graph | null (assoc x graph (==)) = [] | True = snd (head (assoc x graph (==))) -------------------------------------------------------- -- Вспомогательные функции библиотеки: -------------------------------------- -- Преобразование списочной структуры -- -- ((A .(x x ... x ))...(A .(y y ... y ))), -- 1 1 2 k n 1 2 j -- -- в одноуровневый список --------------------------------------------- oneRange:: [(Integer,[Integer])] -> [Integer] oneRange lst | null lst = [] | True = (fst (head lst) : snd (head lst)) ++ oneRange (tail lst) ------------------------------------------------------- -- Преобразование одноуровневого списка LST в множество -- (удаление из списка повторяющихся элементов) ----------------------------------------------- listSet:: [Integer] -> [Integer] listSet lst | null lst = [] | elem (head lst) (tail lst) = listSet (tail lst) | True = head lst : listSet (tail lst) ------------------------------------------------------------- -- Функция, выполняющая линейный поиск в ассоциативном списке -- alist пары, для которой при сравнении её fst-элемента с -- ключом key по тесту test признак не равен False. -- Если пара элементов, удовлетворяющая тесту, найдена, то -- возвращается список из этой пары; иначе - пустой список ---------------------------------------------------------- assoc:: Integer -> [(Integer,[Integer])] -> (Integer -> Integer -> Bool) -> [(Integer,[Integer])] assoc key alist test | null alist = [] | test (fst (head alist)) key = [head alist] | True = assoc key (tail alist) test
Ряд тестовых примеров.
Раскрыть/скрыть текст примеров.
-- Неудачные тестовые примеры функций библиотеки LibGrp_2.hs -- по работе с графовой структурой данных -------------------------------------------- import LibGrp_2 test = testPairLis && testReKey && testReData && testAssoc1 && testRAssoc && testPutAssoc1 && testAddArc && testDeleteNode && testDeleteArc && testWalk && testNeighb2 && testOneRange && testListSet && testAssoc ----------------------------------------------------------------- testPairLis = pairLis [1] [] [(2,[22,222])] == [(2,[22,222])] && pairLis [] [[4,5]] [(2,[22,222])] == [(2,[22,222])] && pairLis [1,2] [[5,6],[7]] [] == [(1,[5,6]),(2,[7])] && pairLis [1,2] [[5,6],[7]] [(3,[33,333]),(4,[44,444])] == [(1,[5,6]),(2,[7]), (3,[33,333]),(4,[44,444])] && pairLis [1,2] [[5,6],[]] [(3,[-3,-33]),(2,[-2,-22])] == [(1,[5,6]),(3,[-3,-33]),(2,[-2,-22])] && pairLis [1,2] [[5,6],[4]] [(3,[-3,-33]),(2,[-2,-22])] == [(1,[5,6]),(3,[-3,-33]),(2,[4,-2,-22])] && pairLis [1,2] [[5,6],[4]] [(3,[-3,-33]),(2,[4,-22])] == [(1,[5,6]),(3,[-3,-33]),(2,[4,-22])] && pairLis [1,2] [[5,6],[4]] [(1,[2,5]),(2,[4,-2])] == [(1,[6,2,5]),(2,[4,-2])] ---------------------------------------------------- testReKey = reKey [] == [] && reKey [(5,[])] == [5] && reKey [(1,[2,3])] == [1] && reKey [(1,[5,6]),(5,[5,6])] == [1,5] && reKey [(1,[5,6]),(2,[3]),(4,[])] == [1,2,4] --------------------------------------------------------- testReData = reData [] == [] && reData [(10,[])] == [[]] && reData [(1,[2,3])] == [[2,3]] && reData [(1,[5,6]),(5,[5,6])] == [[5,6],[5,6]] && reData [(1,[5,6]),(2,[3]),(4,[])] == [[5,6],[3],[]] ------------------------------------------------------------- testAssoc1 = assoc1 2 [] == [] && assoc1 10 [(10,[])] == [] && assoc1 1 [(1,[2,3])] == [2,3] && assoc1 5 [(1,[5,6]),(5,[5,6])] == [5,6] && assoc1 2 [(1,[5,6]),(2,[3]),(4,[])] == [3] --------------------------------------------------------- testRAssoc = rAssoc [2,3] [(1,[2,3])] == [1] && rAssoc [2,3] [] == [] && rAssoc [5,6] [(1,[5,6]),(4,[5,6])] == [1] && rAssoc [6,7] [(1,[7,6]),(4,[5,6])] == [1] -------------------------------------------------------- testPutAssoc1 = putAssoc1 1 [2] [] == [] && putAssoc1 1 [10] [(1,[])] == [(1,[10])] && putAssoc1 2 [3,4,5] [(1,[2,3,4])] == [(1,[2,3,4])] && putAssoc1 1 [3,4,5] [(1,[2,3,4])] == [(1,[3,4,5])] && putAssoc1 3 [5,6] [(1,[2,3,4]),(2,[3]),(3,[])] == [(1,[2,3,4]),(2,[3]),(3,[5,6])] ---------------------------------------------------------------- testAddArc = addArc 1 2 [] == [(1,[2])] && addArc 1 5 [(1,[2,3,4])] == [(1,[5,2,3,4])] && addArc 1 2 [(1,[2,3,4])] == [(1,[2,3,4])] && addArc 2 1 [(1,[2,3,4])] == [(1,[2,3,4]),(2,[1])] && addArc 5 8 [(1,[2,3,4]),(5,[])] == [(1,[2,3,4]),(5,[8])] ---------------------------------------------------------------- testDeleteNode = deleteNode 2 [] == [] && deleteNode 1 [(1,[])] == [] && deleteNode 2 [(2,[3])] == [] && deleteNode 3 [(1,[2,3,4]),(2,[3]),(3,[4])] == [(1,[2,4]),(2,[])] && deleteNode 4 [(2,[4,3]),(4,[2,3])] == [(2,[3])] ------------------------------------------------------ testDeleteArc = deleteArc 1 2 [] == [] && deleteArc 2 3 [(2,[3])] == [(2,[])] && deleteArc 2 3 [(1,[2,3,4]),(2,[3]),(3,[4])] == [(1,[2,3,4]), (2,[]),(3,[4])] && deleteArc 2 3 [(2,[2,3])] == [(2,[2])] && deleteArc 4 3 [(2,[2,3]),(4,[2,3])] == [(2,[2,3]), (4,[2])] -------------------------------------------------------- testWalk = walk [] == [] && walk [(1,[])] == [1] && walk [(1,[2,3,4]),(5,[6,7]),(8,[9])] == [1,2,3,4,5,6,7,8,9] && walk [(1,[2,3,4]),(2,[3]),(3,[4])] == [1,2,3,4] && walk [(1,[2,3,4]),(2,[]),(3,[4,3,2])] == [1,2,3,4] --------------------------------------------------------------- testNeighb2 = neighb2 1 [(1,[2,3,4]),(2,[1,3]),(3,[1,2]), (4,[1])] == [2,3,4] && neighb2 2 [(1,[2,3,4]),(2,[1,3]),(3,[1,2]), (4,[1])] == [1,3] && neighb2 3 [(1,[2,3,4]),(2,[1,3]),(3,[1]), (4,[1])] == [1] && neighb2 2 [(1,[2,3,4]),(2,[])] == [] && neighb2 5 [(1,[2,3]),(2,[1,3]),(3,[1,2])] == [] --------------------------------------------------------------- -- "Вспомогательные" функции ------------------------------------------------- testListSet = listSet [] == [] && listSet [1] == [1] && listSet [1,1,1] == [1] && listSet [1,2,3,3,2,1] == [3,2,1] && listSet [1,1,2,3,2,3,1,2,1] == [3,2,1] ------------------------------------------------------ testOneRange = oneRange [] == [] && oneRange [(1,[])] == [1] && oneRange [(1,[]),(2,[]),(3,[])] == [1,2,3] && oneRange [(1,[-1]),(2,[]),(3,[-3,-33,33])] == [1,-1,2,3,-3,-33,33] ---------------------------------------------------------- testAssoc = assoc 2 [(1,[3])] (==) == [] && assoc 2 [(11,[3,2]),(-2,[4,3,2,1]),(1,[2,1])] (<) == [(-2,[4,3,2,1])] && assoc 2 [(1,[3,-1]),(-2,[]),(2,[1,0,-1])] (==) == [(2,[1,0,-1])] && assoc (-22) [(-22,[]),(1,[2,2])] (<=) == [(-22,[])] && assoc (-22) [(-22,[4]),(1,[2]),(2,[1])] (>) == [(1,[2])]
На следующем шаге мы приведем перечень задач для самостоятельного решения.
