/*
* 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.