Advertisement
Guest User

Dijkstra2

a guest
Nov 17th, 2019
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Kotlin 3.71 KB | None | 0 0
  1. package dijkstra
  2.  
  3. import java.util.*
  4. import java.util.concurrent.Phaser
  5. import java.util.concurrent.atomic.AtomicInteger
  6. import java.util.concurrent.locks.Lock
  7. import java.util.concurrent.locks.ReentrantLock
  8. import kotlin.Comparator
  9. import kotlin.collections.ArrayList
  10. import kotlin.concurrent.thread
  11.  
  12. var activeNodes = AtomicInteger(0)
  13.  
  14. private val NODE_DISTANCE_COMPARATOR = Comparator<Node> { o1, o2 -> Integer.compare(o1!!.distance, o2!!.distance) }
  15.  
  16. class MultiPriorityQueue(size: Int, comparator: Comparator<Node>) {
  17.     private val N: Int = size;
  18.  
  19.     private val _locks = List(2 * N) { ReentrantLock() }
  20.     val locks: List<Lock> = ArrayList(_locks)
  21.  
  22.     private val _queues = List(2 * N) { PriorityQueue<Node>(comparator) }
  23.     val queues: List<PriorityQueue<Node>> = ArrayList(_queues)
  24.  
  25.     fun poll(): Node? {
  26.         val i = (0 until (2 * N - 1)).random()
  27.         val j = (i + 1 until (2 * N)).random()
  28.         val q1 = queues[i]
  29.         val q2 = queues[j]
  30.  
  31.         val lock1 = locks[i]
  32.         val lock2 = locks[j]
  33.         var removed: Node? = null
  34.  
  35.         if (lock1.tryLock() && lock2.tryLock()) {
  36.  
  37.             val node1 = q1.peek()
  38.             val node2 = q2.peek()
  39.  
  40.             if (node1 == null) {
  41.                 removed = node2
  42.                 q2.poll()
  43.             } else {
  44.                 if (node2 == null || node1.distance < node2.distance) {
  45.                     removed = node1
  46.                     q1.poll()
  47.                 } else {
  48.                     removed = node2
  49.                     q2.poll()
  50.                 }
  51.             }
  52.  
  53.             lock1.unlock()
  54.             lock2.unlock()
  55.         }
  56.         return removed
  57.     }
  58.  
  59.  
  60.     fun add(elem: Node) {
  61.  
  62.         while (true) {
  63.             val i: Int = (Random()).nextInt(2 * N)
  64.             val q = queues[i]
  65.             val curLock: Lock = locks[i]
  66.  
  67.             if (curLock.tryLock()) {
  68.                 q.add(elem)
  69.                 curLock.unlock();
  70.                 break
  71.             }
  72.         }
  73.     }
  74. }
  75.  
  76.  
  77. // Returns `Integer.MAX_VALUE` if a path has not been found.
  78. fun shortestPathParallel(start: Node) {
  79.     val workers = Runtime.getRuntime().availableProcessors()
  80.  
  81.     // The distance to the start node is `0`
  82.     start.distance = 0
  83.     // Create a priority (by distance) queue and add the start node into it
  84.  
  85.     val q = MultiPriorityQueue(workers, NODE_DISTANCE_COMPARATOR) // TODO replace me with a multi-queue based PQ!
  86.     q.add(start)
  87.     activeNodes.incrementAndGet()
  88.  
  89.     // Run worker threads and wait until the total work is done
  90.     val onFinish = Phaser(workers + 1) // `arrive()` should be invoked at the end by each worker
  91.     repeat(workers) {
  92.         thread {
  93.             while (true) {
  94.                 // TODO Write the required algorithm here,
  95.                 // TODO break from this loop when there is no more node to process.
  96.                 // TODO Be careful, "empty queue" != "all nodes are processed".
  97.                 val cur: Node = q.poll()
  98.                         ?: if (activeNodes.get() > 0) continue else break;
  99.  
  100.                 for (e in cur.outgoingEdges) {
  101.                     while (e.to.distance > cur.distance + e.weight) {
  102.                         val initDist: Int = e.to.distance
  103.                         val dist: Int = cur.distance + e.weight
  104.                         if (initDist > dist && e.to.casDistance(initDist, dist)) {
  105.                             q.add(e.to)
  106.                             activeNodes.incrementAndGet()
  107.                             break
  108.                         }
  109.                     }
  110.                 }
  111.                 activeNodes.decrementAndGet()
  112.             }
  113.             onFinish.arrive()
  114.         }
  115.     }
  116.     onFinish.arriveAndAwaitAdvance()
  117. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement