Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Haskell
Перезагрузить страницу Ориентированный Граф
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
CryBaByKillZ CryBaByKillZ вне форума
Новичок
 
Сообщений: 6
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 06.06.2011
Exclamation Ориентированный Граф - 06.06.2011, 19:41

Необходимо написать программу поиска компонент сильной связности ориентированного графа.Помогите кто чем может
Ответить с цитированием
  (#2 (permalink)) Старый
Alexiski Alexiski вне форума
Любитель давать советы
 
Сообщений: 4,281
Сказал(а) спасибо: 27
Поблагодарили 54 раз(а) в 54 сообщениях
Регистрация: 16.10.2005
По умолчанию 07.06.2011, 01:20

Как граф задавать будем?
Ответить с цитированием
  (#3 (permalink)) Старый
CryBaByKillZ CryBaByKillZ вне форума
Новичок
 
Сообщений: 6
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 06.06.2011
По умолчанию 07.06.2011, 10:07

да не важно, главное чтобы выполнял алгоритм правильно, было бы очень здорово если бы вы смогли мне помочь
Ответить с цитированием
  (#4 (permalink)) Старый
calabi-yau calabi-yau вне форума
Member
 
Сообщений: 338
Сказал(а) спасибо: 0
Поблагодарили 10 раз(а) в 10 сообщениях
Регистрация: 28.09.2009
По умолчанию 07.06.2011, 21:20

Цитата:
Сообщение от CryBaByKillZ Посмотреть сообщение
да не важно, главное чтобы выполнял алгоритм правильно, было бы очень здорово если бы вы смогли мне помочь
и какой алгоритм, интересно?

haskell Код:
import Data.Graph (dfs, topSort, transposeG)
import Control.Monad (ap)
import Data.Tree (flatten)

scc = map flatten . ap dfs (topSort . transposeG)


Don't fear the Monad
Ответить с цитированием
  (#5 (permalink)) Старый
CryBaByKillZ CryBaByKillZ вне форума
Новичок
 
Сообщений: 6
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 06.06.2011
По умолчанию 08.06.2011, 00:02

я знаю алгоритм на С++, а как его на хаскиле реализовать не знаю...
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
CryBaByKillZ CryBaByKillZ вне форума
Новичок
 
Сообщений: 6
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 06.06.2011
По умолчанию 11.06.2011, 09:32

Ну помогите пожалуйста,calabi-yau
Ответить с цитированием
  (#7 (permalink)) Старый
calabi-yau calabi-yau вне форума
Member
 
Сообщений: 338
Сказал(а) спасибо: 0
Поблагодарили 10 раз(а) в 10 сообщениях
Регистрация: 28.09.2009
По умолчанию 11.06.2011, 21:30

Вышеприведенный код решает вашу задачу:
haskell Код:
*Main> scc $ buildG (0,7) [(0,1),(1,2),(2,3),(3,2),(3,7),(7,3),(4,0),(1,4),(4,5),(1,5),(5,6),(6,5),(2,6),(7,6)]
...
[[5,6],[2,3,7],[0,1,4]]


Don't fear the Monad
Ответить с цитированием
  (#8 (permalink)) Старый
CryBaByKillZ CryBaByKillZ вне форума
Новичок
 
Сообщений: 6
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 06.06.2011
По умолчанию 12.06.2011, 09:39

А почему код такой короткий? можете мне его объяснить?
Ответить с цитированием
  (#9 (permalink)) Старый
calabi-yau calabi-yau вне форума
Member
 
Сообщений: 338
Сказал(а) спасибо: 0
Поблагодарили 10 раз(а) в 10 сообщениях
Регистрация: 28.09.2009
По умолчанию 15.06.2011, 03:19

Цитата:
Сообщение от CryBaByKillZ Посмотреть сообщение
А почему код такой короткий?
спец библиотеки же.
Цитата:
можете мне его объяснить?
topSort . transposeG - получение порядка обхода на обращенном графе.

dfs - обход в глубину всех достижимых вершин графа для каждой из списка вершин.

ap - S комбинатор:
haskell Код:
ap dfs (topSort . transposeG) == \g -> dfs g (topSort (transposeG g))
т.е обход в глубину всех достижимых вершин графа для каждой вершины из списка, полученного на этапе обхода обращенного графа.

map flatten - свертка списков деревьев в список списков вершин.


Don't fear the Monad
Ответить с цитированием
  (#10 (permalink)) Старый
CryBaByKillZ CryBaByKillZ вне форума
Новичок
 
Сообщений: 6
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 06.06.2011
По умолчанию 15.06.2011, 19:07

а можно как-нибудь без этих спец библиотек, чтобы все расписанно было?
Ответить с цитированием
  (#11 (permalink)) Старый
Jean-Esther Jean-Esther вне форума
Member
 
Сообщений: 22
Сказал(а) спасибо: 1
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 07.03.2009
По умолчанию 16.06.2011, 08:47

Может, код покажется громоздким (или, чего я больше боюсь, неправильным), но там используются только примитивы из Prelude.
Граф задается двумерным (т.е. вложенным) списком, где k-м элементом есть список вершин, с которыми соеденна k-я (что, собственно, задает getConnectedVertexes). При желании, можно выбрать другую структуру графа, лишь бы был описан аналог первой функции.
Аналоги isin и join, возможно, уже описаны в стандартном начале.

- формируем список связанных (без учета ситуации, когда от 1 сущ. путь к 2, но не наоборот) с vrtx вершин по уровню родства: [vrtx, <те, что напрямую связанны с ним>, <те, что связанны со связанными на прямую>, <те, что связанны с предыдущими>, ...]
- выбираем первый элемент, который полность как множество совпадает с предыдущим — это множество вершин, к которым есть путь из vrtx.
- из них выбираем те, которые имеют путь к vrtx

haskell Код:
type Graph n = [[n]];
getConnectedVertexes ::  Graph Int -> Int -> [Int];
getConnectedVertexes g = (g !!) . pred;

x `isin` s = any (==x) s; --isin = any . (==)
join = foldl (++) [];
getComponentOf :: Graph Int -> Int -> [Int]
getComponentOf grph vrtx = -- выбираем те, которые имеют путь к vrtx
    (\levels ->
        foldr (\(x,y) z -> if and (flip isin x `map` y) then x else z)
            (error "Something strange has occured") $
            zip levels (tail levels) -- [([Int],[Int])]
    )(flip iterate [vrtx] -- формируем список связанных с vrtx вершин
        (\lvl ->
            join $ getConnectedVertexes grph `map` lvl
        )
    );

getBiComponentOf grph vrtx = -- выбираем те, которые имеют путь к vrtx
    filter (isin vrtx . getComponentOf grph) $
        getComponentOf grph vrtx;

sample = [[1, 3, 4],[2, 3, 4],[3, 2, 4],[4]] :: [[Int]];
sample2 = [[1,2],[1,2],[3]] :: [[Int]];
Ответить с цитированием
  (#12 (permalink)) Старый
calabi-yau calabi-yau вне форума
Member
 
Сообщений: 338
Сказал(а) спасибо: 0
Поблагодарили 10 раз(а) в 10 сообщениях
Регистрация: 28.09.2009
По умолчанию 16.06.2011, 15:05

haskell Код:
import Data.List

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

type Node = Int

transpose_graph :: Graph -> Graph
transpose_graph (ns, g) = (ns, [(b,a) | (a,b) <- g])

visit :: Graph -> [Node] -> ([][Node], Graph)
visit g       []     = ([], g)
visit (ns, g) (v:vs) | v `elem` ns =
  let g0 =
        (v `delete` ns, g)
--
      (xs1, g1) = visit g0 [t | (f,t) <- g, f == v]
      (xs2, g2) = visit g1 vs
  in ((concat xs1 ++ [v]):xs2, g2)

visit (ns, g) (v:vs) = visit (ns, g) vs


dfs g ns = fst (visit g ns)

scc g = dfs g (concat $ reverse $ dfs (transpose_graph g) (fst g))
haskell Код:
*Main> scc $ ([0 .. 7], [(0,1),(1,2),(2,3),(3,2),(3,7),(7,3),(4,0),(1,4),(4,5),(1,5),(5,6),(6,5),(2,6),(7,6)])
...
[[5,6],[2,3,7],[0,4,1]]


Don't fear the Monad
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Остовный граф nyashka Prolog 26 22.12.2013 20:30
Неориент.граф CoCu_cka Prolog 2 15.06.2011 22:30
задача на граф eternalV Pascal 2 22.04.2011 02:28
Граф. sovsem_ novichok Prolog 0 13.07.2010 23:38
Задача на ориентированный граф minzdravrf Задания за деньги 3 01.02.2010 15:48
Связанный граф ler Prolog 20 17.12.2009 03:57
Объекто-ориентированный анализ с примерами на Смолтоке Вася Чайко Smalltalk 1 14.08.2008 15:05
Триангуляция и граф Андрейка C. Алгоритмы 2 25.03.2007 19:35
Достроить граф Teenager Prolog 0 04.12.2006 15:19
Упорядочить граф Den_NN Prolog 0 19.12.2005 00:22



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов