Как я могу генерировать случайные графики с помощью test.check? - PullRequest
Новая
       14

Как я могу генерировать случайные графики с помощью test.check?

0 голосов
/ 31 октября 2018

Я пытаюсь сгенерировать случайный граф в форме списка смежности для генеративного тестирования. Пример графика будет: 

{:a #{:a :b}, :b #{:a :b}}

(Списки смежности реализованы в виде наборов.)

Моя первая идея была такой: 

(def vertex-gen (tcgen/fmap (comp keyword str) tcgen/char-alpha-numeric))

(def random-graph-gen-1
  (tcgen/let [vertices (tcgen/set vertex-gen {:min-elements 1})]
             (tcgen/map (tcgen/elements vertices)
                        (tcgen/set (tcgen/elements vertices)))))

({min-elements 1} требуется, потому что tcgen/elements не работает на пустых наборах.)

Тем не менее, это создает риск создания графиков, таких как 

{:a #{:a :b}}

где :b выбирается случайным образом для списка смежности :a, но не выбирается для самого графа. Так что у :a есть сосед, которого не существует.

Другой вариант - 

(def random-graph-gen-2
  (tcgen/let [vertices (tcgen/set vertex-gen)]
             (->> vertices
                  (map #(->> vertices
                             (tcgen/elements)
                             (tcgen/set)
                             (tcgen/generate)
                             (vector %)))
                  (into {}))))

, который перебирает все вершины и явно генерирует случайный список смежности для каждой вершины. Это гарантирует, что все вершины появятся в графе, но имеет недостаток в том, что test.check не видит генерируемых списков смежности. Поэтому я беспокоюсь, что это испортит логику сокращения.

Есть ли решение, позволяющее избежать обеих этих ловушек?

1 Ответ

0 голосов
/ 31 октября 2018

Вот еще один способ сделать это: 

(def graph-gen
  (gen/let [vertices (gen/set vertex-gen {:min-elements 1})
            edges (-> vertices
                      (gen/elements)
                      (gen/set)
                      (gen/vector (count vertices)))]
    (zipmap vertices edges)))

Здесь представлен второй генератор, который создает набор ребер для каждой вершины, а затем объединяет вершины и ребра в одну карту.

Использование generate во втором примере представляет случайность, которая не связана с размером всего генератора. От generate Документация:

Обратите внимание, что эта функция является помощником разработчика и не предназначена для создания других генераторов.

Но вы можете использовать generate для выборки из генератора для разных размеров: 

(gen/generate graph-gen 2)
=> {:F #{}, :e #{}, :S #{:e}}
(gen/generate graph-gen 10)
=>
{:L #{:n :7 :8 :H},
 :n #{:L :n :7 :C :8 :b :H :V},
 :7 #{:L :7 :C :8 :9 :b},
 :C #{:L :9 :V},
 :8 #{:L :n :7 :C :8 :9 :b :V},
 :9 #{:L :b :a},
 :b #{:n :V},
 :H #{:a},
 :V #{:n :C :b :H},
 :a #{}}
...