edu.uci.ics.jung.algorithms.transformation
Class FoldingTransformer<V,E>

java.lang.Object
  edu.uci.ics.jung.algorithms.transformation.FoldingTransformer<V,E>

public class FoldingTransformer<V,E>
extends Object

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, Joshua O'Madadhain

Constructor Summary

FoldingTransformer()

Method Summary

static <V,E> Graph<V,Collection<E>>	foldHypergraphEdges(Hypergraph<V,E> h, org.apache.commons.collections15.Factory<Graph<V,Collection<E>>> graph_factory) Creates a Graph which is an edge-folded version of h, where hyperedges are replaced by k-cliques in the output graph.
static <V,E> Graph<V,E>	foldHypergraphEdges(Hypergraph<V,E> h, org.apache.commons.collections15.Factory<Graph<V,E>> graph_factory, org.apache.commons.collections15.Factory<E> edge_factory) Creates a Graph which is an edge-folded version of h, where hyperedges are replaced by k-cliques in the output graph.
Graph<E,Collection<V>>	foldHypergraphVertices(Hypergraph<V,E> h, org.apache.commons.collections15.Factory<Graph<E,Collection<V>>> graph_factory) Creates a Graph 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.
static <V,E,F> Graph<E,F>	foldHypergraphVertices(Hypergraph<V,E> h, org.apache.commons.collections15.Factory<Graph<E,F>> graph_factory, org.apache.commons.collections15.Factory<F> edge_factory) Creates a Graph 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.
static <V,E> Graph<V,Collection<V>>	foldKPartiteGraph(KPartiteGraph<V,E> g, org.apache.commons.collections15.Predicate<V> p, org.apache.commons.collections15.Factory<Graph<V,Collection<V>>> graph_factory) Converts g 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.
static <V,E> Graph<V,E>	foldKPartiteGraph(KPartiteGraph<V,E> g, org.apache.commons.collections15.Predicate<V> p, org.apache.commons.collections15.Factory<Graph<V,E>> graph_factory, org.apache.commons.collections15.Factory<E> edge_factory) Converts g into a unipartite graph whose vertex set is the vertices of g's partition p.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

FoldingTransformer

public FoldingTransformer()

Method Detail

foldKPartiteGraph

public static <V,E> Graph<V,E> foldKPartiteGraph(KPartiteGraph<V,E> g,
                                                 org.apache.commons.collections15.Predicate<V> p,
                                                 org.apache.commons.collections15.Factory<Graph<V,E>> graph_factory,
                                                 org.apache.commons.collections15.Factory<E> edge_factory)

Converts g 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.

Type Parameters:

V - vertex type

E - input edge type

Parameters:

g - input k-partite graph

p - predicate specifying vertex partition

graph_factory - factory used to create the output graph

edge_factory - factory used to create the edges in the new graph

Returns:

a copy of the input graph folded with respect to the input partition

foldKPartiteGraph

public static <V,E> Graph<V,Collection<V>> foldKPartiteGraph(KPartiteGraph<V,E> g,
                                                             org.apache.commons.collections15.Predicate<V> p,
                                                             org.apache.commons.collections15.Factory<Graph<V,Collection<V>>> graph_factory)

Converts g 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.

Type Parameters:

V - vertex type

E - input edge type

Parameters:

g - input k-partite graph

p - predicate specifying vertex partition

graph_factory - factory used to create the output graph

Returns:

the result of folding g into unipartite graph whose vertices are those of the p partition of g

foldHypergraphEdges

public static <V,E> Graph<V,Collection<E>> foldHypergraphEdges(Hypergraph<V,E> h,
                                                               org.apache.commons.collections15.Factory<Graph<V,Collection<E>>> graph_factory)

Creates a 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.

Type Parameters:

V - vertex type

E - input edge type

Parameters:

h - hypergraph to be folded

graph_factory - factory used to generate the output graph

Returns:

a copy of the input graph where hyperedges are replaced by cliques

foldHypergraphEdges

public static <V,E> Graph<V,E> foldHypergraphEdges(Hypergraph<V,E> h,
                                                   org.apache.commons.collections15.Factory<Graph<V,E>> graph_factory,
                                                   org.apache.commons.collections15.Factory<E> edge_factory)

Creates a 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 are generated by the specified edge factory.

Type Parameters:

V - vertex type

E - input edge type

Parameters:

h - hypergraph to be folded

graph_factory - factory used to generate the output graph

edge_factory - factory used to create the new edges

Returns:

a copy of the input graph where hyperedges are replaced by cliques

foldHypergraphVertices

public static <V,E,F> Graph<E,F> foldHypergraphVertices(Hypergraph<V,E> h,
                                                        org.apache.commons.collections15.Factory<Graph<E,F>> graph_factory,
                                                        org.apache.commons.collections15.Factory<F> edge_factory)

Creates a Graph 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.

Type Parameters:

V - vertex type

E - input edge type

F - output edge type

Parameters:

h - hypergraph to be folded

graph_factory - factory used to generate the output graph

edge_factory - factory used to generate the output edges

Returns:

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

foldHypergraphVertices

public Graph<E,Collection<V>> foldHypergraphVertices(Hypergraph<V,E> h,
                                                     org.apache.commons.collections15.Factory<Graph<E,Collection<V>>> graph_factory)

Creates a Graph 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.

Parameters:

h - hypergraph to be folded

graph_factory - factory used to generate the output graph

Returns:

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