travering salesman problem : greedy with scala

_log

(List((7,6), (1,7), (9,1), (2,9), (4,2), (3,4), (5,3), (8,5), (0,8)),2812.8078290354997)
[process time] : 22ms

Tsp.scala

import scala.io.Source

object City {
	private def randoms(m:Int) : Stream[Int] = Stream.cons(scala.util.Random.nextInt(m), randoms(m))
	def create(count:Int)(implicit max:Int) = randoms(max).zip(randoms(max)).take(count).zipWithIndex.map(x => x._2 -> x._1).toMap
}
implicit class CsvConverter(filepath: String) {
	//Map[Int,(Int,Int)] : Index -> (X, Y)
	def toCities = Source.fromFile(filepath).getLines.toSeq.map(x => x.split(",")).filter(_.size == 2).map(x => (x(0).toInt, x(1).toInt)).zipWithIndex.map(x => x._2 -> x._1).toMap
}
implicit class CityExtend(val self:(Int,Int)) {
	def +(target:(Int,Int)) : (Int,Int) = (target._1 + self._1, target._2 + self._2)
	def -(target:(Int,Int)) : (Int,Int) = (target._1 - self._1, target._2 - self._2)
	def distance : Double = math.sqrt(self._1 * self._1 + self._2  * self._2)
	def <->(target:(Int,Int)) : Double = (target - self).distance
}
implicit class CitiesExtend(val self:Map[Int,(Int,Int)]) {
	//(city1 -> city2) -> distance
	lazy val distances = (for(i <- 0 until self.size ; j <- 0 until self.size) yield ((i -> j) -> (self(i) <-> self(j)))).toMap
	//(0 -> 1), (1 -> 2) ,...(n -> 0)
	lazy val roots = (0 until self.size).necklacePer.map(x => x zip (x.tail :+ x.head)).toList
	//root -> distance
	def dfs = roots zip roots.par.map(x => (0.0 /: x)((s,v) => s + distances(v)))

	//(city1 -> city2) -> distance
	lazy val nearDistances = distances.toList.sortBy(_._2).filterNot(x => x._1._1 == x._1._2)
	def greedy(visited:List[(Int,Int)] = List[(Int,Int)](), distance:Double = 0.0) : (List[(Int,Int)], Double) = {
		val current = if(visited.isEmpty) 0 else visited.head._2
		val suggests = nearDistances.filter(_._1._1 == current).filter(x => !visited.exists(_._1 == x._1._2))
		if(suggests.isEmpty) (visited, distance)
		else {
			val visit = suggests.head
			greedy(visit._1 +: visited,distance + visit._2)
		}
	 }
	def optimusRoot = greedy(List[(Int,Int)](),0.0)//dfs minBy(_._2)

	//drawing method
	import java.awt.image.BufferedImage
	import java.awt.{Graphics2D,Color,Font,BasicStroke, RenderingHints}
	import java.awt.geom._
	def draw(filepath:String)(implicit max:(Int)) = {
		val circleSize = 15

		val size = (max, max)
		val canvas = new BufferedImage(size._1, size._2, BufferedImage.TYPE_INT_RGB)
		val g = canvas.createGraphics
		g.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON)
		g.setColor(Color.WHITE)
		g.fillRect(0,0,canvas.getWidth, canvas.getHeight)
		//draw cities
		self.foreach(x => {
			val text = "[" + x._1 + "] : " + x._2
			val point = x._2
			g.setColor(Color.RED)
			g.fill(new Ellipse2D.Double(point._1 - (circleSize / 2), point._2 - (circleSize / 2), circleSize, circleSize))
			g.setColor(Color.MAGENTA)
			g.drawString(text,point._1, point._2)
		})
		//draw roots
		val drawRoot = optimusRoot
		drawRoot._1.foreach(x => {
			val point1 = self(x._1)
			val point2 = self(x._2)
			g.setColor(Color.BLUE)
			g.draw(new Line2D.Double(point1._1, point1._2, point2._1, point2._2))
		})

		g.dispose
		javax.imageio.ImageIO.write(canvas, "png", new java.io.File(filepath))
	}
}
implicit class RangeExtension(val self:Range) {
	def necklacePer = self.permutations.filter(x => x(1) < x.reverse.head).filter(_(0) == self.head)
}
implicit class FuncExtension(val self:() => Unit) {
	def processTime = {
		val s = System.currentTimeMillis
		self()
		println("[process time] : " + (System.currentTimeMillis - s) + "ms")
	}
}

implicit val max = 1000
val cities = City.create(count = 10)

(() => println(cities.optimusRoot)).processTime
//cities.draw("optimus.png")