/*
* Copyright (c) 2003, The JUNG Authors
*
* All rights reserved.
*
* This software is open-source under the BSD license; see either
* "license.txt" or
* https://github.com/jrtom/jung/blob/master/LICENSE for a description.
*/
/*
* Created on Apr 21, 2004
*/
package edu.uci.ics.jung.algorithms.transformation;
import java.util.ArrayList;
import java.util.Collection;
import com.google.common.base.Predicate;
import com.google.common.base.Supplier;
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 FoldingTransformer
{
/**
* 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.
*
* @param vertex type
* @param input edge type
* @param g input k-partite graph
* @param p predicate specifying vertex partition
* @param graph_factory Supplier used to create the output graph
* @param edge_factory Supplier used to create the edges in the new graph
* @return a copy of the input graph folded with respect to the input partition
*/
public static Graph foldKPartiteGraph(KPartiteGraph g, Predicate p,
Supplier> graph_factory, Supplier edge_factory)
{
Graph newGraph = graph_factory.get();
// get vertices for the specified partition
Collection vertices = g.getVertices(p);
for (V v : vertices)
{
newGraph.addVertex(v);
for (V s : g.getSuccessors(v))
{
for (V t : g.getSuccessors(s))
{
if (!vertices.contains(t) || t.equals(v))
continue;
newGraph.addVertex(t);
newGraph.addEdge(edge_factory.get(), v, t);
}
}
}
return newGraph;
}
/**
* 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.
*
* @param vertex type
* @param input edge type
* @param g input k-partite graph
* @param p predicate specifying vertex partition
* @param graph_factory Supplier used to create the output graph
* @return the result of folding g into unipartite graph whose vertices
* are those of the p partition of g
*/
public static Graph> foldKPartiteGraph(KPartiteGraph g, Predicate p,
Supplier>> graph_factory)
{
Graph> newGraph = graph_factory.get();
// get vertices for the specified partition, copy into new graph
Collection vertices = g.getVertices(p);
for (V v : vertices)
{
newGraph.addVertex(v);
for (V s : g.getSuccessors(v))
{
for (V t : g.getSuccessors(s))
{
if (!vertices.contains(t) || t.equals(v))
continue;
newGraph.addVertex(t);
Collection v_coll = newGraph.findEdge(v, t);
if (v_coll == null)
{
v_coll = new ArrayList();
newGraph.addEdge(v_coll, v, t);
}
v_coll.add(s);
}
}
}
return newGraph;
}
/**
* 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.
*
* @param vertex type
* @param input edge type
* @param h hypergraph to be folded
* @param graph_factory Supplier used to generate the output graph
* @return a copy of the input graph where hyperedges are replaced by cliques
*/
public static Graph> foldHypergraphEdges(Hypergraph h,
Supplier>> graph_factory)
{
Graph> target = graph_factory.get();
for (V v : h.getVertices())
target.addVertex(v);
for (E e : h.getEdges())
{
ArrayList incident = new ArrayList(h.getIncidentVertices(e));
populateTarget(target, e, incident);
}
return target;
}
/**
* 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 Supplier.
*
* @param vertex type
* @param input edge type
* @param h hypergraph to be folded
* @param graph_factory Supplier used to generate the output graph
* @param edge_factory Supplier used to create the new edges
* @return a copy of the input graph where hyperedges are replaced by cliques
*/
public static Graph foldHypergraphEdges(Hypergraph h,
Supplier> graph_factory, Supplier edge_factory)
{
Graph target = graph_factory.get();
for (V v : h.getVertices())
target.addVertex(v);
for (E e : h.getEdges())
{
ArrayList incident = new ArrayList(h.getIncidentVertices(e));
for (int i = 0; i < incident.size(); i++)
for (int j = i+1; j < incident.size(); j++)
target.addEdge(edge_factory.get(), incident.get(i), incident.get(j));
}
return target;
}
/**
* 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 Supplier.
*
* @param vertex type
* @param input edge type
* @param output edge type
* @param h hypergraph to be folded
* @param graph_factory Supplier used to generate the output graph
* @param edge_factory Supplier used to generate the output edges
* @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 static Graph foldHypergraphVertices(Hypergraph h,
Supplier> graph_factory, Supplier edge_factory)
{
Graph target = graph_factory.get();
for (E e : h.getEdges())
target.addVertex(e);
for (V v : h.getVertices())
{
ArrayList incident = new ArrayList(h.getIncidentEdges(v));
for (int i = 0; i < incident.size(); i++)
for (int j = i+1; j < incident.size(); j++)
target.addEdge(edge_factory.get(), incident.get(i), incident.get(j));
}
return target;
}
/**
* 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.
*
* @param h hypergraph to be folded
* @param graph_factory Supplier 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> foldHypergraphVertices(Hypergraph h,
Supplier>> graph_factory)
{
Graph> target = graph_factory.get();
for (E e : h.getEdges())
target.addVertex(e);
for (V v : h.getVertices())
{
ArrayList incident = new ArrayList(h.getIncidentEdges(v));
populateTarget(target, v, incident);
}
return target;
}
/**
* @param target
* @param e
* @param incident
*/
private static void populateTarget(Graph> target, T e,
ArrayList incident)
{
for (int i = 0; i < incident.size(); i++)
{
S v1 = incident.get(i);
for (int j = i+1; j < incident.size(); j++)
{
S v2 = incident.get(j);
Collection e_coll = target.findEdge(v1, v2);
if (e_coll == null)
{
e_coll = new ArrayList();
target.addEdge(e_coll, v1, v2);
}
e_coll.add(e);
}
}
}
}
Ads help maintain this website.