"Зочем вы кгасите" (с) или истинно декларативная проверка графа на двудольность
Рождество - прекрасное время, когда оценки выставлены и есть время высказаться по поводу двудольных графов. Вторая реализация ("в декларативном стиле"), написанная _adept_ элегантна и эффективна (настолько, насколько эффективны используемые библиотечные функции). Но все же, она использует алгоритм для проверки двудольности, а не определение двудольности напрямую. Что можно было бы сделать, если бы мы уже придумали двудольный граф, но еще не придумали алгоритм?
Мощь Хаскеля отчасти заключается в его исключительно доступной денотационной семантике. Код напрямую соответствует математическим объектам, а многие объекты можно просто выразить кодом. И здесь декларативное видение позволяет описывать объекты (возможно, не самым эффективным с точки зрения вычислительной сложности образом) практически дословно переписывая определение.
Итак, Неориентированный граф G = (W,E) называется двудольным, если множество его вершин можно разбить на две части U \cup V = W, | U | > 0, | V | > 0, так, что
* ни одна вершина в U не соединена с вершинами в U и
* ни одна вершина в V не соединена с вершинами в V
Иными словами, в таком разбиении оба множества U и V независимы.
Разбиение можно задать одним множеством, при этом V будет его дополнением. Множество таких разбиений - булеан множества вершин. Значит,
isBipartite g = any bothIndependent (powerset (nodes g)) where bothIndependent a = independent a && independent ((nodes g) \\ a)
Множество вершин независимо, если в нем нет пары связанных вершин. Иными словами, подграф порожденный этим множеством, не содержин ребер. Получить такой подграф можно, удалив все остальные вершины.
independent a = null $ edges $ delNodes ((nodes g) \\ a) g
Наконец, булеан (множество всех подмножеств). Приведу два варианта. Если у нас есть множество xs для которого известен булеан acc и мы расширим xs добавив в него элемент x, то булеан для этого расширенного множества будет состоять из acc объединенного с acc', в котором каждый из членов был расширен элементом x:
powerset = foldr (\x acc -> acc ++ (map ((:) x) acc)) [[]]
Второй вариант использует понятие индикаторной(характеристической функции) подмножества. Булеан - множество всех подмножеств, поэтому можно построить его, рассмотрев все возможные индикаторы. Задав порядок на множестве (в Хаскеле мы получаем его "бесплатно" если держим множества в списках) можно представлять индикаторы в виде двоичных векторов. Итак,
powerset xs = map subsetByIndicator $ map binExpansion [0..2^(length xs)-1] where subsetByIndicator p = [x|(x,i)<-(zip xs p), i==1] binExpansion x = mod x 2 : binExpansion (div x 2)
Резюмируя, мы описали проверку двудольного графа исходя непосредственно из определения. Получившийся код немного короче, чем рассмотренные примеры с использованием раскраски, но менее эффективен. Вот код целиком:
import Data.Graph.Inductive hiding (empty)
import Data.List
{-a bipartite graph (or bigraph) is a graph whose vertices can be divided into two
disjoint sets U and V such that every edge connects a vertex in U to one in V;
that is, U and V are independent sets-}
{-Any subset of vertices defines a partition (itself and its complement).
Thus, we consider a powerset of vertices and if one of the elements in powerset
and its complement both are independent, the graph is bipartite-}
isBipartite g = any bothIndependent (powerset (nodes g))
where
{- We will check whether set a and its complement ((nodes g) \\a) are
both independent-}
bothIndependent a = independent a && independent ((nodes g) \\ a)
{-A set of vertices is independent if no two verices in it are connected,
meaning that induced subgraph formed by removing the rest of the vertices
has no edges-}
independent a = null $ edges $ delNodes ((nodes g) \\ a) g
{-If acc is a powerset of some set xs and we extend xs by element x, the new
powerset will be formed by original sets acc united with every element of
acc extended by x-}
powerset = foldr (\x acc -> acc ++ (map ((:) x) acc)) [[]]
makeGraph :: [(Int,[Int])] -> Gr () ()
makeGraph g = mkUGraph vs es
where vs = map fst g
es = [(n1,n2) | (n1,es) <- g, n2 <- es]
bipartite =
[(0,[1]),(1,[0,2,8]),(2,[1,3]),(3,[2,6]),(4,[5,7]),(5,[4]),(6,[3]),(7,[4,8]),(8,[1,7])]
not_bipartite =
[(0,[1,2]),(1,[0,2,8]),(2,[1,3]),(3,[2,6]),(4,[5,7]),(5,[4]),(6,[3]),(7,[4,8]),(8,[1,7])]
main = do
print $ isBipartite $ makeGraph bipartite
print $ isBipartite $ makeGraph not_bipartite
Мощь Хаскеля отчасти заключается в его исключительно доступной денотационной семантике. Код напрямую соответствует математическим объектам, а многие объекты можно просто выразить кодом. И здесь декларативное видение позволяет описывать объекты (возможно, не самым эффективным с точки зрения вычислительной сложности образом) практически дословно переписывая определение.
Итак, Неориентированный граф G = (W,E) называется двудольным, если множество его вершин можно разбить на две части U \cup V = W, | U | > 0, | V | > 0, так, что
* ни одна вершина в U не соединена с вершинами в U и
* ни одна вершина в V не соединена с вершинами в V
Иными словами, в таком разбиении оба множества U и V независимы.
Разбиение можно задать одним множеством, при этом V будет его дополнением. Множество таких разбиений - булеан множества вершин. Значит,
isBipartite g = any bothIndependent (powerset (nodes g)) where bothIndependent a = independent a && independent ((nodes g) \\ a)
Множество вершин независимо, если в нем нет пары связанных вершин. Иными словами, подграф порожденный этим множеством, не содержин ребер. Получить такой подграф можно, удалив все остальные вершины.
independent a = null $ edges $ delNodes ((nodes g) \\ a) g
Наконец, булеан (множество всех подмножеств). Приведу два варианта. Если у нас есть множество xs для которого известен булеан acc и мы расширим xs добавив в него элемент x, то булеан для этого расширенного множества будет состоять из acc объединенного с acc', в котором каждый из членов был расширен элементом x:
powerset = foldr (\x acc -> acc ++ (map ((:) x) acc)) [[]]
Второй вариант использует понятие индикаторной(характеристической функции) подмножества. Булеан - множество всех подмножеств, поэтому можно построить его, рассмотрев все возможные индикаторы. Задав порядок на множестве (в Хаскеле мы получаем его "бесплатно" если держим множества в списках) можно представлять индикаторы в виде двоичных векторов. Итак,
powerset xs = map subsetByIndicator $ map binExpansion [0..2^(length xs)-1] where subsetByIndicator p = [x|(x,i)<-(zip xs p), i==1] binExpansion x = mod x 2 : binExpansion (div x 2)
Резюмируя, мы описали проверку двудольного графа исходя непосредственно из определения. Получившийся код немного короче, чем рассмотренные примеры с использованием раскраски, но менее эффективен. Вот код целиком:
import Data.Graph.Inductive hiding (empty)
import Data.List
{-a bipartite graph (or bigraph) is a graph whose vertices can be divided into two
disjoint sets U and V such that every edge connects a vertex in U to one in V;
that is, U and V are independent sets-}
{-Any subset of vertices defines a partition (itself and its complement).
Thus, we consider a powerset of vertices and if one of the elements in powerset
and its complement both are independent, the graph is bipartite-}
isBipartite g = any bothIndependent (powerset (nodes g))
where
{- We will check whether set a and its complement ((nodes g) \\a) are
both independent-}
bothIndependent a = independent a && independent ((nodes g) \\ a)
{-A set of vertices is independent if no two verices in it are connected,
meaning that induced subgraph formed by removing the rest of the vertices
has no edges-}
independent a = null $ edges $ delNodes ((nodes g) \\ a) g
{-If acc is a powerset of some set xs and we extend xs by element x, the new
powerset will be formed by original sets acc united with every element of
acc extended by x-}
powerset = foldr (\x acc -> acc ++ (map ((:) x) acc)) [[]]
makeGraph :: [(Int,[Int])] -> Gr () ()
makeGraph g = mkUGraph vs es
where vs = map fst g
es = [(n1,n2) | (n1,es) <- g, n2 <- es]
bipartite =
[(0,[1]),(1,[0,2,8]),(2,[1,3]),(3,[2,6]),(4,[5,7]),(5,[4]),(6,[3]),(7,[4,8]),(8,[1,7])]
not_bipartite =
[(0,[1,2]),(1,[0,2,8]),(2,[1,3]),(3,[2,6]),(4,[5,7]),(5,[4]),(6,[3]),(7,[4,8]),(8,[1,7])]
main = do
print $ isBipartite $ makeGraph bipartite
print $ isBipartite $ makeGraph not_bipartite