Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## 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 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.

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:
    `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.

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD