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; 033 034import java.util.Iterator; 035import java.util.NoSuchElementException; 036 037public class DepthFirstIterator<T extends Node> implements Iterator<T> { 038 boolean directed; 039 Graph graph; 040 041 Node[] parent; 042 Iterator<Edge>[] iterator; 043 int depth[]; 044 Node next; 045 int maxDepth; 046 047 @SuppressWarnings("unchecked") 048 public DepthFirstIterator(Node startNode, boolean directed) { 049 this.directed = directed; 050 graph = startNode.getGraph(); 051 int n = graph.getNodeCount(); 052 parent = new Node[n]; 053 iterator = new Iterator[n]; 054 depth = new int[n]; 055 056 int s = startNode.getIndex(); 057 for (int i = 0; i < n; i++) 058 depth[i] = i == s ? 0 : -1; 059 next = startNode; 060 } 061 062 protected void gotoNext() { 063 while (next != null) { 064 int i = next.getIndex(); 065 while (iterator[i].hasNext()) { 066 Node neighbor = iterator[i].next().getOpposite(next); 067 int j = neighbor.getIndex(); 068 if (iterator[j] == null) { 069 parent[j] = next; 070 iterator[j] = directed ? neighbor.getLeavingEdgeIterator() 071 : neighbor.getEnteringEdgeIterator(); 072 depth[j] = depth[i] + 1; 073 if (depth[j] > maxDepth) 074 maxDepth = depth[j]; 075 next = neighbor; 076 return; 077 } 078 } 079 next = parent[i]; 080 } 081 } 082 083 public DepthFirstIterator(Node startNode) { 084 this(startNode, true); 085 } 086 087 public boolean hasNext() { 088 return next != null; 089 } 090 091 @SuppressWarnings("unchecked") 092 public T next() { 093 if (next == null) 094 throw new NoSuchElementException(); 095 iterator[next.getIndex()] = directed ? next.getLeavingEdgeIterator() 096 : next.getEnteringEdgeIterator(); 097 Node previous = next; 098 gotoNext(); 099 return (T) previous; 100 } 101 102 public void remove() { 103 throw new UnsupportedOperationException( 104 "This iterator does not support remove"); 105 } 106 107 public int getDepthOf(Node node) { 108 return depth[node.getIndex()]; 109 } 110 111 public int getDepthMax() { 112 return maxDepth; 113 } 114 115 public boolean tabu(Node node) { 116 return depth[node.getIndex()] != -1; 117 } 118 119 public boolean isDirected() { 120 return directed; 121 } 122}