maksmakuta · October 29, 2023 19:42
diff --git a/pathwalker_v3.kt b/pathwalker_v3.kt
 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 pathData = IntArray(graph.size+1) { -1 }
    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))
                    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]}")
    }
 }

 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)
 }
	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 pathData = IntArray(graph.size+1) { -1 }
	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))
	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]}")
	}
	}

	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)
	}