wajueshequsuanfa.txt

这是对挖掘 web社区划分的算法,希望大家能够参考并提出意见.

public class ndGraph
{
         private int n;
         private int [] node;
         private int [] group;
         private int edgenum;
         private int groupnum;
      public ndGraph(int n)
      {
             if(n>1)
             {
                 this.n=n;
                 node = new int[n*(n-1)/2];
                 group = new int[n];
                 this.groupnum = 1;
             }
             else
             System.out.println("n!>1");
      }


      public void addEdge(int i,int j)
      {
             if(i!=j)
             {
                 if(this.node[this.transcode(i,j)]!=1)
                 {
                  this.node[this.transcode(i,j)]=1;
                  this.edgenum++;
                 }
             }
             else
             System.out.println("i==j");
      }


      public void remove(int i,int j)
      {
             if(i!=j)
             {
                 if(this.node[this.transcode(i,j)]!=0)
                 {
                  this.node[this.transcode(i,j)]=0;
                  this.edgenum--;
                 }
             }
             else
             System.out.println("i==j");
      }

      
      public boolean isConn(int i,int j)
      {
            if(i!=j&&this.node[this.transcode(i,j)]!=0)
            return true;
            else 
            return false;
      }


      public void setgroup(int n,int b)
      {
            this.group[n-1]=b;
      }


      public int getGroup(int n)
      {
             return this.group[n-1];
      }


      private int transcode(int i,int j)
      {
             if(i>j)
             return i*(i-1)/2-(i-j);
             else if(i<j)
             return j*(j-1)/2-(j-i);
             else 
             return -1;
      }


      public int getNodenum()
      {
             return this.n;
      }


      public int getDu(int a)
      {
            int m=0;
            for (int i=1;i<=this.n;i++)
                if(i==a)
                continue;
                else if(this.node[this.transcode(a,i)]!=0)
                m++;
            return m;
      }


      public int getKri(int a)
      {
            int sumnum = 0;
            for (int i = 1; i<=this.n; i++)
            {
                 if(i==a)
                 continue;
                 else
                 if(this.node[this.transcode(a,i)]!0&&this.group[a-1]==this.group[i-1])
                 sumnum++;
            }
            return sumnum;
      }


      public float getLama(int a)
      {
            return (float)this.getKri(a)/(float)this.getDu(a)-(float)this.getDu(a)/(float)this.Edgenum;
      }


      public float getQ()
      {
            float sum = 0f;
            sum = sum + this.getGroupNum(0)/77f-(float)Math.pow((this.getGCrossEdge()+this.getGroupNum(0))/77f.2);
            sum = sum + this.getGroupNum(1)/77f-(float)Math.pow((this.getGCrossEdge()+this.getGroupNum(1))/77f.2);
      } 


      public float getminCR()
      {
            float min = 100f;
            float tmp = 0f;
            for (int i = 0;i<this.groupnum;i++)
                 {
                      tmp = (float)this.getGroupNum(i)/this.edgenum;
                      if(tmp<min)
                      min = tmp;
                 }
                 return min;
      } 
  

      public int getEdgenum()
      {
            return this.edgenum;
      }


      public String toString()
      {
            String o = "";
            for (int i = 0;i<this.group.length;j++)
            {
                 o = o + "Group"+i+":";
                 for (int j = 0;j<this.group.length;j++)
                 if(this.group[j]==i)
                 o = o+(j+1)+",";
                 o = o+"\n";
            }
            return o;
      }


      public void split(int m)
      {
           this.groupnum = m;
           for (int i = 0;i<m;i++)
           for (int j = 1;j<=this.getNodenum()/m;j++)
           this.setgroup((j+i*(this.getNodenum()/m)),i);
           if(this.getNodenum()%m!=0)
           {
                for (int i = 0;i<this.getNodenum()%m;i++)
                this.setgroup(this.getNodenum()-i,(int)(Math.random()*m));
           }
      }


      public void splitrnd(int m)
      {
           this.groupnum = m;
           for (int i = 1 ; i<=this.n ; i++)
           this.setgroup(i,(int)(Math.random()*m));
      }


      public int getGnum()
      {
           return this.groupnum;
      }


      public String getGroupinfo()
      {
           String o ="";
           for (int i = 0; i<=this.group.length; i++)
           o +=this.group[i]+"-";
           return o;
      }


      public int getminnode(int g)
      {
           float l =9999f;
           float la = 0f;
           int a = 1;
           for (int i = 1;i<=this.n;i++)
           {
               if(this.group[i-1]==g)
               {
                    la = this.getLama(i);
                    if(la<=1)   {l = la ; a = i;}
               }
           }
           return a;
      }


      public int getminnode()
      {
           float l =9999f;
           float la = 0f;
           int a = 1;
           for (int i = 1;i<=this.n;i++)
           {               
                la = this.getLama(i);
                if(la<=1)   {l = la ; a = i;}               
           }
           return a;
      }


      public String getPath(int a)
      {
           String o ="Node"+a+":";
           for (int i = 1;i<=this.n; i++)
           if (this.isConn(a,i)==true)
           o+=i+"-";
           return o;
      }


      public int judgeEdge(int e)
      {
           int a=0,b=0;
           int m=a;
           for (int i = 1; i<=this.n;i++)
           {
                m = i*(i-1)/2;
                if(e==m)
                {a = i;break;}
                else if (e<m)
                {a = i-1;break;}
                else
                continue;
           }
           b = e-a*(a-1)/2;
           a++;
           b++;
           if (this.getGroup(a)==this.getGroup(b))
           {
                return this.getGroup(a);
           }
           else
           {
                return -1;
           }
      }


      public int getGroupNum(int g)
      {
           int m=0;
           for (int i = 0;i<this.node.length; i++)
           if (this.node[i]==1&&this.judgeEdge(i)==g)
           m++;
           return m;
      }


      public int getnGoupNum(int g)
      {
           int a=0;
           for (int i = 0; i<this.group.length;i++)
           if (this.group[i]==g) a++;
           return a;
      }


      public void repair()
      {
           int[] c = new int[this.group.length];
           for (int i = 0;i<this.n;i++)
           c[i] = this.getNodeNBgroup(i+1);
           for (int i = 0; i<this.n;i++)
           this.setgroup(i+1,c[i]);
      }


      public int getNodeNBgroup(int a)
      {
           int[] b = new int[2];
           for (int i = 0;i<this.n;i++)
           if(this.isConn(a,i+1))
           b[this.isConn(a,i+1)]++;
           if(b[0]==0)
           {
                return 1;
           }
           else if(b[1]==0)
           {
                return 0;
           }
           else
           return this.getGroup(a);
      }
      public static void main(String[] args)
      {
           ndGraph.judgeedge(7);
      }
}