📄 hierarchicalbcengine.java
字号:
*/
protected void clearTemps_and_EdgesFromNodes() {
/*
System.out.println("Before.............");
for(int i=0; i<m_nodes.size(); i++) {
GraphNode n = (GraphNode)m_nodes.elementAt(i);
System.out.println("N: "+n.ID+","+i);
}
System.out.println("origNodesSize: "+origNodesSize);
*/
int curSize = m_nodes.size();
for(int i=origNodesSize; i<curSize; i++)
m_nodes.removeElementAt(origNodesSize);
for(int j=0; j<m_nodes.size(); j++)
((GraphNode)m_nodes.elementAt(j)).edges = null;
nodeLevels=null;
/*
System.out.println("After..............");
for(int i=0; i<m_nodes.size(); i++) {
GraphNode n = (GraphNode)m_nodes.elementAt(i);
System.out.println("N: "+n.ID+","+i);
}
*/
}
/**
* This method makes the "graphMatrix" interconnection
* matrix for the graph given by m_nodes and m_edges
* vectors. The matix is used by other methods.
*/
protected void processGraph() {
origNodesSize = m_nodes.size();
graphMatrix = new int[m_nodes.size()][m_nodes.size()];
/*
System.out.println("The "+m_nodes.size()+" nodes are: ");
for(int i=0; i<m_nodes.size(); i++)
System.out.println((String)m_nodes.elementAt(i)+" ");
System.out.println("\nThe "+m_edges.size()+" edges are: ");
for(int i=0; i<m_edges.size(); i++)
System.out.println((GraphEdge)m_edges.elementAt(i));
*/
for(int i=0; i<m_edges.size(); i++)
graphMatrix[((GraphEdge)m_edges.elementAt(i)).src]
[((GraphEdge)m_edges.elementAt(i)).dest] = ((GraphEdge)m_edges.elementAt(i)).type;
/*
System.out.print("\t");
for(int i=0; i<graphMatrix.length; i++)
System.out.print(((GraphNode)m_nodes.elementAt(i)).ID+" ");
System.out.println("");
for(int i=0; i<graphMatrix.length; i++) {
GraphNode n = (GraphNode)m_nodes.elementAt(i);
System.out.print(n.ID+"\t");
for(int j=0; j<graphMatrix[i].length; j++)
System.out.print(graphMatrix[i][j]+" ");
System.out.println("");
}
*/
}
/*
* This method makes a proper hierarchy of the graph
* by first removing cycles, then assigning levels
* to the nodes and then removing gaps by adding
* dummy vertices.
*/
protected void makeProperHierarchy() {
processGraph();
m_progress.setValue(1);
m_progress.setString("Removing Cycles");
//****removing cycles
removeCycles();
m_progress.setValue(2);
m_progress.setString("Assigning levels to nodes");
//****Assigning vertical level to each node
int nodesLevel[] = new int[m_nodes.size()];
int depth=0;
for(int i=0; i<graphMatrix.length; i++) {
assignLevels(nodesLevel, depth, i, 0);
}
for(int i=0; i<nodesLevel.length; i++) {
if(nodesLevel[i]==0) {
int min=65536;
for(int j=0; j<graphMatrix[i].length; j++) {
if(graphMatrix[i][j]==DIRECTED)
if(min>nodesLevel[j])
min = nodesLevel[j];
}
if(min!=65536 && min>1) //if the shallowest child of a parent has a depth greater than 1
nodesLevel[i]=min-1; // and it is not a lone parent with no children
}
}
//System.out.println("");
int maxLevel=0;
for(int i=0; i<nodesLevel.length; i++) {
if(nodesLevel[i]>maxLevel)
maxLevel = nodesLevel[i];
//System.out.println(((GraphNode)m_nodes.elementAt(i)).ID+" "+i+">"+nodesLevel[i]);
}
int levelCounts[] = new int[maxLevel+1];
for(int i=0; i<nodesLevel.length; i++) {
levelCounts[nodesLevel[i]]++;
}
//System.out.println("------------------------------------------");
//****Assigning nodes to each level
int levelsCounter[] = new int[maxLevel+1];
nodeLevels = new int[maxLevel+1][];
for(byte i=0; i<nodesLevel.length; i++) {
if(nodeLevels[nodesLevel[i]]==null)
nodeLevels[nodesLevel[i]] = new int[ levelCounts[nodesLevel[i]] ];
//nodeLevels[nodesLevel[i]].addElement(new Integer(i));
//System.out.println(((GraphNode)m_nodes.elementAt(i)).ID+" "+nodesLevel[i]+">"+levelCounts[nodesLevel[i]]);
nodeLevels[nodesLevel[i]][levelsCounter[nodesLevel[i]]++] = i;
}
m_progress.setValue(3);
m_progress.setString("Removing gaps by adding dummy vertices");
//****Making a proper Hierarchy by putting in dummy vertices to close all gaps
if(m_jCbEdgeConcentration.isSelected())
removeGapsWithEdgeConcentration(nodesLevel);
else
removeGaps(nodesLevel);
//After assigning levels and adding dummy vertices
//System.out.print("\n\t");
//for(int i=0; i<graphMatrix.length; i++)
// System.out.print(((GraphNode)m_nodes.elementAt(i)).ID+" ");
//System.out.println("");
//for(int i=0; i<graphMatrix.length; i++) {
// System.out.print(((GraphNode)m_nodes.elementAt(i)).ID+"\t");
// for(int j=0; j<graphMatrix[i].length; j++)
// System.out.print(graphMatrix[i][j]+" ");
// System.out.println("");
//}
//****Updating edges[][] array of nodes from
//****the interconnection matrix, which will be used
//****by the Visualizer class to draw edges
for(int i=0; i<graphMatrix.length; i++) {
GraphNode n = (GraphNode)m_nodes.elementAt(i);
int sum=0;
for(int j=0; j<graphMatrix[i].length; j++)
if(graphMatrix[i][j]!=0)
sum++;
n.edges = new int[sum][2];
for(int j=0, k=0; j<graphMatrix[i].length; j++)
if(graphMatrix[i][j]!=0) {
n.edges[k][0] = j;
n.edges[k][1] = graphMatrix[i][j]; k++;
}
//n.edges = graphMatrix[i];
}
//Interconnection matrices at each level, 1 to n-1
//printMatrices(nodeLevels);
}
/**
* This method removes gaps from the graph. It doesn't perform
* any concentration. It takes as an argument of int[]
* of length m_nodes.size() containing the level of each
* node.
*/
private void removeGaps(int nodesLevel[]) {
int temp = m_nodes.size();
int temp2=graphMatrix[0].length, tempCnt=1;
for(int n=0; n<temp; n++) {
for(int i=0; i<temp2; i++) {
int len = graphMatrix.length;
if(graphMatrix[n][i]>0)
if(nodesLevel[i]>nodesLevel[n]+1) {
int tempMatrix[][] =
new int[graphMatrix.length+(nodesLevel[i]-nodesLevel[n]-1)][graphMatrix.length+(nodesLevel[i]-nodesLevel[n]-1)];
int level = nodesLevel[n]+1;
copyMatrix(graphMatrix, tempMatrix);
String s1 = new String("S"+tempCnt++);
m_nodes.addElement(new GraphNode(s1, s1, SINGULAR_DUMMY)); //true));
int temp3 [] = new int[nodeLevels[level].length+1];
//for(int j=0; j<nodeLevels[level].length; j++)
// temp3[j] = nodeLevels[level][j];
System.arraycopy(nodeLevels[level], 0, temp3, 0, nodeLevels[level].length);
temp3[temp3.length-1] = m_nodes.size()-1;
nodeLevels[level] = temp3; level++;
//nodeLevels[level++].addElement(new Integer(m_nodes.size()-1));
//System.out.println("len:"+len+","+nodesLevel[i]+","+nodesLevel[n]);
int k;
for(k=len; k<len+nodesLevel[i]-nodesLevel[n]-1-1; k++) {
String s2 = new String("S"+tempCnt);
m_nodes.addElement( new GraphNode(s2, s2, SINGULAR_DUMMY) ); //true) );
temp3 = new int[nodeLevels[level].length+1];
//for(int j=0; j<nodeLevels[level].length; j++)
// temp3[j] = nodeLevels[level][j];
System.arraycopy(nodeLevels[level], 0, temp3, 0, nodeLevels[level].length);
temp3[temp3.length-1] = m_nodes.size()-1;
nodeLevels[level++] = temp3;
//nodeLevels[level++].addElement(new Integer(m_nodes.size()-1));
tempMatrix[k][k+1]=tempMatrix[n][i]; tempCnt++;
if(k>len)
tempMatrix[k][k-1]=-1*tempMatrix[n][i];
}
tempMatrix[k][i]=tempMatrix[n][i]; //temp[lastTempNodeCreated][targetNode]=temp[origNode][targetNode]
//System.out.println("k "+((GraphNode)m_nodes.elementAt(k)).ID+
// " i "+((GraphNode)m_nodes.elementAt(i)).ID+
// " n "+((GraphNode)m_nodes.elementAt(n)).ID+
// " len "+((GraphNode)m_nodes.elementAt(len)).ID );
tempMatrix[n][len] = tempMatrix[n][i]; //temp[origNode][firstTempNodecreated] = temp[origNode][targetNode]
tempMatrix[len][n] = -1*tempMatrix[n][i]; //temp[firstTempNodeCreated][origNode] for reverse tracing
tempMatrix[i][k] = -1*tempMatrix[n][i]; //temp[targetNode][lastTempNodecreated] for reverse tracing
if(k>len) //temp[lastTempNodeCreated][secondlastNode] for reverse tracing
tempMatrix[k][k-1] = -1*tempMatrix[n][i]; //but only do this if more than 1 temp nodes are created
tempMatrix[n][i] = 0; //temp[origNode][targetNode] = 0 unlinking as they have been
tempMatrix[i][n] = 0; // linked by a chain of temporary nodes now.
graphMatrix = tempMatrix;
}
else {
//****Even if there is no gap just add a reference for the
//****parent to the child for reverse tracing, useful if the
//****there is a reversed edge from parent to child and therefore visualizer
//****would know to highlight this edge when highlighting the child.
graphMatrix[i][n]=-1*graphMatrix[n][i];
}
}
}
//Interconnection matrices at each level, 1 to n-1 after minimizing edges
//printMatrices(nodeLevels);
}
/**
* This method removes gaps from the graph. It tries to minimise the number
* of edges by concentrating multiple dummy nodes from the same parent and
* on the same vertical level into one. It takes as an argument of int[]
* of length m_nodes.size() containing the level of each
* node.
*/
private void removeGapsWithEdgeConcentration(int nodesLevel[]) {
final int temp = m_nodes.size(), temp2=graphMatrix[0].length;
int tempCnt=1;
for(int n=0; n<temp; n++) {
for(int i=0; i<temp2; i++) {
if(graphMatrix[n][i]>0)
if(nodesLevel[i]>nodesLevel[n]+1) {
//System.out.println("Processing node "+((GraphNode)m_nodes.elementAt(n)).ID+
// " for "+((GraphNode)m_nodes.elementAt(i)).ID);
int tempLevel=nodesLevel[n];
boolean tempNodePresent=false;
int k=temp;
int tempnode = n;
while(tempLevel < nodesLevel[i]-1 ) {
tempNodePresent=false;
for(; k<graphMatrix.length; k++) {
if(graphMatrix[tempnode][k]>0) {
//System.out.println("tempnode will be true");
tempNodePresent = true; break;
}
}
if(tempNodePresent) {
tempnode=k; k=k+1;
tempLevel++;
}
else {
if(tempnode!=n)
tempnode=k-1;
//System.out.println("breaking from loop");
break;
}
}
if(((GraphNode)m_nodes.elementAt(tempnode)).nodeType==SINGULAR_DUMMY)
((GraphNode)m_nodes.elementAt(tempnode)).nodeType=PLURAL_DUMMY;
if(tempNodePresent) {
graphMatrix[tempnode][i] = graphMatrix[n][i]; //Link the last known temp node to target
//System.out.println("modifying "+((GraphNode)nodes.elementAt(tempnode)).ID+
// ", "+((GraphNode)nodes.elementAt(n)).ID);
/////graphMatrix[tempnode][n] = -graphMatrix[n][i]; //matrix[lastknowntempnode][source]=-original_val
//System.out.println("modifying "+((GraphNode)nodes.elementAt(i)).ID+
// ", "+((GraphNode)nodes.elementAt(tempnode)).ID);
graphMatrix[i][tempnode] = -graphMatrix[n][i]; //and matrix[target][lastknowntempnode]=-original_val
//for reverse tracing
graphMatrix[n][i] = 0; //unlink source from the target
graphMatrix[i][n] = 0;
continue;
}
int len = graphMatrix.length;
int tempMatrix[][] =
new int[graphMatrix.length+(nodesLevel[i]-nodesLevel[tempnode]-1)]
[graphMatrix.length+(nodesLevel[i]-nodesLevel[tempnode]-1)];
int level = nodesLevel[tempnode]+1;
copyMatrix(graphMatrix, tempMatrix);
String s1 = new String("S"+tempCnt++);
//System.out.println("Adding dummy "+s1);
m_nodes.addElement(new GraphNode(s1, s1, SINGULAR_DUMMY));
int temp3 [] = new int[nodeLevels[level].length+1];
System.arraycopy(nodeLevels[level], 0, temp3, 0, nodeLevels[level].length);
temp3[temp3.length-1] = m_nodes.size()-1;
nodeLevels[level] = temp3;
temp3 = new int[m_nodes.size()+1];
System.arraycopy(nodesLevel, 0, temp3, 0, nodesLevel.length);
temp3[m_nodes.size()-1] = level;
nodesLevel = temp3;
level++;
//nodeLevels[level++].addElement(new Integer(m_nodes.size()-1));
//System.out.println("len:"+len+"("+((GraphNode)m_nodes.elementAt(len)).ID+
// "),"+nodesLevel[i]+","+nodesLevel[tempnode]);
int m;
for(m=len; m<len+nodesLevel[i]-nodesLevel[tempnode]-1-1; m++) {
String s2 = new String("S"+tempCnt++);
//System.out.println("Adding dummy "+s2);
m_nodes.addElement( new GraphNode(s2, s2, SINGULAR_DUMMY) );
temp3 = new int[nodeLevels[level].length+1];
//for(int j=0; j<nodeLevels[level].length; j++)
// temp3[j] = nodeLevels[level][j];
System.arraycopy(nodeLevels[level], 0, temp3, 0, nodeLevels[level].length);
temp3[temp3.length-1] = m_nodes.size()-1;
nodeLevels[level] = temp3;
temp3 = new int[m_nodes.size()+1];
System.arraycopy(nodesLevel, 0, temp3, 0, nodesLevel.length);
temp3[m_nodes.size()-1] = level;
nodesLevel = temp3;
level++;
//nodeLevels[level++].addElement(new Integer(m_nodes.size()-1));
//System.out.println("modifying "+((GraphNode)nodes.elementAt(m)).ID+
// ", "+((GraphNode)nodes.elementAt(m+1)).ID);
tempMatrix[m][m+1]=tempMatrix[n][i]; //tempCnt++;
if(m>len) {
//System.out.println("modifying "+((GraphNode)nodes.elementAt(m)).ID+
// ", "+((GraphNode)nodes.elementAt(m-1)).ID);
tempMatrix[m][m-1]=-1*tempMatrix[n][i];
}
}
//System.out.println("m "+((GraphNode)m_nodes.elementAt(m)).ID+
// " i "+((GraphNode)m_nodes.elementAt(i)).ID+
// " tempnode "+((GraphNode)m_nodes.elementAt(tempnode)).ID+
// " len "+((GraphNode)m_nodes.elementAt(len)).ID );
//System.out.println("modifying "+((GraphNode)nodes.elementAt(m)).ID+
// ", "+((GraphNode)nodes.elementAt(i)).ID);
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -