travering salesman problem : depth first search with scala

_log

(Vector((0,5), (5,1), (1,8), (8,2), (2,3), (3,6), (6,7), (7,4), (4,9), (9,0)),2519.060346766078)
[process time] : 2414ms

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)))
	def optimusRoot = 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)
}


//val cities = "city.csv".toCities
implicit val max = 1000
val cities = City.create(count = 10)
cities.draw("optimus.png")