SimplifyGraph.kt

data class Vertex(
    val id: String,
)

data class Edge(
    val vertexA: Vertex,
    val vertexB: Vertex
) {
    val vertices: List<Vertex> = listOf(vertexA, vertexB)
    
    override fun toString(): String {
        return "Edge(${vertices[0].id} <=> ${vertices[1].id})"
    }
}

data class Graph(
    val vertices: List<Vertex>,
    val edges: List<Edge>,
)

fun simplifyGraph(inputGraph: Graph): Graph {
    val visitedVertices = mutableListOf<Vertex>()
    val usedEdges = mutableListOf<Edge>()

    val edgeMap = inputGraph.edges.flatMap { edge ->
        edge.vertices.map { Pair(it, edge) }
    }.groupBy(
        { it.first },
        { it.second }
    )

    val stack: ArrayDeque<Pair<Edge?, Vertex>> = ArrayDeque(
        listOf(
            Pair(null, inputGraph.vertices.first())
        )
    )

    while (!stack.isEmpty()) {
        val currentPair = stack.removeLast()
        val currentVertex = currentPair.second
        if (!visitedVertices.contains(currentVertex)) {
            visitedVertices.add(currentVertex)
            currentPair.first?.let { usedEdges.add(it) }

            edgeMap[currentVertex]?.forEach { currentEdge ->
                val unvisitedVertex = currentEdge.vertices.filter { !visitedVertices.contains(it) }
                    .firstOrNull()
                unvisitedVertex?.let {
                    stack.add(Pair(currentEdge, it))
                }
            }
        }
    }
    
    return Graph(
        visitedVertices,
        usedEdges
    )
}

fun main(args: Array<String>) {
    val vertA = Vertex("A")
    val vertB = Vertex("B")
    val vertC = Vertex("C")
    val vertD = Vertex("D")
    val vertE = Vertex("E")

    val graph = Graph(
        listOf(vertA, vertB, vertC, vertD, vertE),
        listOf(
            Edge(vertA, vertB),
            Edge(vertB, vertC),
            Edge(vertC, vertD),
            Edge(vertD, vertA),
            Edge(vertA, vertE),
            Edge(vertB, vertE),
            Edge(vertC, vertE),
            Edge(vertD, vertE),
        )
    )

    println(
        "Original graph: $graph"
    )

    println(
        "Simplified graph: ${simplifyGraph(graph)}"
    )
}