Ищете лучшие способы сгенерировать список ребер для графа в среде тестирования свойств jqwik

Question

В настоящее время я использую:

          @Provide
    Arbitrary<List<Tuple.Tuple3<Integer,Integer,Integer>>> edgeLists (
        TypeUsage type, ArbitraryProvider.SubtypeProvider subtype) {
        int vertices = 10;
        int degree_min = 1;
        int degree_max = 4;
        int min_edge_flow = 1;
        int max_edge_flow = 10;

        for (Annotation a : type.getAnnotations()) {
            if (a instanceof MaxFlowParameters) {
                MaxFlowParameters params = (MaxFlowParameters) a;
                vertices = Math.max(1, params.vertices());
                degree_min = Math.max(1, params.degree_min());
                degree_max = Math.min(vertices, Math.max(degree_min, params.degree_max()));
                min_edge_flow = Math.min(vertices, Math.max(0, params.min_edge_flow()));
                max_edge_flow = Math.min(vertices, Math.max(min_edge_flow, params.max_edge_flow()));
            }
        }

        Function<List<Integer>,List<Integer>> expand = new Function<List<Integer>,List<Integer>> () {
            @Override
            public List<Integer> apply (List<Integer> t) {
                List<Integer> result = new ArrayList<>();
                ListUtils.enumerate(t, (idx,copies) -> {
                    while (copies-- > 0) result.add(idx+1);
                    return true;
                });
                return result;
            }
        };

        int num_vertices = vertices;
        int the_min_edge_flow = min_edge_flow;
        int the_max_edge_flow = max_edge_flow;

        return Arbitraries.integers().between(degree_min, degree_max).list().ofSize(vertices).map(expand)
            .flatMap(sources -> Arbitraries.integers().between(1, num_vertices).list().ofSize(sources.size())
                .flatMap(targets -> Arbitraries.integers().between(the_min_edge_flow, the_max_edge_flow).list().ofSize(sources.size())
                    .map(flows -> {
                        int limit = sources.size();
                        List<Tuple3<Integer,Integer,Integer>> result = new ArrayList<>(limit);
                        for (int i = 0; i < limit; i++) {
                            result.add(Tuple.of(sources.get(i), targets.get(i), flows.get(i)));
                        }
                        return result;
                    })));
    }

в этом случае я просто указываю исходные / целевые вершины по идентификатору и добавляю компонент потока (который может быть весом или любым количеством других связанных значений). схема состоит в том, чтобы составить список значений градусов из [Степень_мин, Степень_макс], по одному для каждой вершины, а затем развернуть этот список до списка, в котором каждый источник повторяется несколько раз в градусах. как только у меня есть этот список, я могу генерировать последовательности целей и меток и комбинировать их, чтобы образовать края.

этого достаточно, чтобы гарантировать, что у меня есть полный список вершин и что есть подходящее количество исходящих ребер для каждой вершины. однако я не думаю, что этот подход хорошо масштабируется для добавления более реалистичных / полезных ограничений. В частности, учитывая дополнительные шаги фильтрации и сопоставления, которые, вероятно, потребуются, а в нынешнем виде, вероятно, уже слишком много ...

Например, я думаю, что возможность сделать произвольное для каждого ребра узла, а затем присоединиться к произвольным, чтобы составить общий список ребер, может помочь, но я не вижу никакого способа сделать это в рамках (например, Combine ориентирован на объединение значений, взятых из каждого из нескольких списков, а не на объединение списков).

Ищу любые предложения по улучшению этого.

Answer 1

Поскольку ваш пример не может быть легко воспроизведен (некоторые зависимости отсутствуют), я попытался понять, читая код, какие графики вы создаете. Я, наверное, что-то упустил.

Вот простой подход, который я придумал:

          @Provide
    Arbitrary<Set<Tuple3<String, Set<String>, Integer>>> nodes() {
        int maxVertices = 20;
        int degreeMax = 4;
        int minEdgeFlow = 1;
        int maxEdgeFlow = 10;
    
        Arbitrary<String> anyVertix = Arbitraries.strings().withCharRange('a', 'z').ofLength(3);
        SetArbitrary<String> anyVertices = anyVertix.set().ofMinSize(1).ofMaxSize(maxVertices);
    
        return anyVertices.flatMapEach((vertices, vertix) -> {
            SetArbitrary<String> anyConnections = Arbitraries.of(vertices).set().ofMaxSize(degreeMax);
            Arbitrary<Integer> anyEdgeFlow = Arbitraries.integers().between(minEdgeFlow, maxEdgeFlow);
            return Combinators.combine(anyConnections, anyEdgeFlow)
                              .as((connections, edgeFlow) -> {
                                  connections.remove(vertix);
                                  return Tuple.of(vertix, connections, edgeFlow);
                              });
        });
    }
    
    @Property(tries = 10)
    @Report(Reporting.GENERATED)
    void checkNodes(@ForAll("nodes") Set<Tuple2<String, Set<String>>> nodes) {
        Statistics.label("nodes").collect(nodes.size());
    
        int maxDegree = nodes.stream().mapToInt(node -> node.get2().size()).max().orElse(0);
        Statistics.label("max degree").collect(maxDegree);
    }

Этот метод поставщика создает не список ребер, а набор вершин с их соединениями и потоком ребер. Конечно, одно можно трансформировать в другое.

В генераторах я стремлюсь минимизировать количество плоских карт, потому что плоские карты часто усложняют сжатие.

Тем не менее, создание графиков - это тема, по которой вы можете получить PHD, и некоторые люди ее имеют. Есть несколько стандартных способов создания графиков (например, https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model) и множество более сложных способов. Вы можете проверить несколько других ответов и ресурсов SO:

• Как сгенерировать случайные графики?
• Как сгенерировать случайные графики с помощью test.check?
• https://blog.finxter.com/how-to-generate-random-graphs-with-python/

Трансформировать эти подходы в код jqwik иногда легко, а иногда сложнее.

PS TypeUsage type, ArbitraryProvider.SubtypeProvider subtypeпараметр не обязателен. Добавляйте только те, которые вы используете в методе.