/*
* Copyright (c) 2003, The JUNG Authors 
*
* All rights reserved.
*
* This software is open-source under the BSD license; see either
* "license.txt" or
* https://github.com/jrtom/jung/blob/master/LICENSE for a description.
*/
package edu.uci.ics.jung.algorithms.cluster;

import java.util.Collection;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

import com.google.common.base.Function;

import edu.uci.ics.jung.graph.Graph;



/**
 * Finds all weak components in a graph as sets of vertex sets.  A weak component is defined as
 * a maximal subgraph in which all pairs of vertices in the subgraph are reachable from one
 * another in the underlying undirected subgraph.
 * 

This implementation identifies components as sets of vertex sets. * To create the induced graphs from any or all of these vertex sets, * see algorithms.filters.FilterUtils. *

* Running time: O(|V| + |E|) where |V| is the number of vertices and |E| is the number of edges. * @author Scott White */ public class WeakComponentClusterer implements Function, Set>> { /** * Extracts the weak components from a graph. * @param graph the graph whose weak components are to be extracted * @return the list of weak components */ public Set> apply(Graph graph) { Set> clusterSet = new HashSet>(); HashSet unvisitedVertices = new HashSet(graph.getVertices()); while (!unvisitedVertices.isEmpty()) { Set cluster = new HashSet(); V root = unvisitedVertices.iterator().next(); unvisitedVertices.remove(root); cluster.add(root); Queue queue = new LinkedList(); queue.add(root); while (!queue.isEmpty()) { V currentVertex = queue.remove(); Collection neighbors = graph.getNeighbors(currentVertex); for(V neighbor : neighbors) { if (unvisitedVertices.contains(neighbor)) { queue.add(neighbor); unvisitedVertices.remove(neighbor); cluster.add(neighbor); } } } clusterSet.add(cluster); } return clusterSet; } }

Ads help maintain this website.