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

java.lang.Object
  edu.uci.ics.jung.utils.UserDataDelegate
      edu.uci.ics.jung.graph.impl.AbstractElement
          edu.uci.ics.jung.graph.impl.AbstractArchetypeVertex
              edu.uci.ics.jung.graph.impl.AbstractSparseVertex
                  edu.uci.ics.jung.graph.impl.SimpleDirectedSparseVertex

All Implemented Interfaces:

ArchetypeVertex, Element, Vertex, UserDataContainer, Cloneable

Direct Known Subclasses:

DirectedSparseVertex

public class SimpleDirectedSparseVertex
extends AbstractSparseVertex

An implementation of Vertex that resides in a directed graph; none of its adjoining edges may be parallel.

This implementation stores hash tables that map the neighbors of this vertex to its incident edges. This enables an efficient implementation of findEdge(Vertex). Optimally, this is to be used with DirectedSparseEdge.

Author:

Joshua O'Madadhain

See Also:

DirectedSparseGraph, DirectedSparseEdge

Nested Class Summary

Nested classes/interfaces inherited from interface edu.uci.ics.jung.utils.UserDataContainer

UserDataContainer.CopyAction

Field Summary

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

id, m_Graph

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

factory, udc_delegate

Constructor Summary

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

Method Summary

protected void	addNeighbor_internal(Edge e, Vertex v) Adds the specified edge e and vertex v to the internal data structures of this vertex.
Edge	findEdge(Vertex v) Returns the edge that connects this vertex to the specified vertex v, or null if there is no such edge.
Set	findEdgeSet(Vertex v) Returns the set of edges that connect this vertex to the specified vertex.
protected Collection	getEdges_internal() Returns a list of all incident edges of this vertex.
Set	getInEdges() Returns the set of incoming edges of this vertex.
protected Collection	getNeighbors_internal() Returns a set of all neighbors attached to this vertex.
Set	getOutEdges() Returns the set of outgoing edges of this vertex.
Set	getPredecessors() Returns the set of predecessors of this vertex.
protected Map	getPredsToInEdges() Returns a map from the predecessors of this vertex to its incoming edges.
Set	getSuccessors() Returns the set of successors of this vertex.
protected Map	getSuccsToOutEdges() Returns a map from the successors of this vertex to its outgoing edges.
int	inDegree() Returns the number of incoming edges that are incident to this vertex.
protected void	initialize() Initializes the internal data structures of 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.
protected void	removeNeighbor_internal(Edge e, Vertex v) Removes the specified edge e and vertex v from the internal data structures of this vertex.
protected void	setPredsToInEdges(Map predsToInEdges) Sets this vertex's internal predecessor -> in-edge map to the specified map predsToInEdges.
protected void	setSuccsToOutEdges(Map succsToOutEdges) Sets this vertex's internal successor -> out-edge map to the specified map succsToOutEdges.

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

copy, findEdge, findEdgeSet, toString

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

degree, equals, getEqualVertex, getEquivalentVertex, getIncidentEdges, getIncidentElements, getNeighbors, isIncident, isNeighborOf, numNeighbors

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

addGraph_internal, getGraph, hashCode, removeGraph_internal

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

finalize, getClass, notify, notifyAll, wait, wait, wait

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

degree, getEqualVertex, getEquivalentVertex, getIncidentEdges, getNeighbors, isIncident, isNeighborOf, numNeighbors

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

getGraph, getIncidentElements

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

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

Constructor Detail

SimpleDirectedSparseVertex

public SimpleDirectedSparseVertex()

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

Method Detail

getPredecessors

public 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()

numPredecessors

public int numPredecessors()

Description copied from interface: Vertex

Returns the number of predecessors of this vertex.

See Also:

Vertex.numPredecessors()

getSuccessors

public 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()

numSuccessors

public int numSuccessors()

Description copied from interface: Vertex

Returns the number of successors of this vertex.

See Also:

Vertex.numSuccessors()

getInEdges

public 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 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()

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()

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)

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.

Specified by:

findEdge in interface Vertex

Overrides:

findEdge in class AbstractSparseVertex

See Also:

Vertex.findEdge(Vertex)

findEdgeSet

public Set findEdgeSet(Vertex v)

Returns the set of edges that connect this vertex to the specified vertex. Since this implementation does not allow for parallel edges, this implementation simply returns a set whose contents consist of the return value from findEdge(v).

Specified by:

findEdgeSet in interface Vertex

Overrides:

findEdgeSet in class AbstractSparseVertex

See Also:

Vertex.findEdgeSet(Vertex)

getNeighbors_internal

protected Collection getNeighbors_internal()

Returns a set of all neighbors attached to this vertex. Requires time proportional to the number of neighbors.

Specified by:

getNeighbors_internal in class AbstractArchetypeVertex

See Also:

AbstractArchetypeVertex.getNeighbors_internal()

getEdges_internal

protected Collection getEdges_internal()

Returns a list of all incident edges of this vertex. Requires time proportional to the number of incident edges.

Specified by:

getEdges_internal in class AbstractArchetypeVertex

See Also:

AbstractArchetypeVertex.getEdges_internal()

addNeighbor_internal

protected void addNeighbor_internal(Edge e,
                                    Vertex v)

Description copied from class: AbstractSparseVertex

Adds the specified edge e and vertex v to the internal data structures of this vertex.

Specified by:

addNeighbor_internal in class AbstractSparseVertex

Parameters:

e - the new incident edge of this vertex

v - the new neighbor of this vertex

See Also:

AbstractSparseVertex.addNeighbor_internal(Edge, Vertex)

removeNeighbor_internal

protected void removeNeighbor_internal(Edge e,
                                       Vertex v)

Description copied from class: AbstractSparseVertex

Removes the specified edge e and vertex v from the internal data structures of this vertex.

Specified by:

removeNeighbor_internal in class AbstractSparseVertex

Parameters:

e - the incident edge of this vertex which is being removed

v - the neighbor of this vertex which is being removed

See Also:

AbstractSparseVertex.removeNeighbor_internal(Edge, Vertex)

getPredsToInEdges

protected Map getPredsToInEdges()

Returns a map from the predecessors of this vertex to its incoming edges. If this map has not yet been created, it creates it. This map should not be directly accessed by users.

setPredsToInEdges

protected void setPredsToInEdges(Map predsToInEdges)

Sets this vertex's internal predecessor -> in-edge map to the specified map predsToInEdges. This method should not be directly accessed by users.

getSuccsToOutEdges

protected Map getSuccsToOutEdges()

Returns a map from the successors of this vertex to its outgoing edges. If this map has not yet been created, it creates it. This method should not be directly accessed by users.

setSuccsToOutEdges

protected void setSuccsToOutEdges(Map succsToOutEdges)

Sets this vertex's internal successor -> out-edge map to the specified map succsToOutEdges. This method should not be directly accessed by users.

initialize

protected void initialize()

Initializes the internal data structures of this vertex.

Overrides:

initialize in class AbstractElement

See Also:

AbstractElement.initialize()