package com.jwetherell.algorithms.graph;

import java.util.ArrayList;
import java.util.List;

import com.jwetherell.algorithms.data_structures.Graph;

/**
 * In computer science, a topological sort (sometimes abbreviated topsort or
 * toposort) or topological ordering of a directed graph is a linear ordering of
 * its vertices such that, for every edge uv, u comes before v in the ordering.
 * 
 * @author Justin Wetherell <phishman3579@gmail.com>
 */
public class TopologicalSort {

    private TopologicalSort() {
    };

    public static final List<Graph.Vertex<Integer>> sort(Graph<Integer> graph) {
        List<Graph.Vertex<Integer>> sorted = new ArrayList<Graph.Vertex<Integer>>();
        List<Graph.Vertex<Integer>> noOutgoing = new ArrayList<Graph.Vertex<Integer>>();
        for (Graph.Vertex<Integer> v : graph.getVerticies()) {
            if (v.getEdges().size() == 0) {
                noOutgoing.add(v);
            }
        }
        while (noOutgoing.size() > 0) {
            Graph.Vertex<Integer> v = noOutgoing.remove(0);
            sorted.add(v);
            for (Graph.Edge<Integer> e : graph.getEdges()) {
                Graph.Vertex<Integer> v2 = e.getFromVertex();
                Graph.Vertex<Integer> v3 = e.getToVertex();
                if (v3.equals(v)) {
                    graph.getEdges().remove(e);
                    v2.getEdges().remove(e);
                }
                if (v2.getEdges().size() == 0)
                    noOutgoing.add(v2);
            }
        }
        if (graph.getEdges().size() > 0)
            System.out.println("cycle detected");
        return sorted;
    }
}