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

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

All Implemented Interfaces:

ArchetypeVertex, java.lang.Cloneable, UserDataContainer, Vertex

Direct Known Subclasses:

SparseVertex

public class SimpleSparseVertex

extends AbstractSparseVertex

An implementation of Vertex that resides in a sparse graph which may contain both directed and undirected edges. It does not support 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

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

SimpleSparseVertex()
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.
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.
java.util.Set	getPredecessors() Returns the set of predecessors of this vertex.
java.util.Set	getSuccessors() Returns the set of successors of this vertex.
int	inDegree() Returns the number of incoming edges that are incident to this vertex.
boolean	isDest(Edge e) Returns true if this vertex is a destination of the specified edge e, and false otherwise.
boolean	isPredecessorOf(Vertex v) Returns true if this vertex is a predecessor of the specified vertex v, and false otherwise.
boolean	isSource(Edge e) Returns true if this vertex is a source of the specified edge e, and false otherwise.
boolean	isSuccessorOf(Vertex v) Returns true if this vertex is a successor of the specified vertex v, and false otherwise.
int	numPredecessors() Returns the number of predecessors of this vertex.
int	numSuccessors() Returns the number of successors of this vertex.
int	outDegree() Returns the number of outgoing edges that are incident to this vertex.

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

SimpleSparseVertex

public SimpleSparseVertex()

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

Method Detail

getPredecessors

public java.util.Set getPredecessors()

Description copied from interface: Vertex

Returns the set of predecessors of this vertex. A vertex v is a predecessor of this vertex if and only if v.isPredecessorOf(this) returns true. Each element of the set returned should implement Vertex.

Returns:

all predecessors of this vertex

See Also:

Vertex.getPredecessors()

getSuccessors

public java.util.Set getSuccessors()

Description copied from interface: Vertex

Returns the set of successors of this vertex. A vertex v is a successor of this vertex if and only if v.isSuccessorOf(this) returns true. Each element of the set returned should implement Vertex.

Returns:

all successors of this vertex

See Also:

Vertex.getSuccessors()

inDegree

public int inDegree()

Description copied from interface: Vertex

Returns the number of incoming edges that are incident to this vertex.

Returns:

the number of incoming edges of this vertex

See Also:

Vertex.inDegree()

outDegree

public int outDegree()

Description copied from interface: Vertex

Returns the number of outgoing edges that are incident to this vertex.

Returns:

the number of outgoing edges of this vertex

See Also:

Vertex.outDegree()

numPredecessors

public int numPredecessors()

Description copied from interface: Vertex

Returns the number of predecessors of this vertex.

See Also:

Vertex.numPredecessors()

numSuccessors

public int numSuccessors()

Description copied from interface: Vertex

Returns the number of successors of this vertex.

See Also:

Vertex.numSuccessors()

isSuccessorOf

public boolean isSuccessorOf(Vertex v)

Description copied from interface: Vertex

Returns true if this vertex is a successor of the specified vertex v, and false otherwise. This vertex is a successor of v if and only if there exists an edge e such that v.isSource(e) == true and this.isDest(e) == true. The behavior of this method is undefined if v is not an element of this vertex's graph.

See Also:

Vertex.isSuccessorOf(Vertex)

isPredecessorOf

public boolean isPredecessorOf(Vertex v)

Description copied from interface: Vertex

Returns true if this vertex is a predecessor of the specified vertex v, and false otherwise. This vertex is a predecessor of v if and only if there exists an edge e such that this.isSource(e) == true and v.isDest(e) == true. The behavior of this method is undefined if v is not an element of this vertex's graph.

See Also:

Vertex.isPredecessorOf(Vertex)

isSource

public boolean isSource(Edge e)

Description copied from interface: Vertex

Returns true if this vertex is a source of the specified edge e, and false otherwise. A vertex v is a source of e if e is an outgoing edge of v. The behavior of this method is undefined if e is not an element of this vertex's graph.

See Also:

Vertex.isSource(Edge)

isDest

public boolean isDest(Edge e)

Description copied from interface: Vertex

Returns true if this vertex is a destination of the specified edge e, and false otherwise. A vertex v is a destination of e if e is an incoming edge of v. The behavior of this method is undefined if e is not an element of this vertex's graph.

See Also:

Vertex.isDest(Edge)

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.

Returns:

all edges whose destination is this vertex

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.

Returns:

all edges whose source is this vertex

See Also:

Vertex.getOutEdges()

findEdge

public Edge findEdge(Vertex v)

Description copied from class: AbstractSparseVertex

Returns the edge that connects this vertex to the specified vertex v. This is a simple implementation which checks the opposite vertex of each outgoing edge of this vertex; this solution is general, but not efficient.

Specified by:

findEdge in interface Vertex

Overrides:

findEdge in class AbstractSparseVertex

See Also:

AbstractSparseVertex.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 AbstractSparseVertex

See Also:

AbstractSparseVertex.findEdgeSet(Vertex)