Skip to content

Instantly share code, notes, and snippets.

@maksmakuta

maksmakuta/pathwalker_v3.kt

Last active October 29, 2023 19:42
Show Gist options
  • Save maksmakuta/e5916c13a222b650d096ba24f2a6f6d3 to your computer and use it in GitHub Desktop.
Save maksmakuta/e5916c13a222b650d096ba24f2a6f6d3 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. maksmakuta revised this gist Oct 29, 2023. 1 changed file with 11 additions and 1 deletion.
    12 changes: 11 additions & 1 deletion pathwalker_v3.kt
    View file
    Original file line number Diff line number Diff line change
    @@ -86,6 +86,7 @@ fun gen(size : Int,poss : Int,weights : IntRange,seed : Long = 0L) : Graph{
    }

    fun walker(graph: Graph,start : Int, end : Int){
    val pathData = IntArray(graph.size+1) { -1 }
    val distances = IntArray(graph.size+1) { Int.MAX_VALUE }
    distances[start] = 0

    @@ -104,17 +105,26 @@ fun walker(graph: Graph,start : Int, end : Int){
    if (newDistance < distances[otherVertex]) {
    distances[otherVertex] = newDistance
    pq.add(Pair(otherVertex, newDistance))
    pathData[otherVertex] = currentVertex

    }
    }
    }
    }

    println("time : ${t.inWholeMilliseconds} ms")
    println("time : ${t.inWholeNanoseconds} ns")

    if (distances[end] == Int.MAX_VALUE) {
    println("No path from $start to $end found.")
    } else {
    val path = mutableListOf<Int>()
    var currentVertex = end
    while (currentVertex != -1) {
    path.add(currentVertex)
    currentVertex = pathData[currentVertex]
    }
    path.reverse()
    println("path : ${path.joinToString ("-"){ it.toString() }}")
    println("Shortest distance from vertex $start to vertex $end: ${distances[end]}")
    }
    }
  2. maksmakuta created this gist Oct 29, 2023.
    128 changes: 128 additions & 0 deletions pathwalker_v3.kt
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,128 @@
    import java.io.File
    import java.util.*
    import kotlin.random.Random
    import kotlin.random.nextInt
    import kotlin.time.measureTime

    data class Edge(
    val a : Int,
    val b : Int,
    val w : Int
    ){
    fun print(){
    println("$a -{$w}- $b")
    }

    fun str() = "$a $b $w\n"

    }

    class Graph(val size : Int){

    private val data = arrayListOf<Edge>()

    fun add(edge: Edge){
    if(data.find { it.a == edge.a && it.b == edge.b } == null &&
    data.find { it.a == edge.b && it.b == edge.a } == null)
    data.add(edge)
    }

    fun neighbours(i : Int) : List<Edge>{
    val t = data.filter { it.b == i }.map { Edge(it.b,it.a,it.w) }
    return data.filter { it.a == i } + t
    }

    fun save(name : String){
    val f = File(name)
    f.writeText("$size ${data.size}\n")
    data.forEach {
    f.appendText(it.str())
    }
    }

    fun print(){
    println("size -> $size")
    println("cons -> ${data.size}")
    println("cons : ")
    data.forEach {
    it.print()
    }
    }
    }

    fun gen(size : Int,poss : Int,weights : IntRange,seed : Long = 0L) : Graph{
    val rand = Random(seed)

    fun newEdge(i : Int) : Edge{
    val dest = rand.nextInt(1..size)
    val w = rand.nextInt(weights)
    return if(dest != i){
    Edge(i,dest,w)
    }else{
    newEdge(i)
    }
    }

    val graph = Graph(size)
    val subList = mutableListOf<Edge>()
    for(i in 1..size) {
    var count = 0
    for (j in 1..size) {
    if(rand.nextInt(1,101) < poss && i != j){
    val w = rand.nextInt(weights)
    subList.add(Edge(i,j,w))
    count++
    }
    }
    if(count == 0){
    subList.add(newEdge(i))
    }
    subList.sortedBy { it.w }.forEach {
    graph.add(it)
    }
    subList.clear()
    }
    return graph
    }

    fun walker(graph: Graph,start : Int, end : Int){
    val distances = IntArray(graph.size+1) { Int.MAX_VALUE }
    distances[start] = 0

    val pq = PriorityQueue<Pair<Int, Int>>(compareBy { it.second })
    pq.add(Pair(start, 0))

    val t = measureTime {
    while (pq.isNotEmpty()) {
    val (currentVertex, currentDistance) = pq.poll()
    if (currentDistance > distances[currentVertex]) {
    continue
    }
    for (neighbor in graph.neighbours(currentVertex)) {
    val otherVertex = if (neighbor.a == currentVertex) neighbor.b else neighbor.a
    val newDistance = currentDistance + neighbor.w
    if (newDistance < distances[otherVertex]) {
    distances[otherVertex] = newDistance
    pq.add(Pair(otherVertex, newDistance))
    }
    }
    }
    }

    println("time : ${t.inWholeMilliseconds} ms")
    println("time : ${t.inWholeNanoseconds} ns")

    if (distances[end] == Int.MAX_VALUE) {
    println("No path from $start to $end found.")
    } else {
    println("Shortest distance from vertex $start to vertex $end: ${distances[end]}")
    }
    }

    fun main() {
    val seed = 0L//Random.nextLong()
    println("seed : $seed")
    val graph = gen(50,10,100..1000,seed)
    graph.save("/tmp/test0.txt")
    walker(graph,1,50)
    }