/*
* (C) Copyright 2003-2017, by Barak Naveh and Contributors.
*
* JGraphT : a free Java graph-theory library
*
* This program and the accompanying materials are dual-licensed under
* either
*
* (a) the terms of the GNU Lesser General Public License version 2.1
* as published by the Free Software Foundation, or (at your option) any
* later version.
*
* or (per the licensee's choosing)
*
* (b) the terms of the Eclipse Public License v1.0 as published by
* the Eclipse Foundation.
*/
package org.jgrapht.traverse;
import java.util.*;
import org.jgrapht.*;
/**
* A breadth-first iterator for a directed and an undirected graph. For this iterator to work
* correctly the graph must not be modified during iteration. Currently there are no means to ensure
* that, nor to fail-fast. The results of such modifications are undefined.
*
* @param the graph vertex type
* @param the graph edge type
*
* @author Barak Naveh
* @since Jul 19, 2003
*/
public class BreadthFirstIterator
extends CrossComponentIterator
{
private Deque queue = new ArrayDeque<>();
/**
* Creates a new breadth-first iterator for the specified graph.
*
* @param g the graph to be iterated.
*/
public BreadthFirstIterator(Graph g)
{
this(g, null);
}
/**
* Creates a new breadth-first iterator for the specified graph. Iteration will start at the
* specified start vertex and will be limited to the connected component that includes that
* vertex. If the specified start vertex is null, iteration will start at an
* arbitrary vertex and will not be limited, that is, will be able to traverse all the graph.
*
* @param g the graph to be iterated.
* @param startVertex the vertex iteration to be started.
*/
public BreadthFirstIterator(Graph g, V startVertex)
{
super(g, startVertex);
}
/**
* @see CrossComponentIterator#isConnectedComponentExhausted()
*/
@Override
protected boolean isConnectedComponentExhausted()
{
return queue.isEmpty();
}
/**
* @see CrossComponentIterator#encounterVertex(Object, Object)
*/
@Override
protected void encounterVertex(V vertex, E edge)
{
putSeenData(vertex, null);
queue.add(vertex);
}
/**
* @see CrossComponentIterator#encounterVertexAgain(Object, Object)
*/
@Override
protected void encounterVertexAgain(V vertex, E edge)
{
}
/**
* @see CrossComponentIterator#provideNextVertex()
*/
@Override
protected V provideNextVertex()
{
return queue.removeFirst();
}
}
// End BreadthFirstIterator.java
Ads help maintain this website.