Class AbstractGraph<EdgeType extends AbstractEdge<EdgeType, VertexType>, VertexType extends AbstractVertex<EdgeType, VertexType>>

java.lang.Object

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 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.

See Also:

• Graph
• AbstractEdge
• AbstractVertex

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
private static class	AbstractGraph.IncomingEdgeIterator<EdgeType extends AbstractEdge<EdgeType, VertexType>, VertexType extends AbstractVertex<EdgeType, VertexType>>	Iterator over incoming edges.
private static class	AbstractGraph.OutgoingEdgeIterator<EdgeType extends AbstractEdge<EdgeType, VertexType>, VertexType extends AbstractVertex<EdgeType, VertexType>>	Iterator over outgoing edges.

Field Summary

Fields

Modifier and Type	Field	Description
private final ArrayList<EdgeType>	edgeList
private int	maxEdgeLabel
private int	maxVertexLabel
private final ArrayList<VertexType>	vertexList

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	AbstractGraph()

Method Summary

Modifier and Type	Method	Description
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.
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.
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.
Iterator<EdgeType>	outgoingEdgeIterator(VertexType source)	Get an Iterator over outgoing edges from given vertex.
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.
Iterator<VertexType>	successorIterator(VertexType source)	Get an iterator over the successors of this vertex; i.e., the targets of the vertex's outgoing edges.
Iterator<VertexType>	vertexIterator()	Get Iterator over all vertices in the graph.
Iterable<VertexType>	vertices()

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Details

vertexList

private final ArrayList<VertexType extends AbstractVertex<EdgeType, VertexType>> vertexList

edgeList

private final ArrayList<EdgeType extends AbstractEdge<EdgeType, VertexType>> edgeList

maxVertexLabel

private int maxVertexLabel

maxEdgeLabel

private int maxEdgeLabel

Constructor Details

AbstractGraph

protected AbstractGraph()

Method Details

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 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 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>>

vertices

public Iterable<VertexType> vertices()

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 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 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 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 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)