You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
335 lines
7.8 KiB
335 lines
7.8 KiB
import model.Coord
|
|
import model.Customer
|
|
import model.HHCEdge
|
|
import scala.collection.mutable.ArrayBuffer
|
|
import util.Util
|
|
import config.Conf
|
|
import java.io.File
|
|
import scala.io.Source
|
|
import sim.HHCSim2
|
|
object Main {
|
|
def main(args: Array[String]): Unit = {
|
|
|
|
val conf = new Conf(args.toIndexedSeq)
|
|
|
|
val bufferedSource = Source.fromFile(conf.infile())
|
|
|
|
val customers = HHCSim2.getCustomers(bufferedSource)
|
|
bufferedSource.close()
|
|
|
|
// import Ordering.Double.IeeeOrdering
|
|
// val hhc = new HHCSim(epsilonMax = 40, iterations = 10, WLDMax = 10)
|
|
// val adjList2 =
|
|
// customers
|
|
// .map(Util.formAdjMatrix)
|
|
// .map(e => Util.mstUsingPrims2(e))
|
|
// .map { case (mst, eps) => Util.removeEdges(mst)(eps) }
|
|
// // .map(_._1)
|
|
|
|
// // .map(e => Util.makeAdjacencyList2(e._1))
|
|
// adjList2.map(e => {
|
|
// val (mst, rm) = e
|
|
// for (i <- 0 until mst.size) {
|
|
// print(s"$i -> ")
|
|
// mst(i).foreach(e => {
|
|
// print(f"(${e._1}, ${e._2}%.2f), ")
|
|
// })
|
|
// println
|
|
// }
|
|
|
|
// println(rm)
|
|
// })
|
|
|
|
// val fnl2 = hhc.go(customers)
|
|
// customers.map(println(_))
|
|
|
|
// val edges3 = customers.map(Util.formAdjMatrix)
|
|
|
|
// val fnl2 = go(customers)
|
|
|
|
// fnl2 match {
|
|
// case Left(value) => println(value)
|
|
// case Right(groups) =>
|
|
// groups.foreach(c => {
|
|
// print(s"${c._1} -> ")
|
|
// c._2.foreach(e => {
|
|
// print(f"(${e._1}%d, ${e._2}%.2f), ")
|
|
// })
|
|
// println
|
|
// })
|
|
// }
|
|
|
|
// edges3 match {
|
|
// case Right(e) =>
|
|
// e.foreach { d =>
|
|
// d.foreach(g => print(f"$g%.2f, "))
|
|
// println()
|
|
// }
|
|
// case Left(e) =>
|
|
// println(s"Oops, an error occured. The error message was: $e")
|
|
// }
|
|
|
|
val hhc = new HHCSim2(
|
|
epsilonMax = 40,
|
|
iterations = 10,
|
|
WLDMax = 10,
|
|
customers = customers
|
|
)
|
|
|
|
// val x = hhc.go()
|
|
|
|
val x2 = hhc.go()
|
|
|
|
// x match {
|
|
// case Left(value) => println(value)
|
|
// case Right(value) =>
|
|
// }
|
|
|
|
// x.foreach(d => {
|
|
// val (a, b, c, g, groups) = d
|
|
// // println(c)
|
|
|
|
// // println
|
|
|
|
// // println(b)
|
|
// // for (i <- 0 until b.length) {
|
|
// // if (!b(i).isEmpty) {
|
|
// // print(s"$i ")
|
|
// // print(b(i))
|
|
// // // edgeMappings
|
|
// // // b(i).foreach(e => {
|
|
// // // print(f"(${e.toNode}%d, ${e.weight}%.2f), ")
|
|
// // // })
|
|
// // println
|
|
// // }
|
|
// // }
|
|
// // println
|
|
|
|
// // for (i <- 0 until g.length) {
|
|
// // if (!g(i)._2.isEmpty) {
|
|
// // print(s"$i ")
|
|
// // print(g(i))
|
|
// // // edgeMappings
|
|
// // // b(i).foreach(e => {
|
|
// // // print(f"(${e.toNode}%d, ${e.weight}%.2f), ")
|
|
// // // })
|
|
// // println
|
|
// // }
|
|
// // }
|
|
// println
|
|
|
|
// // var i = 0
|
|
// // b.foreach(e => {
|
|
// // // if (!e.isEmpty) {
|
|
// // print(s"Cluster-$i: ")
|
|
// // i += 1
|
|
// // e.foreach(f => { print(s"$f ") })
|
|
// // println
|
|
// // // }
|
|
// // })
|
|
|
|
// // i = 0
|
|
// // groups.foreach(e => {
|
|
// // // if (!e.isEmpty) {
|
|
// // print(s"Cluster-$i: ")
|
|
// // i += 1
|
|
// // e.foreach(f => { print(f"(${f._1}%d, ${f._2}%.2f), ") })
|
|
// // println
|
|
// // // }
|
|
// // })
|
|
|
|
// })
|
|
|
|
// x2.map(_.map(println))
|
|
|
|
// x.map(e => {
|
|
// val (mst, rm) = e
|
|
// val y = HHCSim2.DFS(0)(mst)
|
|
// println(y)
|
|
// for (i <- 0 until mst.size) {
|
|
// print(s"$i -> ")
|
|
// mst(i).foreach(e => {
|
|
// print(f"(${e.toNode}, ${e.weight}%.2f), ")
|
|
// })
|
|
// println
|
|
// }
|
|
|
|
// println(rm)
|
|
// })
|
|
|
|
val coord1 = Coord(3, 4)
|
|
println(s"Distance from origin = ${coord1.distance}")
|
|
|
|
val cust1 = Customer(coord1, 5)
|
|
val cust2 = Customer(Coord(2, 5), 7)
|
|
|
|
println(s"Customer 1 = ${cust1}")
|
|
println(s"Customer 2 = ${cust2}")
|
|
|
|
val cust3 = Customer(Coord(3, 5), 6)
|
|
val cust4 = Customer(Coord(6, 8), 9)
|
|
val cust5 = Customer(Coord(5, 4), 6)
|
|
|
|
val edge1 = HHCEdge(cust1, cust2)
|
|
val edge2 = HHCEdge(cust3, cust4)
|
|
|
|
println(s"Edge 1 = ${edge1}")
|
|
println(s"Edge 1 weight = ${edge1.weight}")
|
|
|
|
val V = Array(cust1, cust2, cust3, cust4, cust5)
|
|
|
|
val E = Array(edge1, edge2)
|
|
|
|
V.foreach(println(_))
|
|
// prints
|
|
// Customer(Coord(3, 4), 5)
|
|
// Customer(Coord(2, 5), 7)
|
|
// Customer(Coord(3, 5), 6)
|
|
// Customer(Coord(6, 8), 9)
|
|
// Customer(Coord(5, 4), 6)
|
|
E.foreach(println(_))
|
|
//prints
|
|
// HHCEdge(Customer(Coord(3, 4), 5), Customer(Coord(2, 5), 7))
|
|
// HHCEdge(Customer(Coord(3, 5), 6), Customer(Coord(6, 8), 9))
|
|
|
|
// sample adjacency
|
|
// format: off
|
|
val edgesSeq = Seq(
|
|
Seq(0 , 9 , 75, 0 , 0),
|
|
Seq(9 , 0 , 95, 19, 42),
|
|
Seq(75, 95, 0 , 51, 66),
|
|
Seq(0 , 19, 51, 0 , 31),
|
|
Seq(0 , 42, 66, 31, 0)
|
|
);
|
|
|
|
// adjacency list form
|
|
// 0 -> 1 -> 2
|
|
// 1 -> 0 -> 2 -> 3 -> 4
|
|
// 2 -> 0 -> 1 -> 3 -> 4
|
|
// 3 -> 1 -> 2 -> 4
|
|
// 4 -> 1 -> 2 -> 3
|
|
|
|
val edges = edgesSeq.map(e => {
|
|
e.toArray
|
|
}).toArray
|
|
|
|
val (mst,eps) = Util.mstUsingPrims(edges)
|
|
println(s"Epsilon: $eps")
|
|
|
|
// mst
|
|
// 0, 9 , 0 , 0 , 0
|
|
// 9, 0 , 0 , 19, 0
|
|
// 0, 0 , 0 , 51, 0
|
|
// 0, 19, 51, 0 , 31
|
|
// 0, 0 , 0 , 31, 0
|
|
|
|
// format: on
|
|
|
|
// Prim's algorithm
|
|
|
|
// Prim's algorithm result
|
|
// Edge selected 0 - 1: 9
|
|
// Edge selected 1 - 3: 19
|
|
// Edge selected 3 - 4: 31
|
|
// Edge selected 3 - 2: 51
|
|
|
|
// Verify the result with the one at https://www.programiz.com/dsa/prim-algorithm
|
|
|
|
val edges2: Array[Array[Double]] = Array.ofDim(5, 5)
|
|
|
|
// create adjacency matrix from given customers
|
|
for (i <- 0 to 4) {
|
|
for (j <- 0 to 4) {
|
|
edges2(i)(j) = Util.getHaversineDistance(V(i).location, V(j).location)
|
|
}
|
|
}
|
|
|
|
edges2.foreach { e =>
|
|
e.foreach { d =>
|
|
print(f"$d%.2f, ")
|
|
}
|
|
println()
|
|
}
|
|
|
|
// prints
|
|
// 0.00 , 159.64, 112.79, 563.55, 225.88
|
|
// 159.64, 0.00 , 112.94, 564.16, 357.08
|
|
// 112.79, 112.94, 0.00 , 478.40, 252.42
|
|
// 563.55, 564.16, 478.40, 0.00 , 463.64
|
|
// 225.88, 357.08, 252.42, 463.64, 0.00
|
|
|
|
println()
|
|
println("Initial graph:")
|
|
edgesSeq.foreach { e =>
|
|
e.foreach { d =>
|
|
print(s"$d, ")
|
|
}
|
|
println()
|
|
}
|
|
println("MST: ")
|
|
mst.foreach { e =>
|
|
e.foreach { d =>
|
|
print(s"$d, ")
|
|
}
|
|
println()
|
|
}
|
|
|
|
// 0, 9, 0 , 0 , 0
|
|
// 0, 0, 0 , 19, 0
|
|
// 0, 0, 0 , 0 , 0
|
|
// 0, 0, 51, 0 , 31
|
|
// 0, 0, 0 , 0 , 0
|
|
|
|
val (mst2, centr, removed) = Util.findCentroids(mst, eps)
|
|
// val (centr2, eds2) = Util.findCentroids(edges2)
|
|
|
|
println()
|
|
println(s"Centroids: \n$centr")
|
|
println(s"Removed: \n$removed")
|
|
|
|
val (_, clust, _) = Util.findClusters(mst, centr, removed)
|
|
val adjList = Util.makeAdjacencyList(edges, centr)
|
|
|
|
println(s"Clusters:")
|
|
clust.foreach(c => {
|
|
val (e, d) = c
|
|
print(s"$e: ")
|
|
d.foreach(f => {
|
|
print(s"-> $f ")
|
|
})
|
|
println()
|
|
})
|
|
println()
|
|
|
|
val fnl = Util.groupClusters(centr, clust, removed)
|
|
|
|
println(s"Final cluster groups: \n$fnl")
|
|
|
|
// Output
|
|
//
|
|
// Initial graph:
|
|
// 0, 9, 75, 0, 0,
|
|
// 9, 0, 95, 19, 42,
|
|
// 75, 95, 0, 51, 66,
|
|
// 0, 19, 51, 0, 31,
|
|
// 0, 42, 66, 31, 0,
|
|
// MST:
|
|
// 0, 9, 0, 0, 0,
|
|
// 9, 0, 0, 19, 0,
|
|
// 0, 0, 0, 51, 0,
|
|
// 0, 19, 51, 0, 31,
|
|
// 0, 0, 0, 31, 0,
|
|
|
|
// Centroids:
|
|
// Vector(2, 3, 4)
|
|
// Removed:
|
|
// Vector((2,3,51), (3,2,51), (3,4,31), (4,3,31))
|
|
// Clusters:
|
|
// 2: -> 2
|
|
// 3: -> 3 -> 1 -> 0
|
|
// 4: -> 4
|
|
|
|
// Final cluster groups:
|
|
// Map(2 -> Vector((3,51)), 3 -> Vector((4,31), (2,51)), 4 -> Vector((3,31)))
|
|
}
|
|
}
|