public class GraphCollapser
extends java.lang.Object
getCollapsedVertex(Set vertices)
annotateVertex(Vertex collapsedVertex, Set original vertices)
protected boolean shouldAddEdge(
Vertex opposite,
Set rootSet,
Collection edges)
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) {
Modifier and Type | Class and Description |
---|---|
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.
|
Modifier and Type | Field and Description |
---|---|
protected static GraphCollapser |
instance |
Modifier | Constructor and Description |
---|---|
protected |
GraphCollapser() |
Modifier and Type | Method and Description |
---|---|
protected void |
annotateEdge(GraphCollapser.CollapsedEdge newEdge,
java.util.Collection edgesFromWhichWeMightDeriveData)
Overridable method annotates the new collapsed edge with userdata
from the original set.
|
protected void |
annotateVertex(GraphCollapser.CollapsedVertex superVertex,
java.util.Set rootSet)
Overridable method annotates the new collapsed vertex with userdata
from the rootset.
|
protected void |
collapseVerticesIntoSuperVertices(EquivalenceRelation er,
java.util.Map superVertices,
org.apache.commons.collections.MultiMap vertices_to_edges)
Internal method for collapsing a set of vertexes.
|
protected GraphCollapser.CollapsedVertex |
createCollapsedVertex(Graph g,
java.util.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,
java.util.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,
org.apache.commons.collections.MultiMap vertices_to_edges,
java.util.Set coveredCV)
INTERNAL METHOD
|
protected void |
createUndirectedEdge(Graph g,
GraphCollapser.CollapsedVertex superVertex,
Vertex opposite,
java.util.Set relevantEdges)
Overridable method to create a single undirected edge that represents the data in its parameters.
|
protected org.apache.commons.collections.MultiMap |
findEdgesAndVerticesConnectedToRootSet(java.util.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,
java.util.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,
java.util.Map superVertices)
INTERNAL (undocumented) method.
|
protected void |
replaceWith(org.apache.commons.collections.MultiMap m,
Vertex dest,
GraphCollapser.CollapsedVertex superV)
INTERNAL (undocumented) method
|
protected boolean |
shouldAddEdge(Vertex opposite,
java.util.Set rootSet,
java.util.Collection edges)
Overridable method checks whether an edge representing
the given set of edges should be created.
|
protected static GraphCollapser instance
public static GraphCollapser getInstance()
public Graph getCollapsedGraph(EquivalenceRelation equivalence)
equivalence
- A properly-defined EquivalenceRelation representing DISJOINT sets of vertices from the Graph.protected void createEdgesCorrespondingToMap(Graph copy, GraphCollapser.CollapsedVertex cv, org.apache.commons.collections.MultiMap vertices_to_edges, java.util.Set coveredCV)
protected void collapseVerticesIntoSuperVertices(EquivalenceRelation er, java.util.Map superVertices, org.apache.commons.collections.MultiMap vertices_to_edges)
er
- superVertices
- vertices_to_edges
- protected void replaceWith(org.apache.commons.collections.MultiMap m, Vertex dest, GraphCollapser.CollapsedVertex superV)
m
- dest
- superV
- protected void replaceEquivalencesWithCollapsedVertices(EquivalenceRelation er, Graph copy, java.util.Map superVertices)
er
- copy
- superVertices
- public Graph getCollapsedGraph(Graph g, java.util.Set rootSet)
g
- A graph to collapse vertices fromrootSet
- A set of vertice to collapse into one CollapsedVertexprotected void annotateVertex(GraphCollapser.CollapsedVertex superVertex, java.util.Set rootSet)
superVertex
- a new CollapsedVertexrootSet
- a set of Vertexes from the old graph.protected void annotateEdge(GraphCollapser.CollapsedEdge newEdge, java.util.Collection edgesFromWhichWeMightDeriveData)
newEdge
- a new CollapsedEdgeedgesFromWhichWeMightDeriveData
- protected GraphCollapser.CollapsedVertex createCollapsedVertex(Graph g, java.util.Set rootSet)
g
- The input graphrootSet
- The set of vertices which should be represented by the
new vertex.protected void createUndirectedEdge(Graph g, GraphCollapser.CollapsedVertex superVertex, Vertex opposite, java.util.Set relevantEdges)
g
- The graph in which this edge should be addedopposite
- The vertex at the far end of this edgesuperVertex
- 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.protected void createDirectedEdges(Graph graph, GraphCollapser.CollapsedVertex superVertex, Vertex opposite, java.util.Set relevantEdges)
g
- The graph in which this edge should be addedopposite
- The vertex at the far end of this edgesuperVertex
- 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.protected org.apache.commons.collections.MultiMap findEdgesAndVerticesConnectedToRootSet(java.util.Set rootSet)
rootSet
- protected boolean shouldAddEdge(Vertex opposite, java.util.Set rootSet, java.util.Collection edges)
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