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

java.lang.Object
  extended by edu.uci.ics.jung.utils.UserDataDelegate
      extended by edu.uci.ics.jung.graph.impl.AbstractElement
          extended by edu.uci.ics.jung.graph.impl.AbstractArchetypeVertex
              extended by edu.uci.ics.jung.graph.impl.AbstractSparseVertex
                  extended by edu.uci.ics.jung.graph.impl.SimpleSparseVertex
All Implemented Interfaces:
ArchetypeVertex, Element, Vertex, UserDataContainer, Cloneable
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/interfaces inherited from interface edu.uci.ics.jung.utils.UserDataContainer
UserDataContainer.CopyAction
 
Field Summary
protected  Map mNeighborsToEdges
          A map of the vertices connected to this vertex by undirected edges to the corresponding sets of edges.
protected  Map mPredsToInEdges
          A map of the predecessors of this vertex to the corresponding sets of incoming edges.
protected  Map mSuccsToOutEdges
          A map of the successors of this vertex to the corresponding sets of outgoing edges.
 
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
SimpleSparseVertex()
          Creates a new instance of a vertex for inclusion in a sparse 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.
 Set findEdgeSet(Vertex v)
          Returns the set of all edges that connect this vertex with the specified vertex v.
protected  Collection getEdges_internal()
          Returns a set containing all the 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.
protected  Map getNeighborsToEdges()
          Returns a map from the successors of this vertex to its outgoing edges.
 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 setNeighborsToEdges(Map neighborsToEdges)
          Sets this vertex's internal successor -> out-edge map to the specified map succsToOutEdges.
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
 

Field Detail

mPredsToInEdges

protected Map mPredsToInEdges
A map of the predecessors of this vertex to the corresponding sets of incoming edges. Used to speed up findEdge(Vertex).


mSuccsToOutEdges

protected Map mSuccsToOutEdges
A map of the successors of this vertex to the corresponding sets of outgoing edges. Used to speed up findEdge(Vertex).


mNeighborsToEdges

protected Map mNeighborsToEdges
A map of the vertices connected to this vertex by undirected edges to the corresponding sets of edges. Used to speed up findEdge(Vertex).

Constructor Detail

SimpleSparseVertex

public SimpleSparseVertex()
Creates a new instance of a vertex for inclusion in a sparse 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()

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

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

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 Set findEdgeSet(Vertex v)
Description copied from interface: Vertex
Returns the set of all edges that connect this vertex with the specified vertex v. Each edge in this set will be either a directed outgoing edge from this vertex to v, or an undirected edge connecting this vertex to v. findEdge(v) may be used to return a single (arbitrary) element of this set. 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)

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

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.


getNeighborsToEdges

protected Map getNeighborsToEdges()
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.


setNeighborsToEdges

protected void setNeighborsToEdges(Map neighborsToEdges)
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()

getEdges_internal

protected Collection getEdges_internal()
Description copied from class: AbstractArchetypeVertex
Returns a set containing all the incident edges of this vertex. This is an internal method which is not intended for users.

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(edu.uci.ics.jung.graph.Edge, edu.uci.ics.jung.graph.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(edu.uci.ics.jung.graph.Edge, edu.uci.ics.jung.graph.Vertex)