edu.uci.ics.jung.graph.impl
Class SparseVertex
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.SimpleSparseVertex
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
Constructor Summary |
SparseVertex()
Creates a new instance of a vertex for inclusion in a
sparse graph. |
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 |
SparseVertex
public SparseVertex()
- Creates a new instance of a vertex for inclusion in a
sparse graph.
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 vertexv
- 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 removedv
- the neighbor of this vertex which is being removed- See Also:
AbstractSparseVertex.removeNeighbor_internal(Edge, Vertex)