third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/filters/FilterUtils.java

   1 /**
   2  * Copyright (c) 2008, the JUNG Project and the Regents of the University
   3  * of California
   4  * All rights reserved.
   5  *
   6  * This software is open-source under the BSD license; see either
   7  * "license.txt" or
   8  * http://jung.sourceforge.net/license.txt for a description.
   9  * Created on Jun 7, 2008
  10  *
  11  */
  12 package edu.uci.ics.jung.algorithms.filters;
  13
  14 import java.util.ArrayList;
  15 import java.util.Collection;
  16
  17 import edu.uci.ics.jung.graph.Hypergraph;
  18
  19 /**
  20  * Utility methods relating to filtering.
  21  */
  22 public class FilterUtils
  23 {
  24         /**
  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>.
  30          *
  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>
  39          */
  40         @SuppressWarnings("unchecked")
  41         public static <V,E,G extends Hypergraph<V,E>> G createInducedSubgraph(Collection<V>
  42                 vertices, G graph)
  43         {
  44                 G subgraph = null;
  45                 try
  46                 {
  47                         subgraph = (G)graph.getClass().newInstance();
  48
  49                         for (V v : vertices)
  50                         {
  51                                 if (!graph.containsVertex(v))
  52                                         throw new IllegalArgumentException("Vertex " + v +
  53                                                 " is not an element of " + graph);
  54                                 subgraph.addVertex(v);
  55                         }
  56
  57                         for (E e : graph.getEdges())
  58                         {
  59                                 Collection<V> incident = graph.getIncidentVertices(e);
  60                                 if (vertices.containsAll(incident))
  61                                         subgraph.addEdge(e, incident, graph.getEdgeType(e));
  62                         }
  63                 }
  64         catch (InstantiationException e)
  65         {
  66             throw new RuntimeException("Unable to create copy of existing graph: ", e);
  67         }
  68         catch (IllegalAccessException e)
  69         {
  70             throw new RuntimeException("Unable to create copy of existing graph: ", e);
  71         }
  72                 return subgraph;
  73         }
  74
  75         /**
  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>
  86          */
  87         public static <V,E,G extends Hypergraph<V,E>> Collection<G>
  88                 createAllInducedSubgraphs(Collection<? extends Collection<V>>
  89                         vertex_collections, G graph)
  90         {
  91                 Collection<G> subgraphs = new ArrayList<G>();
  92
  93                 for (Collection<V> vertex_set : vertex_collections)
  94                         subgraphs.add(createInducedSubgraph(vertex_set, graph));
  95
  96                 return subgraphs;
  97         }
  98 }