// Copyright (C) 1996 DIMACS Center, Rutgers, The State University of New Jersey
// Author(s): 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 <LINK/graph/Graph.h>
#include <LINK/graph/Vertex.h>
#include <LINK/graph/Edge.h>
#include <LINK/graph/Attribute.h>
#include <LINK/algorithm/Algorithms.h>

// rev_compare_vertices_by_finishtime()
// for sorting our list of vertices (reversed, by finishtime)
typedef Vertex* VertexPtr;
int rev_compare_vertices_by_finishtime(const VertexPtr& v1, const VertexPtr& v2) {
    int t1, t2;
    getAttribute((GraphObject*) v1, "finishtime", t1);
    getAttribute((GraphObject*) v2, "finishtime", t2);
    return (t2 - t1);
}


// root_vertex()
// after a DFS(), what is the root of this vertex's tree in the DFS forest?
Vertex*
root_vertex(Vertex*v) {
    Vertex* pred;
    getAttribute((GraphObject*)v, "pred", pred);
    if(pred) {
	return root_vertex(pred);
    }
    else {
	return v;
    }
}


// StronglyConnectedComponents()
// returns a set of the strongly connected components
Set< Set <Vertex*> >
StronglyConnectedComponents(Graph *graph, char *graph_view) {

    Set< Set<Vertex*> > result;

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

    DepthFirstSearch(graph);

    Graph* grapht = graph->transpose(CLONE);

    Sequence<Vertex*> dfs;
    dfs = DepthFirstSearch(grapht, 0, rev_compare_vertices_by_finishtime);

    while(!dfs.emptyQ()) {

	Iterator<Vertex*> get_v(&dfs);
	Vertex* v;

	// look at our first vertex
	get_v(v);

	Vertex* root = root_vertex(v);

	Set<Vertex*> scc;

	scc.insert(graph->vertex(grapht->rank(v)));
	dfs.remove(v);

	// and get all the vertices which share its root
	while(get_v(v)) {
	    if(root_vertex(v) == root) {
		scc.insert(graph->vertex(grapht->rank(v)));
		dfs.remove(v);
	    }
	}

	result.insert(scc);

    }

    delete grapht;
    
    return result;

}