1. Куча / Говнокод #18581

    +2

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    import qualified Data.Map as M
import Data.Maybe
import Data.Array
import Control.Monad
import Control.Monad.State
import Control.Monad.IfElse

type Graph = Array Int [Int]

isBipartite g = isJust $ runStateT (mapM_ fill (indices g)) M.empty
  where
    fill     v = whenM (M.notMember v`fmap`get) $ spread True v
    spread k v = whenM (paint k v)              $ mapM_ (spread (not k)) (g!v)

paint k v = get >>= \c -> case M.lookup v c of 
    Nothing     -> put (M.insert v k c) >> return True
    Just x|x==k ->                         return False
          |True ->                         fail ""

    Проверка двудольности графа.
    http://antilamer.livejournal.com/298055.html?format=light

    Запостил: roman-kashitsyn, 06 Августа 2015

    Комментарии (23) RSS

    • ava roman-kashitsyn 06.08.2015 10:59 # 0

      Как это делают унылые императивщики
      type Graph [][]int
 
const (
	colorGray  = iota
	colorWhite = iota
	colorBlack = iota
)
 
func dfs(g Graph, colors []int, v int, c int) bool {
	colors[v] = c
	invertColor := c%2 + 1
	for _, n := range g[v] {
		if colors[n] == c || colors[n] == colorGray && !dfs(g, colors, n, invertColor) {
			return false
		}
	}
	return true
}
 
func IsBipartite(g Graph) bool {
	colors := make([]int, len(g))
	for v := range g {
		if colors[v] == colorGray && !dfs(g, colors, v, colorWhite) {
			return false
		}
	}
	return true
}
      Ответить

      • ava imihajlov 06.08.2015 11:10 # 0

        Нет никакой проблемы переписать этот же алгоритм на хаскель один-в-один, просто заменив изменяемый массив colors на список, который функция dfs будет возвращать вместе со своим true/false, а в IsBibartite использовать fold для итерации по массиву.
        Просто кто-то слишком любит обмазываться говном использовать монады.
        Ответить

        • ava roman-kashitsyn 06.08.2015 11:15 # 0

          > изменяемый массив colors на список
          Изящно превратив линейный алгоритм в квадратичный? Map тогда уж, так заплатим хотя бы логарифмом.
          Ответить

    • ava bormand 06.08.2015 11:05 # +2

      Блин, как же сложно читать хаскель...
      Ответить

    • ava kegdan 06.08.2015 12:29 # 0

      Ничоси тут кто то монадами обмазался. Без косяка не разберешься
      Ответить

    • ava Vasiliy 06.08.2015 13:27 # 0

      Control.Monad.IfElse
      Мне вот это монада нравится.
      Ответить

    • ava bormand 06.08.2015 14:13 # +1

      Присоединюсь к вакханалии:
      isBipartite graph =
    isJust $ foldM step M.empty (indices graph)
    where
        paint colormap [] = Just colormap
        paint colormap ((node, color) : xs) =
            case M.lookup node colormap of
                Nothing -> paint (M.insert node color colormap) (zip (graph ! node) (repeat $ not color) ++ xs)
                Just c | c == color -> paint colormap xs
                       | otherwise -> Nothing
        step colormap node =
            case M.lookup node colormap of
                Nothing -> paint colormap [(node, True)]
                Just _ -> Just colormap
      Ответить

    • ava kegdan 06.08.2015 16:29 # 0

      Мой домик из грязи код на шарпе

      https://ideone.com/2UFtiE


      Оцените говнистость
      Ответить

      • ava roman-kashitsyn 06.08.2015 16:35 # 0

        Так вроде у тебя алгоритм абсолютно тот же, просто для представления графа ты вместо adjacency list почему-то выбрал adjacency matrix.
        Ответить

        • ava kegdan 06.08.2015 16:50 # 0

          А есть другой алгоритм? Этот самый логичный. Мне кажется adjacency matrix удобнее имхо

          Меня больше интересует говнистость - мне ж на работу когда нибудь придется устраиваться. На джуниора тянет?
          Ответить

          • ava bormand 06.08.2015 16:52 # 0

            > adjacency matrix удобнее
            Ну офигеть как удобнее. Сканить всю строку вместо того, чтобы тупо пробежаться по списку нужных рёбер.
            Ответить

            • ava kegdan 06.08.2015 16:53 # 0

              Я имел в виду удобнее не для данного алгоритма, а для хранения и обработки графа в целом

              Хотя я давно этим не занимался, он скорее нагляднее, а удобность еще нужно обмозговать
              Ответить

              • ava bormand 06.08.2015 17:02 # +1

                > для хранения и обработки графа в целом
                Да ну... На практике графы всё-таки разряжённые. И в итоге твоя матрица жрёт овердохуя памяти O(N^2) и ищет соседние узлы за O(N).

                И всё это ради одной почти никому нинужной операции за O(1) - получить edge между двумя узлами. Причём adjacency list, если его реализовать через Set, может справиться с ней за O(log(M)), где M - количество исходящих из первой ноды рёбер, что вполне приемлемо.
                Ответить

                • ava kegdan 06.08.2015 17:05 # 0

                  Да, действительно. Был не прав, каюсь.

                  В adjacency matrix проще редактировать и искать входящие в вершину ребра.
                  Ответить

                  • ava bormand 06.08.2015 17:07 # 0

                    > искать входящие в вершину ребра
                    Если это настолько нужно - можно и обратные списки сохранить. Память вырастет всего вдвое, а не пропорционально квадрату :)

                    Но можно пример, где это нужно?

                    > редактировать
                    Да ну. Вставки в set/list тоже примитивны.
                    Ответить

                  • ava roman-kashitsyn 06.08.2015 17:39 # 0

                    > искать входящие в вершину ребра
                    Обычно проще один раз построить граф, в котором все рёбра инвертированы.

                    А если граф не ориентированный, то вообще ничего делать не нужно.
                    Ответить

                    • ava kegdan 06.08.2015 17:40 # 0

                      Это да. Понял я свою ошибке, ах не тираньте меня. Пойду в макдак работать
                      Ответить

                    • ava kegdan 06.08.2015 17:48 # 0

                      так?
                      https://ideone.com/Mf5rDd
                      Ответить

          • ava roman-kashitsyn 06.08.2015 16:56 # +2

            Подумай лучше на тему преимуществ и недостатков представлений графов. Adjacency Matrix редко используется, т.к. все алгоритмы скатываются в O(|V|^2), а все самые интересные алгоритмы - линейные или квазилинейные, т.е. O(|V| + |E|). Да, |E| может быть |V|^2, но чаще всего нет.

            Матрица реально нужна, например, в Флойде-Уоршелле, но там сам алгоритм кубический.
            Ответить

            • ava bormand 06.08.2015 16:59 # 0

              > Флойде-Уоршелле
              Это который с тройным циклом?
              Ответить

              • ava roman-kashitsyn 06.08.2015 17:00 # +1

                Да, кратчайшее от всех до всех, им же транзитивное замыкание можно построить. Марлоу его даже запараллелить на хаски умудрился (как пример в книжке).
                Ответить

    Добавить комментарий