/*
 * 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.