import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.HashSet;
import java.util.Map;
import java.util.Stack;
import java.util.Queue;

import graphlib.*;

// Eksempler til BFÅP F2008 opgavesæt 4
// sestoft@itu.dk 2008-02-19

public class Exercises4 {

  /**
   * @param args
   */
  public static void main(String[] args) {
    Graph<Edge<Node>, Node> graph1 = gt6_6();
    breadthfirst(graph1, graph1.nodes.get(1));
  }
  
  /** 
   * Queue-based breadth-first traversal with printout 
   * of the graph's nodes 
   */
  public static void breadthfirst(Graph<Edge<Node>, Node> graph, Node start) {
    HashSet<Node> exploredNodes  = new HashSet<Node>();
    Queue<Node> toVisit = new LinkedList<Node>();

    System.out.println("Queue-based breadth-first traversal:");
    toVisit.offer(start);
    while (!toVisit.isEmpty()) {
      Node v = toVisit.poll();
      if (!exploredNodes.contains(v)) {
        System.out.print(v.index + " ");
        exploredNodes.add(v);
        for (Edge<Node> edge : graph.edges.get(v.index)) {
          Node w = edge.getOtherEnd(v);
          toVisit.offer(w);
        }
      }
    }
    System.out.println();
  }
  
  private static Graph<Edge<Node>, Node> gt6_6() {
    // The undirected graph from Goodrich & Tamassia figure 6.6
    Node 
      a = new Node(1), b = new Node(2), c = new Node(3), d = new Node(4), 
      e = new Node(5), f = new Node(6), g = new Node(7), h = new Node(8), 
      i = new Node(9), j = new Node(10), k = new Node(11), l = new Node(12), 
      m = new Node(13), n = new Node(14), o = new Node(15), p = new Node(16);
    Node[] nodesArray = new Node[] { a, b, c, d, e, f, g, h, i, j, k, l, m, o, p };
    ArrayList<Node> myNodes = new ArrayList<Node>();
    for (Node node : nodesArray)
      myNodes.add(node);
    Graph<Edge<Node>, Node> graph = new Graph<Edge<Node>, Node>(myNodes);
    graph.addEdge(new Edge<Node>(a, e, Edge.BOTH));
    graph.addEdge(new Edge<Node>(e, i, Edge.BOTH));
    graph.addEdge(new Edge<Node>(i, m, Edge.BOTH));    
    
    graph.addEdge(new Edge<Node>(a, b, Edge.BOTH));
    graph.addEdge(new Edge<Node>(a, f, Edge.BOTH));
    graph.addEdge(new Edge<Node>(e, f, Edge.BOTH));
    graph.addEdge(new Edge<Node>(f, i, Edge.BOTH));
    graph.addEdge(new Edge<Node>(i, j, Edge.BOTH));
    graph.addEdge(new Edge<Node>(i, n, Edge.BOTH));
    graph.addEdge(new Edge<Node>(m, n, Edge.BOTH));
    
    graph.addEdge(new Edge<Node>(b, f, Edge.BOTH));

    graph.addEdge(new Edge<Node>(b, c, Edge.BOTH));
    graph.addEdge(new Edge<Node>(j, g, Edge.BOTH));
    graph.addEdge(new Edge<Node>(j, k, Edge.BOTH));
    graph.addEdge(new Edge<Node>(n, k, Edge.BOTH));
    
    graph.addEdge(new Edge<Node>(c, g, Edge.BOTH));
    graph.addEdge(new Edge<Node>(g, k, Edge.BOTH));
    graph.addEdge(new Edge<Node>(k, o, Edge.BOTH));

    graph.addEdge(new Edge<Node>(c, d, Edge.BOTH));
    graph.addEdge(new Edge<Node>(g, d, Edge.BOTH));
    graph.addEdge(new Edge<Node>(g, l, Edge.BOTH));
    graph.addEdge(new Edge<Node>(o, p, Edge.BOTH));

    graph.addEdge(new Edge<Node>(d, h, Edge.BOTH));
    graph.addEdge(new Edge<Node>(h, l, Edge.BOTH));
    graph.addEdge(new Edge<Node>(l, p, Edge.BOTH));
    return graph;
    }

  private static Graph<Edge<Node>, Node> gt6_21() {
    // The directed graph from Goodrich & Tamassia figure 6.21
    Node 
      a = new Node(1), b = new Node(2), c = new Node(3), 
      d = new Node(4), e = new Node(5), f = new Node(6),
      g = new Node(7), h = new Node(8);
    Node[] nodesArray = new Node[] { a, b, c, d, e, f, g, h };
    ArrayList<Node> myNodes = new ArrayList<Node>();
    for (Node node : nodesArray)
      myNodes.add(node);
    Graph<Edge<Node>, Node> graph = new Graph<Edge<Node>, Node>(myNodes);
    graph.addEdge(new Edge<Node>(a, c, Edge.FORWARD));
    graph.addEdge(new Edge<Node>(a, d, Edge.FORWARD));
    graph.addEdge(new Edge<Node>(b, d, Edge.FORWARD));
    graph.addEdge(new Edge<Node>(b, f, Edge.FORWARD));
    graph.addEdge(new Edge<Node>(c, h, Edge.FORWARD));
    graph.addEdge(new Edge<Node>(c, e, Edge.FORWARD));
    graph.addEdge(new Edge<Node>(c, d, Edge.FORWARD));
    graph.addEdge(new Edge<Node>(d, f, Edge.FORWARD));
    graph.addEdge(new Edge<Node>(e, g, Edge.FORWARD));
    graph.addEdge(new Edge<Node>(g, h, Edge.FORWARD));
    graph.addEdge(new Edge<Node>(f, g, Edge.FORWARD));
    graph.addEdge(new Edge<Node>(f, h, Edge.FORWARD));
    // Uncomment to create cyclic subgraph so topological sort fails:
    // graph.addEdge(new Edge<Node>(h, b, Edge.FORWARD));
    return graph;
  }
}