001/* 002 * Copyright 2006 - 2013 003 * Stefan Balev <stefan.balev@graphstream-project.org> 004 * Julien Baudry <julien.baudry@graphstream-project.org> 005 * Antoine Dutot <antoine.dutot@graphstream-project.org> 006 * Yoann Pigné <yoann.pigne@graphstream-project.org> 007 * Guilhelm Savin <guilhelm.savin@graphstream-project.org> 008 * 009 * This file is part of GraphStream <http://graphstream-project.org>. 010 * 011 * GraphStream is a library whose purpose is to handle static or dynamic 012 * graph, create them from scratch, file or any source and display them. 013 * 014 * This program is free software distributed under the terms of two licenses, the 015 * CeCILL-C license that fits European law, and the GNU Lesser General Public 016 * License. You can use, modify and/ or redistribute the software under the terms 017 * of the CeCILL-C license as circulated by CEA, CNRS and INRIA at the following 018 * URL <http://www.cecill.info> or under the terms of the GNU LGPL as published by 019 * the Free Software Foundation, either version 3 of the License, or (at your 020 * option) any later version. 021 * 022 * This program is distributed in the hope that it will be useful, but WITHOUT ANY 023 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A 024 * PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. 025 * 026 * You should have received a copy of the GNU Lesser General Public License 027 * along with this program. If not, see <http://www.gnu.org/licenses/>. 028 * 029 * The fact that you are presently reading this means that you have had 030 * knowledge of the CeCILL-C and LGPL licenses and that you accept their terms. 031 */ 032package org.graphstream.graph.implementations; 033 034import java.util.AbstractCollection; 035import java.util.Collection; 036import java.util.HashSet; 037import java.util.Iterator; 038import java.util.NoSuchElementException; 039 040import org.graphstream.graph.BreadthFirstIterator; 041import org.graphstream.graph.DepthFirstIterator; 042import org.graphstream.graph.Edge; 043import org.graphstream.graph.Graph; 044import org.graphstream.graph.Node; 045import org.graphstream.stream.SourceBase; 046 047/** 048 * <p> 049 * This class provides a basic implementation of {@code Node} interface, to 050 * minimize the effort required to implement this interface. 051 * </p> 052 * 053 * <p> 054 * This class implements all the methods of 055 * {@link org.graphstream.graph.implementations#AbstractElement} and most of the 056 * methods of {@link org.graphstream.graph#Node} (there are "only" ten abstract 057 * methods). In addition to these, subclasses must provide implementations for 058 * {@link #addEdgeCallback(AbstractEdge)} and 059 * {@link #removeEdgeCallback(AbstractEdge)} which are called by the parent 060 * graph when an edge incident to this node is added to or removed from the 061 * graph. This class has a low memory overhead (one reference as field). 062 * </p> 063 */ 064public abstract class AbstractNode extends AbstractElement implements Node { 065 066 // *** Fields *** 067 068 /** 069 * The graph to which this node belongs 070 */ 071 protected AbstractGraph graph; 072 073 // *** Constructors 074 075 /** 076 * Constructs a new node. This constructor copies the parameters into the 077 * corresponding fields 078 * 079 * @param graph 080 * The graph to which this node belongs. 081 * @param id 082 * Unique identifier of this node. 083 */ 084 protected AbstractNode(AbstractGraph graph, String id) { 085 super(id); 086 this.graph = graph; 087 } 088 089 // *** Inherited from abstract element *** 090 091 @Override 092 protected void attributeChanged(AttributeChangeEvent event, 093 String attribute, Object oldValue, Object newValue) { 094 graph.listeners.sendAttributeChangedEvent(id, 095 SourceBase.ElementType.NODE, attribute, event, oldValue, 096 newValue); 097 } 098 099 /** 100 * @return The id of the parent graph 101 * @see org.graphstream.graph.implementations.AbstractElement#myGraphId() 102 */ 103 // protected String myGraphId() { 104 // return graph.getId(); 105 // } 106 107 /** 108 * This implementation calls the corresponding method of the parent graph 109 * 110 * @see org.graphstream.graph.implementations.AbstractElement#newEvent() 111 */ 112 // protected long newEvent() { 113 // return graph.newEvent(); 114 // } 115 116 @Override 117 /** 118 * This implementation calls the corresponding method of the parent graph 119 * 120 * @see org.graphstream.graph.implementations.AbstractElement#nullAttributesAreErrors() 121 */ 122 protected boolean nullAttributesAreErrors() { 123 return graph.nullAttributesAreErrors(); 124 } 125 126 // *** Inherited from Node *** 127 128 /** 129 * This implementation returns {@link #graph}. 130 * 131 * @see org.graphstream.graph.Node#getGraph() 132 */ 133 public Graph getGraph() { 134 return graph; 135 } 136 137 public abstract int getDegree(); 138 139 public abstract int getInDegree(); 140 141 public abstract int getOutDegree(); 142 143 // [has|get]Edge[Toward|From|Between](Node|int|String) -> 2 * 3 * 3 = 18 144 // methods 145 146 /** 147 * This implementation returns {@code true} if {@link #getEdgeToward(Node)} 148 * is not {@code null}. 149 * 150 * @see org.graphstream.graph.Node#getEdgeToward(org.graphstream.graph.Node) 151 */ 152 public boolean hasEdgeToward(Node node) { 153 return getEdgeToward(node) != null; 154 } 155 156 /** 157 * This implementation returns {@code true} if {@link #getEdgeToward(int)} 158 * is not {@code null}. 159 * 160 * @see org.graphstream.graph.Node#hasEdgeToward(int) 161 */ 162 public boolean hasEdgeToward(int index) { 163 return getEdgeToward(index) != null; 164 } 165 166 /** 167 * This implementation returns {@code true} if {@link #getEdgeToward(Node)} 168 * is not {@code null}. 169 * 170 * @see org.graphstream.graph.Node#hasEdgeToward(java.lang.String) 171 */ 172 public boolean hasEdgeToward(String id) { 173 return getEdgeToward(id) != null; 174 } 175 176 /** 177 * This implementation returns {@code true} if {@link #getEdgeFrom(Node)} is 178 * not {@code null}. 179 * 180 * @see org.graphstream.graph.Node#hasEdgeFrom(org.graphstream.graph.Node) 181 */ 182 public boolean hasEdgeFrom(Node node) { 183 return getEdgeFrom(node) != null; 184 } 185 186 /** 187 * This implementation returns {@code true} if {@link #getEdgeFrom(int)} is 188 * not {@code null}. 189 * 190 * @see org.graphstream.graph.Node#hasEdgeFrom(int) 191 */ 192 public boolean hasEdgeFrom(int index) { 193 return getEdgeFrom(index) != null; 194 } 195 196 /** 197 * This implementation returns {@code true} if {@link #getEdgeFrom(Node)} is 198 * not {@code null}. 199 * 200 * @see org.graphstream.graph.Node#hasEdgeFrom(java.lang.String) 201 */ 202 public boolean hasEdgeFrom(String id) { 203 return getEdgeFrom(id) != null; 204 } 205 206 /** 207 * This implementation returns {@code true} if {@link #getEdgeBetween(Node)} 208 * is not {@code null}. 209 * 210 * @see org.graphstream.graph.Node#hasEdgeBetween(org.graphstream.graph.Node) 211 */ 212 public boolean hasEdgeBetween(Node node) { 213 return getEdgeBetween(node) != null; 214 } 215 216 /** 217 * This implementation returns {@code true} if {@link #getEdgeBetween(int)} 218 * is not {@code null}. 219 * 220 * @see org.graphstream.graph.Node#hasEdgeBetween(int) 221 */ 222 public boolean hasEdgeBetween(int index) { 223 return getEdgeBetween(index) != null; 224 } 225 226 /** 227 * This implementation returns {@code true} if {@link #getEdgeBetween(Node)} 228 * is not {@code null}. 229 * 230 * @see org.graphstream.graph.Node#hasEdgeBetween(java.lang.String) 231 */ 232 public boolean hasEdgeBetween(String id) { 233 return getEdgeBetween(id) != null; 234 } 235 236 public abstract <T extends Edge> T getEdgeToward(Node node); 237 238 /** 239 * This implementation uses {@link #getEdgeToward(Node)} 240 * 241 * @see org.graphstream.graph.Node#getEdgeToward(int) 242 */ 243 public <T extends Edge> T getEdgeToward(int index) { 244 return getEdgeToward(graph.getNode(index)); 245 } 246 247 /** 248 * This implementation uses {@link #getEdgeToward(Node)} 249 * 250 * @see org.graphstream.graph.Node#getEdgeToward(java.lang.String) 251 */ 252 public <T extends Edge> T getEdgeToward(String id) { 253 return getEdgeToward(graph.getNode(id)); 254 } 255 256 public abstract <T extends Edge> T getEdgeFrom(Node node); 257 258 /** 259 * This implementation uses {@link #getEdgeFrom(Node)} 260 * 261 * @see org.graphstream.graph.Node#getEdgeFrom(int) 262 */ 263 public <T extends Edge> T getEdgeFrom(int index) { 264 return getEdgeFrom(graph.getNode(index)); 265 } 266 267 /** 268 * This implementation uses {@link #getEdgeFrom(Node)} 269 * 270 * @see org.graphstream.graph.Node#getEdgeFrom(java.lang.String) 271 */ 272 public <T extends Edge> T getEdgeFrom(String id) { 273 return getEdgeFrom(graph.getNode(id)); 274 } 275 276 public abstract <T extends Edge> T getEdgeBetween(Node node); 277 278 /** 279 * This implementation uses {@link #getEdgeBetween(Node)} 280 * 281 * @see org.graphstream.graph.Node#getEdgeBetween(int) 282 */ 283 public <T extends Edge> T getEdgeBetween(int index) { 284 return getEdgeBetween(graph.getNode(index)); 285 } 286 287 /** 288 * This implementation uses {@link #getEdgeBetween(Node)} 289 * 290 * @see org.graphstream.graph.Node#getEdgeBetween(java.lang.String) 291 */ 292 public <T extends Edge> T getEdgeBetween(String id) { 293 return getEdgeBetween(graph.getNode(id)); 294 } 295 296 // get[_|Entering|Leaving]EdgeIterator 297 298 public abstract <T extends Edge> Iterator<T> getEdgeIterator(); 299 300 public abstract <T extends Edge> Iterator<T> getEnteringEdgeIterator(); 301 302 public abstract <T extends Edge> Iterator<T> getLeavingEdgeIterator(); 303 304 // getEach[_Entering|Leaving]Edge 305 306 /** 307 * This implementation uses {@link #getEdgeIterator()} 308 * 309 * @see org.graphstream.graph.Node#getEachEdge() 310 */ 311 public <T extends Edge> Iterable<T> getEachEdge() { 312 return new Iterable<T>() { 313 public Iterator<T> iterator() { 314 return getEdgeIterator(); 315 } 316 }; 317 } 318 319 /** 320 * This implementation uses {@link #getEnteringEdgeIterator()} 321 * 322 * @see org.graphstream.graph.Node#getEachEnteringEdge() 323 */ 324 public <T extends Edge> Iterable<T> getEachEnteringEdge() { 325 return new Iterable<T>() { 326 public Iterator<T> iterator() { 327 return getEnteringEdgeIterator(); 328 } 329 }; 330 } 331 332 /** 333 * This implementation uses {@link #getLeavingEdgeIterator()} 334 * 335 * @see org.graphstream.graph.Node#getEachLeavingEdge() 336 */ 337 public <T extends Edge> Iterable<T> getEachLeavingEdge() { 338 return new Iterable<T>() { 339 public Iterator<T> iterator() { 340 return getLeavingEdgeIterator(); 341 } 342 }; 343 } 344 345 // get[_|Entering|Leaving]EdgeSet 346 347 /** 348 * This implementation uses {@link #getEdgeIterator()} and 349 * {@link #getDegree()} 350 * 351 * @see org.graphstream.graph.Node#getEdgeSet() 352 */ 353 public <T extends Edge> Collection<T> getEdgeSet() { 354 return new AbstractCollection<T>() { 355 @Override 356 public Iterator<T> iterator() { 357 return getEdgeIterator(); 358 } 359 360 @Override 361 public int size() { 362 return getDegree(); 363 } 364 }; 365 } 366 367 /** 368 * This implementation uses {@link #getEnteringEdgeIterator()} and 369 * {@link #geIntDegree()} 370 * 371 * @see org.graphstream.graph.Node#getEnteringEdgeSet() 372 */ 373 public <T extends Edge> Collection<T> getEnteringEdgeSet() { 374 return new AbstractCollection<T>() { 375 @Override 376 public Iterator<T> iterator() { 377 return getEnteringEdgeIterator(); 378 } 379 380 @Override 381 public int size() { 382 return getInDegree(); 383 } 384 }; 385 } 386 387 /** 388 * This implementation uses {@link #getLeavingIterator()} and 389 * {@link #geOuttDegree()} 390 * 391 * @see org.graphstream.graph.Node#getLeavingEdgeSet() 392 */ 393 public <T extends Edge> Collection<T> getLeavingEdgeSet() { 394 return new AbstractCollection<T>() { 395 @Override 396 public Iterator<T> iterator() { 397 return getLeavingEdgeIterator(); 398 } 399 400 @Override 401 public int size() { 402 return getOutDegree(); 403 } 404 }; 405 } 406 407 /** 408 * This implementation uses {@link #getEdgeIterator()} 409 * 410 * @see java.lang.Iterable#iterator() 411 */ 412 public Iterator<Edge> iterator() { 413 return getEdgeIterator(); 414 } 415 416 public abstract <T extends Edge> T getEdge(int i); 417 418 public abstract <T extends Edge> T getEnteringEdge(int i); 419 420 public abstract <T extends Edge> T getLeavingEdge(int i); 421 422 /** 423 * This implementation uses {@link #getEdgeIterator()} and stores the 424 * visited nodes in a set. In this way it ensures that each neighbor will be 425 * visited exactly once, even in multi-graph. 426 * 427 * @see org.graphstream.graph.Node#getNeighborNodeIterator() 428 */ 429 public <T extends Node> Iterator<T> getNeighborNodeIterator() { 430 return new Iterator<T>() { 431 Iterator<Edge> edgeIt = getEdgeIterator(); 432 HashSet<T> visited = new HashSet<T>(getDegree()); 433 T next; 434 { 435 gotoNext(); 436 } 437 438 private void gotoNext() { 439 while (edgeIt.hasNext()) { 440 next = edgeIt.next().getOpposite(AbstractNode.this); 441 if (!visited.contains(next)) { 442 visited.add(next); 443 return; 444 } 445 } 446 next = null; 447 } 448 449 public boolean hasNext() { 450 return next != null; 451 } 452 453 public T next() { 454 if (next == null) 455 throw new NoSuchElementException(); 456 T current = next; 457 gotoNext(); 458 return current; 459 } 460 461 public void remove() { 462 throw new UnsupportedOperationException( 463 "This iterator does not support remove"); 464 465 } 466 467 // Iterator<Edge> edgeIterator = getEdgeIterator(); 468 // 469 // public boolean hasNext() { 470 // return edgeIterator.hasNext(); 471 // } 472 // 473 // public T next() { 474 // return edgeIterator.next().getOpposite(AbstractNode.this); 475 // } 476 // 477 // public void remove() { 478 // throw new UnsupportedOperationException( 479 // "This iterator does not support remove"); 480 // } 481 }; 482 } 483 484 // breadth- and depth-first iterator 485 486 /** 487 * This implementation creates an instance of 488 * {@link org.graphstream.graph#BreadthFirstIterator} and returns it. 489 * 490 * @see org.graphstream.graph.Node#getBreadthFirstIterator() 491 */ 492 public <T extends Node> Iterator<T> getBreadthFirstIterator() { 493 // XXX change it when the old iterator disappears 494 // XXX change the return type to have access to the other methods 495 return new BreadthFirstIterator<T>(this); 496 } 497 498 /** 499 * This implementation creates an instance of 500 * {@link org.graphstream.graph#BreadthFirstIterator} and returns it. 501 * 502 * @see org.graphstream.graph.Node#getBreadthFirstIterator(boolean) 503 */ 504 public <T extends Node> Iterator<T> getBreadthFirstIterator(boolean directed) { 505 // XXX change it when the old iterator disappears 506 // XXX change the return type to have access to the other methods 507 return new BreadthFirstIterator<T>(this, directed); 508 } 509 510 /** 511 * This implementation creates an instance of 512 * {@link org.graphstream.graph#DepthFirstIterator} and returns it. 513 * 514 * @see org.graphstream.graph.Node#getDepthFirstIterator() 515 */ 516 public <T extends Node> Iterator<T> getDepthFirstIterator() { 517 // XXX change it when the old iterator disappears 518 // XXX change the return type to have access to the other methods 519 return new DepthFirstIterator<T>(this); 520 } 521 522 /** 523 * This implementation creates an instance of 524 * {@link org.graphstream.graph#DepthFirstIterator} and returns it. 525 * 526 * @see org.graphstream.graph.Node#getDepthFirstIterator(boolean) 527 */ 528 public <T extends Node> Iterator<T> getDepthFirstIterator(boolean directed) { 529 // XXX change it when the old iterator disappears 530 // XXX change the return type to have access to the other methods 531 return new DepthFirstIterator<T>(this, directed); 532 } 533 534 // *** Other methods *** 535 536 /** 537 * This method is called automatically when an edge incident to this node is 538 * created. Subclasses use it to add the edge to their data structure. 539 * 540 * @param edge 541 * a new edge incident to this node 542 */ 543 protected abstract boolean addEdgeCallback(AbstractEdge edge); 544 545 /** 546 * This method is called automatically before removing an edge incident to 547 * this node. Subclasses use it to remove the edge from their data 548 * structure. 549 * 550 * @param edge 551 * an edge incident to this node that will be removed 552 */ 553 protected abstract void removeEdgeCallback(AbstractEdge edge); 554 555 /** 556 * This method is called for each node when the graph is cleared. Subclasses 557 * may use it to clear their data structures in order to facilitate the 558 * garbage collection. 559 */ 560 protected abstract void clearCallback(); 561 562 /** 563 * Checks if an edge enters this node. Utility method that can be useful in 564 * subclasses. 565 * 566 * @param e 567 * an edge 568 * @return {@code true} if {@code e} is entering edge for this node. 569 */ 570 public boolean isEnteringEdge(Edge e) { 571 return e.getTargetNode() == this 572 || (!e.isDirected() && e.getSourceNode() == this); 573 } 574 575 /** 576 * Checks if an edge leaves this node. Utility method that can be useful in 577 * subclasses. 578 * 579 * @param e 580 * an edge 581 * @return {@code true} if {@code e} is leaving edge for this node. 582 */ 583 public boolean isLeavingEdge(Edge e) { 584 return e.getSourceNode() == this 585 || (!e.isDirected() && e.getTargetNode() == this); 586 } 587 588 /** 589 * Checks if an edge is incident to this node. Utility method that can be 590 * useful in subclasses. 591 * 592 * @param e 593 * an edge 594 * @return {@code true} if {@code e} is incident edge for this node. 595 */ 596 public boolean isIncidentEdge(Edge e) { 597 return e.getSourceNode() == this || e.getTargetNode() == this; 598 } 599}