001: /**
002: * GraphChecker.java
003: *
004: * Authors:
005: *
006: * Bojanic Sasa sasaboy@neobee.net
007: * Djojic Predrag predrag@prozone.co.yu
008: */package org.enhydra.shark.xpdl;
009:
010: import java.util.Vector;
011:
012: /**
013: * You can use this class to check if the graph is cyclic, or to
014: * find index of corresponding join node for the given split node index.
015: * When constructing class, you have to pass it the incidence matrix, which
016: * has to be the two-dimensional array of booleans , where the rows and
017: * column indexes represents the graph node indexes, and values represents
018: * if there is a connection between these nodes. If there is connection
019: * from node <b>i</b> to the node <b>j</b> it is represented by putting
020: * <b>true</true> into j'th column of the i'th row.
021: */
022: public class GraphChecker {
023: private boolean[][] mat;
024:
025: private boolean[][] tempMat;
026:
027: private int dim = 0;
028:
029: private boolean isLinked(int srcNode, int dstNode) {
030: return mat[srcNode][dstNode];
031: }
032:
033: // private void link(int srcNode, int dstNode){
034: // mat[srcNode][dstNode]=true;
035: // }
036:
037: private void unlink(int srcNode, int dstNode) {
038: mat[srcNode][dstNode] = false;
039: }
040:
041: private void unlinkParents(int node) {
042: for (int i = 0; i < dim; i++) {
043: unlink(i, node);
044: }
045: }
046:
047: private void unlinkChildren(int node) {
048: for (int i = 0; i < dim; i++) {
049: unlink(node, i);
050: }
051: }
052:
053: private Integer node(int index) {
054: return new Integer(index);
055: }
056:
057: private int index(Integer node) {
058: return node.intValue();
059: }
060:
061: private int indexAt(Vector nodeSet, int pos) {
062: return index((Integer) nodeSet.elementAt(pos));
063: }
064:
065: private boolean isInSet(Vector nodeSet, int nodeIndex) {
066: for (int i = 0; i < nodeSet.size(); i++) {
067: if (nodeIndex == indexAt(nodeSet, i)) {
068: return true;
069: }
070: }
071: return false;
072: }
073:
074: private boolean isGraphEmpty() {
075: boolean link = false;
076: for (int i = 0; i < dim; i++) {
077: for (int j = 0; j < dim; j++) {
078: link = link || isLinked(i, j);
079: }
080: }
081: return !link;
082: }
083:
084: // private boolean isJoin(int node){
085: // int parentCount=0;
086: // for(int i=0;i<dim;i++){
087: // if(isLinked(i,node)){
088: // parentCount++;
089: // }
090: // }
091: // return (parentCount>1);
092: //
093: // }
094:
095: private boolean isSplit(int node) {
096: int childCount = 0;
097: for (int i = 0; i < dim; i++) {
098: if (isLinked(node, i)) {
099: childCount++;
100: }
101: }
102: return (childCount > 1);
103: }
104:
105: private boolean isIsolated(int node) {
106: return (!hasChild(node)) || (!hasParent(node));
107: }
108:
109: private boolean hasChild(int node) {
110: boolean child = false;
111: for (int i = 0; i < dim; i++) {
112: child = child || isLinked(node, i);
113: }
114: return child;
115: }
116:
117: private boolean hasParent(int node) {
118: boolean parent = false;
119: for (int i = 0; i < dim; i++) {
120: parent = parent || isLinked(i, node);
121: }
122: return parent;
123: }
124:
125: /**
126: * Constructs the GraphChecker object.
127: *
128: * @param matParam The two dimensional array of booleans representing
129: * the graphs incidence matrix.
130: */
131: public GraphChecker(boolean[][] matParam) {
132: tempMat = matParam;
133: dim = tempMat.length;
134: mat = new boolean[dim][dim];
135: for (int x = 0; x < dim; x++) {
136: for (int y = 0; y < dim; y++) {
137: mat[x][y] = tempMat[x][y];
138: }
139: }
140:
141: }
142:
143: private void undo() {
144: for (int x = 0; x < dim; x++) {
145: for (int y = 0; y < dim; y++) {
146: mat[x][y] = tempMat[x][y];
147: }
148: }
149: }
150:
151: /**
152: * @return <code>true</code> if the graph is cyclic, and <code>false</code>
153: * otherwise.
154: */
155: public boolean isGraphCyclic() {
156: boolean ret = false;
157: boolean changed = true;
158: undo();
159: while (changed) {
160: changed = false;
161: for (int i = 0; i < dim; i++) {
162: if ((!hasChild(i)) || (!hasParent(i))) {
163: if (hasChild(i)) {
164: unlinkChildren(i);
165: changed = true;
166: }
167: if (hasParent(i)) {
168: unlinkParents(i);
169: changed = true;
170: }
171: }
172: }
173: }
174: ret = !isGraphEmpty();
175: undo();
176: return ret;
177: }
178:
179: /**
180: * @return The array of graph node indexes that are within some graph cycle.
181: * If the graph is not cyclic, returns <code>null</code>.
182: */
183: public int[] getCyclicNodes() {
184: undo();
185: boolean changed = true;
186: while (changed) {
187: changed = false;
188: for (int i = 0; i < dim; i++) {
189: if ((!hasChild(i)) || (!hasParent(i))) {
190: if (hasChild(i)) {
191: unlinkChildren(i);
192: changed = true;
193: }
194: if (hasParent(i)) {
195: unlinkParents(i);
196: changed = true;
197: }
198: }
199: }
200: }
201: if (!isGraphEmpty()) {
202: int nodeCount = 0;
203: for (int i = 0; i < dim; i++) {
204: if (!isIsolated(i)) {
205: nodeCount++;
206: }
207: }
208: int[] nodeArray = new int[nodeCount];
209: int index = 0;
210: for (int i = 0; i < dim; i++) {
211: if (!isIsolated(i)) {
212: nodeArray[index++] = i;
213: }
214: }
215: undo();
216: return nodeArray;
217: }
218:
219: undo();
220: return null;
221: }
222:
223: /**
224: * Returns index of corresponding join node for the given split node index.
225: * @param nodeX The index of split node
226: * @return Index of corresponding join node if it exists, <b>-1</b> otherwise.
227: */
228: public int getJoinIndex(int nodeX) {
229: undo();
230: if (!isGraphCyclic()) {
231: undo();
232: if (isSplit(nodeX)) { // checking if the node has at least two outgoing branches
233: Vector workingSet = new Vector();
234: // putting the children of given node into the workingSet (there
235: // must be at least two children)
236: for (int i = 0; i < dim; i++) {
237: if (isLinked(nodeX, i)) {
238: unlink(nodeX, i);
239: workingSet.addElement(node(i));
240: }
241: }
242: boolean changed = true;
243: while (changed) {
244: changed = false;
245: Vector tempSet = new Vector();
246: // remove all nodes that have parent (they are waiting for
247: // parent to get to them) from working set, and place them
248: // into temporary set
249: //System.out.println("WS1="+workingSet);
250: for (int j = workingSet.size() - 1; j >= 0; j--) {
251: int actual = indexAt(workingSet, j);
252: if (hasParent(actual)
253: && !(isInSet(tempSet, actual))) {
254: tempSet.addElement(node(actual));
255: workingSet.remove(j);
256: }
257: }
258: //System.out.println("WS2="+workingSet);
259: // if temporary set is empty, and working set has only one
260: // node -> this node is one we are looking for
261: if (workingSet.size() == 1 && tempSet.size() == 0) {
262: return indexAt(workingSet, 0);
263: }
264:
265: // iterating through the whole set
266: for (int j = 0; j < workingSet.size(); j++) {
267: // determine the index of the node from j'th position within the working set
268: int actual = indexAt(workingSet, j);
269: boolean actualChanged = false;
270: // Iterating through incidence matrix and finding the children
271: for (int k = 0; k < dim; k++) {
272: if (isLinked(actual, k)) { // if the k'th node is the child
273: unlink(actual, k); // unlinking it
274: changed = true; // something is is changed
275: actualChanged = true;
276: if (!(isInSet(tempSet, k))) { // if child was not in the tempSet
277: tempSet.addElement(node(k)); // put it to wait for the next while loop iteration
278: }
279: }
280: }
281: // if nothing changed to the actual node->it is possibly the
282: // the wanted node, so put it into tempSet
283: if (!actualChanged
284: && !(isInSet(tempSet, actual))) {
285: tempSet.addElement(node(actual));
286: }
287: //System.out.println("actual="+actual+"WSS="+(workingSet.size()-1)+", j="+j+", TSS="+tempSet.size()+", TS="+tempSet);
288: //System.out.println("Iter "+j+", ts="+tempSet);
289: }
290: // working set for the next iteration becomes tempSet
291: workingSet = tempSet;
292: }
293: }
294: return -1;
295: }
296: return -1;
297: }
298: }
|