Graph Definition

通用接口

规范定义，图中的算法会频繁使用图的定义

interface Graph {

    fun isEmpty(): Boolean {
        return getVertexesNum() == 0
    }

    fun isDirected(): Boolean

    fun isWeighted(): Boolean

    fun getVertexesNum(): Int = vertexIndex().size()

    fun getEdgeNum(): Int

    fun getVertexes(): List<Vertex> = vertexIndex().getVertexes()

    fun getEdges(): List<Edge>

    fun getEdge(from: String, to: String): Edge? {
        val fromV = vertexIndex().getVertex(from)
        val toV = vertexIndex().getVertex(to)
        if (fromV == null || toV == null) {
            return null
        }
        return getEdge(fromV.id, toV.id)
    }

    fun getEdge(from: Int, to: Int): Edge?

    fun connect(from: String, to: String) = connect(from, to, DEFAULT_UNWEIGHTED_VALUE)

    fun connect(from: String, to: String, weight: Double)

    fun adjacentEdges(name: String): List<Edge> {
        return vertexIndex().getVertex(name)?.let { vertex ->
            adjacentEdges(vertex.id)
        } ?: emptyList()
    }

    fun adjacentEdges(id: Int): List<Edge>

    fun clear()

    fun showGraph()

    fun vertexIndex(): VertexIndex

    // 获取邻接矩阵
    fun getAdjacencyMatrix(): Array<Array<Double?>>? = null

    // 获取邻接表
    fun getAdjacencyList(): Array<TreeMap<Int, Double>>? = null

}

图的实现

稀疏图主要用邻接表实现，稠密图主要用邻接矩阵实现

稀疏图

class SparseGraph : Graph {

    companion object {
        val log = getLogger(DenseGraph::class.java)
    }

    private val directed: Boolean
    private val weighted: Boolean

    private val vertexIndex = VertexIndex()

    private var adjacencyList: Array<TreeMap<Int, Double>> = Array(0) { TreeMap() }
    private var edgesCount: Int = 0

    constructor(directed: Boolean, weighted: Boolean) {
        this.directed = directed
        this.weighted = weighted
    }

    override fun isDirected(): Boolean = this.directed

    override fun isWeighted(): Boolean = this.weighted

    override fun getEdgeNum(): Int = this.edgesCount

    override fun getEdges(): List<Edge> {
        return adjacencyList.flatMapIndexed { from, edges ->
            if (edges.isEmpty()) {
                emptyList() // 返回空列表而不是 null
            } else {
                val fromV = vertexIndex.getVertex(from)!!
                edges.map { (toId, weight) ->
                    val toV = vertexIndex.getVertex(toId)!!
                    Edge(from = fromV, to = toV, weight = weight)
                }
            }
        }
    }

    override fun getEdge(from: Int, to: Int): Edge? {
        if (from < 0 || to < 0 || from >= vertexIndex.size() || to >= vertexIndex.size()) {
            return null
        }
        if (from == to) {
            return null
        }
        return adjacencyList[from].let {
            it[to]?.let { weight ->
                val fromVertex = vertexIndex.getVertex(from)!!
                val toVertex = vertexIndex.getVertex(to)!!
                Edge(from = fromVertex, to = toVertex, weight = weight)
            }
        }
    }

    override fun connect(from: String, to: String, weight: Double) {
        if (from.isBlank() || to.isBlank()) {
            throw IllegalArgumentException("Vertex names cannot be empty")
        }

        if (from == to) {
            return
        }
        this.connect(
            vertexIndex.createVertex(from).id,
            vertexIndex.createVertex(to).id,
            weight,
            this.directed
        )
    }

    private fun connect(from: Int, to: Int, weight: Double, directed: Boolean) {
        this.expand(maxOf(from, to) + 1)

        val edges = adjacencyList[from]
        val isNewEdge = !edges.containsKey(to)

        if (!isNewEdge) {
            log.warn("Edge from $from to $to already exists, updating weight to $weight")
            this.edgesCount--
        }

        edges[to] = weight
        this.edgesCount++
        if (!directed) {
            this.connect(to, from, weight, true)
        }

    }

    private fun expand(size: Int) {
        if (size > adjacencyList.size) {
            val newAdjList = Array(size) { TreeMap<Int, Double>() }
            System.arraycopy(adjacencyList, 0, newAdjList, 0, adjacencyList.size)
            this.adjacencyList = newAdjList
        }
    }

    override fun adjacentEdges(id: Int): List<Edge> {
        if (id < 0 || id >= vertexIndex.size()) {
            return emptyList()
        }
        val fromVertex = vertexIndex.getVertex(id)!!
        val neighbors = adjacencyList[id]
        return neighbors.map { (toId, weight) ->
            val toVertex = vertexIndex.getVertex(toId) ?: return@map null
            Edge(from = fromVertex, to = toVertex, weight = weight)
        }.filterNotNull()
    }

    override fun clear() {
        vertexIndex.clear()
        adjacencyList = Array(0) { TreeMap() }
        edgesCount = 0
    }

    override fun showGraph() {
        println("Graph: ${if (directed) "Directed" else "Undirected"}, ${if (weighted) "Weighted" else "Unweighted"}")
        println("Vertices: ${vertexIndex.size()}")
        println("Edges: $edgesCount")

        // 打印邻接表
        println("\nAdjacency List:")
        val startFmt = "%s(%d) : "
        val toFmt = "%s(%d) -- %.2f -> %s(%d)   "

        adjacencyList.forEachIndexed { from, map ->
            if (map.isEmpty()) {
                return@forEachIndexed
            }
            val fromV = vertexIndex.getVertex(from)!!
            print(startFmt.format(fromV.name, fromV.id))
            map.forEach { (toId, weight) ->
                val toV = vertexIndex.getVertex(toId)!!
                print(toFmt.format(fromV.name, fromV.id, weight, toV.name, toId))
            }
            println()
        }

    }

    override fun vertexIndex(): VertexIndex = this.vertexIndex

    override fun getAdjacencyList(): Array<TreeMap<Int, Double>> = this.adjacencyList

}

稠密图

class DenseGraph : Graph {

    companion object {
        val log = getLogger(DenseGraph::class.java)
    }

    private val directed: Boolean
    private val weighted: Boolean

    private var adjacencyMatrix: Array<Array<Double?>>

    private val vertexIndex = VertexIndex()
    private var edgesCount: Int = 0

    constructor(directed: Boolean, weighted: Boolean) {
        this.directed = directed
        this.weighted = weighted
        adjacencyMatrix = Array(2) { Array(2) { null } }
    }

    override fun isDirected(): Boolean = this.directed

    override fun isWeighted(): Boolean = this.weighted

    override fun getEdgeNum(): Int = this.edgesCount

    override fun getEdges(): List<Edge> {
        return if (isEmpty()) {
            emptyList()
        } else {
            val edges = mutableListOf<Edge>()
            for (i in 0 until adjacencyMatrix.size) {
                for (j in 0 until adjacencyMatrix.size) {
                    adjacencyMatrix[i][j]?.let { weight ->
                        val fromV = vertexIndex.getVertex(i)!!
                        val toV = vertexIndex.getVertex(j)!!
                        edges.add(Edge(from = fromV, to = toV, weight = weight))
                    }
                }
            }
            edges
        }
    }

    override fun getEdge(from: Int, to: Int): Edge? {
        if (from < 0 || to < 0 || from >= vertexIndex.size() || to >= vertexIndex.size()) {
            return null
        }

        if (from == to) {
            return null // No self-loops in this implementation
        }

        val weight = adjacencyMatrix[from][to]
        return if (weight == null) {
            null
        } else {
            Edge(
                from = vertexIndex.getVertex(from)!!,
                to = vertexIndex.getVertex(to)!!,
                weight = weight
            )
        }
    }

    override fun connect(from: String, to: String, weight: Double) {
        if (from.isBlank() || to.isBlank()) {
            throw IllegalArgumentException("Vertex names cannot be empty")
        }
        if (from == to) {
            return
        }
        val fromV = vertexIndex.createVertex(from)
        val toV = vertexIndex.createVertex(to)

        this.expand(vertexIndex.size())
        this.connect(fromV.id, toV.id, weight, directed = this.directed)
    }

    private fun expand(size: Int) {
        if (size > adjacencyMatrix.size) {
            val newSize = size
            val newMatrix = Array(newSize) { Array<Double?>(newSize) { null } }
            adjacencyMatrix.forEachIndexed { i, row ->
                System.arraycopy(row, 0, newMatrix[i], 0, row.size)
            }
            adjacencyMatrix = newMatrix
        }
    }

    private fun connect(from: Int, to: Int, weight: Double, directed: Boolean) {
        adjacencyMatrix[from][to]?.let { existingWeight ->
            log.debug("Edge from $from to $to already exists with weight $existingWeight, updating to $weight")
            edgesCount--
        }
        adjacencyMatrix[from][to] = weight
        edgesCount++
        if (!directed) {
            this.connect(to, from, weight, true)
        }
    }

    override fun adjacentEdges(id: Int): List<Edge> {
        if (isEmpty() || id < 0 || id >= vertexIndex.size()) {
            return emptyList()
        }
        val fromV = vertexIndex.getVertex(id)!!
        return adjacencyMatrix[id].mapIndexedNotNull { toIndex, weight ->
            weight?.let {
                val toV = vertexIndex.getVertex(toIndex)!!
                Edge(from = fromV, to = toV, weight = it)
            }
        }
    }

    override fun clear() {
        vertexIndex.clear()
        edgesCount = 0
        adjacencyMatrix = Array(2) { Array(2) { null } }
    }

    override fun showGraph() {
        println("Graph: ${if (directed) "Directed" else "Undirected"}, ${if (weighted) "Weighted" else "Unweighted"}")
        println("Vertices: ${vertexIndex.size()}")
        println("Edges: $edgesCount") //

        // 先打印顶点信息
        println("Vertex Information:")
        vertexIndex.getVertexes().forEach(::println)

        // 打印 matrix 并在第一行和第一列显示顶点信息
        println("\nAdjacency Matrix:")

        // 打印顶点ID作为列标题
        print("      ") // 留出行标题的空间
        for (i in 0 until vertexIndex.size()) {
            val v = vertexIndex.getVertex(i)!!
            print(beautify("${v.id}:${v.name}", 5))
        }
        println()

        // 打印矩阵内容
        for (i in 0 until vertexIndex.size()) {
            val v = vertexIndex.getVertex(i)!!
            print(beautify("${v.id}:${v.name}", 5))

            for (j in 0 until vertexIndex.size()) {
                val element = adjacencyMatrix[i][j]
                if (element != null) {
                    print(beautify(element.toString(), 5))
                } else {
                    print(beautify("nil", 5))
                }
            }
            println()
        }
    }

    override fun vertexIndex(): VertexIndex = this.vertexIndex

    override fun getAdjacencyMatrix(): Array<Array<Double?>>? = this.adjacencyMatrix

}