Skip to content

Graph's Algorithms

图中的算法

图的遍历

无向图求联通分量

有向无环图的拓扑排序

无向图的最小生成树

单源最短路径

环路分析

图的基础算法校验

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
abstract class GraphCompute {
    protected val graph: Graph

    constructor(graph: Graph) {
        this.graph = graph
    }

    fun checkEmpty(): GraphCompute {
        require(!graph.isEmpty()) {
            "Graph is empty"
        }
        return this
    }

    fun checkDirected(expectedDirected: Boolean): GraphCompute {
        require(graph.isDirected() == expectedDirected) {
            "Graph is not ${if (expectedDirected) "directed" else "undirected"}"
        }
        return this
    }

    fun checkWeighted(expectedWeighted: Boolean): GraphCompute {
        require(graph.isWeighted() == expectedWeighted) {
            "Graph is not ${if (expectedWeighted) "weighted" else "unweighted"}"
        }
        return this
    }

    fun checkVertex(name: String, required: Boolean): Vertex {
        return graph.vertexIndex().getVertex(name) ?: if (required) {
            throw IllegalArgumentException("Vertex '$name' not found")
        } else {
            throw NoSuchElementException("Vertex '$name' not found")
        }
    }

}