Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

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

    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

All Implemented Interfaces:
  ArchetypeVertex, Cloneable, Element, UserDataContainer, Vertex

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 inherited from class 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)`

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD