// Copyright (C) 1996 DIMACS Center, Rutgers, The State University of New Jersey
// Author(s): Michael Murphy (Los Alamos National Laboratory),
//	      Chris Burrows (Trenton State College)

// This software is copyrighted by the DIMACS Center at Rutgers, The State
// University of New Jersey.  IT IS PROVIDED AS IS, AND THE AUTHORS, DIMACS, AND
// RUTGERS, THE STATE UNIVERSITY OF NEW JERSEY  DISCLAIM
// ALL LIABILITY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
// DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, OR ANY
// DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.

// THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
// INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE, AND NON-INFRINGEMENT.  THIS SOFTWARE
// IS PROVIDED ON AN "AS IS" BASIS, AND THE AUTHORS AND DISTRIBUTORS HAVE
// NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
// MODIFICATIONS.

// The authors hereby grant permission to use, copy, modify, distribute,
// and license this software and its documentation for any purpose, provided
// that existing copyright notices are retained in all copies and that this
// notice is included verbatim in any distributions. No written agreement,
// license, or royalty fee is required for any of the authorized uses.
// Modifications to this software may be copyrighted by their authors
// and need not follow the licensing terms described here, provided that
// the new terms are clearly indicated on the first page of each file where
// they apply.

// Last File Update: 31-Jul-1996
// 

#include <stdio.h>
#include <strstream.h>
#include <LINK/graph/Graph.h>
#include <LINK/graph/Vertex.h>
#include <LINK/graph/Edge.h>
#include <LINK/graph/Attribute.h>
#include <LINK/basic/Sequence.h>
#include <LINK/basic/BinaryHeap.h>
#include <LINK/algorithm/Algorithms.h>

static char sortedColor[] = "red";
static char nolabel[] = "";

typedef Vertex * VertexPtr;
inline int comp_by_finishtime(const VertexPtr& v1, const VertexPtr& v2) {
    int t1, t2;
    getAttribute((GraphObject*)v1, "finishtime", t1);
    getAttribute((GraphObject*)v2, "finishtime", t2);
    return t1 - t2;
}

inline int reverse_comp_by_finishtime(const VertexPtr& v1, const VertexPtr& v2) {
    return -comp_by_finishtime(v1, v2);
}


Sequence<Vertex*>
TopologicalSort(Graph* graph, char* graph_view)
{

    ResetAttributes(graph);

    Sequence<Vertex*> result;

    if (!graph->binaryQ() || !graph->directedQ()) {
	error("TopologicalSort: Graph must be directed binary");
	return result;
    }

    DepthFirstSearch(graph, graph_view);

    Edge *edge;

    const MSet<Edge*>& edges(graph->edges());
    Iterator<Edge*> get_edge(&edges);

    while (get_edge(edge)) {
	int edge_t;
	getAttribute((GraphObject*) edge, "type", edge_t);
        if (edge_t == BACK_EDGE_TYPE) {
	    error("TopologicalSort: Graph must be acyclic");
	    return result;
	}
    }

    int order = graph->order();

    List<Vertex*> sorting_list;
    int i;
    for(i=0;i<order;i++) 
	sorting_list.append(graph->vertex(i));
    
    sorting_list.sort(reverse_comp_by_finishtime);
    
    result = sorting_list;

    for(i=0;i<order;i++) 
	animateVertex(graph->vertex(i), graph_view, "color", "color", INIT_STEP, (char*)"black");
    
    get_edge.reset();
    while (get_edge(edge))
	animateEdge(edge, graph_view, "color", "color", INIT_STEP, (char*)"black");

    if (graph_view) {
	sorting_list.sort(comp_by_finishtime);
	while (order>0) {
	    Vertex* v = sorting_list.get();
	    animateVertex(v, graph_view, "color", "color", ALG_STEP, (char*)sortedColor);
	    ostrstream oss; oss << order << ends; char* tmp = oss.str();
	    animateVertex(v, graph_view, "label", "vertex-label", ALG_STEP, tmp);
	    delete[] tmp;
	    
	    const MSet<Edge*>& edges(graph->inIncidentEdges(v));
	    Iterator<Edge*> get_edges(&edges);
	    while (get_edges(edge)) {
		animateEdge(edge, graph_view, "color", "color", ALG_STEP, (char*)sortedColor);
	    }
	    order--;
	}
    }

    return result;

}