2 * Copyright (c) 2008, the JUNG Project and the Regents of the University
6 * This software is open-source under the BSD license; see either
8 * http://jung.sourceforge.net/license.txt for a description.
9 * Created on Jun 7, 2008
12 package edu.uci.ics.jung.algorithms.filters;
14 import java.util.ArrayList;
15 import java.util.Collection;
17 import edu.uci.ics.jung.graph.Hypergraph;
20 * Utility methods relating to filtering.
22 public class FilterUtils
25 * Creates the induced subgraph from <code>graph</code> whose vertex set
26 * is equal to <code>vertices</code>. The graph returned has
27 * <code>vertices</code> as its vertex set, and includes all edges from
28 * <code>graph</code> which are incident only to elements of
29 * <code>vertices</code>.
31 * @param <V> the vertex type
32 * @param <E> the edge type
33 * @param vertices the subset of <code>graph</code>'s vertices around
34 * which the subgraph is to be constructed
35 * @param graph the graph whose subgraph is to be constructed
36 * @return the subgraph induced by <code>vertices</code>
37 * @throws IllegalArgumentException if any vertex in
38 * <code>vertices</code> is not in <code>graph</code>
40 @SuppressWarnings("unchecked")
41 public static <V,E,G extends Hypergraph<V,E>> G createInducedSubgraph(Collection<V>
47 subgraph = (G)graph.getClass().newInstance();
51 if (!graph.containsVertex(v))
52 throw new IllegalArgumentException("Vertex " + v +
53 " is not an element of " + graph);
54 subgraph.addVertex(v);
57 for (E e : graph.getEdges())
59 Collection<V> incident = graph.getIncidentVertices(e);
60 if (vertices.containsAll(incident))
61 subgraph.addEdge(e, incident, graph.getEdgeType(e));
64 catch (InstantiationException e)
66 throw new RuntimeException("Unable to create copy of existing graph: ", e);
68 catch (IllegalAccessException e)
70 throw new RuntimeException("Unable to create copy of existing graph: ", e);
76 * Creates the induced subgraphs of <code>graph</code> associated with each
77 * element of <code>vertex_collections</code>.
78 * Note that these vertex collections need not be disjoint.
79 * @param <V> the vertex type
80 * @param <E> the edge type
81 * @param vertex_collections the collections of vertex collections to be
82 * used to induce the subgraphs
83 * @param graph the graph whose subgraphs are to be created
84 * @return the induced subgraphs of <code>graph</code> associated with each
85 * element of <code>vertex_collections</code>
87 public static <V,E,G extends Hypergraph<V,E>> Collection<G>
88 createAllInducedSubgraphs(Collection<? extends Collection<V>>
89 vertex_collections, G graph)
91 Collection<G> subgraphs = new ArrayList<G>();
93 for (Collection<V> vertex_set : vertex_collections)
94 subgraphs.add(createInducedSubgraph(vertex_set, graph));