/* * Copyright (c) 2003, the JUNG Project and the Regents of the University * of California * All rights reserved. * * This software is open-source under the BSD license; see either * "license.txt" or * http://jung.sourceforge.net/license.txt for a description. */ /* * Created on Apr 21, 2004 */ package edu.uci.ics.jung.algorithms.transformation; import java.util.ArrayList; import java.util.Collection; import org.apache.commons.collections15.Factory; import org.apache.commons.collections15.Predicate; import edu.uci.ics.jung.graph.Graph; import edu.uci.ics.jung.graph.Hypergraph; import edu.uci.ics.jung.graph.KPartiteGraph; /** * Methods for creating a "folded" graph based on a k-partite graph or a * hypergraph. * *
A "folded" graph is derived from a k-partite graph by identifying * a partition of vertices which will become the vertices of the new graph, copying * these vertices into the new graph, and then connecting those vertices whose * original analogues were connected indirectly through elements * of other partitions.
* *A "folded" graph is derived from a hypergraph by creating vertices based on * either the vertices or the hyperedges of the original graph, and connecting * vertices in the new graph if their corresponding vertices/hyperedges share a * connection with a common hyperedge/vertex.
* * @author Danyel Fisher * @author Joshua O'Madadhain */ public class FoldingTransformerg
into a unipartite graph whose vertex set is the
* vertices of g
's partition p
. For vertices
* a
and b
in this partition, the resultant
* graph will include the edge (a,b)
if the original graph
* contains edges (a,c)
and (c,b)
for at least
* one vertex c
.
*
* The vertices of the new graph are the same as the vertices of the
* appropriate partition in the old graph; the edges in the new graph are
* created by the input edge Factory
.
If there is more than 1 such vertex c
for a given pair
* (a,b)
, the type of the output graph will determine whether
* it will contain parallel edges or not.
This function will not create self-loops.
* * @paramg
into a unipartite graph whose vertices are the
* vertices of g
's partition p
, and whose edges
* consist of collections of the intermediate vertices from other partitions.
* For vertices
* a
and b
in this partition, the resultant
* graph will include the edge (a,b)
if the original graph
* contains edges (a,c)
and (c,b)
for at least
* one vertex c
.
*
* The vertices of the new graph are the same as the vertices of the
* appropriate partition in the old graph; the edges in the new graph are
* collections of the intermediate vertices c
.
This function will not create self-loops.
* * @paramp
partition of g
*/
public static Graph
which is an edge-folded version of h
, where
* hyperedges are replaced by k-cliques in the output graph.
*
* The vertices of the new graph are the same objects as the vertices of
* h
, and a
* is connected to b
in the new graph if the corresponding vertices
* in h
are connected by a hyperedge. Thus, each hyperedge with
* k vertices in h
induces a k-clique in the new graph.
The edges of the new graph consist of collections of each hyperedge that connected * the corresponding vertex pair in the original graph.
* * @paramGraph
which is an edge-folded version of h
, where
* hyperedges are replaced by k-cliques in the output graph.
*
* The vertices of the new graph are the same objects as the vertices of
* h
, and a
* is connected to b
in the new graph if the corresponding vertices
* in h
are connected by a hyperedge. Thus, each hyperedge with
* k vertices in h
induces a k-clique in the new graph.
The edges of the new graph are generated by the specified edge factory.
* * @paramGraph
which is a vertex-folded version of h
, whose
* vertices are the input's hyperedges and whose edges are induced by adjacent hyperedges
* in the input.
*
* The vertices of the new graph are the same objects as the hyperedges of
* h
, and a
* is connected to b
in the new graph if the corresponding edges
* in h
have a vertex in common. Thus, each vertex incident to
* k edges in h
induces a k-clique in the new graph.
The edges of the new graph are created by the specified factory.
* * @paramGraph
which is a vertex-folded version of h
, whose
* vertices are the input's hyperedges and whose edges are induced by adjacent hyperedges
* in the input.
*
* The vertices of the new graph are the same objects as the hyperedges of
* h
, and a
* is connected to b
in the new graph if the corresponding edges
* in h
have a vertex in common. Thus, each vertex incident to
* k edges in h
induces a k-clique in the new graph.
The edges of the new graph consist of collections of each vertex incident to * the corresponding hyperedge pair in the original graph.
* * @param h hypergraph to be folded * @param graph_factory factory used to generate the output graph * @return a transformation of the input graph whose vertices correspond to the input's hyperedges * and edges are induced by hyperedges sharing vertices in the input */ public Graph