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

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
                      extended by edu.uci.ics.jung.graph.impl.SparseVertex
All Implemented Interfaces:
ArchetypeVertex, Element, Vertex, UserDataContainer, Cloneable
Direct Known Subclasses:
BipartiteVertex, GraphCollapser.CollapsedSparseVertex, LazySparseVertex

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/interfaces inherited from interface edu.uci.ics.jung.utils.UserDataContainer
UserDataContainer.CopyAction
 
Field Summary
 
Fields inherited from class edu.uci.ics.jung.graph.impl.SimpleSparseVertex
mNeighborsToEdges, mPredsToInEdges, mSuccsToOutEdges
 
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
SparseVertex()
          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, or null if there is no such edge.
 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 list of all incident edges of this vertex.
 Set getInEdges()
          Returns the set of incoming edges of this vertex.
 Set getOutEdges()
          Returns the set of outgoing edges of 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.
 
Methods inherited from class edu.uci.ics.jung.graph.impl.SimpleSparseVertex
getNeighbors_internal, getNeighborsToEdges, getPredecessors, getPredsToInEdges, getSuccessors, getSuccsToOutEdges, inDegree, initialize, isDest, isPredecessorOf, isSource, isSuccessorOf, numPredecessors, numSuccessors, outDegree, setNeighborsToEdges, setPredsToInEdges, setSuccsToOutEdges
 
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

SparseVertex

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

Method Detail

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.

Specified by:
getInEdges in interface Vertex
Overrides:
getInEdges in class SimpleSparseVertex
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.

Specified by:
getOutEdges in interface Vertex
Overrides:
getOutEdges in class SimpleSparseVertex
Returns:
all edges whose source is this vertex
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 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 SimpleSparseVertex
See Also:
Vertex.findEdgeSet(Vertex)

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.

Overrides:
getEdges_internal in class SimpleSparseVertex
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.

Overrides:
addNeighbor_internal in class SimpleSparseVertex
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.

Overrides:
removeNeighbor_internal in class SimpleSparseVertex
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)