edu.uci.ics.jung.algorithms.blockmodel
Class GraphCollapser

java.lang.Object
  edu.uci.ics.jung.algorithms.blockmodel.GraphCollapser

Direct Known Subclasses:

BipartiteGraphCollapser

public class GraphCollapser

extends java.lang.Object

This is a skeleton class for collapsing graphs. In particular, it takes in a Graph g and a set of vertices to be collapsed into one, "rootset". It then returns a variant of the graph in which the root set has been merged into one vertex (of class CollapsedVertex). The user has the opportunity to override a number of these functions (thus, the need for instantiation only exists for overriding). There are several issues to be resolved:

• What sort of Collapsed vertex should be created? getCollapsedVertex(Set vertices)
• What userdata goes on the collapsed vertex? annotateVertex(Vertex collapsedVertex, Set original vertices)
• Should an edge be connected to a given vertex, given a set of vertices? protected boolean shouldAddEdge( Vertex opposite, Set rootSet, Collection edges)
• How do I add, or annotate, an edge from the super vertex to a given vertex? public void addDirectedEdges( Graph graph, Vertex superVertex, Vertex opposite, Set relevantEdges) protected void addUndirectedEdge(Vertex opposite, Vertex superVertex, Set relevantEdges) { protected boolean shouldAddEdge( Vertex opposite, Set rootSet, Collection edges) {

Author:

Danyel Fisher

Nested Class Summary

static interface	GraphCollapser.CollapsedEdge The CollapsedEdge interface represents a set of edges in some other graph.
static class	GraphCollapser.CollapsedSparseVertex A CollapsedSparseVertex extends CollapsedVertex.
static interface	GraphCollapser.CollapsedVertex This interface represents a vertex that holds a set of objects in some other graph.
static class	GraphCollapser.DirectedCollapsedEdge This class represents a Collapsed Directed edge, and extends DirectedSparseEdge.
static class	GraphCollapser.UndirectedCollapsedEdge This class represents a Collapsed Undirected edge, and extends UndirectedSparseEdge.

Method Summary

Graph	getCollapsedGraph(EquivalenceRelation equivalence) This version collects sets of vertices in an equivalence relation into a single CollapsedVertex.
Graph	getCollapsedGraph(Graph g, java.util.Set rootSet) This function collapses a series of vertices in one EquivalenceSet into one CollapsedVertex.
static GraphCollapser	getInstance()

Methods inherited from class java.lang.Object

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

Method Detail

getInstance

public static GraphCollapser getInstance()

getCollapsedGraph

public Graph getCollapsedGraph(EquivalenceRelation equivalence)

This version collects sets of vertices in an equivalence relation into a single CollapsedVertex.

Parameters:

equivalence - A properly-defined EquivalenceRelation representing DISJOINT sets of vertices from the Graph.

Returns:

a copy of the original graph where vertices are replaced by their collapsed equivalents

getCollapsedGraph

public Graph getCollapsedGraph(Graph g,
                               java.util.Set rootSet)

This function collapses a series of vertices in one EquivalenceSet into one CollapsedVertex.

Parameters:

g - A graph to collapse vertices from

rootSet - A set of vertice to collapse into one CollapsedVertex

Returns:

A graph with rootset.size()-1 fewer vertices.