/*
 *    Copyright 2013 University of Southern California
 *
 *  Licensed under the Apache License, Version 2.0 (the "License");
 *  you may not use this file except in compliance with the License. 
 *  You may obtain a copy of the License at
 *
 *    http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing,
 *  software distributed under the License is distributed on an
 *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 *  KIND, either express or implied.  See the License for the
 *  specific language governing permissions and limitations
 *  under the License.
 */

package edu.usc.goffish.gofs.graph.algorithms;

import java.util.*;

import edu.usc.goffish.gofs.graph.*;
import edu.usc.goffish.gofs.util.*;

public final class ConnectedComponents {

	public static <TVertex extends IVertex, TEdge extends IEdge> Collection<? extends Collection<TVertex>> findWeak(IGraph<? extends TVertex, TEdge> graph) {

		// TODO: profile DFS/BFS based WCC detection for undirected graphs vs disjoint set implementation

		// initialize disjoint set
		DisjointSets<TVertex> ds = new DisjointSets<TVertex>(graph.numVertices());
		for (TVertex vertex : graph.vertices()) {
			ds.addSet(vertex);
		}

		// union edge pairs
		for (TEdge edge : graph.edges()) {
			@SuppressWarnings("unchecked")
			TVertex source = (TVertex)edge.getSource();
			@SuppressWarnings("unchecked")
			TVertex sink = (TVertex)edge.getSink();

			ds.union(source, sink);
		}

		return ds.retrieveSets();
	}
}
