JGraphT：Blossom/KolmogorovWeightedPerfectMatching 算法中的无限循环

Question

我正在尝试使用 JGraphT 中的 Blossom 算法在一组团队之间创建配对，使用成本基于他们是否已经互相比赛以及他们的相对点差是多少（即类似瑞士）。但是在每 5000 次左右的情况下，我得到一个似乎是无限循环的东西（或者至少，应该花费 1/1000 秒的东西至少需要十个小时，这对我来说就像一个无限循环）。

这是调用 KolmogorovWeightedPerfectMatching 的（Kotlin）方法：

    fun blossomScheduleWeek(div: Division): List<Array<Team>> {
        // Assume team list is sorted by contract
        val graph: Graph<Team, DefaultWeightedEdge> = SimpleWeightedGraph(DefaultWeightedEdge::class.java)

        // Function for calculating match cost between two teams
        fun matchCost(teamA: Team, teamB: Team): Double =
            // Code here to calculate two team's match cost

        // Add vertices for each team
        for (team in div.teamArray()) {
            graph.addVertex(team)
        }

        // Add edges for every two unique teams that haven't played already
        for (team in div.teamArray()) {
            for (opponent in div.teamArray()) {
                if (team == opponent) continue
                if (graph.containsEdge(team, opponent)) continue
                if (team.hasFaced(opponent)) continue
                Graphs.addEdge(graph, team, opponent, matchCost(team, opponent))
            }
        }

        // Do matching algorithm
        val algorithm = KolmogorovWeightedPerfectMatching(graph, ObjectiveSense.MINIMIZE)
        return algorithm.matching.edges.map { arrayOf(graph.getEdgeSource(it), graph.getEdgeTarget(it)) }
    }

这是我的 JVM 线程转储。

"main@1" prio=5 tid=0x1 nid=NA runnable
  java.lang.Thread.State: RUNNABLE
      at org.jgrapht.alg.matching.blossom.v5.BlossomVDualUpdater.updateDuals(BlossomVDualUpdater.java:110)
      at org.jgrapht.alg.matching.blossom.v5.KolmogorovWeightedPerfectMatching.lazyComputeWeightedPerfectMatching(KolmogorovWeightedPerfectMatching.java:469)
      at org.jgrapht.alg.matching.blossom.v5.KolmogorovWeightedPerfectMatching.getMatching(KolmogorovWeightedPerfectMatching.java:279)
      at com.vibeisveryo.tournamentsim.tournament.Swiss.blossomScheduleWeek(Swiss.kt:186)
      at com.vibeisveryo.tournamentsim.Main$main$1.invoke(Main.kt:27)
      at com.vibeisveryo.tournamentsim.Main$main$1.invoke(Main.kt:27)
      at com.vibeisveryo.tournamentsim.tournament.Swiss.runMatches(Swiss.kt:55)
      at com.vibeisveryo.tournamentsim.measurement.Measurement$measureDistortions$3.invoke(Measurement.kt:40)
      at com.vibeisveryo.tournamentsim.measurement.Measurement$measureDistortions$3.invoke(Measurement.kt:36)
      at com.vibeisveryo.tournamentsim.util.MeasureIterative.measureIterative(MeasureIterative.kt:25)
      at com.vibeisveryo.tournamentsim.measurement.Measurement.measureDistortions(Measurement.kt:36)
      at com.vibeisveryo.tournamentsim.Main.main(Main.kt:27)