|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
public interface Graph<V,E extends Edge<V>>
A graph represents general relationships between pairs of elements from
among a set of elements. The elements are called vertices, and
the relationships between them are called edges.
The graph algorithms we present do not depend on a particular graph implementation. Instead,
they are implemented entirely in terms of
the Graph ADT. One advantage of this approach
is that it allows the presentation and implementation of the graph algorithms
to be expressed independent of the underlying graph representation.
The Graph
interface that provides the methods
required to create and modify a graph, and methods to perform commonly needed
computation on the graph, such as computing a shortest path tree for a specified
source, determining if a graph is cyclic, or finding a
valid topological order for a precedence graph.
Method Summary | |
---|---|
void |
addEdge(E edge)
Adds the given edge to this graph. |
boolean |
addVertex(V vertex)
Adds the given vertex to this graph. |
boolean |
allowsMultiEdges()
Returns true if and only if this graph allows multi-edges. |
boolean |
containsEdge(V source,
V dest)
Returns true if and only if there is an edge from source
to dest in this graph. |
boolean |
containsVertex(V vertex)
Returns true if and only if the given vertex is in this graph. |
Iterator<E> |
edgesFrom(V vertex)
Returns an iterator over the outgoing edges from the given vertex. |
Iterator<E> |
edgesTo(V vertex)
Returns an iterator over the incoming edges for the given vertex. |
Set<Set<V>> |
getConnectedComponents()
Returns a set holding the set of vertices in each connected component of this graph. |
PositionalCollection<E> |
getCycle()
Returns a positional collection containing the edges in some cycle in this graph, in the order they appear in the cycle. |
E |
getEdge(V source,
V dest)
Returns an edge in the graph from source
to dest , or null if there is no such edge. |
Set<Set<V>> |
getStronglyConnectedComponents()
Returns a set holding the set of vertices in each strongly connected component of this graph. |
boolean |
hasCycle()
Returns true if and only this graph has a cycle. |
boolean |
isDirected()
Returns true if and only if this graph is a directed graph. |
NonMutatingIterator<V> |
iterator()
Returns a non-mutating iterator over the vertices in this graph. |
int |
numConnectedComponents()
Returns the number of connected components in this graph. |
int |
numStronglyConnectedComponents()
Returns the number of strongly connected components in this graph. |
int |
numVertices()
Returns the number of vertices in this graph. |
boolean |
removeEdge(E edge)
Removes the given edge from this graph. |
boolean |
removeVertex(V vertex)
Removes the given vertex from this graph. |
PositionalCollection<V> |
topologicalOrder()
Returns a positional collection that holds a permutation of the vertices of a directed graph in a valid topological order. |
InTree<V,E> |
unweightedShortestPaths(V source)
Uses breadth-first search to compute and return a shortest path tree for the given source vertex. |
Method Detail |
---|
void addEdge(E edge)
boolean addVertex(V vertex)
boolean allowsMultiEdges()
boolean containsEdge(V source, V dest)
source
to dest
in this graph.
boolean containsVertex(V vertex)
Iterator<E> edgesFrom(V vertex)
Iterator<E> edgesTo(V vertex)
E getEdge(V source, V dest)
source
to dest
, or null if there is no such edge.
boolean isDirected()
NonMutatingIterator<V> iterator()
iterator
in interface Iterable<V>
int numVertices()
boolean removeEdge(E edge)
boolean removeVertex(V vertex)
Set<Set<V>> getConnectedComponents()
GraphException
when
the graph is directed since the connected components are defined only for
an undirected graph.
PositionalCollection<E> getCycle()
GraphException
if the
graph is acyclic. The hasCycle
method can be used to determine
if the graph has a cycle.
Set<Set<V>> getStronglyConnectedComponents()
GraphException
when
the graph is undirected since the strongly connected components are defined only for
a directed graph.
boolean hasCycle()
int numConnectedComponents()
GraphException
when
the graph is directed since the connected components are defined only for
an undirected graph.
int numStronglyConnectedComponents()
GraphException
when
the graph is undirected since the strongly connected components are defined only for
a directed graph.
PositionalCollection<V> topologicalOrder()
GraphException
if the graph is
undirected, or if there is a directed cycle.
InTree<V,E> unweightedShortestPaths(V source)
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |