API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Mar 28th, 2015
202
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 13.28 KB | None | 0 0
raw download clone embed print report
  1. package clique_algo;
  2.  
  3. import java.io.BufferedReader;
  4. import java.io.FileNotFoundException;
  5. import java.io.FileReader;
  6. import java.io.FileWriter;
  7. import java.io.IOException;
  8. import java.io.PrintWriter;
  9. import java.util.StringTokenizer;
  10. import java.util.Vector;
  11.  
  12.  
  13. /**
  14.  * this class represents an undirected 0/1 sparse Graph
  15.  * @author Boaz
  16.  *
  17.  */
  18.  class Graph {
  19.      private String _file_name;
  20.      private Vector <VertexSet> _V;
  21.      private double _TH; // the threshold value
  22.      private int _E_size = 0;
  23.      private boolean _mat_flag=true;
  24.      Graph(String file, double th) {
  25.         this._file_name = file;
  26.         _TH = th;
  27.         _V = new  Vector <VertexSet>();
  28.          init();
  29.      }
  30.      
  31.     private void init() {
  32.         FileReader fr=null;
  33.         try {
  34.             fr = new FileReader(this._file_name);
  35.         } catch (FileNotFoundException e) { e.printStackTrace();}
  36.         BufferedReader is = new BufferedReader(fr);
  37.         try {
  38.             String s = is.readLine();
  39.             StringTokenizer st = new StringTokenizer(s,", ");
  40.             int len = st.countTokens();
  41.             int line = 0;
  42.            
  43.             String ll = "0%   20%   40%   60%   80%   100%";
  44.             int t = Math.max(1,len/ll.length());
  45.             if(Clique_Tester.Debug){
  46.                 System.out.println("Reading a corrolation matrix of size: "+len+"*"+len+" this may take a while");
  47.                 System.out.println(ll);
  48.             }
  49.             _mat_flag = true;
  50.             if (s.startsWith("A")) {
  51.                 if(Clique_Tester.Debug){
  52.                     System.out.println("Assumes compact representation! two line haeder!!!");
  53.                     System.out.println("Header Line1: "+s);
  54.                     s = is.readLine();
  55.                     System.out.println("Header Line2: "+s);
  56.                     s = is.readLine();
  57.                     st = new StringTokenizer(s,", ");
  58.                     _mat_flag = false;
  59.                 }
  60.             }
  61.    
  62.             while(s!=null) {
  63.                
  64.                 if(Clique_Tester.Debug){
  65.                     if(line%t==0) System.out.print(".");                                
  66.                 }
  67.                 VertexSet vs = new VertexSet();
  68.                 if(_mat_flag){
  69.                     for(int i=0;i<len;i++) {
  70.                         float v = new Double(st.nextToken()).floatValue();
  71.                         if(v>_TH & line< i) {
  72.                             vs.add(i);
  73.                             _E_size++;
  74.                         }
  75.                     }
  76.                 }
  77.                 else {
  78.                     st.nextToken();
  79.                     while(st.hasMoreTokens()) {
  80.                         int ind = new Integer(st.nextToken()).intValue();
  81.                         // bug fixed as for Ronens format.
  82.                         if(line<ind) vs.add(ind);
  83.                     }
  84.                 }
  85.                 this._V.add(vs);
  86.                 line++;
  87.                 s = is.readLine();
  88.             if(s!=null) st = new StringTokenizer(s,", ");
  89.             }
  90.             if(this._mat_flag & Clique_Tester.Convert) {write2file();}
  91.             if(Clique_Tester.Debug){
  92.                 System.out.println("");
  93.                 System.out.print("done reading the graph! ");
  94.                 this.print();}
  95.         } catch (IOException e) {e.printStackTrace();}
  96.      }
  97.    
  98.     public VertexSet Ni(int i) {
  99.         VertexSet ans = _V.elementAt(i);
  100.         return  ans;
  101.     }
  102.     public void print() {
  103.         System.out.println("Graph: |V|="+this._V.size()+" ,  |E|="+_E_size);
  104.        
  105.     }
  106.    
  107.     /*************** Clique Algorithms ******************/
  108.     /*Vector<VertexSet>  All_Cliques(int Q_size) {
  109.         Vector<VertexSet> ans = new Vector<VertexSet>();
  110.         Vector<VertexSet>C0 = allEdges(); // all edges – all cliques of size 2/
  111.         ans.addAll(C0);
  112.         for(int i=3;i<=Q_size;i++) {
  113.             Vector<VertexSet>C1 = allC(C0);
  114.             ans.addAll(C1);
  115.             C0 = C1;
  116.         } // for
  117.         return ans;
  118.     }
  119.     Vector<VertexSet>  All_Cliques(int min_Q_size, int max_Q_size) {
  120.         Vector<VertexSet> ans = new Vector<VertexSet>();
  121.         Vector<VertexSet> C0 = allEdges(), C1=null; // all edges – all cliques of size 2/
  122.         for(int i=0;i<C0.size();i++) {
  123.             VertexSet curr = C0.elementAt(i);
  124.             C1 = All_Cliques_of_edge(curr, min_Q_size,  max_Q_size);
  125. //          System.out.println("Edge: ["+curr.at(0)+","+curr.at(1)+"]");
  126.             ans.addAll(C1);
  127.         }
  128.         return ans;
  129.     }*/
  130.     /**
  131.      * this method retuns all the Cliques of size between [min,max] which contains the subVertexSet e (usually an edge);
  132.      * @param min_Q_size
  133.      * @param max_Q_size
  134.      * @return
  135.      */
  136.     /*
  137.     Vector<VertexSet>  All_Cliques_of_edge(VertexSet e, int min_Q_size, int max_Q_size) {
  138.         Vector<VertexSet> ans = new Vector<VertexSet>();
  139.         ans.add(e);
  140.         int i=0;
  141.         int last_size = e.size();
  142.         while(i<ans.size() & last_size <=max_Q_size) {
  143.             VertexSet curr = ans.elementAt(i);
  144.             VertexSet inter = intersection(curr);
  145.             addbiggerCliQ(ans,curr,inter);
  146.             last_size = ans.elementAt(ans.size()-1).size();
  147.             i++;
  148.         }
  149.         int start = 0; i=0;
  150.         while(i<ans.size() && start==0) {
  151.             if(ans.elementAt(i).size()<min_Q_size) {ans.remove(0);}
  152.             else start=1;
  153.             i++;
  154.         }
  155.         return ans;
  156.     }
  157.     Vector<VertexSet> allC(Vector<VertexSet> C0) {
  158.         Vector<VertexSet> ans = new Vector<VertexSet>();
  159.         for(int i=0;i<C0.size();i++) {
  160.             VertexSet curr = C0.elementAt(i);
  161.             VertexSet inter = intersection(curr);
  162.             if(inter.size()>0)  
  163.                 addbiggerCliQ(ans,curr,inter); // strange clique expqnding function
  164.     }  
  165.         return ans;
  166.     }
  167.     VertexSet intersection(VertexSet C) {
  168.         VertexSet ans = _V.elementAt(C.at(0));
  169.         for(int i=0;ans.size()>0 & i<C.size();i++)
  170.             ans = ans.intersection(_V.elementAt(C.at(i)));
  171.         return ans;
  172.     }
  173.     private void addbiggerCliQ(Vector<VertexSet> ans,VertexSet curr ,VertexSet inter) {
  174.         int last = curr.at(curr.size()-1);
  175.         for(int i=0;i<inter.size();i++) {
  176.             int ind_inter = inter.at(i);
  177.             if(last<ind_inter) {
  178.                 VertexSet c = new VertexSet(curr);
  179.                 c.add(ind_inter);
  180.                 ans.add(c);
  181.             }
  182.         }
  183.     }
  184.     private Vector<VertexSet> addbiggerCliQ(VertexSet curr ,VertexSet inter) {
  185.         Vector<VertexSet> ans = new Vector<VertexSet>(inter.size());
  186.         int last = curr.at(curr.size()-1); // last vertex in the current clique (ordered!)
  187.         for(int i=0;i<inter.size();i++) {
  188.             int ind_inter = inter.at(i);
  189.             if(last<ind_inter) {
  190.                 VertexSet c = new VertexSet(curr);
  191.                 c.add(ind_inter);
  192.                 ans.add(c);
  193.             }
  194.         }
  195.         return ans;
  196.     }*/
  197.     /**
  198.      * computes all the 2 cliques --> i.e. all the edges
  199.      * @return
  200.      */
  201.     private Vector<VertexSet> allEdges() { // all edges – all cliques of size 2/
  202.         Vector<VertexSet> ans = new Vector<VertexSet>();
  203.         for(int i=0;i<_V.size();i++) {
  204.             VertexSet curr = _V.elementAt(i);
  205.             for(int a=0;a<curr.size();a++) {
  206.                 if(i<curr.at(a)) {
  207.                     VertexSet tmp = new VertexSet();
  208.                     tmp.add(i) ;
  209.                     tmp.add(curr.at(a));
  210.                     ans.add(tmp);
  211.                 }
  212.             }
  213.            
  214.         }
  215.         return ans;
  216.     }
  217.     /**
  218.      * This method computes all cliques of size [min,max] or less using a memory efficient DFS like algorithm.
  219.      * The implementation was written with CUDA in mind - as a based code for a possibly implementation of parallel cernal.
  220.      *
  221.      */
  222.     Vector<VertexSet>  All_Cliques_DFS(int min_size, int max_size) {
  223.         Clique.init(this);
  224.         Vector<VertexSet> ans = new Vector<VertexSet>();
  225.         Vector<VertexSet>C0 = allEdges(); // all edges – all cliques of size 2/
  226.     //  ans.addAll(C0);
  227.         int len = C0.size();
  228.         //System.out.println("|E|= "+len);
  229.         int count = 0;
  230.         for(int i=0;i<len;i++) {
  231.            
  232.             VertexSet curr_edge = C0.elementAt(i);
  233.             Clique edge = new Clique(curr_edge.at(0),curr_edge.at(1) );
  234.            
  235.             Vector<Clique> C1 = allC_seed(edge, min_size, max_size);
  236.             count+=C1.size();
  237.             //System.out.println("alg2 "+i+") edge:["+curr_edge.at(0)+","+curr_edge.at(1)+"]"+C1.size() +"  total: "+count);
  238.             addToSet(ans, C1);
  239.         } // for
  240.         return ans;
  241.     }
  242.     /**
  243.      *
  244.      * @param min_size
  245.      * @param max_size
  246.      */
  247.      public void All_Cliques_DFS(String out_file, int min_size, int max_size) {
  248.             Clique.init(this);
  249.             Vector<VertexSet>C0 = allEdges(); // all edges – all cliques of size 2/
  250.             int len = C0.size();
  251.             System.out.println("|E|= "+len);
  252.             int count = 0;
  253.            
  254.             StringBuilder sb=new StringBuilder();
  255.            
  256.             FileWriter fw=null;
  257.             try {fw = new FileWriter(out_file);}
  258.             catch (IOException e) {e.printStackTrace();}
  259.             PrintWriter os = new PrintWriter(fw);
  260.             //os.println("A");
  261.            
  262.             String ll = "0%   20%   40%   60%   80%   100%";
  263.             int t = Math.max(1,len/ll.length());
  264.             if(Clique_Tester.Debug){
  265.                 System.out.println("Computing all cliques of size["+min_size+","+max_size+"] based on "+len+" edges graph, this may take a while");
  266.                 System.out.println(ll);
  267.             }
  268.             os.println("All Cliques: file [min max] TH,"+this._file_name+","+min_size+", "+max_size+", "+this._TH);
  269.             os.println("index, edge, clique size, c0, c1, c2, c3, c4,  c5, c6, c7, c8, c9");
  270. //          for(int i=0;i<len;i++) {
  271. //             
  272. //              VertexSet curr_edge = C0.elementAt(i);
  273. //              Clique edge = new Clique(curr_edge.at(0),curr_edge.at(1) );
  274. //              Vector<Clique> C1 = allC_seed(edge, min_size, max_size);
  275. //         
  276. //             
  277. ////                for(int b=0;b<C1.size();b++) {
  278. ////                    Clique c = C1.elementAt(b);
  279. ////                    if (c.size()>=min_size) {
  280. ////                        sb.append(count+", "+i+","+c.size()+", "+c.toFile());
  281. ////                        sb.append('\n');
  282. ////                        count++;
  283. ////                    }
  284. ////                }
  285. ////                if(count > Clique_Tester.MAX_CLIQUE) {
  286. ////                    sb.append("ERROR: too many cliques! - cutting off at "+Clique_Tester.MAX_CLIQUE+" for larger files change the default Clique_Tester.MAX_CLIQUE param");
  287. ////                    sb.append('\n');
  288. ////                    System.out.println("ERROR: too many cliques! - cutting off at "+Clique_Tester.MAX_CLIQUE+" for larger files change the default Clique_Tester.MAX_CLIQUE param");
  289. ////                    i=len;
  290. ////                }
  291. //              if(i%t==0) {
  292. //                  System.out.print(".");
  293. //              }
  294. //          } // for
  295.            
  296.             myThread1[] myThreads=new myThread1[10];
  297.             int counter=0;
  298.             int currentcounter=0;
  299.             for(int i=0;i<myThreads.length;i++){
  300.                 myThreads[i]=new myThread1(min_size,max_size,t);
  301.             }
  302.             while(counter!=len){
  303.                 for(int i=0;i<myThreads.length&&counter!=len;i++){
  304.                     if(myThreads[i].isAvailable()){
  305.                         if(myThreads[i].done){
  306.                             counter++;
  307.                             //System.out.println("hey1");
  308.                             if(myThreads[i].FINISH_TEST){
  309.                                 counter=len;
  310.                                 System.out.println("hey");
  311.                                 for(int j=0;j<myThreads.length;j++){
  312.                                     myThreads[j].stop();
  313.                                 }
  314.                             }
  315.                             myThreads[i].done=false;
  316.                         }
  317.                         if(counter==len)break;
  318.                         else if(currentcounter<len){
  319.                             VertexSet curr_edge = C0.elementAt(currentcounter);
  320.                             Clique edge = new Clique(curr_edge.at(0),curr_edge.at(1) );
  321.                             myThreads[i].edge=edge;
  322.                             myThreads[i].i=currentcounter;
  323.                             myThreads[i].run();
  324.                             currentcounter++;
  325.                         }
  326.                     }
  327.                 }
  328.             }
  329.             for(int i=0;i<myThreads.length;i++){
  330.                 os.println(myThreads[i].sb);
  331.             }
  332.                
  333.             System.out.println();
  334.             //os.append(sb);
  335.             os.close();
  336.             try {
  337.                 fw.close();
  338.             } catch (IOException e) {
  339.                 // TODO Auto-generated catch block
  340.                 e.printStackTrace();
  341.             }
  342.            
  343.         }
  344.    
  345.     /**
  346.      * this function simply add the clique (with no added intersection data) to the set of cliques)
  347.      * @param ans
  348.      * @param C1
  349.      */
  350.     private void addToSet(Vector<VertexSet> ans, Vector<Clique> C1) {
  351.         for(int i=0;i<C1.size();i++) {
  352.             ans.add(C1.elementAt(i).clique());
  353.         }
  354.     }
  355.     Vector<Clique> allC_seed(Clique edge, int min_size, int max_size) {
  356.         Vector<Clique> ans = new Vector<Clique>();
  357.         ans.add(edge);
  358.         int i=0;
  359.     //  int size = 2;
  360.         while (ans.size()>i) {
  361.             Clique curr = ans.elementAt(i);
  362.             if(curr.size()<max_size) {
  363.                 VertexSet Ni = curr.commonNi();
  364.                 for(int a=0;a<Ni.size();a++) {
  365.                     Clique c = new Clique(curr,Ni.at(a));
  366.                     ans.add(c);
  367.                 }
  368.             }
  369.             else {i=ans.size();} // speedup trick
  370.             i++;
  371.         }
  372.        
  373.         return ans;
  374.     }
  375.  
  376.     public void write2file() {
  377.         FileWriter fw=null;
  378.         StringBuilder sb= new StringBuilder();
  379.         try {fw = new FileWriter(this._file_name+"_DG.txt");}
  380.         catch (IOException e) {e.printStackTrace();}
  381.         PrintWriter os = new PrintWriter(fw);
  382.         os.println("ALL_Cliques: of file: "+_file_name+",  TH:"+this._TH);
  383.         os.println("");
  384.         for(int i=0;i<this._V.size();i++) {
  385.             VertexSet curr = _V.elementAt(i);
  386.             sb.append(i+", "+curr.toFile());
  387.             sb.append('\n');
  388.         }
  389.         os.println(sb);
  390.         os.close();
  391.         try {
  392.             fw.close();
  393.         } catch (IOException e) {
  394.             e.printStackTrace();
  395.         }
  396.     }
  397. }
  398. class myThread1 extends Thread{
  399.    
  400.     Clique edge;
  401.     private int min,max;
  402.     StringBuilder sb=new StringBuilder();
  403.     private boolean available=true;
  404.     boolean done=false;
  405.     boolean FINISH_TEST=false;
  406.     int i,t;
  407.    
  408.     public myThread1(int min, int max,int t){
  409.         this.min=min;
  410.         this.max=max;
  411.         this.t=t;
  412.     }
  413.    
  414.    
  415.     synchronized boolean isAvailable(){
  416.         boolean temp=available;
  417.         available=false;
  418.         return temp;
  419.     }
  420.     public void run(){
  421.         Vector<Clique> C1=allC_seed(edge,min,max);
  422.         int count=0;
  423.         for(int b=0;b<C1.size();b++) {
  424.             Clique c = C1.elementAt(b);
  425.             if (c.size()>=min) {
  426.                 sb.append(count+", "+i+","+c.size()+", "+c.toFile());
  427.                 sb.append('\n');
  428.                 count++;
  429.             }
  430.         }
  431.         if(count > Clique_Tester.MAX_CLIQUE) {
  432.             sb.append("ERROR: too many cliques! - cutting off at "+Clique_Tester.MAX_CLIQUE+" for larger files change the default Clique_Tester.MAX_CLIQUE param");
  433.             sb.append('\n');
  434.             System.out.println("ERROR: too many cliques! - cutting off at "+Clique_Tester.MAX_CLIQUE+" for larger files change the default Clique_Tester.MAX_CLIQUE param");
  435.             FINISH_TEST=true;
  436.         }
  437.         if(i%t==0) {
  438.             System.out.print(".");
  439.         }
  440.         done=true;
  441.         available=true;
  442.     }
  443.     Vector<Clique> allC_seed(Clique edge, int min_size, int max_size) {
  444.         Vector<Clique> ans = new Vector<Clique>();
  445.         ans.add(edge);
  446.         int i=0;
  447.     //  int size = 2;
  448.         while (ans.size()>i) {
  449.             Clique curr = ans.elementAt(i);
  450.             if(curr.size()<max_size) {
  451.                 VertexSet Ni = curr.commonNi();
  452.                 for(int a=0;a<Ni.size();a++) {
  453.                     Clique c = new Clique(curr,Ni.at(a));
  454.                     ans.add(c);
  455.                 }
  456.             }
  457.             else {i=ans.size();} // speedup trick
  458.             i++;
  459.         }
  460.        
  461.         return ans;
  462.     }
  463.    
  464. }
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!