API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Jan 18th, 2018
67
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 11.29 KB | None | 0 0
raw download clone embed print report
  1. package ML;
  2.  
  3. import javafx.util.Pair;
  4.  
  5. import java.io.*;
  6. import java.util.*;
  7.  
  8. public class Main {
  9.  
  10.     public static void main(String[] args) throws FileNotFoundException {
  11.         // write your code here
  12.         int K;
  13.         System.out.println("Dati numarul de clustere : ");
  14.         Scanner s1 = new Scanner(System.in);
  15.         K = s1.nextInt();
  16.  
  17.         BufferedReader br = new BufferedReader(new FileReader("dset500.csv"));
  18.  
  19.         try {
  20.             BufferedWriter bw = new BufferedWriter(new FileWriter("KMeansOut.txt"));
  21.         } catch (IOException e) {
  22.             e.printStackTrace();
  23.         }
  24.  
  25.         //adding points - reading csv
  26.         ArrayList<Point> points = new ArrayList<Point>();
  27.         String line;
  28.         ArrayList<ArrayList<Point>> adjList = new ArrayList<>();
  29.         ArrayList<Boolean> vizList = new ArrayList<Boolean>();
  30.         double x, y;
  31.         try {
  32.             while ((line = br.readLine()) != null) {
  33.                 String[] lines = line.split(",");
  34.                 x = Double.parseDouble(lines[0]);
  35.                 y = Double.parseDouble(lines[1]);
  36.                 Point pointy = new Point(x, y);
  37.                 //System.out.println("(" + x + ", " + y + ")");
  38.                 points.add(pointy);
  39.                 adjList.add(new ArrayList<Point>());
  40.                 vizList.add(false);
  41.             }
  42.         } catch (IOException e) {
  43.             e.printStackTrace();
  44.         }
  45.  
  46.         System.out.println("Avem " + points.size() + " puncte.");
  47.         System.out.println();
  48.         System.out.println();
  49.  
  50.         Collections.sort(points, new PointComparator());
  51.         //System.out.println(vizList.size());
  52.         //Acum avem o ordine pentru a ne putea referi la adjList si vizList
  53.  
  54.  
  55.         //let's make some edges
  56.  
  57.         ArrayList<Pair<Edge, Pair<Integer, Integer>>> allEdges = new ArrayList<>();
  58.         for (int i = 0; i < points.size() - 1; ++i) {
  59.             for (int j = i + 1; j < points.size(); ++j) {
  60.                 Pair<Integer, Integer> auxPair = new Pair<>(i, j);
  61.                 Pair<Edge, Pair<Integer, Integer>> auxEdgePair = new Pair<>(new Edge(points.get(i), points.get(j)), auxPair);
  62.                 allEdges.add(auxEdgePair);
  63.                 // System.out.println("("+auxEdgePair.getKey().getSquareLength() + ", " + points.get(auxEdgePair.getValue().getKey()).getX() + ", " + points.get(auxEdgePair.getValue().getKey()).getY() + ", " + points.get(auxEdgePair.getValue().getValue()).getX() + ", " + points.get(auxEdgePair.getValue().getValue()).getY());
  64.             }
  65.         }
  66.         //   System.out.println(new Point(4.63982706567831,2.65349724511111).getSqDist(new Point(4.75194435915857,3.00555353562793)));
  67.         Collections.sort(allEdges, new Comparator<Pair<Edge, Pair<Integer, Integer>>>() {
  68.             @Override
  69.             public int compare(final Pair<Edge, Pair<Integer, Integer>> o1, final Pair<Edge, Pair<Integer, Integer>> o2) {
  70.                 // TODO: implement your logic here
  71.                 double i1 = o1.getKey().getSquareLength();
  72.                 double i2 = o2.getKey().getSquareLength();
  73.                 if (i1 > i2) return 1;
  74.                 else if (i2 > i1) return -1;
  75.                 else return 0;
  76.             }
  77.         });
  78.  
  79.         /*for(int i=0; i<allEdges.size();++i){
  80.             System.out.println("("+allEdges.get(i).getKey().getSquareLength() + ", " + points.get(allEdges.get(i).getValue().getKey()).getX() + ", " + points.get(allEdges.get(i).getValue().getKey()).getY() + ", " + points.get(allEdges.get(i).getValue().getValue()).getX() + ", " + points.get(allEdges.get(i).getValue().getValue()).getY());
  81.         }*/
  82.  
  83.         //Sorted edges. Time to Kruskal.
  84.  
  85.  
  86.         ArrayList<Pair<Edge, Pair<Integer, Integer>>> MST = new ArrayList<>();
  87.  
  88.         MST.clear();
  89.         for (int i = 0; i < vizList.size(); ++i) {
  90.             vizList.set(i, false);
  91.         }
  92.         ArrayList<Set<Integer>> disjointSets = new ArrayList<>();
  93.         for (int i = 0; i < allEdges.size(); ++i) {
  94.             //easy add
  95.  
  96.             //if 2 points are not visited, we add the edge; since they are not visited, they are in no disjoint set
  97.             if (!vizList.get(allEdges.get(i).getValue().getKey()) && !vizList.get(allEdges.get(i).getValue().getValue())) {
  98.                 MST.add(allEdges.get(i));
  99.                 vizList.set(allEdges.get(i).getValue().getKey(), true);
  100.                 vizList.set(allEdges.get(i).getValue().getValue(), true);
  101.                 Set<Integer> newSet = new HashSet<>();
  102.                 newSet.add(allEdges.get(i).getValue().getValue());
  103.                 newSet.add(allEdges.get(i).getValue().getValue());
  104.                 disjointSets.add(newSet);
  105.                 continue;
  106.             }
  107.             //if 1 point is visited, we have to find its disjoint set and add the next; since an if clause can't tell which is visited, we need 2 \
  108.             else if (vizList.get(allEdges.get(i).getValue().getKey()) && !vizList.get(allEdges.get(i).getValue().getValue())) {
  109.                 for (int j = 0; j < disjointSets.size(); ++j) {
  110.                     if (disjointSets.get(j).contains(allEdges.get(i).getValue().getKey())) {
  111.                         disjointSets.get(j).add(allEdges.get(i).getValue().getValue());
  112.                         MST.add(allEdges.get(i));
  113.                         vizList.set(allEdges.get(i).getValue().getValue(), true);
  114.                         vizList.set(allEdges.get(i).getValue().getKey(), true);
  115.                         continue;
  116.                     }
  117.                 }
  118.             } else if (vizList.get(allEdges.get(i).getValue().getValue()) && !vizList.get(allEdges.get(i).getValue().getKey())) {
  119.                 for (int j = 0; j < disjointSets.size(); ++j) {
  120.                     if (disjointSets.get(j).contains(allEdges.get(i).getValue().getValue())) {
  121.                         disjointSets.get(j).add(allEdges.get(i).getValue().getKey());
  122.                         MST.add(allEdges.get(i));
  123.                         vizList.set(allEdges.get(i).getValue().getValue(), true);
  124.                         vizList.set(allEdges.get(i).getValue().getKey(), true);
  125.                         continue;
  126.                     }
  127.                 }
  128.             }
  129.             //both visited remain; we must either merge the 2 sets or continue if both are in the same set
  130.             else {
  131.                 int foundFirst = -1;
  132.                 int foundSecond = -1;
  133.                 for (int j = 0; j < disjointSets.size(); ++j) {
  134.                     if (disjointSets.get(j).contains(allEdges.get(i).getValue().getValue())) {
  135.                         foundSecond = j;
  136.                     }
  137.                     if (disjointSets.get(j).contains(allEdges.get(i).getValue().getKey())) {
  138.                         foundFirst = j;
  139.                     }
  140.                 }
  141.                /* if (foundFirst == foundSecond) {
  142.                     System.out.println(foundFirst + " == " + foundSecond);
  143.                 }
  144.                 else{
  145.                     System.out.println(foundFirst + " != " + foundSecond);
  146.                 }*/
  147.                 if (foundFirst != -1 && foundSecond != -1 && foundFirst != foundSecond) {
  148.                     Set<Integer> aux = new HashSet<>();
  149.                     aux.addAll(disjointSets.get(foundFirst));
  150.                     aux.addAll(disjointSets.get(foundSecond));
  151.  
  152.                     if (foundFirst > foundSecond) {
  153.                         disjointSets.remove(foundFirst);
  154.                         disjointSets.remove(foundSecond);
  155.                     } else {
  156.                         disjointSets.remove(foundSecond);
  157.                         disjointSets.remove(foundFirst);
  158.                     }
  159.                     disjointSets.add(aux);
  160.                     MST.add(allEdges.get(i));
  161.                     continue;
  162.                 }
  163.             }
  164.         }
  165.  
  166.  
  167.         for (int i = 0; i < MST.size(); ++i) {
  168.             //    System.out.println("("+MST.get(i).getKey().getSquareLength() + ", " + points.get(MST.get(i).getValue().getKey()).getX() + ", " + points.get(MST.get(i).getValue().getKey()).getY() + ", " + points.get(MST.get(i).getValue().getValue()).getX() + ", " + points.get(MST.get(i).getValue().getValue()).getY() + ")");
  169.         }
  170.  
  171.         /*for(int i=0; i<disjointSets.size();++i){
  172.                 System.out.println(disjointSets.get(i));
  173.         }*/
  174.         System.out.println(MST.size() + " " + allEdges.size());
  175.        /* for(int i=0; i<MST.size(); ++i){
  176.             if(MST.get(i).getValue().getKey() == 285 || MST.get(i).getValue().getValue() == 280){
  177.                 System.out.println(MST.get(i).getKey().getSquareLength() + " " + MST.get(i).getValue().getKey() + " " + MST.get(i).getValue().getValue());
  178.             }
  179.         }*/
  180.  
  181.         Collections.sort(MST, new Comparator<Pair<Edge, Pair<Integer, Integer>>>() {
  182.             @Override
  183.             public int compare(final Pair<Edge, Pair<Integer, Integer>> o1, final Pair<Edge, Pair<Integer, Integer>> o2) {
  184.                 // TODO: implement your logic here
  185.                 double i1 = o1.getKey().getSquareLength();
  186.                 double i2 = o2.getKey().getSquareLength();
  187.                 if (i1 > i2) return 1;
  188.                 else if (i2 > i1) return -1;
  189.                 else return 0;
  190.             }
  191.         });
  192.  
  193.         ArrayList<Set<Integer>> clustersByIndex = new ArrayList<>();
  194.  
  195.  
  196.         for(int i=0; i<MST.size()-K+1; ++i){
  197.             //System.out.println("Iteratia "+ (i+1));
  198.             Integer firstPoint = MST.get(i).getValue().getKey();
  199.             Integer secondPoint = MST.get(i).getValue().getValue();
  200.             Integer cluster1 = -1;
  201.             Integer cluster2 = -1;
  202.                 for(int j=0; j<clustersByIndex.size(); ++j){
  203.                     if(clustersByIndex.get(j).contains(firstPoint)){
  204.                         cluster1=j;
  205.                     }
  206.                     if(clustersByIndex.get(j).contains(secondPoint)){
  207.                         cluster2=j;
  208.                     }
  209.                 }
  210.                 if(cluster1==-1 && cluster2==-1){
  211.                     HashSet<Integer> auxSet = new HashSet<>();
  212.                     auxSet.add(firstPoint);
  213.                     auxSet.add(secondPoint);
  214.                     clustersByIndex.add(auxSet);
  215.                 }
  216.                 else if(cluster1!=-1 && cluster2==-1){
  217.                     clustersByIndex.get(cluster1).add(secondPoint);
  218.                 }
  219.                 else if(cluster2!=-1 && cluster1==-1){
  220.                     clustersByIndex.get(cluster2).add(firstPoint);
  221.                 }
  222.                 else{
  223.                     if(cluster1==cluster2) continue;
  224.                     Set<Integer> auxSet = new HashSet<>();
  225.                     auxSet.addAll(clustersByIndex.get(cluster1));
  226.                     auxSet.addAll(clustersByIndex.get(cluster2));
  227.                     if(cluster1>cluster2){
  228.                         clustersByIndex.remove(cluster1);
  229.                         clustersByIndex.remove(cluster2);
  230.                         clustersByIndex.add(auxSet);
  231.                     }
  232.                     else{
  233.                         clustersByIndex.remove(cluster2);
  234.                         clustersByIndex.remove(cluster1);
  235.                         clustersByIndex.add(auxSet);
  236.                     }
  237.                 }
  238.             }
  239.  
  240.  
  241.         System.out.println(clustersByIndex.size());
  242.  
  243.  
  244.     }
  245. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!