001 /** 002 * Copyright (c) 2003 Daffodil Software Ltd all rights reserved, 003 * Modifications Copyright (c) 2008 Regiscope Digital Imaging Co, LLC, All rights reserved. 004 * This program is free software; you can redistribute it and/or modify 005 * it under the terms of version 2 of the GNU General Public License as 006 * published by the Free Software Foundation. 007 * There are special exceptions to the terms and conditions of the GPL 008 * as it is applied to this software. See the GNU General Public License for more details. 009 * 010 * This program is distributed in the hope that it will be useful, 011 * but WITHOUT ANY WARRANTY; without even the implied warranty of 012 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 013 * GNU General Public License for more details. 014 * 015 * You should have received a copy of the GNU General Public License 016 * along with this program; if not, write to the Free Software 017 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 018 */ 019 020 021 package org.dbreplicator.graph; 022 023 import org.apache.log4j.Logger; 024 import java.math.*; 025 import java.util.*; 026 import org.dbreplicator.replication.RepException; 027 028 029 030 public class DirectedGraph 031 implements DGraph { 032 033 protected static Logger log = Logger.getLogger(DirectedGraph.class.getName()); 034 035 // The total amount of vertices in the graph. 036 private int totalVerticesGraph; 037 038 /** 039 The total amount of edges in the graph. Needs to 040 be <CODE>long</CODE>, because more than 041 <CODE>Integer.MAX_VALUE</CODE> edges are allowed. 042 (Special measures are taken in this case, though.) 043 */ 044 private long EdgesInGraph; 045 046 // The current cylcle status when searching the entire graph. 047 private boolean cycleStatus; 048 049 050 // A linked list of all vertex objects in the graph, 051 // for iterative access. (Link to beginning of list) 052 053 private ListElement mainVertexList; 054 055 // A linked list of all edge objects in the graph, 056 // for iterative access. (Link to beginning of list) 057 058 private ListElement mainEdgeList; 059 060 061 //The main hash table, which is an array of list elements, 062 //with a length that is always prime. 063 private ListElement[] mainHashTable; 064 065 066 ArrayList tablesInCycle=new ArrayList(); 067 068 069 /** 070 A directed graph with weighted edges. Constructed with an 071 integer, which is the first size of the hash table. 072 */ 073 074 public DirectedGraph(int hashTableInit) { 075 076 totalVerticesGraph = 0; 077 EdgesInGraph = 0; 078 mainVertexList = null; 079 mainEdgeList = null; 080 if (hashTableInit < 11) hashTableInit = 11; 081 mainHashTable = new ListElement[hashTableInit]; 082 for (int i = 0; i < mainHashTable.length; i++) { 083 mainHashTable[i] = new ListElement(); 084 } 085 } 086 087 088 /** 089 Does the hashing. Finds the 090 place where the object goes or is. 091 It wants an embedded vertex object 092 as its parameter, and it will return the 093 list element<UL> 094 <LI>where the object is or</LI> 095 <LI>the element BEFORE the element where 096 the object should go.</LI></UL> 097 In other words, it returns the list element 098 where the search terminates in the hash table. 099 @return ListElement instance where the object 100 is, or after which the object should come, the 101 testing of which case is the reality should be 102 done at the caller 103 @param objInVertex the object inside the vertex 104 that we want to find 105 */ 106 107 public ListElement searchVertex(Object objInVertex) { 108 ListElement endOfSearchChain; 109 Vertex vertex = null; 110 int index = Math.abs(objInVertex.hashCode()) %mainHashTable.length; 111 endOfSearchChain = mainHashTable[index]; 112 if (endOfSearchChain.next == null) { 113 return endOfSearchChain; 114 } 115 while (endOfSearchChain.next != null) { 116 endOfSearchChain = endOfSearchChain.next; 117 vertex = (Vertex) endOfSearchChain.hangingVertexOrEdge; 118 if (vertex.vertexObject.equals(objInVertex)) { 119 return endOfSearchChain; 120 } 121 } 122 return endOfSearchChain; 123 } 124 125 /** 126 This method is used when we know that the vertex 127 is NOT in the hash table, and we want to keep all 128 edge associations. (during a full reHash() operation) 129 @param the JbVertex we wish to reinsert into table. 130 @return <tt>true</tt> if the hashing proceeds as normal. 131 */ 132 133 private boolean hashVertex(Vertex vertexToHash) { 134 135 ListElement hanger = new ListElement(vertexToHash); 136 ListElement previous = searchVertex(vertexToHash.vertexObject); 137 previous.next = hanger; 138 return true; 139 } 140 141 /** 142 Finds the edge-object between 2 vertices. 143 @param first The origin of the edge 144 @param second The destination of the edge 145 @throws java.lang.IllegalArgumentException if either of the 146 param vertices are not found in this graph 147 @return the edge from first to second, null if no edge from 148 first to second 149 */ 150 151 private Edge searchEdge(Object first, Object second) { 152 //finding vertex1 153 ListElement targetLE = searchVertex(first); 154 Vertex firstVertex = (Vertex) targetLE.hangingVertexOrEdge; 155 if (firstVertex == null) { 156 return null; 157 // throw new IllegalArgumentException("First param-vertex not found."); 158 } 159 if (!firstVertex.vertexObject.equals(first)){ 160 return null; 161 // throw new IllegalArgumentException("First param-vertex not found."); 162 } 163 //finding vertex2 164 targetLE = searchVertex(second); 165 Vertex secondVertex = (Vertex) targetLE.hangingVertexOrEdge; 166 if (secondVertex == null ){ 167 return null; 168 // throw new IllegalArgumentException("Second param-vertex not found."); 169 } 170 if (!secondVertex.vertexObject.equals(second)){ 171 return null; 172 // throw new IllegalArgumentException("Second param-vertex not found."); 173 } 174 //searching edge chain for Edge:(1 --> 2) 175 Edge edge; 176 for (ListElement i = firstVertex.firstEdge; i != null; i = i.next) { 177 edge = (Edge) i.hangingVertexOrEdge; 178 if (edge.targetVertex == secondVertex) 179 return edge; 180 } 181 return null; 182 } 183 184 /** 185 Called when the addVertex-method sees that the load 186 of the hash table is > 1. Allocates a new hash table 187 with a length of at least 2x+1, where x is the old 188 length. The new length is (also) prime. Then iterates 189 through all vertex objects in graph and relocates them 190 into the new table accordingly. 191 @return <tt>true</tt> if all vertices successfully rehashed 192 into a new hash table 193 */ 194 195 private boolean reHash() { 196 197 BigInteger ourPrime = 198 new BigInteger(String.valueOf(mainHashTable.length * 2 + 1)); 199 BigInteger two = new BigInteger("2"); 200 //probability that we end up with a non-prime 201 //is 1/32 (2^n where n=5, prob=rather small) 202 while (!ourPrime.isProbablePrime(5)) { 203 ourPrime = ourPrime.add(two); 204 } 205 //test if the new number is bigger than Integer.MAX_VALUE 206 //use "longValue" because "intValue" would not work, obviously 207 if (ourPrime.longValue() > Integer.MAX_VALUE) { 208 //then make the table size Integer.MAX_VALUE 209 mainHashTable = new ListElement[Integer.MAX_VALUE]; 210 } 211 else { 212 //make the table size 213 mainHashTable = new ListElement[ourPrime.intValue()]; 214 } 215 for (int k = 0; k < mainHashTable.length; k++) { 216 mainHashTable[k] = new ListElement(); 217 } 218 //go throught the full vertex list and 219 //hash each into the new table 220 for (ListElement j = mainVertexList; j != null; j = j.next) { 221 if (!hashVertex( (Vertex) j.hangingVertexOrEdge)) 222 return false; 223 } 224 return true; 225 } 226 227 /** 228 Recursively seeks a cycle starting from the 229 vertex given as a parameter. Marks its way 230 through the vertices by setting the marker- 231 attribute in each vertex-object. 232 @param startVertex Vertex where the search begins. 233 */ 234 235 public void findCycle(Vertex startVertex) { 236 if (cycleStatus == true)return; 237 if (startVertex.graphMarker > 0) { 238 cycleStatus = true; 239 return; 240 } 241 startVertex.graphMarker++; 242 Edge current; 243 for (ListElement i = startVertex.firstEdge; i != null; i = i.next) { 244 current = (Edge) i.hangingVertexOrEdge; 245 tablesInCycle.add(current.targetVertex); 246 findCycle(current.targetVertex); 247 current.targetVertex.graphMarker--; 248 } 249 } 250 251 /** 252 Clears all vertex markers 253 */ 254 255 private void clearAllMarkers() { 256 Vertex vertex; 257 for (ListElement i = mainVertexList; i != null; i = i.next) { 258 vertex = (Vertex) i.hangingVertexOrEdge; 259 vertex.graphMarker = 0; 260 } 261 } 262 263 /** 264 This method draws a "picture" of the main hash table. 265 It works nicely if the max chain length is ~< 4. 266 Of course it sorta scrolls the screen for big 267 graphs, so.. directing to a file isn't a bad 268 option sometimes. It does NOT attempt to draw any 269 kind of representation of the graph or edges or 270 anything complex like that. It can help in debugging 271 matters pertaining to the hash table structure. 272 */ 273 274 public String toString() { 275 String result = ""; 276 Double load = new Double( (double) totalVerticesGraph / 277 (double) mainHashTable.length); 278 Vertex vertex; 279 for (int i = 0; i < mainHashTable.length; i++) { 280 for (ListElement j = mainHashTable[i]; j != null; j = j.next) { 281 vertex = (Vertex) j.hangingVertexOrEdge; 282 if (vertex == null) { 283 result += " nil"; 284 } 285 else { 286 if (vertex.vertexObject != null) 287 result += "LEobj"; // vertex.vertexObject); 288 } 289 if (j.next != null) result += "-> "; 290 if (j.next == null) result += "-|\n"; 291 } 292 } 293 result += "Vertex Total: " + this.totalVerticesGraph + "\n"; 294 result += "Hash Table size: " + this.mainHashTable.length + "\n"; 295 result += "Load factor : " + load + "\n"; 296 return result; 297 } 298 299 //--------------------------------------------------------------------- 300 // Predefined methods required in implementation. (interface) 301 //--------------------------------------------------------------------- 302 /** 303 Compares the specified object with this directed graph for equality. 304 Returns <tt>true</tt> if the specified object is also a directed graph 305 and the two directed graphs have the same vertices and edges. 306 @param obj the object to be compared for equality with this directed 307 graph. 308 @return <tt>true</tt> if the specified Object is equal to this directed 309 graph. 310 */ 311 312 public boolean equals(Object obj) { 313 DGraph other; 314 try { 315 other = (DGraph) obj; 316 } 317 catch (java.lang.ClassCastException e) { 318 return false; 319 } 320 321 if ( (other.vertexCount() != this.totalVerticesGraph) || 322 (other.edgeCount() != this.EdgesInGraph)) { 323 return false; 324 } 325 //since equal number of vertices is now tested, we 326 //can jump out if total==0 (both==0) 327 if (totalVerticesGraph == 0)return true; 328 Vertex vertex; 329 Edge edge; 330 ListElement edgeLE; 331 for (ListElement i = mainVertexList; i != null; i = i.next) { 332 vertex = (Vertex) i.hangingVertexOrEdge; 333 Object thisObj = vertex.vertexObject; //shorthand assignment 334 if (!other.hasVertex(thisObj))return false; 335 //testing each edge from this vertex 336 edgeLE = vertex.firstEdge; //"edge-list-element" 337 for (edgeLE = vertex.firstEdge; edgeLE != null; edgeLE = edgeLE.next) { 338 edge = (Edge) edgeLE.hangingVertexOrEdge; 339 if (!other.hasEdge(thisObj, edge.targetVertex.vertexObject))return false; 340 if (other.edgeWeight(thisObj, edge.targetVertex.vertexObject) != 341 edge.whatIsWeight()) { 342 return false; 343 } 344 } 345 } 346 //All vertices and edges tested to be equal. 347 //And we're still here. So it must be equal. 348 349 return true; 350 } 351 352 /** 353 Returns the hash code value for this directed graph. The hash code of a 354 directed graph is defined to be the sum of the hash codes of the vertices 355 in the directed graph. The sum is allowed to overflow if needed. This 356 definition ensures that if <code>s1.equals(s2)</code> then 357 <code>s1.hashCode() == s2.hashCode()</code> for any two directed graphs 358 <code>s1</code> and <code>s2</code>, as required by the general contract 359 of the <tt>java.lang.Object.hashCode</tt> method. 360 @return the hash code value for this directed graph. 361 */ 362 363 public int hashCode() { 364 int code = 0; 365 Vertex vertex; 366 for (ListElement i = mainVertexList; i != null; i = i.next) { 367 vertex = (Vertex) i.hangingVertexOrEdge; 368 code += vertex.vertexObject.hashCode(); 369 } 370 return code; 371 } 372 373 /** 374 Adds the specified vertex to this directed graph if the vertex is not 375 null and the vertex is not already present in this directed graph. More 376 formally, adds the specified vertex <code>obj</code> to this directed 377 graph if <code>obj != null</code> and this directed graph contains no 378 vertex <code>e</code> such that <code>obj.equals(e)</code>. The number of 379 vertices in this directed graph may not exceed <tt>Integer.MAX_VALUE</tt>. 380 @param obj the vertex to be added to this directed graph. 381 @return <tt>true</tt> if the specified vertex was added to this directed 382 graph. 383 @throws java.lang.IllegalStateException if this directed graph contains 384 the maximum number of vertices. 385 @throws java.lang.IllegalArgumentException if a specified vertex is null. 386 */ 387 388 public boolean addVertex(Object obj) throws RepException { 389 if (obj == null){ 390 throw new RepException("REP020",new Object[]{"","Param-vertex was null."}); 391 } 392 if (obj == this){ 393 throw new RepException("REP020",new Object[]{"","Param-vertex cannot be this graph."}); 394 } 395 if (totalVerticesGraph + 1 > Integer.MAX_VALUE){ 396 throw new RepException("REP020",new Object[]{"","Vertex count exceeds Integer.MAX_VALUE!"}); 397 } 398 if (totalVerticesGraph + 1 > mainHashTable.length) reHash(); 399 Vertex theNewVertex = new Vertex(obj); 400 ListElement place = searchVertex(obj); 401 if (place.hangingVertexOrEdge != null) { 402 Vertex lastFound = (Vertex) place.hangingVertexOrEdge; 403 if (lastFound.vertexObject.equals(obj)) { 404 return false; //already exists in table!! 405 } 406 } 407 ListElement newHashLE = new ListElement(theNewVertex); 408 place.next = newHashLE; 409 ListElement newListLE = new ListElement(theNewVertex); 410 newListLE.next = mainVertexList; 411 mainVertexList = newListLE; 412 totalVerticesGraph++; 413 return true; 414 } 415 416 /** 417 Returns <tt>true</tt> if this directed graph contains the specified 418 vertex. More formally, returns <tt>true</tt> if and only if 419 <code>obj != null</code> and this directed graph contains a vertex 420 <code>e</code> such that <code>obj.equals(e)</code>. 421 @param obj the vertex whose presence in this directed graph is to be 422 tested. 423 @return <tt>true</tt> if this directed graph contains the specified 424 vertex. 425 @throws java.lang.IllegalArgumentException if the specified vertex is 426 null. 427 */ 428 429 public boolean hasVertex(Object obj) { 430 if (obj == null) { 431 return false; 432 // throw new IllegalArgumentException("Param-vertex is null."); 433 } 434 Vertex vertex; 435 ListElement requested = searchVertex(obj); 436 vertex = (Vertex) requested.hangingVertexOrEdge; 437 if (vertex == null) 438 return false; //no chain even exists at table[hash(obj)] 439 if (vertex.vertexObject.equals(obj)) { 440 return true; 441 } 442 return false; //object was not in collision chain 443 } 444 445 /** 446 Returns <tt>true</tt> if there are vertices in this directed graph. 447 @return <tt>true</tt> if there are vertices in this directed graph. 448 */ 449 450 public boolean hasVertices() { 451 return (totalVerticesGraph > 0); 452 } 453 454 /** 455 Returns the number of vertices in this directed graph. 456 @return the number of vertices in this directed graph. 457 */ 458 459 public int vertexCount() { 460 return (int) totalVerticesGraph; 461 } 462 463 /** 464 Returns an array containing all vertices in this directed graph. The 465 vertices need not be in any special order. 466 <p> 467 The returned array will be "safe" in that no references to it are 468 maintained by this directed graph. In other words, this method must 469 allocate a new array even if this collection is backed by an array. The 470 caller is thus free to modify the returned array. 471 @return an array containing all vertices in this directed graph. 472 */ 473 474 public Object[] verticesToArray() { 475 Object[] arrayOfAllVertices = new Object[totalVerticesGraph]; 476 int j = 0; // alternate counter for array 477 Vertex vertex; 478 for (ListElement i = mainVertexList; i != null; i = i.next) { 479 vertex = (Vertex) i.hangingVertexOrEdge; 480 arrayOfAllVertices[j++] = vertex.vertexObject; 481 } 482 return arrayOfAllVertices; 483 } 484 485 /** 486 Adds an edge of a specified weight from the vertex <tt>first</tt> to the 487 vertex <tt>second</tt>. 488 @param first the vertex that the edge leaves from. 489 @param second the vertex that the edge enters. 490 @param weight the non-negative weight of the edge. 491 @return <tt>true</tt> if the specified vertex was added to this directed 492 graph, <tt>false</tt> if there already is an edge from the vertex 493 <tt>first</tt> to the vertex <tt>second</tt>. 494 @throws java.lang.IllegalArgumentException if a specified vertex was null 495 or not found in this directed graph, or if the specified weight was 496 negative. 497 */ 498 499 public boolean addEdge(java.lang.Object first, java.lang.Object second, 500 int weight) throws RepException { 501 if (weight < 0){ 502 throw new RepException("REP020",new Object[]{"","Weight was negative."}); 503 } 504 if (hasEdge(first, second))return false; 505 //finding target vertex 506 ListElement requestedLE = searchVertex(second); 507 Vertex targetVertex = (Vertex) requestedLE.hangingVertexOrEdge; 508 if (targetVertex == null){ 509 throw new RepException("REP020",new Object[]{"","Second param-vertex (target) not found."}); 510 } 511 //finding source vertex 512 requestedLE = searchVertex(first); 513 Vertex sourceVertex = (Vertex) requestedLE.hangingVertexOrEdge; 514 if (sourceVertex == null){ 515 throw new RepException("REP020",new Object[]{"","First param-vertex (source) not found."}); 516 } 517 //creating new edge, then creating 2 LEobjects with it. 518 Edge theNewEdge = new Edge(targetVertex, weight); 519 ListElement hangerInVertex = new ListElement(theNewEdge); 520 ListElement hangerInList = new ListElement(theNewEdge); 521 //adding hangerInVertex to beginning of edge chain inside vertex 522 hangerInVertex.next = sourceVertex.firstEdge; 523 sourceVertex.firstEdge = hangerInVertex; 524 //incrementing out degree of child 525 sourceVertex.addOutDegree(); 526 //incrementing in degree of parent 527 targetVertex.addInDegree(); 528 //adding listLEobject to beginning of 529 //main linked edge list 530 hangerInList.next = mainEdgeList; 531 mainEdgeList = hangerInList; 532 EdgesInGraph++; 533 return true; 534 } 535 536 /** 537 Returns <tt>true</tt> if this directed graph contains an edge that leaves 538 from the vertex <tt>first</tt> and enters the vertex <tt>second</tt>. 539 @param first the vertex that the edge should leave from. 540 @param second the vertex that the edge should enter. 541 @return <tt>true</tt> if this directed graph contains an edge that leaves 542 from the vertex <tt>first</tt> and enters the vertex <tt>second</tt>. 543 @throws java.lang.IllegalArgumentException if a specified vertex was null 544 or not found in this directed graph. 545 */ 546 547 public boolean hasEdge(java.lang.Object first, java.lang.Object second) { 548 if (searchEdge(first, second) != null)return true; 549 //no exceptions actually need to be thrown here, as 550 //the real work is doen by the helper method findEdge() 551 return false; 552 } 553 554 /** 555 Returns the weight of the edge that leaves from the vertex <tt>first</tt> 556 and enters the vertex <tt>second</tt>. 557 @param first the vertex that the edge should leave from. 558 @param second the vertex that the edge should enter. 559 @return the weight of the edge that leaves from the vertex <tt>first</tt> 560 and enters the vertex <tt>second</tt>. Returns -1 if there is no such 561 edge. 562 @throws java.lang.IllegalArgumentException if a specified vertex was null 563 or not found in this directed graph. 564 */ 565 566 public int edgeWeight(java.lang.Object first, java.lang.Object second){ 567 Edge targetEdge = searchEdge(first, second); 568 if (targetEdge == null)return -1; 569 return targetEdge.whatIsWeight(); 570 } 571 572 /** 573 Returns the number of edges that enter the specified vertex. 574 @param obj Object of the vertex that the edges should enter. 575 @return the number of edges that enter the specified vertex. 576 @throws java.lang.IllegalArgumentException if a specified vertex was null 577 or not found in this directed graph. 578 */ 579 580 public int inDegree(java.lang.Object obj) throws RepException { 581 //check if the obj is null 582 if (obj == null){ 583 throw new RepException("REP020",new Object[]{"","Param vertex object was null."}); 584 } 585 ListElement requested; 586 requested = searchVertex(obj); 587 Vertex vertex = (Vertex) requested.hangingVertexOrEdge; 588 if (vertex == null) { 589 throw new RepException("REP020",new Object[]{"","Param vertex not found in graph. (hash index empty)"}); 590 } 591 if (vertex.vertexObject.equals(obj)) { 592 return vertex.whatIsInDegree(); 593 } 594 else { 595 //was not found in hash table 596 throw new RepException("REP020",new Object[]{"","Param vertex not found in graph. (not in collision chain)"}); 597 } 598 } 599 600 /** 601 Returns the number of edges that leave from the specified vertex. 602 @param obj the vertex that the edges should leave from. 603 @return the number of edges that leave from the specified vertex. 604 @throws java.lang.IllegalArgumentException if a specified vertex was null 605 or not found in this directed graph. 606 */ 607 608 public int outDegree(java.lang.Object obj) throws RepException { 609 //check if the obj is null 610 if (obj == null){ 611 throw new RepException("REP020",new Object[]{"","Param vertex object was null."}); 612 } 613 ListElement requested; 614 requested = searchVertex(obj); 615 Vertex vertex = (Vertex) requested.hangingVertexOrEdge; 616 if (vertex == null) { 617 throw new RepException("REP020",new Object[]{"","Param vertex not found in graph. (hash index empty)"}); 618 } 619 if (vertex.vertexObject.equals(obj)) { 620 return vertex.whatIsOutDegree(); 621 } 622 else { 623 //was not found in hash table 624 throw new RepException("REP020",new Object[]{"","Param vertex not found in graph. (not in collision chain)"}); 625 } 626 } 627 628 /** 629 Returns an array containing all vertices that are adjacent to the 630 specified vertex. A vertex v is adjacent to a vertex u if there is an 631 edge that leaves from u and enters v. 632 <p> 633 The returned array will be "safe" in that no references to it are 634 maintained by this directed graph. In other words, this method must 635 allocate a new array even if this collection is backed by an array. The 636 caller is thus free to modify the returned array. 637 @param obj the specified vertex. 638 @return an array containing all vertices that are adjacent to the 639 specified vertex. 640 @throws java.lang.IllegalArgumentException if a specified vertex was null 641 or not found in this directed graph. 642 */ 643 644 public Object[] adjacentsOf(java.lang.Object obj) throws RepException { 645 if (obj == null){ 646 throw new RepException("REP020",new Object[]{"","Null parameter specified."}); 647 } 648 //finding source vertex 649 ListElement requested = searchVertex(obj); 650 Vertex vertex = (Vertex) requested.hangingVertexOrEdge; 651 if (vertex == null) { 652 throw new RepException("REP020",new Object[]{"","Param vertex not found in graph. (hash index empty)"}); 653 } 654 if (vertex.vertexObject.equals(obj)) { 655 Object[] arrayOfAdjacents = new Object[vertex.whatIsOutDegree()]; 656 ListElement theEdgeHanger = vertex.firstEdge; 657 Edge theEdge; 658 for (int i = 0; i < arrayOfAdjacents.length; i++) { 659 theEdge = (Edge) theEdgeHanger.hangingVertexOrEdge; 660 arrayOfAdjacents[i] = theEdge.targetVertex.vertexObject; 661 theEdgeHanger = theEdgeHanger.next; 662 } 663 return arrayOfAdjacents; 664 } 665 else { 666 //was not found in hash table 667 throw new RepException("REP020",new Object[]{"","Param vertex not found in graph. (not in collision chain)"}); 668 } 669 } 670 671 /** 672 <p>Returns <tt>true</tt> if the specified vertex is isolated. A vertex is 673 isolated if there are no edges leaving from or entering the vertex, or 674 the only edge leaving from the vertex enters the vertex itself and the 675 only edge entering the vertex leaves from the vertex itself. 676 @param obj the vertex that is to be tested for isolation. 677 @return <tt>true</tt> if the specified vertex is isolated. 678 @throws java.lang.IllegalArgumentException if a specified vertex was null 679 or not found in this directed graph. 680 */ 681 682 public boolean isIsolated(java.lang.Object obj) throws RepException { 683 if (obj == null){ 684 throw new RepException("REP020",new Object[]{"","The parameter given was null."}); 685 } 686 ListElement targetLE = searchVertex(obj); 687 Vertex thisVertex = (Vertex) targetLE.hangingVertexOrEdge; 688 if (thisVertex == null){ 689 throw new RepException("REP020",new Object[]{"","Specified vertex not found in graph. (hash index empty)"}); 690 } 691 if (thisVertex.vertexObject != obj){ 692 throw new RepException("REP020",new Object[]{"","Specified vertex not found in graph. (not in collision chain)"}); 693 } 694 if ( (thisVertex.whatIsInDegree() == 0) && 695 (thisVertex.whatIsOutDegree() == 0))return true; 696 // if it is a self loop i.e A<-->A 697 if ( (thisVertex.whatIsInDegree() == 1) && 698 (thisVertex.whatIsOutDegree() == 1)) { 699 targetLE = thisVertex.firstEdge; 700 Edge onlyEdge = (Edge) targetLE.hangingVertexOrEdge; 701 if (onlyEdge.targetVertex == thisVertex)return true; 702 } 703 return false; 704 } 705 706 /** 707 Returns <tt>true</tt> if there are edges in this directed graph. 708 @return <tt>true</tt> if there are edges in this directed graph. 709 */ 710 711 public boolean hasEdges() { 712 return (EdgesInGraph > 0); 713 } 714 715 /** 716 Returns the number of edges in this directed graph. If this directed 717 graph contains more than <tt>Integer.MAX_VALUE</tt> edges, returns 718 <tt>Integer.MAX_VALUE</tt>. 719 @return the number of edges in this directed graph. 720 */ 721 722 public int edgeCount() { 723 if (EdgesInGraph > Integer.MAX_VALUE) { 724 return Integer.MAX_VALUE; 725 } 726 else { 727 return (int) EdgesInGraph; 728 } 729 } 730 731 /** 732 Returns the sum of the weights of all edges in this directed graph. If 733 the sum is more than <tt>Integer.MAX_VALUE</tt>, returns 734 <tt>Integer.MAX_VALUE</tt>. 735 @return the sum of the weights of all edges in this directed graph. 736 */ 737 738 public int edgeWeight() { 739 //check for edges then 740 //create some vars for intermediate storage 741 if (this.EdgesInGraph == 0)return 0; 742 long sum = 0; 743 Edge edge; 744 //go through the mainEdgeList 745 //increment sum 746 for (ListElement i = mainEdgeList; i != null; i = i.next) { 747 edge = (Edge) i.hangingVertexOrEdge; 748 if (sum + edge.whatIsWeight() > Integer.MAX_VALUE) { 749 return Integer.MAX_VALUE; 750 } 751 sum += edge.whatIsWeight(); 752 } 753 return (int) sum; 754 } 755 756 /** 757 Returns an array of all of the vertices in this directed graph in some 758 topological sort order. <p> 759 The returned array will be "safe" in that no references to it are 760 maintained by this directed graph. In other words, this method must 761 allocate a new array even if this collection is backed by an array. The 762 caller is thus free to modify the returned array. 763 @return an array of all of the vertices in this directed graph in some 764 topological sort order. Returns null if no topological sort is possible. 765 */ 766 767 public Object[] topologicalSort() { 768 if (hasCycle() == true) { 769 //cycle found, no topological sort possible 770 return null; 771 } 772 //we don't creat the array until we have checked 773 //no cycles exist. 774 Object[] topologicalArray = new Object[totalVerticesGraph]; 775 topoIndex = 0; 776 Vertex vertex; 777 //Start going through vertices, setting all markers to indegree, 778 //when =0, put into array and sub-seek adjacents, decrementing 779 //simultaneously and recursively putting all who == 0 after decr. 780 for (ListElement n = mainVertexList; n != null; n = n.next) { 781 vertex = (Vertex) n.hangingVertexOrEdge; 782 if (vertex.graphMarker == 0) vertex.graphMarker = vertex.whatIsInDegree(); 783 if (vertex.graphMarker == 0) { 784 //after the inDegree is assigned, if this vertex 785 //STILL has 0 (no "dependents") we can call put() 786 putAndDecrement(topologicalArray, vertex); 787 } 788 } 789 clearAllMarkers(); 790 return topologicalArray; 791 } 792 793 /** 794 Helper variable to keep track of topoligical sort 795 array indexing. A global var, passing it around in 796 recursive calls would be very messy. 797 */ 798 799 private int topoIndex; 800 801 /** 802 A recursive helper method to put found vertex into array, 803 and decrement adjacents. It is necessary to pass the array 804 we are constructing around from method call to method call 805 in order to maximize effectiveness, this way it's not a 806 global variable, in case we don't ever need to create it. 807 @param theArray the array of vertices that we are constructing 808 @param start the vertex where we are starting this sub-call 809 */ 810 811 private void putAndDecrement(Object[] theArray, Vertex start) { 812 //putting the vertex object into the next free spot in array 813 theArray[topoIndex++] = start.vertexObject; 814 //when the vertex has been put into array we mark it with -1 815 start.graphMarker = -1; 816 Edge edge; 817 //now we are going to go through the edge-list and decrement 818 //all the vertex-inDegrees (markers) by one, 819 //and if we decrement any of them to 0, we'll call this 820 //method recursively again to put that vertex into the array 821 //next. 822 for (ListElement i = start.firstEdge; i != null; i = i.next) { 823 edge = (Edge) i.hangingVertexOrEdge; 824 if (edge.targetVertex.graphMarker == 0) { 825 //this is a case where the topologicalSort() 826 //method has not got this far yet, so we need 827 //to do som of its work for it, and mark the inDegree. 828 edge.targetVertex.graphMarker = edge.targetVertex.whatIsInDegree(); 829 } 830 //decrementing the adjacent vertex 831 edge.targetVertex.graphMarker--; 832 if (edge.targetVertex.graphMarker == 0) { 833 //if 0, we can now move on through this edge to 834 //put its vertex recursively as well 835 putAndDecrement(theArray, edge.targetVertex); 836 } 837 } 838 } 839 840 /** 841 Returns <tt>true</tt> if there is a cycle in the directed graph. 842 @return <tt>true</tt> if there is a cycle in the directed graph. 843 */ 844 845 public boolean hasCycle() { 846 cycleStatus = false; 847 Vertex eachVertexInTurn; 848 for (ListElement i = mainVertexList; (i != null) && (cycleStatus != true);i = i.next) { 849 eachVertexInTurn = (Vertex) i.hangingVertexOrEdge; 850 findCycle(eachVertexInTurn); 851 if (cycleStatus) { 852 //newList to add first vertex from which traversing of graph was started 853 ArrayList newList = new ArrayList(); 854 newList.add(eachVertexInTurn); 855 newList.addAll(tablesInCycle); 856 tablesInCycle.clear(); 857 tablesInCycle.addAll(newList); 858 } 859 clearAllMarkers(); 860 } 861 if (cycleStatus == false)return false; 862 return true; 863 } 864 865 /** 866 Returns <tt>true</tt> if the directed graph forms a linear list. A 867 directed graph with no vertices or one vertex without a self loop is 868 also considered to form a linear list. 869 @return <tt>true</tt> if the directed graph forms a linear list. 870 */ 871 872 public boolean isLinearList() { 873 //we start by checking some obvious 874 //conditions, the simplest ones 875 if (totalVerticesGraph == 0)return true; 876 if (totalVerticesGraph == 1) { 877 //if only one vertex, check for cycle 878 // then return the result and we're done 879 if (EdgesInGraph == 1) { 880 if (hasCycle() == true)return false; 881 return true; 882 } 883 } 884 //after having established the above conditions, 885 //the next obvious sign that it's not a linear list 886 //is if there isn't EXACTLY one less edge than vertices. 887 if (totalVerticesGraph != (EdgesInGraph + 1))return false; 888 //now we start looking for a place to start the checking (in=0) 889 //if at any time we find a vertex with inDegree or outDegree 890 //of more than 1, we can quit and return false 891 Vertex vertex; 892 Vertex startVertex = null; 893 for (ListElement n = mainVertexList; n != null; n = n.next) { 894 vertex = (Vertex) n.hangingVertexOrEdge; 895 if ( (vertex.whatIsInDegree() > 1) || (vertex.whatIsOutDegree() > 1)) { 896 return false; 897 } 898 if (vertex.whatIsInDegree() == 0) { 899 //if this is not the only vertex with in=0, return false 900 if (startVertex != null)return false; 901 startVertex = vertex; 902 } 903 } 904 //now we have a either a link to the "first" 905 //vertex in the supposed linear list, 906 //or then we have a null 907 if (startVertex == null)return false; 908 if (hasCycle() == true)return false; 909 //if all of the above conditions are done, 910 //and we are still here, then our graph is a 911 //linear list 912 return true; 913 } 914 915 //return ArrayList of tables in cycle 916 public ArrayList TablesInCycle(){ 917 return tablesInCycle; 918 } 919 }
Sponsors
