Произвольный экземпляр для создания несмещенных графиков для быстрой проверки

module Main where

import Test.QuickCheck
import Data.Set as Set    

data Edge v = Edge {source :: v, target :: v}
                  deriving (Show,Eq,Ord)

data Graph v = Graph {nodes :: Set v, edges :: Set (Edge v)}
               deriving Show

instance Arbitrary v => Int-> Arbitrary (Edge v) where
    arbitrary = sized aux 
        where aux n = do s <- arbitrary
                         t <- arbitrary `suchThat` (/= s)
                         return $ Edge {source = s, target = t}


instance (Ord v, Arbitrary v) => Arbitrary (Graph v) where
    arbitrary = aux `suchThat` isValid
        where aux = do ns <- arbitrary 
                       es <- arbitrary 
                       return $ Graph {nodes = fromList ns, edges = fromList es}

Это текущее определение экземпляра генерирует графы с несколькими ребрами, как мне изменить его, чтобы он был менее предвзятым и удовлетворял этим двум функциям? :

- | Функция isDAG проверяет, является ли график ациклическим.

isDAG :: Ord v => Graph v -> Bool
isDAG g = isValid g && all nocycle (nodes g)
    where nocycle v = all (\a -> v `notMember` reachable g a) $ Set.map target (adj g v)

- | Функция isForest проверяет, является ли действительный DAG florest (набором деревьев), другими словами, - если каждый узел (вершина) имеет максимум одну смежную.

isForest :: Ord v => DAG v -> Bool
isForest g = isDAG g && all (\v -> length (adj g v) <= 1) (nodes g)

testing graph geometry haskell quickcheck
person Fluids    schedule 04.04.2016    source источник
comment
73233 ›Quando for grande quero poder correr scripts for avaliar indivíduos.   -  person Fluids    schedule 02.06.2016

Ответы (2)


arrow_upward
3
arrow_downward

Сначала вы должны выяснить, как построить граф, удовлетворяющий этим свойствам.

DAG: Если ваши узлы допускают некоторый порядок и для каждого ребра (u,v) у вас есть u < v, то график ациклический. Этот порядок может быть любым, поэтому вы можете просто создать произвольный порядок для набора узлов в графе.

Лес: если ваш граф не имеет ребер, это свойство тривиально выполняется. Первоначально вы можете добавить любое ребро, источником которого является любой узел. Если вы добавляете ребро, удалите его источник из оставшихся доступных узлов.

Думаю, большой вопрос в том, как это перевести в код. QuickCheck предоставляет множество комбинаторов, особенно. для выбора из списков, с заменой и без, различных размеров и т. д.

instance (Ord v, Arbitrary v) => Arbitrary (Graph v) where 
  arbitrary = do 
    ns <- Set.fromList <$> liftA2 (++) (replicateM 10 arbitrary) arbitrary

Сначала вы создаете случайный набор узлов.

    let ns' = map reverse $ drop 2 $ inits $ Set.toList ns

Для каждого узла вычисляется (непустой) набор узлов, которые «больше», чем этот узел. Здесь «больше» просто означает в соответствии с произвольным порядком, вызванным порядком элементов в списке. Это дает вам свойство DAG.

    es <- sublistOf ns' >>= 
            mapM (\(f:ts) -> Edge f <$> elements ts)

Затем вы получаете случайный подсписок этого списка (который дает вам свойство леса), и для каждого элемента в этом случайном подсписке вы создаете ребро, указывающее от «самого большого» узла в этом наборе к тому, который «меньше».

    return $ Graph ns (Set.fromList es)

Тогда все готово! Тестируйте так:

main = quickCheck $ forAll arbitrary (liftA2 (&&) (isDAG :: Graph Integer -> Bool) isForest)
person user2407038    schedule 04.04.2016

arrow_upward
0
arrow_downward

Естественный способ построения графиков - индуктивное добавление по одному узлу за раз. Тогда становится довольно легко обеспечить соблюдение требуемых свойств:

  • Если для каждого добавленного узла его края указывают только на существующие узлы (а не в другом направлении), мы гарантируем свойство DAG.
  • Если от узла идет не более одного ребра, мы гарантируем свойство леса. (Поскольку вы не предоставили функцию adj, неясно, подразумевается ли под «лесом» не более одного края, идущего от узла или к узлу. )

Таким образом, процесс создания такого графа будет выглядеть следующим образом:

  1. Сгенерируйте список случайных узлов.
  2. Постройте граф, добавляя их один за другим. Для каждого узла либо добавьте случайное ребро к одному из уже добавленных узлов, либо не добавьте ребро (выбирайте случайным образом).

Главный фактор здесь - решить, добавлять ли преимущество или нет. Изменяя этот параметр, вы получаете больше или меньше деревьев в вашем лесу. Один из вариантов - использовать _2 _ за что.

person Petr    schedule 27.04.2016