SHARE
TWEET

Untitled

a guest Oct 19th, 2019 76 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. Edmond La Chance UQAC 2019
  3. Exemple algorithme Fast Coloring avec table, et broadcast variables
  4.  */
  5. package coloring
  6.  
  7. import org.apache.spark.{SparkConf, SparkContext}
  8. import scala.collection.mutable.ArrayBuffer
  9. import scala.util.Random
  10.  
  11. case class node(var color: Int = 1, var tiebreakvalue: Int = 0, len: Int = 0)
  12. {
  13.   var adjlist = new Array[Int](len)
  14.  
  15.    def printadjlist: String = {
  16.     var output = "adjlist : "
  17.     adjlist.foreach(output += _)
  18.     output
  19.   }
  20.  
  21.   override def toString: String = {
  22.     s"color : $color, tiebreakvalue : $tiebreakvalue"
  23.   }
  24. }
  25.  
  26. case class edge_data(src: Long, dst: Long)
  27.  
  28. object coloring extends Serializable {
  29.  
  30.   //Return infered
  31.   def randomTieBreakers(graph: Array[(Int,node)]) = {
  32.     var tiebreakers = ArrayBuffer[Int]()
  33.     var count = graph.size
  34.     //Generate normal IDs
  35.     for (i <- 0 until count) tiebreakers += i
  36.     //Generate tiebreakers
  37.     Random.setSeed(System.nanoTime())
  38.     tiebreakers = Random.shuffle(tiebreakers)
  39.     tiebreakers
  40.   }
  41.  
  42.   //Color using the FC2 algorithm
  43.   def fc2(graph: Array[(Int,node)], sc: SparkContext) = {
  44.     //Step 1 : We generate tiebreakers
  45.     var tiebreakers = randomTieBreakers(graph)
  46.  
  47.     //Apply tiebreakers
  48.     for (i <- 0 until tiebreakers.size)
  49.       graph(i)._2.tiebreakvalue = tiebreakers(i)
  50.  
  51.     println("Printing after tiebreakers")
  52.     graph foreach println
  53.     println
  54.  
  55.     //Execute the algorithm
  56.     var graphRDD = sc.makeRDD(graph)
  57.  
  58.     loop
  59.  
  60.     def loop(): Unit = {
  61.       //On broadcast les couleurs, tiebreakers à tout le monde
  62.       val essentiels = graphRDD.flatMap(node => {
  63.         Some((node._1, node._2.tiebreakvalue))
  64.       }).collect.sortBy(_._1).map(elem => elem._2)
  65.  
  66.       val bcast = sc.broadcast(essentiels)
  67.  
  68.       graphRDD = graphRDD.map(n =>
  69.       {
  70.         var toBeKnight = true
  71.  
  72.         for (i <- 0 until n._2.adjlist.length) {
  73.           var adjacent = n._2.adjlist(i)
  74.           if (adjacent == 1) {
  75.             val tieBreakerVoisin = bcast.value(i)
  76.             if (tieBreakerVoisin != -1) {
  77.               if (tieBreakerVoisin < n._2.tiebreakvalue) //-1 = knight
  78.                 toBeKnight = false
  79.             }
  80.           }
  81.  
  82.         }
  83.         if (toBeKnight == true) {
  84.           n._2.tiebreakvalue = -1
  85.         }
  86.         else {
  87.           n._2.color += 1
  88.         }
  89.  
  90.         n
  91.          //return the modified object
  92.       })
  93.  
  94.       graphRDD.cache()
  95.  
  96.       println("Check pour fin")
  97.  
  98.       //DEBUG on check les couleurs
  99.     //  graphRDD.collect.foreach( println(_))
  100.  
  101.       //On check pour la fin. Fin = tout le monde est un knight
  102.       val result = graphRDD.filter(node => {
  103.         if (node._2.tiebreakvalue == -1) false
  104.         else true
  105.       })
  106.  
  107.       //If every node is a knight we can return
  108.       if (result.isEmpty()) return
  109.  
  110.       //Else we restart the loop
  111.       loop
  112.     }
  113.  
  114.     //Return the colors of the graph
  115.     graphRDD.map(node => node._2.color).collect()
  116.  
  117.   }
  118. }
  119.  
  120. object testAlgo extends App {
  121.  
  122.   val conf = new SparkConf()
  123.     .setAppName("Petersen Graph version Examen")
  124.     .setMaster("local[*]")
  125.   val sc = SparkContext.getOrCreate(conf)
  126.   sc.setLogLevel("ERROR")
  127.  
  128.   var edges = Array(
  129.     edge_data(1L, 2L), edge_data(1L, 3L), edge_data(1L, 6L),
  130.     edge_data(2L, 7L), edge_data(2L, 8L),
  131.     edge_data(3L, 4L), edge_data(3L, 9L),
  132.     edge_data(4L, 5L), edge_data(4L, 8L),
  133.     edge_data(5L, 6L), edge_data(5L, 7L),
  134.     edge_data(6L, 10L),
  135.     edge_data(7L, 9L),
  136.     edge_data(8L, 10L),
  137.     edge_data(9L, 10L)
  138.   )
  139.  
  140.   //Créer une collection avec des yield
  141.   var graph = for (i <- 1 to 10) yield  Tuple2(i-1, new node(1, 0, 10))
  142.  
  143.   //Fill the adjmatrix
  144.   edges.foreach(e => {
  145.     val src = e.src.toInt
  146.     val dst = e.dst.toInt
  147.     graph(src - 1)._2.adjlist(dst - 1) = 1
  148.     graph(dst - 1)._2.adjlist(src - 1) = 1
  149.   })
  150.  
  151.   println
  152.   graph foreach( e=> print(e._2.printadjlist+"\n") )
  153.   graph foreach println
  154.   println
  155.  
  156.   //Execute the algorithm
  157.   val results = coloring.fc2(graph.toArray, sc)
  158.  
  159.   println("\nColors of the graph\n")
  160.   results.foreach(color => print(color + " "))
  161. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top