1 9 10 package org.enhydra.jawe.xml; 11 12 import java.util.*; 13 14 24 public class GraphChecker { 25 private boolean[][] mat; 26 27 private boolean[][] tempMat; 28 29 private int dim=0; 30 31 private boolean isLinked(int srcNode, int dstNode){ 32 return mat[srcNode][dstNode]; 33 } 34 35 36 private void link(int srcNode, int dstNode){ 37 mat[srcNode][dstNode]=true; 38 } 39 40 41 private void unlink(int srcNode, int dstNode){ 42 mat[srcNode][dstNode]=false; 43 } 44 45 private void unlinkParents(int node){ 46 for(int i=0;i<dim;i++){ 47 unlink(i,node); 48 } 49 } 50 51 private void unlinkChildren(int node){ 52 for(int i=0;i<dim;i++){ 53 unlink(node,i); 54 } 55 } 56 57 private Integer node(int index){ 58 return new Integer (index); 59 } 60 61 private int index(Integer node){ 62 return node.intValue(); 63 } 64 65 private int indexAt(Vector nodeSet,int pos){ 66 return index((Integer )nodeSet.elementAt(pos)); 67 } 68 69 private boolean isInSet(Vector nodeSet,int nodeIndex){ 70 for (int i=0; i<nodeSet.size(); i++){ 71 if(nodeIndex==indexAt(nodeSet,i)){ 72 return true; 73 } 74 } 75 return false; 76 } 77 78 private boolean isGraphEmpty(){ 79 boolean link=false; 80 for(int i=0; i<dim; i++){ 81 for(int j=0;j<dim;j++){ 82 link=link||isLinked(i,j); 83 } 84 } 85 return !link; 86 } 87 88 private boolean isJoin(int node){ 89 int parentCount=0; 90 for(int i=0;i<dim;i++){ 91 if(isLinked(i,node)){ 92 parentCount++; 93 } 94 } 95 return (parentCount>1); 96 97 } 98 99 private boolean isSplit(int node){ 100 int childCount=0; 101 for(int i=0;i<dim;i++){ 102 if(isLinked(node,i)){ 103 childCount++; 104 } 105 } 106 return (childCount>1); 107 } 108 109 private boolean isIsolated(int node){ 110 return (!hasChild(node))||(!hasParent(node)); 111 } 112 113 private boolean hasChild(int node){ 114 boolean child=false; 115 for(int i=0;i<dim;i++){ 116 child = child || isLinked(node,i); 117 } 118 return child; 119 } 120 121 private boolean hasParent(int node){ 122 boolean parent=false; 123 for(int i=0;i<dim;i++){ 124 parent = parent || isLinked(i,node); 125 } 126 return parent; 127 } 128 129 135 public GraphChecker(boolean[][] matParam){ 136 tempMat=matParam; 137 dim=tempMat.length; 138 mat= new boolean[dim][dim]; 139 for(int x=0; x<dim; x++){ 140 for(int y=0; y<dim; y++){ 141 mat[x][y]=tempMat[x][y]; 142 } 143 } 144 145 } 146 147 private void undo(){ 148 for(int x=0; x<dim; x++){ 149 for(int y=0; y<dim; y++){ 150 mat[x][y]=tempMat[x][y]; 151 } 152 } 153 } 154 155 156 160 public boolean isGraphCyclic(){ 161 boolean ret=false; 162 boolean changed=true; 163 undo(); 164 while(changed){ 165 changed=false; 166 for(int i=0; i<dim; i++){ 167 if((!hasChild(i))||(!hasParent(i))){ 168 if(hasChild(i)){ 169 unlinkChildren(i); 170 changed=true; 171 } 172 if(hasParent(i)){ 173 unlinkParents(i); 174 changed=true; 175 } 176 } 177 } 178 } 179 ret=!isGraphEmpty(); 180 undo(); 181 return ret; 182 } 183 184 188 public int[] getCyclicNodes(){ 189 undo(); 190 boolean ret=false; 191 boolean changed=true; 192 while(changed){ 193 changed=false; 194 for(int i=0; i<dim; i++){ 195 if((!hasChild(i))||(!hasParent(i))){ 196 if(hasChild(i)){ 197 unlinkChildren(i); 198 changed=true; 199 } 200 if(hasParent(i)){ 201 unlinkParents(i); 202 changed=true; 203 } 204 } 205 } 206 } 207 if (!isGraphEmpty()){ 208 int nodeCount=0; 209 for(int i=0; i<dim; i++){ 210 if (!isIsolated(i)){ 211 nodeCount++; 212 } 213 } 214 int[] nodeArray=new int[nodeCount]; 215 int index=0; 216 for(int i=0; i<dim; i++){ 217 if (!isIsolated(i)){ 218 nodeArray[index++]=i; 219 } 220 } 221 undo(); 222 return nodeArray; 223 }else{ 224 undo(); 225 return null; 226 } 227 } 228 229 234 public int getJoinIndex(int nodeX){ 235 undo(); 236 if (!isGraphCyclic()){ 237 undo(); 238 if (isSplit(nodeX)){ Vector workingSet=new Vector(); 240 for(int i=0; i<dim; i++){ 243 if (isLinked(nodeX,i)){ 244 unlink(nodeX,i); 245 workingSet.addElement(node(i)); 246 } 247 } 248 boolean changed=true; 249 while(changed){ 250 changed=false; 251 Vector tempSet=new Vector(); 252 for(int j=workingSet.size()-1; j>=0;j--){ 257 int actual=indexAt(workingSet,j); 258 if (hasParent(actual)&&!(isInSet(tempSet,actual))){ 259 tempSet.addElement(node(actual)); 260 workingSet.remove(j); 261 } 262 } 263 if (workingSet.size()==1 && tempSet.size()==0) { 267 return indexAt(workingSet,0); 268 } 269 270 for(int j=0; j<workingSet.size(); j++){ 272 int actual=indexAt(workingSet,j); 274 boolean actualChanged=false; 275 for(int k=0; k<dim; k++){ 277 if(isLinked(actual,k)){ unlink(actual,k); changed=true; actualChanged=true; 281 if (!(isInSet(tempSet,k))){ tempSet.addElement(node(k)); } 284 } 285 } 286 if(!actualChanged && !(isInSet(tempSet,actual))){ 289 tempSet.addElement(node(actual)); 290 } 291 } 294 workingSet=tempSet; 296 } 297 } 298 return -1; 299 } 300 return -1; 301 } 302 } 303 | Popular Tags |