KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > enhydra > jawe > xml > GraphChecker


1 /**
2  * GraphChecker.java
3  *
4  * Authors:
5  *
6  * Bojanic Sasa sasaboy@neobee.net
7  * Djojic Predrag predrag@prozone.co.yu
8  */

9
10 package org.enhydra.jawe.xml;
11
12 import java.util.*;
13
14 /**
15  * You can use this class to check if the graph is cyclic, or to
16  * find index of corresponding join node for the given split node index.
17  * When constructing class, you have to pass it the incidence matrix, which
18  * has to be the two-dimensional array of booleans , where the rows and
19  * column indexes represents the graph node indexes, and values represents
20  * if there is a connection between these nodes. If there is connection
21  * from node <b>i</b> to the node <b>j</b> it is represented by putting
22  * <b>true</true> into j'th column of the i'th row.
23  */

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 JavaDoc node(int index){
58       return new Integer JavaDoc(index);
59    }
60
61    private int index(Integer JavaDoc node){
62       return node.intValue();
63    }
64
65    private int indexAt(Vector nodeSet,int pos){
66       return index((Integer JavaDoc)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    /**
130     * Constructs the GraphChecker object.
131     *
132     * @param matParam The two dimensional array of booleans representing
133     * the graphs incidence matrix.
134     */

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    /**
157     * @return <code>true</code> if the graph is cyclic, and <code>false</code>
158     * otherwise.
159     */

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    /**
185     * @return The array of graph node indexes that are within some graph cycle.
186     * If the graph is not cyclic, returns <code>null</code>.
187     */

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    /**
230     * Returns index of corresponding join node for the given split node index.
231     * @param nodeX The index of split node
232     * @return Index of corresponding join node if it exists, <b>-1</b> otherwise.
233     */

234    public int getJoinIndex(int nodeX){
235       undo();
236       if (!isGraphCyclic()){
237          undo();
238          if (isSplit(nodeX)){ // checking if the node has at least two outgoing branches
239
Vector workingSet=new Vector();
240             // putting the children of given node into the workingSet (there
241
// must be at least two children)
242
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                // remove all nodes that have parent (they are waiting for
253
// parent to get to them) from working set, and place them
254
// into temporary set
255
//System.out.println("WS1="+workingSet);
256
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 //System.out.println("WS2="+workingSet);
264
// if temporary set is empty, and working set has only one
265
// node -> this node is one we are looking for
266
if (workingSet.size()==1 && tempSet.size()==0) {
267                   return indexAt(workingSet,0);
268                }
269
270                // iterating through the whole set
271
for(int j=0; j<workingSet.size(); j++){
272                   // determine the index of the node from j'th position within the working set
273
int actual=indexAt(workingSet,j);
274                   boolean actualChanged=false;
275                   // Iterating through incidence matrix and finding the children
276
for(int k=0; k<dim; k++){
277                      if(isLinked(actual,k)){ // if the k'th node is the child
278
unlink(actual,k); // unlinking it
279
changed=true; // something is is changed
280
actualChanged=true;
281                         if (!(isInSet(tempSet,k))){ // if child was not in the tempSet
282
tempSet.addElement(node(k)); // put it to wait for the next while loop iteration
283
}
284                      }
285                   }
286                   // if nothing changed to the actual node->it is possibly the
287
// the wanted node, so put it into tempSet
288
if(!actualChanged && !(isInSet(tempSet,actual))){
289                      tempSet.addElement(node(actual));
290                   }
291 //System.out.println("actual="+actual+"WSS="+(workingSet.size()-1)+", j="+j+", TSS="+tempSet.size()+", TS="+tempSet);
292
//System.out.println("Iter "+j+", ts="+tempSet);
293
}
294                // working set for the next iteration becomes tempSet
295
workingSet=tempSet;
296             }
297          }
298          return -1;
299       }
300       return -1;
301    }
302 }
303
Popular Tags