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

java.lang.Object
  edu.uci.ics.jung.utils.UserData
      edu.uci.ics.jung.graph.impl.AbstractSparseVertex
          edu.uci.ics.jung.graph.impl.SimpleSparseVertex
              edu.uci.ics.jung.graph.impl.SparseVertex

All Implemented Interfaces:

ArchetypeVertex, java.lang.Cloneable, UserDataContainer, Vertex

Direct Known Subclasses:

BipartiteVertex, GraphCollapser.CollapsedSparseVertex

public class SparseVertex

extends SimpleSparseVertex

An implementation of Vertex that resides in a sparse graph which may contain directed and/or undirected edges, as well as parallel edges.

This implementation stores hash tables that map the successors of this vertex to its outgoing edges, and its predecessors to its incoming edges. This enables an efficient implementation of findEdge(Vertex), but causes the routines that return the sets of neighbors and of incident edges to require time proportional to the number of neighbors.

Author:

Joshua O'Madadhain, Scott White, Danyel Fisher

See Also:

SparseGraph

Nested Class Summary

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

UserDataContainer.CopyAction

Field Summary

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

CLONE, REMOVE, SHARED

Constructor Summary

SparseVertex()
Creates a new instance of a vertex for inclusion in a sparse graph.

Method Summary

Edge	findEdge(Vertex v) Returns the edge that connects this vertex to the specified vertex v, or null if there is no such edge.
java.util.Set	findEdgeSet(Vertex v) Returns the set of all edges that connect this vertex with the specified vertex v.
java.util.Set	getInEdges() Returns the set of incoming edges of this vertex.
java.util.Set	getOutEdges() Returns the set of outgoing edges of this vertex.

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

getPredecessors, getSuccessors, inDegree, isDest, isPredecessorOf, isSource, isSuccessorOf, numPredecessors, numSuccessors, outDegree

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

copy, degree, equals, getEqualVertex, getEquivalentVertex, getGraph, getIncidentEdges, getNeighbors, hashCode, isIncident, isNeighborOf, numNeighbors, 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

getClass, notify, notifyAll, wait, wait, wait

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

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

Constructor Detail

SparseVertex

public SparseVertex()

Creates a new instance of a vertex for inclusion in a sparse graph.

Method Detail

getInEdges

public java.util.Set getInEdges()

Description copied from interface: Vertex

Returns the set of incoming edges of this vertex. An edge e is an incoming edge of this vertex if and only if this.isDest(e) returns true. Each element of the set returned should implement Edge.

Specified by:

getInEdges in interface Vertex

Overrides:

getInEdges in class SimpleSparseVertex

See Also:

Vertex.getInEdges()

getOutEdges

public java.util.Set getOutEdges()

Description copied from interface: Vertex

Returns the set of outgoing edges of this vertex. An edge e is an outgoing edge of this vertex if and only if this.isSource(e) returns true. Each element of the set returned should implement Edge.

Specified by:

getOutEdges in interface Vertex

Overrides:

getOutEdges in class SimpleSparseVertex

See Also:

Vertex.getOutEdges()

findEdge

public Edge findEdge(Vertex v)

Returns the edge that connects this vertex to the specified vertex v, or null if there is no such edge. Implemented using a hash table for a performance improvement over the implementation in AbstractSparseVertex. Looks for a directed edge first, and then for an undirected edge if no directed edges are found.

Specified by:

findEdge in interface Vertex

Overrides:

findEdge in class SimpleSparseVertex

See Also:

Vertex.findEdge(Vertex)

findEdgeSet

public java.util.Set findEdgeSet(Vertex v)

Description copied from interface: Vertex

Returns the set of all edges that connect this vertex with the specified vertex v. If v is not connected to this vertex, returns an empty Set.

Specified by:

findEdgeSet in interface Vertex

Overrides:

findEdgeSet in class SimpleSparseVertex

See Also:

Vertex.findEdgeSet(Vertex)