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

// BFS Visitor concept from BGL

using GCollections;

public interface Visitor<Graph,Vertex,Edge> {
  void initialize_vertex(Vertex u, Graph g);
  void discover_vertex(Vertex u, Graph g);
  void examine_edge(Edge e, Graph g);
  void tree_edge(Edge e, Graph g);
  void non_tree_edge(Edge e, Graph g);
  void gray_target(Edge e, Graph g);
  void black_target(Edge e, Graph g);
  void finish_vertex(Vertex u, Graph g);
}

// breadth_first_visit algorithm from BGL

public class graph_search {
  public static void go<
    GraphT,
    Vertex,
    Edge,
    VertexIterator,
    OutEdgeIterator,
    Vis,
    ColorMap,
    QueueType>
  (GraphT g, Vertex s, Vis vis, ColorMap color, QueueType Q)
    where GraphT: VertexListAndIncidenceGraph<
		    Vertex,
		    Edge,
		    VertexIterator,
		    OutEdgeIterator>,
	  Edge: GraphEdge<Vertex>,
	  VertexIterator: IEnumerable<Vertex>,
	  OutEdgeIterator: IEnumerable<Edge>,
	  Vis: Visitor<GraphT,Vertex,Edge>,
	  ColorMap: ReadWritePropertyMap<Vertex,ColorValue>,
	  QueueType: Buffer<Vertex> {
    vis.discover_vertex(s, g);
    ((ReadWritePropertyMap<Vertex,ColorValue>)color)[s] = ColorValue.gray;
    Q.push(s);
    while (!Q.empty()) {
      Vertex u = Q.pop();
      vis.discover_vertex(u, g);
      for (IEnumerator<Edge> ei = g.out_edges(u).GetEnumerator(); ei.MoveNext();) {
      //foreach (Edge e in g.out_edges(u)) {
        Edge e = ei.Current;
	Vertex v = e.target;
	vis.examine_edge(e, g);
	if (((ReadWritePropertyMap<Vertex,ColorValue>)color)[v] == ColorValue.white) {
	  vis.tree_edge(e, g);
	  ((ReadWritePropertyMap<Vertex,ColorValue>)color)[v] = ColorValue.gray;
	  Q.push(v);
	} else {
	  vis.non_tree_edge(e, g);
	  if (((ReadWritePropertyMap<Vertex,ColorValue>)color)[v] == ColorValue.gray) {
	    vis.gray_target(e, g);
	  } else {
	    vis.black_target(e, g);
	  }
	}
      }
      vis.finish_vertex(u, g);
      ((ReadWritePropertyMap<Vertex,ColorValue>)color)[u] = ColorValue.black;
    }
  }
}


// breadth_first_search algorithm from BGL

public class breadth_first_search {
  public static void go<
    GraphT,
    Vertex,
    Edge,
    VertexIterator,
    OutEdgeIterator,
    Vis,
    ColorMap>
  (GraphT g, Vertex s, Vis vis, ColorMap color)
    where GraphT: VertexListAndIncidenceGraph<
		    Vertex,
		    Edge,
		    VertexIterator,
		    OutEdgeIterator>,
	  Edge: GraphEdge<Vertex>,
	  VertexIterator: IEnumerable<Vertex>,
	  OutEdgeIterator: IEnumerable<Edge>,
	  Vis: Visitor<GraphT,Vertex,Edge>,
	  ColorMap: ReadWritePropertyMap<Vertex,ColorValue> {
    queue<Vertex> Q = new queue<Vertex>();
    for (IEnumerator<Vertex> ui = g.vertices().GetEnumerator(); ui.MoveNext();) {
      Vertex u = ui.Current;
    //foreach(Vertex u in g.vertices()) {
      vis.initialize_vertex(u, g);
      ((ReadWritePropertyMap<Vertex,ColorValue>)color)[u] = ColorValue.white;
    }
    graph_search.go<GraphT, Vertex, Edge, VertexIterator, OutEdgeIterator, Vis, ColorMap, queue<Vertex> >(g,s,vis,color,Q);
  }
}