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 BreadthFirstIterator<T extends Node> implements Iterator<T> { 038 protected boolean directed; 039 protected Graph graph; 040 protected Node[] queue; 041 protected int[] depth; 042 protected int qHead, qTail; 043 044 public BreadthFirstIterator(Node startNode, boolean directed) { 045 this.directed = directed; 046 graph = startNode.getGraph(); 047 int n = graph.getNodeCount(); 048 queue = new Node[n]; 049 depth = new int[n]; 050 051 int s = startNode.getIndex(); 052 for (int i = 0; i < n; i++) 053 depth[i] = i == s ? 0 : -1; 054 queue[0] = startNode; 055 qHead = 0; 056 qTail = 1; 057 } 058 059 public BreadthFirstIterator(Node startNode) { 060 this(startNode, true); 061 } 062 063 public boolean hasNext() { 064 return qHead < qTail; 065 } 066 067 @SuppressWarnings("unchecked") 068 public T next() { 069 if (qHead >= qTail) 070 throw new NoSuchElementException(); 071 Node current = queue[qHead++]; 072 int level = depth[current.getIndex()] + 1; 073 Iterable<Edge> edges = directed ? current.getEachLeavingEdge() 074 : current.getEachEdge(); 075 for (Edge e : edges) { 076 Node node = e.getOpposite(current); 077 int j = node.getIndex(); 078 if (depth[j] == -1) { 079 queue[qTail++] = node; 080 depth[j] = level; 081 } 082 } 083 return (T)current; 084 } 085 086 public void remove() { 087 throw new UnsupportedOperationException( 088 "This iterator does not support remove"); 089 } 090 091 public int getDepthOf(Node node) { 092 return depth[node.getIndex()]; 093 } 094 095 public int getDepthMax() { 096 return depth[queue[qTail - 1].getIndex()]; 097 } 098 099 public boolean tabu(Node node) { 100 return depth[node.getIndex()] != -1; 101 } 102 103 public boolean isDirected() { 104 return directed; 105 } 106}