寻求在jqwik属性测试框架中生成图边列表的更优方法

现有实现优化建议 #

1. 实现逐顶点生成边再合并的需求 #

你需要的列表拼接逻辑不需要依赖Combine组件的固定值组合，通过Arbitrary.sequence即可实现，逐顶点生成边的结构扩展性也更强：

@Provide
Arbitrary<List<Tuple.Tuple3<Integer,Integer,Integer>>> edgeLists(TypeUsage type, ArbitraryProvider.SubtypeProvider subtype) {
    // 先解析参数，抽成单独的参数对象更清晰
    FlowGenConfig config = parseConfig(type);
    
    // 为每个顶点生成对应出度的边列表Arbitrary
    List<Arbitrary<List<Tuple.Tuple3<Integer,Integer,Integer>>>> perVertexEdges = IntStream.rangeClosed(1, config.vertices)
        .mapToObj(sourceId -> {
            // 先生成当前顶点的出度
            Arbitrary<Integer> degree = Arbitraries.integers().between(config.degreeMin, config.degreeMax);
            // 生成对应数量的目标顶点+流量，此处可直接加禁止自环、禁止重复边等约束
            return degree.flatMap(d -> Combinators.combine(
                Arbitraries.integers().between(1, config.vertices).filter(v -> v != sourceId).list().ofSize(d),
                Arbitraries.integers().between(config.minEdgeFlow, config.maxEdgeFlow).list().ofSize(d)
            ).as((targets, flows) -> IntStream.range(0, d)
                .mapToObj(i -> Tuple.of(sourceId, targets.get(i), flows.get(i)))
                .toList()
            ));
        }).toList();
    
    // 合并所有顶点的出边列表生成全局边列表
    return Arbitraries.sequence(perVertexEdges)
        .map(listOfLists -> listOfLists.stream().flatMap(List::stream).toList());
}

// 把参数解析抽成单独方法，逻辑更清晰
private FlowGenConfig parseConfig(TypeUsage type) {
    int vertices = 10;
    int degreeMin = 1;
    int degreeMax = 4;
    int minEdgeFlow = 1;
    int maxEdgeFlow = 10;
    for (Annotation a : type.getAnnotations()) {
        if (a instanceof MaxFlowParameters params) {
            vertices = Math.max(1, params.vertices());
            degreeMin = Math.max(1, params.degree_min());
            degreeMax = Math.min(vertices, Math.max(degreeMin, params.degree_max()));
            minEdgeFlow = Math.min(vertices, Math.max(0, params.min_edge_flow()));
            maxEdgeFlow = Math.min(vertices, Math.max(minEdgeFlow, params.max_edge_flow()));
        }
    }
    return new FlowGenConfig(vertices, degreeMin, degreeMax, minEdgeFlow, maxEdgeFlow);
}

// 单独存参数的record，Java 16以下版本替换为普通类即可
record FlowGenConfig(int vertices, int degreeMin, int degreeMax, int minEdgeFlow, int maxEdgeFlow) {}

这种结构后续新增约束非常方便，只需要修改对应顶点的边生成逻辑即可，不需要调整全局拼接逻辑。

2. 简化现有嵌套flatMap #

如果要保留你原来的生成逻辑，也可以用Combinators.combine替换三层嵌套flatMap，提升可读性：

return Arbitraries.integers().between(degree_min, degree_max).list().ofSize(vertices).map(expand)
    .flatMap(sources -> Combinators.combine(
        Arbitraries.integers().between(1, num_vertices).list().ofSize(sources.size()),
        Arbitraries.integers().between(the_min_edge_flow, the_max_edge_flow).list().ofSize(sources.size())
    ).as((targets, flows) -> IntStream.range(0, sources.size())
        .mapToObj(i -> Tuple.of(sources.get(i), targets.get(i), flows.get(i)))
        .toList()
    ));

3. 测试用例优化 #

• searchOrdersEqual方法中Collections.shuffle会直接修改输入的edgeList，每次打乱都基于上一次的结果，建议每次循环都复制一份原列表再打乱，测试逻辑更严谨：

List<Tuple.Tuple3<Integer,Integer,Integer>> original = new ArrayList<>(edgeList);
for (int i = 0; i < 10; i++) {
    List<Tuple.Tuple3<Integer,Integer,Integer>> shuffled = new ArrayList<>(original);
    Collections.shuffle(shuffled, random);
    Graph<String,IntegerFlow> graph = new GraphBuilder().withEdges(shuffled).build();
    // 剩余校验逻辑不变
}

• validMinCutCandidate的割值计算可以用stream简化，减少嵌套循环的出错概率。

4. 复杂约束扩展建议 #

如果需要支持弱连通、无环等更复杂的图结构约束，可以在边列表生成完成后加全局filter，或者自定义生成器实现，比在生成过程中硬编码约束要灵活很多。

内容的提问来源于stack exchange，提问作者FeralWhippet