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

java.lang.Object
  extended by edu.uci.ics.jung.algorithms.blockmodel.GraphCollapser
Direct Known Subclasses:
BipartiteGraphCollapser

public class GraphCollapser
extends 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:

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.
 
Field Summary
protected static GraphCollapser instance
           
 
Constructor Summary
protected GraphCollapser()
           
 
Method Summary
protected  void annotateEdge(GraphCollapser.CollapsedEdge newEdge, Collection edgesFromWhichWeMightDeriveData)
          Overridable method annotates the new collapsed edge with userdata from the original set.
protected  void annotateVertex(GraphCollapser.CollapsedVertex superVertex, Set rootSet)
          Overridable method annotates the new collapsed vertex with userdata from the rootset.
protected  void collapseVerticesIntoSuperVertices(EquivalenceRelation er, Map superVertices, MultiMap vertices_to_edges)
          Internal method for collapsing a set of vertexes.
protected  GraphCollapser.CollapsedVertex createCollapsedVertex(Graph g, Set rootSet)
          Overridable method to create a single vertex representing a set of vertices in the graph.
protected  void createDirectedEdges(Graph graph, GraphCollapser.CollapsedVertex superVertex, Vertex opposite, Set relevantEdges)
          Overridable method to create a up to two directed edges that represents the data in its parameters.
protected  void createEdgesCorrespondingToMap(Graph copy, GraphCollapser.CollapsedVertex cv, MultiMap vertices_to_edges, Set coveredCV)
          INTERNAL METHOD
protected  void createUndirectedEdge(Graph g, GraphCollapser.CollapsedVertex superVertex, Vertex opposite, Set relevantEdges)
          Overridable method to create a single undirected edge that represents the data in its parameters.
protected  MultiMap findEdgesAndVerticesConnectedToRootSet(Set rootSet)
          INTERNAL METHOD.
 Graph getCollapsedGraph(EquivalenceRelation equivalence)
          This version collects sets of vertices in an equivalence relation into a single CollapsedVertex.
 Graph getCollapsedGraph(Graph g, Set rootSet)
          This function collapses a series of vertices in one EquivalenceSet into one CollapsedVertex.
static GraphCollapser getInstance()
           
protected  void replaceEquivalencesWithCollapsedVertices(EquivalenceRelation er, Graph copy, Map superVertices)
          INTERNAL (undocumented) method.
protected  void replaceWith(MultiMap m, Vertex dest, GraphCollapser.CollapsedVertex superV)
          INTERNAL (undocumented) method
protected  boolean shouldAddEdge(Vertex opposite, Set rootSet, Collection edges)
          Overridable method checks whether an edge representing the given set of edges should be created.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

instance

protected static GraphCollapser instance
Constructor Detail

GraphCollapser

protected GraphCollapser()
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

createEdgesCorrespondingToMap

protected void createEdgesCorrespondingToMap(Graph copy,
                                             GraphCollapser.CollapsedVertex cv,
                                             MultiMap vertices_to_edges,
                                             Set coveredCV)
INTERNAL METHOD


collapseVerticesIntoSuperVertices

protected void collapseVerticesIntoSuperVertices(EquivalenceRelation er,
                                                 Map superVertices,
                                                 MultiMap vertices_to_edges)
Internal method for collapsing a set of vertexes.

Parameters:
er -
superVertices -
vertices_to_edges -

replaceWith

protected void replaceWith(MultiMap m,
                           Vertex dest,
                           GraphCollapser.CollapsedVertex superV)
INTERNAL (undocumented) method

Parameters:
m -
dest -
superV -

replaceEquivalencesWithCollapsedVertices

protected void replaceEquivalencesWithCollapsedVertices(EquivalenceRelation er,
                                                        Graph copy,
                                                        Map superVertices)
INTERNAL (undocumented) method.

Parameters:
er -
copy -
superVertices -

getCollapsedGraph

public Graph getCollapsedGraph(Graph g,
                               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.

annotateVertex

protected void annotateVertex(GraphCollapser.CollapsedVertex superVertex,
                              Set rootSet)
Overridable method annotates the new collapsed vertex with userdata from the rootset. By default, does nothing.

Parameters:
superVertex - a new CollapsedVertex
rootSet - a set of Vertexes from the old graph.

annotateEdge

protected void annotateEdge(GraphCollapser.CollapsedEdge newEdge,
                            Collection edgesFromWhichWeMightDeriveData)
Overridable method annotates the new collapsed edge with userdata from the original set. By default, does nothing.

Parameters:
newEdge - a new CollapsedEdge
edgesFromWhichWeMightDeriveData -

createCollapsedVertex

protected GraphCollapser.CollapsedVertex createCollapsedVertex(Graph g,
                                                               Set rootSet)
Overridable method to create a single vertex representing a set of vertices in the graph.

Parameters:
g - The input graph
rootSet - The set of vertices which should be represented by the new vertex.
Returns:
a new CollapsedVertex

createUndirectedEdge

protected void createUndirectedEdge(Graph g,
                                    GraphCollapser.CollapsedVertex superVertex,
                                    Vertex opposite,
                                    Set relevantEdges)
Overridable method to create a single undirected edge that represents the data in its parameters. Should call annotateEdge with the new edge.

Parameters:
g - The graph in which this edge should be added
opposite - The vertex at the far end of this edge
superVertex - The vertex at the near end of this edge. (For an undirecte graph, it doesn't really matter).
relevantEdges - The set of edges that this edge is meant to represent.

createDirectedEdges

protected void createDirectedEdges(Graph graph,
                                   GraphCollapser.CollapsedVertex superVertex,
                                   Vertex opposite,
                                   Set relevantEdges)
Overridable method to create a up to two directed edges that represents the data in its parameters. This method, by default, creates one edge in each direction that there is an edge in relevantEdges. Should call annotateEdge with the new edge.

Parameters:
g - The graph in which this edge should be added
opposite - The vertex at the far end of this edge
superVertex - The vertex at the near end of this edge. (For an undirecte graph, it doesn't really matter).
relevantEdges - The set of edges that this edge is meant to represent.

findEdgesAndVerticesConnectedToRootSet

protected MultiMap findEdgesAndVerticesConnectedToRootSet(Set rootSet)
INTERNAL METHOD. For a set of vertices, finds all the edges connected to them, indexed (in a MultiMap) to the vertices to which they connect. Thus, in the graph with edges (A-C, A-D, B-C), with input (A, B), the result will be ( C {A-C, B-C}; D {A-D} )

Parameters:
rootSet -
Returns:

shouldAddEdge

protected boolean shouldAddEdge(Vertex opposite,
                                Set rootSet,
                                Collection edges)
Overridable method checks whether an edge representing the given set of edges should be created. The edge will run from a new CollapsedVertex representing the rootSet to opposite; it will replace all the edges in the collection edges. By default, this method returns true.

Parameters:
opposite -
rootSet - a set of vertices that currently are one end of these edges.
edges - a non-empty collection of edges that may be replaced
Returns:
a boolean value. If true, the system will replace these edges with one new collapsededge; if false, the system will remove all these edges from the graph.