FindBugs™ 1.3.9

edu.umd.cs.findbugs.graph
Class AbstractGraph<EdgeType extends AbstractEdge<EdgeType,VertexType>,VertexType extends AbstractVertex<EdgeType,VertexType>>

java.lang.Object
  extended by edu.umd.cs.findbugs.graph.AbstractGraph<EdgeType,VertexType>
All Implemented Interfaces:
Graph<EdgeType,VertexType>
Direct Known Subclasses:
CallGraph, CFG, ConstraintGraph, InheritanceGraph, InterproceduralCallGraph

public abstract class AbstractGraph<EdgeType extends AbstractEdge<EdgeType,VertexType>,VertexType extends AbstractVertex<EdgeType,VertexType>>
extends java.lang.Object
implements Graph<EdgeType,VertexType>

A simple Graph implementation where the vertex objects store a list of incoming and outgoing edges. The edge link fields are stored in the edge objects, which means a fairly low space overhead.

The abstract allocateEdge() method must be implemented.

Author:
David Hovemeyer
See Also:
Graph, AbstractEdge, AbstractVertex

Constructor Summary
AbstractGraph()
           
 
Method Summary
 void addVertex(VertexType v)
          Add given vertex to the graph.
protected abstract  EdgeType allocateEdge(VertexType source, VertexType target)
           
 boolean containsVertex(VertexType v)
          Determine if the graph contains the given vertex.
 EdgeType createEdge(VertexType source, VertexType target)
          Add a new edge to the graph.
 java.util.Iterator<EdgeType> edgeIterator()
          Get Iterator over all edges in the graph.
 int getNumEdgeLabels()
          Get the number of numeric labels that have been assigned to edges.
 int getNumEdges()
          Get number of edges in the graph.
 int getNumIncomingEdges(VertexType vertex)
          Get number of edges going into given vertex.
 int getNumOutgoingEdges(VertexType vertex)
          Get number of edges going out of given vertex.
 int getNumVertexLabels()
          Get the number of numeric (integer) labels that have been assigned to vertices in the graph.
 int getNumVertices()
          Get number of vertices in the graph.
 java.util.Iterator<EdgeType> incomingEdgeIterator(VertexType target)
          Get an Iterator over incoming edges to a given vertex.
 EdgeType lookupEdge(VertexType source, VertexType target)
          Look up an edge by source and target vertex.
 java.util.Iterator<EdgeType> outgoingEdgeIterator(VertexType source)
          Get an Iterator over outgoing edges from given vertex.
 java.util.Iterator<VertexType> predecessorIterator(VertexType target)
          Get an iterator over the predecessors of this vertex; i.e., the sources of the vertex's incoming edges.
 void removeEdge(EdgeType edge)
          Remove given edge from the graph.
 void removeVertex(VertexType v)
          Remove given vertex from the graph.
 void setNumEdgeLabels(int numLabels)
          Reset the number of edge labels.
 void setNumVertexLabels(int numLabels)
          Reset number of (integer) labels.
 java.util.Iterator<VertexType> successorIterator(VertexType source)
          Get an iterator over the successors of this vertex; i.e., the targets of the vertex's outgoing edges.
 java.util.Iterator<VertexType> vertexIterator()
          Get Iterator over all vertices in the graph.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

AbstractGraph

public AbstractGraph()
Method Detail

getNumEdges

public int getNumEdges()
Description copied from interface: Graph
Get number of edges in the graph.

Specified by:
getNumEdges in interface Graph<EdgeType extends AbstractEdge<EdgeType,VertexType>,VertexType extends AbstractVertex<EdgeType,VertexType>>

getNumVertices

public int getNumVertices()
Description copied from interface: Graph
Get number of vertices in the graph.

Specified by:
getNumVertices in interface Graph<EdgeType extends AbstractEdge<EdgeType,VertexType>,VertexType extends AbstractVertex<EdgeType,VertexType>>

edgeIterator

public java.util.Iterator<EdgeType> edgeIterator()
Description copied from interface: Graph
Get Iterator over all edges in the graph.

Specified by:
edgeIterator in interface Graph<EdgeType extends AbstractEdge<EdgeType,VertexType>,VertexType extends AbstractVertex<EdgeType,VertexType>>

vertexIterator

public java.util.Iterator<VertexType> vertexIterator()
Description copied from interface: Graph
Get Iterator over all vertices in the graph.

Specified by:
vertexIterator in interface Graph<EdgeType extends AbstractEdge<EdgeType,VertexType>,VertexType extends AbstractVertex<EdgeType,VertexType>>

addVertex

public void addVertex(VertexType v)
Description copied from interface: Graph
Add given vertex to the graph. The vertex should not be part of any other graph.

Specified by:
addVertex in interface Graph<EdgeType extends AbstractEdge<EdgeType,VertexType>,VertexType extends AbstractVertex<EdgeType,VertexType>>
Parameters:
v - the vertex to add

containsVertex

public boolean containsVertex(VertexType v)
Description copied from interface: Graph
Determine if the graph contains the given vertex.

Specified by:
containsVertex in interface Graph<EdgeType extends AbstractEdge<EdgeType,VertexType>,VertexType extends AbstractVertex<EdgeType,VertexType>>
Parameters:
v - the vertex
Returns:
true if the vertex is part of the graph, false if not

createEdge

public EdgeType createEdge(VertexType source,
                           VertexType target)
Description copied from interface: Graph
Add a new edge to the graph. Duplicate edges (with same source and target vertices) are allowed.

Specified by:
createEdge in interface Graph<EdgeType extends AbstractEdge<EdgeType,VertexType>,VertexType extends AbstractVertex<EdgeType,VertexType>>
Parameters:
source - the source vertex
target - the target vertex
Returns:
the new edge

lookupEdge

public EdgeType lookupEdge(VertexType source,
                           VertexType target)
Description copied from interface: Graph
Look up an edge by source and target vertex. If multiple edges with same source and target vertex exist, one is selected arbitrarily.

Specified by:
lookupEdge in interface Graph<EdgeType extends AbstractEdge<EdgeType,VertexType>,VertexType extends AbstractVertex<EdgeType,VertexType>>
Parameters:
source - the source vertex
target - the target vertex
Returns:
a matching edge, or null if there is no matching edge

getNumVertexLabels

public int getNumVertexLabels()
Description copied from interface: Graph
Get the number of numeric (integer) labels that have been assigned to vertices in the graph. All vertices in the graph are guaranteed to have labels in the range 0..n, where n is the value returned by this method.

Specified by:
getNumVertexLabels in interface Graph<EdgeType extends AbstractEdge<EdgeType,VertexType>,VertexType extends AbstractVertex<EdgeType,VertexType>>

setNumVertexLabels

public void setNumVertexLabels(int numLabels)
Description copied from interface: Graph
Reset number of (integer) labels. This might be necessary if an algorithm has assigned new labels to a graph's vertices.

Specified by:
setNumVertexLabels in interface Graph<EdgeType extends AbstractEdge<EdgeType,VertexType>,VertexType extends AbstractVertex<EdgeType,VertexType>>

getNumEdgeLabels

public int getNumEdgeLabels()
Description copied from interface: Graph
Get the number of numeric labels that have been assigned to edges.

Specified by:
getNumEdgeLabels in interface Graph<EdgeType extends AbstractEdge<EdgeType,VertexType>,VertexType extends AbstractVertex<EdgeType,VertexType>>

setNumEdgeLabels

public void setNumEdgeLabels(int numLabels)
Description copied from interface: Graph
Reset the number of edge labels.

Specified by:
setNumEdgeLabels in interface Graph<EdgeType extends AbstractEdge<EdgeType,VertexType>,VertexType extends AbstractVertex<EdgeType,VertexType>>

removeEdge

public void removeEdge(EdgeType edge)
Description copied from interface: Graph
Remove given edge from the graph.

Specified by:
removeEdge in interface Graph<EdgeType extends AbstractEdge<EdgeType,VertexType>,VertexType extends AbstractVertex<EdgeType,VertexType>>

removeVertex

public void removeVertex(VertexType v)
Description copied from interface: Graph
Remove given vertex from the graph. Note that all edges referencing the vertex will be removed.

Specified by:
removeVertex in interface Graph<EdgeType extends AbstractEdge<EdgeType,VertexType>,VertexType extends AbstractVertex<EdgeType,VertexType>>

outgoingEdgeIterator

public java.util.Iterator<EdgeType> outgoingEdgeIterator(VertexType source)
Description copied from interface: Graph
Get an Iterator over outgoing edges from given vertex.

Specified by:
outgoingEdgeIterator in interface Graph<EdgeType extends AbstractEdge<EdgeType,VertexType>,VertexType extends AbstractVertex<EdgeType,VertexType>>
Parameters:
source - the source vertex
Returns:
an Iterator over outgoing edges

incomingEdgeIterator

public java.util.Iterator<EdgeType> incomingEdgeIterator(VertexType target)
Description copied from interface: Graph
Get an Iterator over incoming edges to a given vertex.

Specified by:
incomingEdgeIterator in interface Graph<EdgeType extends AbstractEdge<EdgeType,VertexType>,VertexType extends AbstractVertex<EdgeType,VertexType>>
Parameters:
target - the target vertex
Returns:
an Iterator over incoming edges

getNumIncomingEdges

public int getNumIncomingEdges(VertexType vertex)
Description copied from interface: Graph
Get number of edges going into given vertex.

Specified by:
getNumIncomingEdges in interface Graph<EdgeType extends AbstractEdge<EdgeType,VertexType>,VertexType extends AbstractVertex<EdgeType,VertexType>>
Parameters:
vertex - the vertex
Returns:
number of edges going into the vertex

getNumOutgoingEdges

public int getNumOutgoingEdges(VertexType vertex)
Description copied from interface: Graph
Get number of edges going out of given vertex.

Specified by:
getNumOutgoingEdges in interface Graph<EdgeType extends AbstractEdge<EdgeType,VertexType>,VertexType extends AbstractVertex<EdgeType,VertexType>>
Parameters:
vertex - the vertex
Returns:
number of edges going out of the vertex

successorIterator

public java.util.Iterator<VertexType> successorIterator(VertexType source)
Description copied from interface: Graph
Get an iterator over the successors of this vertex; i.e., the targets of the vertex's outgoing edges.

Specified by:
successorIterator in interface Graph<EdgeType extends AbstractEdge<EdgeType,VertexType>,VertexType extends AbstractVertex<EdgeType,VertexType>>
Parameters:
source - the source vertex
Returns:
an Iterator over the successors of the vertex

predecessorIterator

public java.util.Iterator<VertexType> predecessorIterator(VertexType target)
Description copied from interface: Graph
Get an iterator over the predecessors of this vertex; i.e., the sources of the vertex's incoming edges.

Specified by:
predecessorIterator in interface Graph<EdgeType extends AbstractEdge<EdgeType,VertexType>,VertexType extends AbstractVertex<EdgeType,VertexType>>
Parameters:
target - the target vertex
Returns:
an Iterator over the predecessors of the vertex

allocateEdge

protected abstract EdgeType allocateEdge(VertexType source,
                                         VertexType target)

FindBugs™ 1.3.9

FindBugs™ is licenced under the LGPL. Copyright © 2006 University of Maryland.