goldman.graph
Interface Graph<V,E extends Edge<V>>

All Superinterfaces:
Iterable<V>
All Known Subinterfaces:
WeightedGraph<V,E>
All Known Implementing Classes:
AbstractGraph, AbstractWeightedGraph, AbstractWeightedGraph.FlowGraph, AdjacencyList, AdjacencyMatrix, WeightedAdjacencyList, WeightedAdjacencyMatrix

public interface Graph<V,E extends Edge<V>>
extends Iterable<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

addEdge

void addEdge(E edge)
Adds the given edge to this graph. If the graph does not allow multi-edges, this method requires that there is not already an edge from the source to the destination.


addVertex

boolean addVertex(V vertex)
Adds the given vertex to this graph. It returns true if the vertex is successfully added, and false if the vertex already existed in the graph.


allowsMultiEdges

boolean allowsMultiEdges()
Returns true if and only if this graph allows multi-edges.


containsEdge

boolean containsEdge(V source,
                     V dest)
Returns true if and only if there is an edge from source to dest in this graph.


containsVertex

boolean containsVertex(V vertex)
Returns true if and only if the given vertex is in this graph.


edgesFrom

Iterator<E> edgesFrom(V vertex)
Returns an iterator over the outgoing edges from the given vertex.


edgesTo

Iterator<E> edgesTo(V vertex)
Returns an iterator over the incoming edges for the given vertex. This is an optional operation for directed graphs.


getEdge

E getEdge(V source,
          V dest)
Returns an edge in the graph from source to dest, or null if there is no such edge.


isDirected

boolean isDirected()
Returns true if and only if this graph is a directed graph.


iterator

NonMutatingIterator<V> iterator()
Returns a non-mutating iterator over the vertices in this graph.

Specified by:
iterator in interface Iterable<V>

numVertices

int numVertices()
Returns the number of vertices in this graph.


removeEdge

boolean removeEdge(E edge)
Removes the given edge from this graph. It returns true when the edge is successfully removed, and false if the edge did not exist in the graph.


removeVertex

boolean removeVertex(V vertex)
Removes the given vertex from this graph. It returns true when the vertex is successfully removed, and false if the vertex did not exist in the graph. Removing a vertex implicitly removes all of its incident edges. Because edges may be deleted lazily in some implementations on the basis of whether or not the incident vertices are still in the graph, this method requires that the removed vertex (or any equivalent one) is never added back into the graph


getConnectedComponents

Set<Set<V>> getConnectedComponents()
Returns a set holding the set of vertices in each connected component of this graph. This method is applicable only for undirected graphs. It throws a GraphException when the graph is directed since the connected components are defined only for an undirected graph.


getCycle

PositionalCollection<E> getCycle()
Returns a positional collection containing the edges in some cycle in this graph, in the order they appear in the cycle. It throws a GraphException if the graph is acyclic. The hasCycle method can be used to determine if the graph has a cycle.


getStronglyConnectedComponents

Set<Set<V>> getStronglyConnectedComponents()
Returns a set holding the set of vertices in each strongly connected component of this graph. This method is applicable only for directed graphs. It throws a GraphException when the graph is undirected since the strongly connected components are defined only for a directed graph.


hasCycle

boolean hasCycle()
Returns true if and only this graph has a cycle.


numConnectedComponents

int numConnectedComponents()
Returns the number of connected components in this graph. It throws a GraphException when the graph is directed since the connected components are defined only for an undirected graph.


numStronglyConnectedComponents

int numStronglyConnectedComponents()
Returns the number of strongly connected components in this graph. It throws a GraphException when the graph is undirected since the strongly connected components are defined only for a directed graph.


topologicalOrder

PositionalCollection<V> topologicalOrder()
Returns a positional collection that holds a permutation of the vertices of a directed graph in a valid topological order. It throws a GraphException if the graph is undirected, or if there is a directed cycle.


unweightedShortestPaths

InTree<V,E> unweightedShortestPaths(V source)
Uses breadth-first search to compute and return a shortest path tree for the given source vertex.