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

   1 /*
   2  * Copyright (c) 2003, 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  */
  10 /*
  11  * Created on Apr 21, 2004
  12  */
  13 package edu.uci.ics.jung.algorithms.transformation;
  14
  15 import java.util.ArrayList;
  16 import java.util.Collection;
  17
  18 import org.apache.commons.collections15.Factory;
  19 import org.apache.commons.collections15.Predicate;
  20
  21 import edu.uci.ics.jung.graph.Graph;
  22 import edu.uci.ics.jung.graph.Hypergraph;
  23 import edu.uci.ics.jung.graph.KPartiteGraph;
  24
  25 /**
  26  * Methods for creating a "folded" graph based on a k-partite graph or a
  27  * hypergraph.
  28  *
  29  * <p>A "folded" graph is derived from a k-partite graph by identifying
  30  * a partition of vertices which will become the vertices of the new graph, copying
  31  * these vertices into the new graph, and then connecting those vertices whose
  32  * original analogues were connected indirectly through elements
  33  * of other partitions.</p>
  34  *
  35  * <p>A "folded" graph is derived from a hypergraph by creating vertices based on
  36  * either the vertices or the hyperedges of the original graph, and connecting
  37  * vertices in the new graph if their corresponding vertices/hyperedges share a
  38  * connection with a common hyperedge/vertex.</p>
  39  *
  40  * @author Danyel Fisher
  41  * @author Joshua O'Madadhain
  42  */
  43 public class FoldingTransformer<V,E>
  44 {
  45
  46     /**
  47      * Converts <code>g</code> into a unipartite graph whose vertex set is the
  48      * vertices of <code>g</code>'s partition <code>p</code>.  For vertices
  49      * <code>a</code> and <code>b</code> in this partition, the resultant
  50      * graph will include the edge <code>(a,b)</code> if the original graph
  51      * contains edges <code>(a,c)</code> and <code>(c,b)</code> for at least
  52      * one vertex <code>c</code>.
  53      *
  54      * <p>The vertices of the new graph are the same as the vertices of the
  55      * appropriate partition in the old graph; the edges in the new graph are
  56      * created by the input edge <code>Factory</code>.</p>
  57      *
  58      * <p>If there is more than 1 such vertex <code>c</code> for a given pair
  59      * <code>(a,b)</code>, the type of the output graph will determine whether
  60      * it will contain parallel edges or not.</p>
  61      *
  62      * <p>This function will not create self-loops.</p>
  63      *
  64      * @param <V> vertex type
  65      * @param <E> input edge type
  66      * @param g input k-partite graph
  67      * @param p predicate specifying vertex partition
  68      * @param graph_factory factory used to create the output graph
  69      * @param edge_factory factory used to create the edges in the new graph
  70      * @return a copy of the input graph folded with respect to the input partition
  71      */
  72     public static <V,E> Graph<V,E> foldKPartiteGraph(KPartiteGraph<V,E> g, Predicate<V> p,
  73             Factory<Graph<V,E>> graph_factory, Factory<E> edge_factory)
  74     {
  75         Graph<V,E> newGraph = graph_factory.create();
  76
  77         // get vertices for the specified partition
  78         Collection<V> vertices = g.getVertices(p);
  79         for (V v : vertices)
  80         {
  81             newGraph.addVertex(v);
  82             for (V s : g.getSuccessors(v))
  83             {
  84                 for (V t : g.getSuccessors(s))
  85                 {
  86                     if (!vertices.contains(t) || t.equals(v))
  87                         continue;
  88                     newGraph.addVertex(t);
  89                     newGraph.addEdge(edge_factory.create(), v, t);
  90                 }
  91             }
  92         }
  93         return newGraph;
  94     }
  95
  96     /**
  97      * Converts <code>g</code> into a unipartite graph whose vertices are the
  98      * vertices of <code>g</code>'s partition <code>p</code>, and whose edges
  99      * consist of collections of the intermediate vertices from other partitions.
 100      * For vertices
 101      * <code>a</code> and <code>b</code> in this partition, the resultant
 102      * graph will include the edge <code>(a,b)</code> if the original graph
 103      * contains edges <code>(a,c)</code> and <code>(c,b)</code> for at least
 104      * one vertex <code>c</code>.
 105      *
 106      * <p>The vertices of the new graph are the same as the vertices of the
 107      * appropriate partition in the old graph; the edges in the new graph are
 108      * collections of the intermediate vertices <code>c</code>.</p>
 109      *
 110      * <p>This function will not create self-loops.</p>
 111      *
 112      * @param <V> vertex type
 113      * @param <E> input edge type
 114      * @param g input k-partite graph
 115      * @param p predicate specifying vertex partition
 116      * @param graph_factory factory used to create the output graph
 117      * @return the result of folding g into unipartite graph whose vertices
 118      * are those of the <code>p</code> partition of g
 119      */
 120     public static <V,E> Graph<V, Collection<V>> foldKPartiteGraph(KPartiteGraph<V,E> g, Predicate<V> p,
 121             Factory<Graph<V, Collection<V>>> graph_factory)
 122     {
 123         Graph<V, Collection<V>> newGraph = graph_factory.create();
 124
 125         // get vertices for the specified partition, copy into new graph
 126         Collection<V> vertices = g.getVertices(p);
 127
 128         for (V v : vertices)
 129         {
 130             newGraph.addVertex(v);
 131             for (V s : g.getSuccessors(v))
 132             {
 133                 for (V t : g.getSuccessors(s))
 134                 {
 135                     if (!vertices.contains(t) || t.equals(v))
 136                         continue;
 137                     newGraph.addVertex(t);
 138                     Collection<V> v_coll = newGraph.findEdge(v, t);
 139                     if (v_coll == null)
 140                     {
 141                         v_coll = new ArrayList<V>();
 142                         newGraph.addEdge(v_coll, v, t);
 143                     }
 144                     v_coll.add(s);
 145                 }
 146             }
 147         }
 148         return newGraph;
 149     }
 150
 151     /**
 152      * Creates a <code>Graph</code> which is an edge-folded version of <code>h</code>, where
 153      * hyperedges are replaced by k-cliques in the output graph.
 154      *
 155      * <p>The vertices of the new graph are the same objects as the vertices of
 156      * <code>h</code>, and <code>a</code>
 157      * is connected to <code>b</code> in the new graph if the corresponding vertices
 158      * in <code>h</code> are connected by a hyperedge.  Thus, each hyperedge with
 159      * <i>k</i> vertices in <code>h</code> induces a <i>k</i>-clique in the new graph.</p>
 160      *
 161      * <p>The edges of the new graph consist of collections of each hyperedge that connected
 162      * the corresponding vertex pair in the original graph.</p>
 163      *
 164      * @param <V> vertex type
 165      * @param <E> input edge type
 166      * @param h hypergraph to be folded
 167      * @param graph_factory factory used to generate the output graph
 168      * @return a copy of the input graph where hyperedges are replaced by cliques
 169      */
 170     public static <V,E> Graph<V, Collection<E>> foldHypergraphEdges(Hypergraph<V,E> h,
 171             Factory<Graph<V, Collection<E>>> graph_factory)
 172     {
 173         Graph<V, Collection<E>> target = graph_factory.create();
 174
 175         for (V v : h.getVertices())
 176             target.addVertex(v);
 177
 178         for (E e : h.getEdges())
 179         {
 180             ArrayList<V> incident = new ArrayList<V>(h.getIncidentVertices(e));
 181             populateTarget(target, e, incident);
 182         }
 183         return target;
 184     }
 185
 186
 187     /**
 188      * Creates a <code>Graph</code> which is an edge-folded version of <code>h</code>, where
 189      * hyperedges are replaced by k-cliques in the output graph.
 190      *
 191      * <p>The vertices of the new graph are the same objects as the vertices of
 192      * <code>h</code>, and <code>a</code>
 193      * is connected to <code>b</code> in the new graph if the corresponding vertices
 194      * in <code>h</code> are connected by a hyperedge.  Thus, each hyperedge with
 195      * <i>k</i> vertices in <code>h</code> induces a <i>k</i>-clique in the new graph.</p>
 196      *
 197      * <p>The edges of the new graph are generated by the specified edge factory.</p>
 198      *
 199      * @param <V> vertex type
 200      * @param <E> input edge type
 201      * @param h hypergraph to be folded
 202      * @param graph_factory factory used to generate the output graph
 203      * @param edge_factory factory used to create the new edges
 204      * @return a copy of the input graph where hyperedges are replaced by cliques
 205      */
 206     public static <V,E> Graph<V,E> foldHypergraphEdges(Hypergraph<V,E> h,
 207             Factory<Graph<V,E>> graph_factory, Factory<E> edge_factory)
 208     {
 209         Graph<V,E> target = graph_factory.create();
 210
 211         for (V v : h.getVertices())
 212             target.addVertex(v);
 213
 214         for (E e : h.getEdges())
 215         {
 216             ArrayList<V> incident = new ArrayList<V>(h.getIncidentVertices(e));
 217             for (int i = 0; i < incident.size(); i++)
 218                 for (int j = i+1; j < incident.size(); j++)
 219                     target.addEdge(edge_factory.create(), incident.get(i), incident.get(j));
 220         }
 221         return target;
 222     }
 223
 224     /**
 225      * Creates a <code>Graph</code> which is a vertex-folded version of <code>h</code>, whose
 226      * vertices are the input's hyperedges and whose edges are induced by adjacent hyperedges
 227      * in the input.
 228      *
 229      * <p>The vertices of the new graph are the same objects as the hyperedges of
 230      * <code>h</code>, and <code>a</code>
 231      * is connected to <code>b</code> in the new graph if the corresponding edges
 232      * in <code>h</code> have a vertex in common.  Thus, each vertex incident to
 233      * <i>k</i> edges in <code>h</code> induces a <i>k</i>-clique in the new graph.</p>
 234      *
 235      * <p>The edges of the new graph are created by the specified factory.</p>
 236      *
 237      * @param <V> vertex type
 238      * @param <E> input edge type
 239      * @param <F> output edge type
 240      * @param h hypergraph to be folded
 241      * @param graph_factory factory used to generate the output graph
 242      * @param edge_factory factory used to generate the output edges
 243      * @return a transformation of the input graph whose vertices correspond to the input's hyperedges
 244      * and edges are induced by hyperedges sharing vertices in the input
 245      */
 246     public static <V,E,F> Graph<E,F> foldHypergraphVertices(Hypergraph<V,E> h,
 247             Factory<Graph<E,F>> graph_factory, Factory<F> edge_factory)
 248     {
 249         Graph<E,F> target = graph_factory.create();
 250
 251         for (E e : h.getEdges())
 252             target.addVertex(e);
 253
 254         for (V v : h.getVertices())
 255         {
 256             ArrayList<E> incident = new ArrayList<E>(h.getIncidentEdges(v));
 257             for (int i = 0; i < incident.size(); i++)
 258                 for (int j = i+1; j < incident.size(); j++)
 259                     target.addEdge(edge_factory.create(), incident.get(i), incident.get(j));
 260         }
 261
 262         return target;
 263     }
 264
 265     /**
 266      * Creates a <code>Graph</code> which is a vertex-folded version of <code>h</code>, whose
 267      * vertices are the input's hyperedges and whose edges are induced by adjacent hyperedges
 268      * in the input.
 269      *
 270      * <p>The vertices of the new graph are the same objects as the hyperedges of
 271      * <code>h</code>, and <code>a</code>
 272      * is connected to <code>b</code> in the new graph if the corresponding edges
 273      * in <code>h</code> have a vertex in common.  Thus, each vertex incident to
 274      * <i>k</i> edges in <code>h</code> induces a <i>k</i>-clique in the new graph.</p>
 275      *
 276      * <p>The edges of the new graph consist of collections of each vertex incident to
 277      * the corresponding hyperedge pair in the original graph.</p>
 278      *
 279      * @param h hypergraph to be folded
 280      * @param graph_factory factory used to generate the output graph
 281      * @return a transformation of the input graph whose vertices correspond to the input's hyperedges
 282      * and edges are induced by hyperedges sharing vertices in the input
 283      */
 284     public Graph<E,Collection<V>> foldHypergraphVertices(Hypergraph<V,E> h,
 285             Factory<Graph<E,Collection<V>>> graph_factory)
 286     {
 287         Graph<E,Collection<V>> target = graph_factory.create();
 288
 289         for (E e : h.getEdges())
 290             target.addVertex(e);
 291
 292         for (V v : h.getVertices())
 293         {
 294             ArrayList<E> incident = new ArrayList<E>(h.getIncidentEdges(v));
 295             populateTarget(target, v, incident);
 296         }
 297         return target;
 298     }
 299
 300     /**
 301      * @param target
 302      * @param e
 303      * @param incident
 304      */
 305     private static <S,T> void populateTarget(Graph<S, Collection<T>> target, T e,
 306             ArrayList<S> incident)
 307     {
 308         for (int i = 0; i < incident.size(); i++)
 309         {
 310             S v1 = incident.get(i);
 311             for (int j = i+1; j < incident.size(); j++)
 312             {
 313                 S v2 = incident.get(j);
 314                 Collection<T> e_coll = target.findEdge(v1, v2);
 315                 if (e_coll == null)
 316                 {
 317                     e_coll = new ArrayList<T>();
 318                     target.addEdge(e_coll, v1, v2);
 319                 }
 320                 e_coll.add(e);
 321             }
 322         }
 323     }
 324
 325 }