Package edu.uci.ics.jung.algorithms.blockmodel

Implementations of a notion of graph equivalence for blockmodeling, and a mechanism for collapsing blocks.

See:
          Description

Interface Summary
EquivalenceAlgorithm Any blockmodel equivalence algorithm should implement this method; it allows users to access EquivalenceAlgorithms more easily.
GraphCollapser.CollapsedEdge The CollapsedEdge interface represents a set of edges in some other graph.
GraphCollapser.CollapsedVertex This interface represents a vertex that holds a set of objects in some other graph.
 

Class Summary
BipartiteGraphCollapser A variant of the GraphCollapser that overrides two minor functions and defines CollapsedBipartiteEdge and CollapsedBipartiteVertex.
EquivalenceRelation An EquivalenceRelation holds a number of Equivalent vertices from the same graph.
GraphCollapser This is a skeleton class for collapsing graphs.
GraphCollapser.CollapsedSparseVertex A CollapsedSparseVertex extends CollapsedVertex.
GraphCollapser.DirectedCollapsedEdge This class represents a Collapsed Directed edge, and extends DirectedSparseEdge.
GraphCollapser.UndirectedCollapsedEdge This class represents a Collapsed Undirected edge, and extends UndirectedSparseEdge.
StructurallyEquivalent Checks a graph for sets of structurally equivalent vertices: vertices that share all the same edges.
StructurallyEquivalentII Checks a graph for sets of structurally equivalent vertices: vertices that share all the same edges.
 

Package edu.uci.ics.jung.algorithms.blockmodel Description

Implementations of a notion of graph equivalence for blockmodeling, and a mechanism for collapsing blocks.

The definition of "equivalence" used here is different from the equivalence functions defined between graphs. This equivalence refers to the network measure forms of equivalence used for blockmodeling. In blockmodeling, groups of vertices are clustered together by similarity (as if "blocked" together on the diagonal of a matrix).

This implementation provides:

EquivalenceAlgorithm
An interface for an algorithm that returns an EquivalenceRelation.
EquivalenceRelation
A class that represents several mutually-exclusive partitions of a set. The object is constructed with a Set of Sets; the members of each set are all vertices from the graph. The ER needn't cover all vertices; it contains a funtion called "getSingletons" that returns vertices that are not equivalent to any other vertex.
StructurallyEquivalent
An algorithm that finds sets of vertices that are structurally equivalent. In order for two vertices i and j to be structurally equivalent, the set of i's neighbors must be identical to the set of j's neighbors, with the exception of i and j themselves. (In those cases, a directed edge may join i to j only if another directed edge runs the other way.)
GraphCollapser
Runs through an EquivalenceRelation, replacing all the vertices in each set of the relation with one vertex of type GraphCollapser.CollapsedVertex. It also replaces all the edges from each vertex to the graph with a GraphCollapser.CollapsedEdge. (See the class documentation to see how this is done.)
BipartiteGraphCollapser
Extends the GraphCollapser to work for BipartiteGraphs.