Aaaaa988

Graph

Oct 14th, 2020
859
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.*;
  2. import java.util.*;
  3. import java.util.LinkedList;
  4.  
  5. class Graph
  6. {
  7.     private int V;
  8.     private LinkedList<Integer> adj[];
  9.  
  10.     Graph(int v)
  11.     {
  12.         V = v;
  13.         adj = new LinkedList[v];
  14.         for (int i=0; i<v; ++i)
  15.             adj[i] = new LinkedList();
  16.     }
  17.  
  18.     void addEdge(int v,int w)
  19.     {
  20.         if (!adj[v].contains(w))
  21.                 adj[v].add(w);
  22.         if (!adj[w].contains(v))
  23.             adj[w].add(v);
  24.     }
  25.  
  26.     boolean greedyColoring(int resultEdge)
  27.     {
  28.         int result[] = new int[V];
  29.  
  30.         Arrays.fill(result, -1);
  31.  
  32.         result[0] = 0;
  33.  
  34.         boolean available[] = new boolean[V];
  35.  
  36.         Arrays.fill(available, true);
  37.  
  38.         for (int u = 1; u < V; u++)
  39.         {
  40.             Iterator<Integer> it = adj[u].iterator() ;
  41.             while (it.hasNext())
  42.             {
  43.                 int i = it.next();
  44.                 if (result[i] != -1)
  45.                     available[result[i]] = false;
  46.             }
  47.  
  48.             int cr;
  49.             for (cr = 0; cr < V; cr++){
  50.                 if (available[cr])
  51.                     break;
  52.             }
  53.  
  54.             result[u] = cr;
  55.             Arrays.fill(available, true);
  56.         }
  57.  
  58.         boolean flag = true;
  59.         for (int u = 0; u < V; u++) {
  60.             if(result[u] >=3){
  61.                 flag = false;
  62.             }
  63.         }
  64.  
  65.         if (flag){
  66.             String outputFileName = "file1.txt";
  67.  
  68.             try (BufferedWriter writter = new BufferedWriter(new FileWriter(outputFileName))) {
  69.                 writter.write("1000,"+resultEdge+",colorFirst,colorSecond\n");
  70.                 for (int i = 0; i < 1000; i++){
  71.                     for (int j = 0; j < adj[i].size(); j++){
  72.                         writter.write(i+ "," +adj[i].get(j)+","+result[i]+","+result[adj[i].get(j)]);
  73.                         writter.write("\n");
  74.                     }
  75.                 }
  76.             }
  77.             catch (IOException e) {
  78.                 e.printStackTrace();
  79.             }
  80.  
  81.         }
  82.         return flag;
  83.     }
  84.  
  85.     public static void main(String args[])
  86.     {
  87.         int n = 1000;
  88.         Random rnd = new Random();
  89.         boolean result;
  90.         int resultEdge = 0;
  91.         int iteration = 0;
  92.         do {
  93.             iteration++;
  94.  
  95.             if(iteration % 1000 == 0)
  96.                 System.out.println("iteration "+iteration/1000+"K");
  97.             resultEdge = 0;
  98.             Graph g1 = new Graph(n);
  99.  
  100.             for (int i = 0; i < n; i++) {
  101.                 int countNeigh = rnd.nextInt(8) + 1;
  102.                 for (int j = 1; j <= countNeigh; j++) {
  103.                     if(i+1 == n) break;
  104.                     int Neigh;
  105.                     do {
  106.                         Neigh = rnd.nextInt(n) ;
  107.  
  108.                     } while (i >= Neigh);
  109.  
  110.                     if(g1.adj[i].size()+1 < 8)
  111.                         if(g1.adj[Neigh].size()+1 < 3){
  112.                             resultEdge++;
  113.                             g1.addEdge(i, Neigh);
  114.                         }
  115.  
  116.                 }
  117.             }
  118.             result = g1.greedyColoring(resultEdge);
  119.         }while(!result);
  120.         System.out.println(result);
  121.         System.out.println("result edge = " + resultEdge);
  122.  
  123.     }
  124. }
RAW Paste Data