public class SparseVertex extends SimpleSparseVertex
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.
SparseGraph
UserDataContainer.CopyAction
mNeighborsToEdges, mPredsToInEdges, mSuccsToOutEdges
id, m_Graph
factory, udc_delegate
Constructor and Description |
---|
SparseVertex()
Creates a new instance of a vertex for inclusion in a
sparse graph.
|
Modifier and Type | Method and Description |
---|---|
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. |
java.util.Set |
findEdgeSet(Vertex v)
Returns the set of all edges that connect this vertex
with the specified vertex
v . |
protected java.util.Collection |
getEdges_internal()
Returns a list of all incident edges of this vertex.
|
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.
|
protected void |
removeNeighbor_internal(Edge e,
Vertex v)
Removes the specified edge
e and vertex v
from the internal data structures of this vertex. |
getNeighbors_internal, getNeighborsToEdges, getPredecessors, getPredsToInEdges, getSuccessors, getSuccsToOutEdges, inDegree, initialize, isDest, isPredecessorOf, isSource, isSuccessorOf, numPredecessors, numSuccessors, outDegree, setNeighborsToEdges, setPredsToInEdges, setSuccsToOutEdges
copy, findEdge, findEdgeSet, toString
degree, equals, getEqualVertex, getEquivalentVertex, getIncidentEdges, getIncidentElements, getNeighbors, isIncident, isNeighborOf, numNeighbors
addGraph_internal, getGraph, hashCode, removeGraph_internal
addUserDatum, clone, containsUserDatumKey, getUserDatum, getUserDatumCopyAction, getUserDatumKeyIterator, importUserData, removeUserDatum, setUserDataFactory, setUserDatum
finalize, getClass, notify, notifyAll, wait, wait, wait
degree, getEqualVertex, getEquivalentVertex, getIncidentEdges, getNeighbors, isIncident, isNeighborOf, numNeighbors
getGraph, getIncidentElements
addUserDatum, clone, containsUserDatumKey, getUserDatum, getUserDatumCopyAction, getUserDatumKeyIterator, importUserData, removeUserDatum, setUserDatum
public SparseVertex()
public java.util.Set getInEdges()
Vertex
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
.getInEdges
in interface Vertex
getInEdges
in class SimpleSparseVertex
Vertex.getInEdges()
public java.util.Set getOutEdges()
Vertex
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
.getOutEdges
in interface Vertex
getOutEdges
in class SimpleSparseVertex
Vertex.getOutEdges()
public Edge findEdge(Vertex v)
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.findEdge
in interface Vertex
findEdge
in class SimpleSparseVertex
Vertex.findEdge(Vertex)
public java.util.Set findEdgeSet(Vertex v)
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
.findEdgeSet
in interface Vertex
findEdgeSet
in class SimpleSparseVertex
Vertex.findEdgeSet(Vertex)
protected java.util.Collection getEdges_internal()
getEdges_internal
in class SimpleSparseVertex
AbstractArchetypeVertex.getEdges_internal()
protected void addNeighbor_internal(Edge e, Vertex v)
AbstractSparseVertex
e
and vertex v
to the internal data structures of this vertex.addNeighbor_internal
in class SimpleSparseVertex
e
- the new incident edge of this vertexv
- the new neighbor of this vertexAbstractSparseVertex.addNeighbor_internal(Edge, Vertex)
protected void removeNeighbor_internal(Edge e, Vertex v)
AbstractSparseVertex
e
and vertex v
from the internal data structures of this vertex.removeNeighbor_internal
in class SimpleSparseVertex
e
- the incident edge of this vertex which is being removedv
- the neighbor of this vertex which is being removedAbstractSparseVertex.removeNeighbor_internal(Edge, Vertex)