Class FoldingTransformer<V,E>
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.
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionstatic <V,
E> Graph <V, E> foldHypergraphEdges
(Hypergraph<V, E> h, com.google.common.base.Supplier<Graph<V, E>> graph_factory, com.google.common.base.Supplier<E> edge_factory) Creates aGraph
which is an edge-folded version ofh
, where hyperedges are replaced by k-cliques in the output graph.static <V,
E> Graph <V, Collection<E>> foldHypergraphEdges
(Hypergraph<V, E> h, com.google.common.base.Supplier<Graph<V, Collection<E>>> graph_factory) Creates aGraph
which is an edge-folded version ofh
, where hyperedges are replaced by k-cliques in the output graph.static <V,
E, F> Graph <E, F> foldHypergraphVertices
(Hypergraph<V, E> h, com.google.common.base.Supplier<Graph<E, F>> graph_factory, com.google.common.base.Supplier<F> edge_factory) Creates aGraph
which is a vertex-folded version ofh
, whose vertices are the input's hyperedges and whose edges are induced by adjacent hyperedges in the input.Graph
<E, Collection<V>> foldHypergraphVertices
(Hypergraph<V, E> h, com.google.common.base.Supplier<Graph<E, Collection<V>>> graph_factory) Creates aGraph
which is a vertex-folded version ofh
, whose vertices are the input's hyperedges and whose edges are induced by adjacent hyperedges in the input.static <V,
E> Graph <V, E> foldKPartiteGraph
(KPartiteGraph<V, E> g, com.google.common.base.Predicate<V> p, com.google.common.base.Supplier<Graph<V, E>> graph_factory, com.google.common.base.Supplier<E> edge_factory) Convertsg
into a unipartite graph whose vertex set is the vertices ofg
's partitionp
.static <V,
E> Graph <V, Collection<V>> foldKPartiteGraph
(KPartiteGraph<V, E> g, com.google.common.base.Predicate<V> p, com.google.common.base.Supplier<Graph<V, Collection<V>>> graph_factory) Convertsg
into a unipartite graph whose vertices are the vertices ofg
's partitionp
, and whose edges consist of collections of the intermediate vertices from other partitions.private static <S,
T> void populateTarget
(Graph<S, Collection<T>> target, T e, ArrayList<S> incident)
-
Constructor Details
-
FoldingTransformer
public FoldingTransformer()
-
-
Method Details
-
foldKPartiteGraph
public static <V,E> Graph<V,E> foldKPartiteGraph(KPartiteGraph<V, E> g, com.google.common.base.Predicate<V> p, com.google.common.base.Supplier<Graph<V, E>> graph_factory, com.google.common.base.Supplier<E> edge_factory) Convertsg
into a unipartite graph whose vertex set is the vertices ofg
's partitionp
. For verticesa
andb
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 vertexc
.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 typeE
- input edge type- Parameters:
g
- input k-partite graphp
- predicate specifying vertex partitiongraph_factory
- Supplier used to create the output graphedge_factory
- Supplier 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, com.google.common.base.Predicate<V> p, com.google.common.base.Supplier<Graph<V, Collection<V>>> graph_factory) Convertsg
into a unipartite graph whose vertices are the vertices ofg
's partitionp
, and whose edges consist of collections of the intermediate vertices from other partitions. For verticesa
andb
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 vertexc
.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 typeE
- input edge type- Parameters:
g
- input k-partite graphp
- predicate specifying vertex partitiongraph_factory
- Supplier 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, com.google.common.base.Supplier<Graph<V, Collection<E>>> graph_factory) Creates aGraph
which is an edge-folded version ofh
, 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
, anda
is connected tob
in the new graph if the corresponding vertices inh
are connected by a hyperedge. Thus, each hyperedge with k vertices inh
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 typeE
- input edge type- Parameters:
h
- hypergraph to be foldedgraph_factory
- Supplier 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, com.google.common.base.Supplier<Graph<V, E>> graph_factory, com.google.common.base.Supplier<E> edge_factory) Creates aGraph
which is an edge-folded version ofh
, 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
, anda
is connected tob
in the new graph if the corresponding vertices inh
are connected by a hyperedge. Thus, each hyperedge with k vertices inh
induces a k-clique in the new graph.The edges of the new graph are generated by the specified edge Supplier.
- Type Parameters:
V
- vertex typeE
- input edge type- Parameters:
h
- hypergraph to be foldedgraph_factory
- Supplier used to generate the output graphedge_factory
- Supplier used to create the new edges- Returns:
- a copy of the input graph where hyperedges are replaced by cliques
-
foldHypergraphVertices
public static <V,E, Graph<E,F> F> foldHypergraphVertices(Hypergraph<V, E> h, com.google.common.base.Supplier<Graph<E, F>> graph_factory, com.google.common.base.Supplier<F> edge_factory) Creates aGraph
which is a vertex-folded version ofh
, 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
, anda
is connected tob
in the new graph if the corresponding edges inh
have a vertex in common. Thus, each vertex incident to k edges inh
induces a k-clique in the new graph.The edges of the new graph are created by the specified Supplier.
- Type Parameters:
V
- vertex typeE
- input edge typeF
- output edge type- Parameters:
h
- hypergraph to be foldedgraph_factory
- Supplier used to generate the output graphedge_factory
- Supplier 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, com.google.common.base.Supplier<Graph<E, Collection<V>>> graph_factory) Creates aGraph
which is a vertex-folded version ofh
, 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
, anda
is connected tob
in the new graph if the corresponding edges inh
have a vertex in common. Thus, each vertex incident to k edges inh
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 foldedgraph_factory
- Supplier 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
-
populateTarget
private static <S,T> void populateTarget(Graph<S, Collection<T>> target, T e, ArrayList<S> incident) - Parameters:
target
-e
-incident
-
-