// Copyright 2003, Trustees of Indiana University
// Please see the license in the file ../LICENSE

// breadth_first_visit algorithm from BFS

import java.lang.*;

public class graph_search {
  public static <
    Vertex,
    Edge extends GraphEdge<Vertex>,
    VertexIterator extends java.util.Iterator<Vertex>,
    OutEdgeIterator extends java.util.Iterator<Edge>,
    Vis extends Visitor,
    ColorMap extends ReadWritePropertyMap<Vertex,java.lang.Integer>,
    QueueType extends Buffer<Vertex>>
  void graph_search(VertexListAndIncidenceGraph<Vertex,Edge,VertexIterator,OutEdgeIterator> g, Vertex s, Visitor vis, ColorMap color, QueueType Q) {
    vis.discover_vertex(s, g);
    color.set(s, ColorValue.gray());
    Q.push(s);
    while (!Q.empty()) {
      Vertex u = Q.pop();
      vis.discover_vertex(u, g);
      for(OutEdgeIterator e_iter = g.out_edges(u); e_iter.hasNext(); ) {
	Edge e = e_iter.next();
	Vertex v = e.target();
	vis.examine_edge(e, g);
	if (color.get(v).equals(ColorValue.white())) {
	  vis.tree_edge(e, g);
	  color.set(v, ColorValue.gray());
	  Q.push(v);
	} else {
	  vis.non_tree_edge(e, g);
	  if (color.get(v).equals(ColorValue.gray())) {
	    vis.gray_target(e, g);
	  } else {
	    vis.black_target(e, g);
	  }
	}
      }
      vis.finish_vertex(u, g);
      color.set(u, ColorValue.black());
    }
  }
}