edu.uci.ics.jung.graph.impl
Class BipartiteGraph

java.lang.Object
  edu.uci.ics.jung.utils.UserDataDelegate
      edu.uci.ics.jung.graph.impl.AbstractArchetypeGraph
          edu.uci.ics.jung.graph.impl.AbstractSparseGraph
              edu.uci.ics.jung.graph.impl.SparseGraph
                  edu.uci.ics.jung.graph.impl.UndirectedSparseGraph
                      edu.uci.ics.jung.graph.impl.BipartiteGraph

All Implemented Interfaces:

ArchetypeGraph, Cloneable, Graph, UndirectedGraph, UserDataContainer

public class BipartiteGraph

extends UndirectedSparseGraph

A Bipartite graph is divided into A vertices and B vertices. Edges only connect A vertices to B vertices, and vice versa. This class extends UndirectedSparseGraph; thus, the Graph is made up of UndirectedSparseVertices.

Vertices can only be added to the graph with a flag that says which class they will be added to (using BipartiteGraph.Choice ); edges must be of type BipartiteGraph, which must consist of two vertices, one each from CLASSA and CLASSB.

 BipartiteGraph bpg = new BipartiteGraph;
 Vertex va = bpg.addVertex( new UndirectedSparseVertex(), BipartiteGraph.CLASSA );
 Vertex vb = bpg.addVertex( new UndirectedSparseVertex(), BipartiteGraph.CLASSB );
 bpg.addBipartiteEdge( new BipartiteEdge( va, vb ));
 

Note that the traditional addVertex() and addEdge() will both throw a FatalException.

The function fold creates an UndirectedGraph based on finding vertices that share a common neighbor.

Since:

1.0.1

Author:

danyelf

Nested Class Summary

static class

BipartiteGraph.Choice This small enumerated type merely forces a user to pick class "A" or "B" when adding a Vertex to a BipartiteGraph.

Nested classes inherited from class edu.uci.ics.jung.graph.impl.AbstractArchetypeGraph

AbstractArchetypeGraph.Requirements

Nested classes inherited from class edu.uci.ics.jung.utils.UserDataContainer

UserDataContainer.CopyAction

Field Summary

static Object	BIPARTITE_USER_TAG The tag for the UserData attached to a single Edge.
static BipartiteGraph.Choice	CLASSA
static BipartiteGraph.Choice	CLASSB

Fields inherited from class edu.uci.ics.jung.graph.impl.AbstractSparseGraph

mEdges, mVertices

Fields inherited from class edu.uci.ics.jung.graph.impl.AbstractArchetypeGraph

edge_requirements, mEdgeIDs, mGraphListenerHandler, mVertexIDs, vertex_requirements

Fields inherited from class edu.uci.ics.jung.utils.UserDataDelegate

factory, udc_delegate

Fields inherited from interface edu.uci.ics.jung.graph.Graph

DIRECTED_EDGE, NOT_PARALLEL_EDGE, SIMPLE_EDGE, UNDIRECTED_EDGE

Fields inherited from interface edu.uci.ics.jung.graph.ArchetypeGraph

SUBSET_MANAGER

Constructor Summary

BipartiteGraph()

Method Summary

BipartiteEdge	addBipartiteEdge(BipartiteEdge bpe) Adds a BipartiteEdge to the Graph.
Edge	addEdge(Edge ae) Deprecated. Use addBipartiteEdge
BipartiteVertex	addVertex(BipartiteVertex v, BipartiteGraph.Choice choice) Adds a single vertex to the graph in the specified partition.
Vertex	addVertex(Vertex av) Deprecated. Use addBipartiteVertex
static Graph	fold(BipartiteGraph bpg, BipartiteGraph.Choice vertexSet) Creates a one-part graph from a bipartite graph by folding Vertices from one class into a second class.
Set	getAllVertices(BipartiteGraph.Choice choice) Returns the set of all vertices from that class.
BipartiteGraph.Choice	getPartition(BipartiteVertex v) Returns the partition for vertex v.
void	initialize() Initializes all of the graph's internal data structures.
void	removeVertex(Vertex v) Removes v from this graph.

Methods inherited from class edu.uci.ics.jung.graph.impl.AbstractSparseGraph

getEdges, getVertices, isDirected, removeEdge, removeEdges, removeVertices

Methods inherited from class edu.uci.ics.jung.graph.impl.AbstractArchetypeGraph

addAllNotInitializers, addListener, checkConstraints, copy, getEdgeConstraints, getVertexConstraints, listenersExist, newInstance, numEdges, numVertices, removeAllEdges, removeAllVertices, removeListener, toString

Methods inherited from class edu.uci.ics.jung.utils.UserDataDelegate

addUserDatum, clone, containsUserDatumKey, getUserDatum, getUserDatumCopyAction, getUserDatumKeyIterator, importUserData, removeUserDatum, setUserDataFactory, setUserDatum

Methods inherited from class java.lang.Object

equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface edu.uci.ics.jung.graph.Graph

isDirected, removeEdge

Methods inherited from interface edu.uci.ics.jung.graph.ArchetypeGraph

addListener, copy, getEdgeConstraints, getEdges, getVertexConstraints, getVertices, newInstance, numEdges, numVertices, removeAllEdges, removeAllVertices, removeEdges, removeListener, removeVertices

Methods inherited from interface edu.uci.ics.jung.utils.UserDataContainer

addUserDatum, clone, containsUserDatumKey, getUserDatum, getUserDatumCopyAction, getUserDatumKeyIterator, importUserData, removeUserDatum, setUserDatum

Field Detail

CLASSA

public static final BipartiteGraph.Choice CLASSA

CLASSB

public static final BipartiteGraph.Choice CLASSB

BIPARTITE_USER_TAG

public static final Object BIPARTITE_USER_TAG

The tag for the UserData attached to a single Edge.

Constructor Detail

BipartiteGraph

public BipartiteGraph()

Method Detail

initialize

public void initialize()

Description copied from class: AbstractArchetypeGraph

Initializes all of the graph's internal data structures. Should always be called by any mechanism that creates a new instance of AbstractSparseGraph (for example, constructors and implementations of newInstance()). If you add predicates here, please set their isInitializeFlag to TRUE.

Note: this method is not a substitute for removeAllVertices(), as it will not notify the vertices and edges that they have been removed from the graph.

Overrides:

initialize in class AbstractSparseGraph

getAllVertices

public Set getAllVertices(BipartiteGraph.Choice choice)

Returns the set of all vertices from that class. All vertices in the return set will be of class A or class B, depending on the parameter.

getPartition

public BipartiteGraph.Choice getPartition(BipartiteVertex v)

Returns the partition for vertex v.

Parameters:

v -

addVertex

public BipartiteVertex addVertex(BipartiteVertex v,
                                 BipartiteGraph.Choice choice)

Adds a single vertex to the graph in the specified partition. Note that the vertex must be compatible with BipartiteVertex.

Throws an IllegalArgumentException if v is not an element of either partition.

Parameters:

v - the vertex to be added to the class

choice - the class to which the vertex should be added

Returns:

the input vertex

addBipartiteEdge

public BipartiteEdge addBipartiteEdge(BipartiteEdge bpe)

Adds a BipartiteEdge to the Graph. This function is simply a typed version of addEdge

Parameters:

bpe - a BipartiteEdge

Returns:

the edge, now a member of the graph.

addEdge

public Edge addEdge(Edge ae)

Deprecated. Use addBipartiteEdge

DO NOT USE THIS METHOD. Contractually required, but merely throws a FatalException.

Specified by:

addEdge in interface Graph

Overrides:

addEdge in class AbstractSparseGraph

See Also:

AbstractSparseGraph.addEdge(edu.uci.ics.jung.graph.Edge)

addVertex

public Vertex addVertex(Vertex av)

Deprecated. Use addBipartiteVertex

DO NOT USE THIS METHOD. Contractually required, but merely throws a FatalException.

Specified by:

addVertex in interface Graph

Overrides:

addVertex in class AbstractSparseGraph

See Also:

AbstractSparseGraph.addVertex(edu.uci.ics.jung.graph.Vertex)

fold

public static Graph fold(BipartiteGraph bpg,
                         BipartiteGraph.Choice vertexSet)

Creates a one-part graph from a bipartite graph by folding Vertices from one class into a second class. This function creates a new UndirectedGraph (with vertex set V') in which:

• each vertex in V' has an equivalent V in bpg.getAllVertices( class )
• an edge E' joins V'1 and V'2 iff there is a path of length 2 from V1 to V2 (by way of some third vertex in the other class, VXs)
• each edge E' is annotated with the set of vertices VXs

In social network analysis and related fields, this operation transforms an actor-by-event chart into an actor-by-actor chart.

Parameters:

bpg - The bipartite graph to be folded

vertexSet - Chooses the set of vertices to be brought into the new Graph.

Returns:

an UndirectedSparseGraph.

removeVertex

public void removeVertex(Vertex v)

Description copied from interface: Graph

Removes v from this graph. Any edges incident to v which become ill-formed (as defined in the documentation for ArchetypeEdge) as a result of removing v are also removed from this graph. Throws IllegalArgumentException if v is not in this graph.

Specified by:

removeVertex in interface Graph

Overrides:

removeVertex in class AbstractSparseGraph