Created
October 29, 2023 07:03
-
-
Save maksmakuta/0513b691a8be1c0f7e95a3fc163d45d6 to your computer and use it in GitHub Desktop.
Upgraded version of https://gist.github.com/maksmakuta/941eee6b00b451b24033232d989a58fa
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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") | |
| } | |
| } | |
| 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 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){ | |
| println() | |
| if (start in 0..graph.size && end in 0..graph.size && start != end) { | |
| val list = mutableListOf<Int>() | |
| var total = 0 | |
| var curr = start | |
| var comps = 0 | |
| val t = measureTime { | |
| while (true) { | |
| list.add(curr) | |
| val neighbours = graph.neighbours(curr) | |
| if (neighbours.isNotEmpty()) { | |
| var dist = Int.MAX_VALUE | |
| var t = 0 | |
| for (i in neighbours.indices) { | |
| val n = neighbours[i] | |
| comps++ | |
| if(n.b !in list) { | |
| if ((n.b == end || n.w < dist) && t != end) { | |
| println(" ${n.a} -[${n.w}]- ${n.b} ") | |
| t = n.b | |
| dist = n.w | |
| }else{ | |
| break | |
| } | |
| } | |
| } | |
| curr = t | |
| if (dist != Int.MAX_VALUE) | |
| total += dist | |
| } | |
| if (curr == end) { | |
| list.add(end) | |
| println("found path") | |
| break | |
| } | |
| } | |
| println() | |
| println(list.joinToString("-") { it.toString() }) | |
| println("distance : $total") | |
| println("moves : ${list.size - 1}") | |
| println("comps : $comps") | |
| } | |
| println("time : ${t.inWholeMilliseconds} ms") | |
| println("time : ${t.inWholeNanoseconds} ns") | |
| } else { | |
| when (start) { | |
| end -> println("Error: start == end") | |
| !in 0..<graph.size -> println("Error: start is out of graph") | |
| else -> println("Error: end is out of graph") | |
| } | |
| } | |
| } | |
| fun main() { | |
| val seed = 8714362708517061972L//Random.nextLong() | |
| println("seed : $seed") | |
| val graph = gen(50,5,100..1000,seed) | |
| //graph.print() | |
| walker(graph,1,50) | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment