// D. Scott
// CCI - Problem 4.7
// Find build order for projects with dependencies

import java.util.LinkedList;

class Graph {
    public LinkedList<Node> nodes;
    
    public Graph(Node n) {
        this.nodes = new LinkedList<>();
        this.addNode(n);
    }
    
    public void addNode(Node n) {
        nodes.add(n);
    }
}

class Node {
    public String name;
    LinkedList<Node> children;
    public boolean visited;
    
    public Node() {
        this.name = "";
        children = new LinkedList<Node>();
        this.visited = false;
    }
    
    public Node(String n) {
        this.name = n;
        children = new LinkedList<Node>();
        this.visited = false;
    }
        
    public void addChild(Node c) {
            children.add(c);
    }
}
        

public static void main (String[] args) {
    Node a = new Node("a");
    Node b = new Node("b");
    Node c = new Node("c");
    Node d = new Node("d");
    Node e = new Node("e");
    Node f = new Node("f");
    
    a.addChild(d);
    b.addChild(d);
    d.addChild(c);
    f.addChild(a);
    f.addChild(b);
    
    Graph g = new Graph(a);
    g.addNode(b);
    g.addNode(c);
    g.addNode(d);
    g.addNode(e);
    g.addNode(f);
    
    Node start = g.nodes.get(0);
    int i = 1;
    
    // proceed through all nodes in graph, using each as a potential starting point
    while (start != null) {0
        System.out.println("\nChecking for start node "+start.name);
        System.out.println("--------------------------\n");
        LinkedList<Node> order = new LinkedList<>();
        
        // perform DFS on graph
        LinkedList<Node> ordering = search(start,order);
        
        // check for projects with no dependencies and append to front of ordering
        for (int j = 0; j < g.nodes.size(); j++) {
            Node cur = g.nodes.get(j);
            boolean has_dependency = false;
            for (int k = 0; k < g.nodes.size(); k++) {
                Node comp = g.nodes.get(k);
                for (int l = 0; l < comp.children.size(); l++) {
                    Node comp_dependencies = comp.children.get(l);
                    if (comp_dependencies.name == cur.name)
                        has_dependency = true;
                }
            }
            if (has_dependency == false) {
                boolean already_added = false;
                for (int k = 0; k < order.size(); k++)
                    if (order.get(k).name == cur.name)
                        already_added = true;
                if (already_added == false)
                    order.add(cur);
            }

        }

        // display results (success/failure)
        System.out.println("The build order is: \n")
        for (int j = 0; j < order.size(); j++)
            System.out.print(order.get(j).name + ", ");
        if (order.size() == g.nodes.size()) {
            System.out.println("\n\n\tSuccessful ordering!");
            break;
        } else {
            for (int j = 0; j < g.nodes.size(); j++)
                g.nodes.get(j).visited = false;
            System.out.println("\n\n\tCannot complete project with start node "+start.name);
            start = g.nodes.get(i++);
        }
    }
    
    return;
    
}

// DFS on graph with root r, returns LL ordering of DFS
public LinkedList<Node> search(Node r, LinkedList<Node> order) {
    if (r == null)
        return order;
    order.add(r);
    r.visited = true;
    for (int i = 0; i < r.children.size(); i++) {
        Node c = r.children.get(i);
        if (c.visited == false)
            search(c,order);
    }
}