1

我在 Kotlin 中有以下有向图的定义。（我还在学习 Kotlin，所以请原谅任何缺点。总是欢迎改进和建议。）我的目标是有一个方法，reverse它保持顶点和循环，但交换其他边的方向。

// We use an edge list because it makes it the easiest to swap.
data class ReversibleDirectedGraph<T>(val vertices: Set<T>, val edgeList: List<Pair<T,T>>) {

    // This should be a self-inverting function.
    fun reverse(): ReversibleDirectedGraph<T> {
        // Make sure all vertices in edgeList are in vertices.
        val allVertices = edgeList.flatMap { it.toList() }
        require(allVertices.all { it in vertices }) { "Illegal graph specification" }

        // Swap the edges.
        val newEdgeList = edgeList.map { it.second to it.first }
        return ReversibleDirectedGraph(allVertices.toSet(), newEdgeList)
    }
}

fun main() {
    // Example test: works correctly. Double edge reversal results in original graph.
    val g = ReversibleDirectedGraph(setOf(0, 1, 2, 3),
        listOf(0 to 1, 2 to 1, 3 to 2, 3 to 0, 1 to 3))
    println(g)
    val gr = g.reverse()
    println(gr)
    val grr = gr.reverse()
    println(grr)
    println(grr == g)
}

我想使用基于属性的测试来使用 KotinTest 测试此代码，但我在构建它以正确生成无向图的随机样本时遇到了麻烦。如果我能做到这一点，我可以将边缘方向反转两次，然后确保实现原始图形。

我熟悉Gen.list,Gen.choose等，但我似乎无法将这些部分组合在一起以获得最终产品，即随机无向图。

我已经完成了这一点，但这显然缺少部分，我希望有人能够提供帮助。我怀疑我可以在 Scala 中做到这一点，因为我在那里有更多的经验，但我决心学习 Kotlin。最终，大致如下：

class ReversibleDirectedGraphTest: StringSpec() {
    init {
        "reversibleDirectedGraphTest" {
            forAll { g: ReversibleDirectedGraph<Int> ->
                assertEqual(g.reverse().reverse() == g) }
            }
        }
    }
}

任何帮助/建议将不胜感激。谢谢！

4

1 回答 1

0

我最终遵循了@monkjack 的建议并创建了自己的Gen. 我必须明确地提供Gen给.forAlltry...catch

class GraphGen: Gen<ReversibleDirectedGraph<Int>> {
    override fun constants() =
        listOf(
            ReversibleDirectedGraph(emptySet(), emptySet()),
            ReversibleDirectedGraph(setOf(0), setOf(0 to 0)),
            ReversibleDirectedGraph(setOf(0, 1), emptySet()),
            ReversibleDirectedGraph(setOf(0, 1), setOf(0 to 1))
        )

    override fun random(): Sequence<ReversibleDirectedGraph<Int>> = generateSequence {
        val vertexGen = Gen.choose(0, 20)
        val vertices = Gen.set(vertexGen).random().first()
        val vertexList = vertices.toList()
        val edgeGen = Gen.set(Gen.pair(Gen.from(vertexList), Gen.from(vertexList))).random()

        // On rare occasions, this throws an exception with origin and bound, probably due
        // to the number of sets. In those cases, we use an emptySet instead as a placeholder.
        val edges = try { edgeGen.first() } catch (e: IllegalArgumentException) { null }
        ReversibleDirectedGraph(vertices, edges?: emptySet())
    }
}

class ReversibleDirectedGraphTest: StringSpec() {
    init {
        "reversibleDirectedGraphTest" {
            forAll(GraphGen()) { g -> g.reverse().reverse() == g }
        }
    }
}
于 2019-11-11T21:54:30.227 回答