📄 hierarchicalbcengine.java
字号:
//System.out.println("\nCrossings after phaseIID: "+crossings(nodeLevels));
}
return nodeLevels;
}
}
/**
* See Sugiyama et al. 1981 (full reference give at top)
* lindex is the index of the level we want to process.
* In this method we'll sort the vertices at the level one
* below lindex according to their UP-barycenters (or column
* barycenters).
*/
protected void phaseID(final int lindex, final int levels[][]) {
float colBC[]; //= new float[levels[lindex+1].size()];
colBC = calcColBC(lindex, levels);
//System.out.println("In ID Level"+(lindex+1)+":");
//System.out.print("\t");
//for(int i=0; i<colBC.length; i++)
// {System.out.print("Col"+(i+1)+":"+colBC[i]+" ");
// }
//System.out.println("");
//colBC = calcColBC1(lindex, levels);
//for(int i=0; i<colBC.length; i++)
// {System.out.print("Col"+(i+1)+":"+colBC[i]+" ");
// }
//System.out.println("");
//System.out.print("\n\tNodes ");
//for(int i=0; i<levels[lindex+1].length; i++)
// System.out.print(levels[lindex+1][i]+" ");
//System.out.println("");
//System.out.println("\nCrossings: "+crossings(levels));
//inspect(false, lindex, levels, colBC);
isort(levels[lindex+1], colBC);
//combSort11(levels[lindex+1], colBC);
//System.out.println("After sorting");
//System.out.print("\t");
//for(int i=0; i<colBC.length; i++)
// {System.out.print("Col"+(i+1)+":"+colBC[i]+" ");
// }
//System.out.print("\n\tNodes ");
//for(int i=0; i<levels[lindex+1].length; i++)
// System.out.print(levels[lindex+1][i]+" ");
//System.out.println("\nCrossings: "+crossings(levels));
///System.out.println("");
}
/**
* See Sugiyama et al. 1981 (full reference give at top)
* lindex is the index of the level we want to process.
* In this method we'll sort the vertices at the level
* lindex according to their DOWN-barycenters (or row
* barycenters).
*/
public void phaseIU(final int lindex, final int levels[][]) {
float rowBC[];
rowBC = calcRowBC(lindex, levels);
//System.out.println("In IU Level"+(lindex+1)+":");
//System.out.print("\t");
//for(int i=0; i<rowBC.length; i++)
// {System.out.print("Row"+(i+1)+":"+rowBC[i]+" ");
// }
// System.out.print("\n\t");
// rowBC = calcRowBC1(lindex, levels);
// for(int i=0; i<rowBC.length; i++)
// {System.out.print("Row"+(i+1)+":"+rowBC[i]+" ");
// }
// System.out.println("");
//System.out.print("\n\tNodes ");
//for(int i=0; i<levels[lindex].length; i++)
// System.out.print(levels[lindex][i]+" ");
//System.out.println("\nCrossings: "+crossings(levels));
//inspect(true, lindex, levels, rowBC);
isort(levels[lindex], rowBC);
//combSort11(levels[lindex], rowBC);
//System.out.println("After sorting\n\t");
//for(int i=0; i<rowBC.length; i++)
// {System.out.print("Row"+(i+1)+":"+rowBC[i]+" ");
// }
//System.out.print("\n\tNodes ");
//for(int i=0; i<levels[lindex].length; i++)
// System.out.print(levels[lindex][i]+" ");
//System.out.println("\nCrossings: "+crossings(levels));
}
/**
* See Sugiyama et al. 1981 (full reference give at top)
*/
public void phaseIID(final int lindex, final int levels[][]) {
float colBC[];
colBC = calcColBC(lindex, levels);
//System.out.println("getting into phase IID");
for(int i=0; i<colBC.length-1; i++) {
if(colBC[i]==colBC[i+1]) {
//System.out.println("Crossings before begining of iteration: "+crossings(levels));
int tempLevels[][] = new int[levels.length][];
copy2DArray(levels, tempLevels);
//System.out.println("Interchanging: "+((GraphNode)m_nodes.elementAt(levels[lindex+1][i])).ID+" & "+
// ((GraphNode)m_nodes.elementAt(levels[lindex+1][(i+1)])).ID+
// " at level "+(lindex+1) );
int node1 = levels[lindex+1][i];
int node2 = levels[lindex+1][i+1];
levels[lindex+1][i+1] = node1;
levels[lindex+1][i] = node2;
for(int k=lindex+1; k<levels.length-1; k++)
phaseID(k, levels);
//System.out.println("Crossings temp:"+crossings(tempLevels)+" graph:"+crossings(levels));
if(crossings(levels)<=crossings(tempLevels))
{ //System.out.println("Crossings temp: "+crossings(tempLevels)+" Crossings levels: "+crossings(levels));
copy2DArray(levels, tempLevels); } //printMatrices(levels); }
else {
copy2DArray(tempLevels, levels);
levels[lindex+1][i+1] = node1;
levels[lindex+1][i] = node2;
}
//System.out.println("Crossings after PhaseID of phaseIID, in iteration "+i+" of "+(colBC.length-1)+" at "
// +lindex+", levels: "+crossings(levels)+" temp: "+crossings(tempLevels));
//tempLevels = new int[levels.length][];
//copy2DArray(levels, tempLevels);
for(int k=levels.length-2; k>=0; k--)
phaseIU(k, levels);
//System.out.println("Crossings temp:"+crossings(tempLevels)+" graph:"+crossings(levels));
//if(crossings(tempLevels)<crossings(levels))
// { //System.out.println("Crossings temp: "+crossings(tempLevels)+" Crossings levels: "+crossings(levels));
// copy2DArray(tempLevels, levels); } //printMatrices(levels); }
if(crossings(tempLevels)<crossings(levels))
copy2DArray(tempLevels, levels);
//System.out.println("Crossings after PhaseIU of phaseIID, in iteration "+i+" of "+(colBC.length-1)+" at "
// +lindex+", levels: "+crossings(levels)+" temp: "+crossings(tempLevels));
//colBC = calcColBC(lindex, levels);
}
}
}
/**
* See Sugiyama et al. 1981 (full reference give at top)
*/
public void phaseIIU(final int lindex, final int levels[][]) {
float rowBC[];
rowBC = calcRowBC(lindex, levels);
//System.out.println("Getting into phaseIIU");
for(int i=0; i<rowBC.length-1; i++) {
if(rowBC[i]==rowBC[i+1]) {
//System.out.println("Crossings before begining of iteration: "+crossings(levels));
int tempLevels[][] = new int[levels.length][];
copy2DArray(levels, tempLevels);
//System.out.println("Interchanging: "+((GraphNode)m_nodes.elementAt(levels[lindex][i])).ID+" & "+
// ((GraphNode)m_nodes.elementAt(levels[lindex][i+1])).ID+
// " at level "+(lindex+1) );
int node1 = levels[lindex][i];
int node2 = levels[lindex][i+1];
levels[lindex][i+1] = node1;
levels[lindex][i] = node2;
for(int k=lindex-1; k>=0; k--)
phaseIU(k, levels);
if(crossings(levels)<=crossings(tempLevels))
{ //System.out.println("Crossings temp: "+crossings(tempLevels)+" Crossings levels: "+crossings(levels));
copy2DArray(levels, tempLevels); } //printMatrices(levels);
else {
copy2DArray(tempLevels, levels);
levels[lindex][i+1] = node1;
levels[lindex][i] = node2;
}
//System.out.println("Crossings after PhaseIU of PhaseIIU, in iteration "+i+" of "+(rowBC.length-1)+" at "
// +lindex+", levels: "+crossings(levels)+" temp: "+crossings(tempLevels));
//tempLevels = new int[levels.length][];
//copy2DArray(levels, tempLevels);
for(int k=0; k<levels.length-1; k++) //lindex-1; k++)
phaseID(k, levels);
//if(crossings(tempLevels)<crossings(levels))
// { //System.out.println("Crossings temp: "+crossings(tempLevels)+" Crossings levels: "+crossings(levels));
// copy2DArray(tempLevels, levels); } //printMatrices(levels); }
if(crossings(tempLevels)<=crossings(levels))
copy2DArray(tempLevels, levels);
//System.out.println("Crossings after PhaseID of phaseIIU, in iteration "+i+" of "+(rowBC.length-1)+" at "
// +lindex+", levels: "+crossings(levels)+" temp: "+crossings(tempLevels));
//rowBC = calcRowBC(lindex, levels);
}
}
}
/**
* See Sugiyama et al. 1981 (full reference give at top)
*/
protected float [] calcRowBC(final int lindex, final int levels[][]){
float rowBC[] = new float[levels[lindex].length];
GraphNode n;
for(int i=0; i<levels[lindex].length; i++) {
int sum=0;
n = (GraphNode)m_nodes.elementAt(levels[lindex][i]);
for(int j=0; j<n.edges.length; j++) {
if(n.edges[j][1]>0) {
sum++;
try {
rowBC[i] = rowBC[i]+indexOfElementInLevel(n.edges[j][0], levels[lindex+1])+1;
}
catch(Exception ex) { return null; }
}
}
if(rowBC[i]!=0)
rowBC[i] = rowBC[i]/sum;
}
return rowBC;
}
/**
* See Sugiyama et al. 1981 (full reference give at top)
*/
protected float [] calcColBC(final int lindex, final int levels[][]) {
float colBC[] = new float[levels[lindex+1].length];
GraphNode n;
for(int i=0; i<levels[lindex+1].length; i++) {
int sum=0;
n = (GraphNode)m_nodes.elementAt(levels[lindex+1][i]);
for(int j=0; j<n.edges.length; j++) {
if(n.edges[j][1]<1) {
sum++;
try{
colBC[i] = colBC[i]+indexOfElementInLevel(n.edges[j][0], levels[lindex])+1;
}
catch(Exception ex) { return null; }
}
}
if(colBC[i]!=0)
colBC[i]=colBC[i]/sum;
}
return colBC;
}
/**
* Prints out the interconnection matrix at each level.
* See Sugiyama et al. 1981 (full reference give at top)
*/
protected void printMatrices(final int levels[][]) {
int i=0;
for(i=0; i<levels.length-1; i++) {
float rowBC[]=null; float colBC[]=null;
try{
rowBC = calcRowBC(i, levels); colBC = calcColBC(i, levels);
}
catch(NullPointerException ne) {
System.out.println("i: "+i+" levels.length: "+levels.length); ne.printStackTrace(); return;
}
System.out.print("\nM"+(i+1)+"\t");
for(int j=0; j<levels[i+1].length; j++) {
System.out.print( ((GraphNode)m_nodes.elementAt(levels[i+1][j])).ID + " ");
//((Integer)levels[i+1].elementAt(j)).intValue())+" ");
}
System.out.println("");
for(int j=0; j<levels[i].length; j++) {
System.out.print( ((GraphNode)m_nodes.elementAt(levels[i][j])).ID+"\t");
//((Integer)levels[i].elementAt(j)).intValue())+"\t");
for(int k=0; k<levels[i+1].length; k++) {
System.out.print(graphMatrix[levels[i][j]] //((Integer)levels[i].elementAt(j)).intValue()]
[levels[i+1][k]]+" "); //((Integer)levels[i+1].elementAt(k)).intValue()]+" ");
}
System.out.println(rowBC[j]);
}
System.out.print("\t");
for(int k=0; k<levels[i+1].length; k++)
System.out.print(colBC[k]+" ");
}
System.out.println("\nAt the end i: "+i+" levels.length: "+levels.length);
}
/**
* This methods sorts the vertices in level[] according to their
* barycenters in BC[], using combsort11. It, however, doesn't touch the
* vertices with barycenter equal to zero.
*/
/*
protected static void combSort11(int level[], float BC[]) { //This method should be removed
int switches, j, top, gap, lhold;
float hold;
gap = BC.length;
do {
gap=(int)(gap/1.3);
switch(gap) {
case 0:
gap = 1;
break;
case 9:
case 10:
gap=11;
break;
default:
break;
}
switches=0;
top = BC.length-gap;
for(int i=0; i<top; i++) {
j=i+gap;
if(BC[i]==0 || BC[j]==0)
continue;
if(BC[i] > BC[j]) {
hold=BC[i];
BC[i]=BC[j];
BC[j]=hold;
lhold = level[i];
level[i] = level[j];
level[j] = lhold;
switches++;
}//endif
}//endfor
}while(switches>0 || gap>1);
}
*/
/**
* This methods sorts the vertices in level[] according to their
* barycenters in BC[], using insertion sort. It, however, doesn't touch the
* vertices with barycenter equal to zero.
*/
protected static void isort(int level[], float BC[]) { //Both level and BC have elements in the same order
float temp;
int temp2;
for(int i=0; i<BC.length-1; i++) {
int j=i;
temp=BC[j+1];
temp2=level[j+1];
if(temp==0)
continue;
int prej=j+1;
while( j>-1 && (temp<BC[j]|| BC[j]==0) ) {
if(BC[j]==0){
j--; continue;}
else {
BC[prej] = BC[j];
level[prej] = level[j];
prej=j;
j--;
}
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -