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