目前我正在使用:
@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;
})));
}
@Provide
Arbitrary<Graph<String,IntegerFlow>> graphs (TypeUsage type, ArbitraryProvider.SubtypeProvider subtype) {
return Combinators.withBuilder(() -> new GraphBuilder())
.use(this.edgeLists(type, subtype)).in((builder, edges) -> builder.withEdges(edges))
.build(builder -> builder.build());
}
@Property
void searchOrdersEqual (
@ForAll @From("edgeLists") List<Tuple.Tuple3<Integer,Integer,Integer>> edgeList,
@ForAll Random random) {
// for current in memory graph impl the search order in which augmenting paths are found will change
// if the order the edges are declared in changes. so if we see that one search order does not
// yield the same result as another, that the algo can not always be finding the max flow. if search
// orders return the same result, its still not guaranteed its finding max-flow, that will
// require additional tests. if this test fails, however, we definitely know that the algo is not
// always finding max flow.
int last = -1;
for (int i = 0; i < 10; i++) {
Collections.shuffle(edgeList, random);
Graph<String,IntegerFlow> graph = new GraphBuilder().withEdges(edgeList).build();
int next = new FordFulkerson<>(graph, graph.get(0), graph.get(graph.vertexCount()-1)).maxflow();
if (last < 0) last = next;
Assertions.assertThat(next).isEqualTo(last);
}
}
@Property
void validMinCutCandidate (@ForAll @From("graphs") Graph<String,IntegerFlow> graph) {
// given the testing constraints we are not going to find the actual min-cut, as that would involve
// re-implementation in some form. however we can check if its possible that there is a valid min-cut
// very easily. if we find that its not even possible that a valid min-cut is specified by a solution
// we know that the algorithm can not be finding the true max-flow.
Vertex<String,IntegerFlow> source = graph.get(0);
Vertex<String,IntegerFlow> sink = graph.get(graph.vertexCount() - 1);
MaxIntegerFlow<String,IntegerFlow> algorithm = new FordFulkerson<>(graph, source, sink);
int flow = algorithm.maxflow();
int possibleCut = 0;
for (Vertex<String,IntegerFlow> vertex : graph.vertices()) {
if (vertex == sink) continue;
for (Traverser<Edge<String,IntegerFlow>> trav = vertex.outgoing(); trav.moveNext();) {
if (trav.get().label().available() == 0) {
possibleCut += trav.get().label().flow();
}
}
}
Assertions.assertThat(possibleCut).isGreaterThanOrEqualTo(flow);
}
在这种情况下,我只是通过 id 指定源/目标顶点并添加一个流组件(可以是权重或任何数量的其他关联值)。该方案是从 [degree_min,degree_max] 制作一个度值列表,每个顶点一个,然后将该列表扩展为一个列表,其中每个源都重复度数次。一旦我有了那个列表,我就可以生成目标和标签序列并组合起来形成边缘。
这足以保证我有一个完整的顶点列表,并且每个顶点都有适当数量的传出边。但是,我认为这种方法不能很好地扩展以添加更现实/有用的约束。特别是考虑到可能采取的额外过滤和映射步骤,而且就目前而言,可能已经有太多了……
例如,我认为能够为每个节点的边缘创建任意值,然后加入任意值以生成边缘的整体列表可能会有所帮助,但我看不到在框架内有任何方法可以做到这一点(例如,Combine 是面向合并取自几个列表中的每一个的值,而不是加入列表)。
寻找任何改进这一点的建议。