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

Interface	Description
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

Class	Description
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.