|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectedu.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.SimpleSparseVertex
public class SimpleSparseVertex
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.
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 |
---|
protected Map mPredsToInEdges
findEdge(Vertex)
.
protected Map mSuccsToOutEdges
findEdge(Vertex)
.
protected Map mNeighborsToEdges
findEdge(Vertex)
.
Constructor Detail |
---|
public SimpleSparseVertex()
Method Detail |
---|
public Set getPredecessors()
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
.
Vertex.getPredecessors()
public Set getSuccessors()
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
.
Vertex.getSuccessors()
public int inDegree()
Vertex
Vertex.inDegree()
public int outDegree()
Vertex
Vertex.outDegree()
public int numPredecessors()
Vertex
Vertex.numPredecessors()
public int numSuccessors()
Vertex
Vertex.numSuccessors()
public boolean isSuccessorOf(Vertex v)
Vertex
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.
Vertex.isSuccessorOf(Vertex)
public boolean isPredecessorOf(Vertex v)
Vertex
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.
Vertex.isPredecessorOf(Vertex)
public boolean isSource(Edge e)
Vertex
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.
Vertex.isSource(Edge)
public boolean isDest(Edge e)
Vertex
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.
Vertex.isDest(Edge)
public 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
.
Vertex.getInEdges()
public 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
.
Vertex.getOutEdges()
public Edge findEdge(Vertex v)
AbstractSparseVertex
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.
findEdge
in interface Vertex
findEdge
in class AbstractSparseVertex
AbstractSparseVertex.findEdge(Vertex)
public 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 AbstractSparseVertex
AbstractSparseVertex.findEdgeSet(Vertex)
protected Collection getNeighbors_internal()
getNeighbors_internal
in class AbstractArchetypeVertex
AbstractArchetypeVertex.getNeighbors_internal()
protected Map getPredsToInEdges()
protected void setPredsToInEdges(Map predsToInEdges)
predsToInEdges
.
This method should not be directly accessed by users.
protected Map getSuccsToOutEdges()
protected void setSuccsToOutEdges(Map succsToOutEdges)
succsToOutEdges
.
This method should not be directly accessed by users.
protected Map getNeighborsToEdges()
protected void setNeighborsToEdges(Map neighborsToEdges)
succsToOutEdges
.
This method should not be directly accessed by users.
protected void initialize()
initialize
in class AbstractElement
AbstractElement.initialize()
protected Collection getEdges_internal()
AbstractArchetypeVertex
getEdges_internal
in class AbstractArchetypeVertex
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 AbstractSparseVertex
e
- the new incident edge of this vertexv
- the new neighbor of this vertexAbstractSparseVertex.addNeighbor_internal(edu.uci.ics.jung.graph.Edge, edu.uci.ics.jung.graph.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 AbstractSparseVertex
e
- the incident edge of this vertex which is being removedv
- the neighbor of this vertex which is being removedAbstractSparseVertex.removeNeighbor_internal(edu.uci.ics.jung.graph.Edge, edu.uci.ics.jung.graph.Vertex)
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |