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

java.lang.Object
  edu.uci.ics.jung.utils.UserData
      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, java.lang.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.utils.UserDataContainer

UserDataContainer.CopyAction

Field Summary

static java.lang.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.utils.UserData

CLONE, REMOVE, SHARED

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.
java.util.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()
void	removeVertex(Vertex v) Removes v from this graph.

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

getEdges, getVertices, isDirected, removeAllEdges, removeAllVertices, removeEdge, removeEdges, removeVertices

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

addListener, copy, getEdgeConstraints, getVertexConstraints, newInstance, numEdges, numVertices, removeListener, toString

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

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

Methods inherited from class java.lang.Object

equals, 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, 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 java.lang.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()

getAllVertices

public java.util.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