goldman.graph
Class AbstractGraph<V,E extends Edge<V>>

java.lang.Object
  extended by goldman.graph.AbstractGraph<V,E>
All Implemented Interfaces:
Graph<V,E>, Iterable<V>
Direct Known Subclasses:
AbstractWeightedGraph, AdjacencyList, AdjacencyMatrix

public abstract class AbstractGraph<V,E extends Edge<V>>
extends Object
implements Graph<V,E>

The AbstractGraph class embodies algorithms that perform computations on a graph in terms of the Graph interface. This allows subclasses that use any graph representation to benefit from these algorithms.


Field Summary
static double INF
          Representation for infinity.
 
Constructor Summary
AbstractGraph(GraphRepresentation<V,E> graph, boolean multigraph)
          It creates an abstract graph with the given specification.
 
Method Summary
 void addEdge(E e)
          Adds the given edge to this graph.
 boolean addVertex(V v)
          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 v)
          Returns true if and only if the given vertex is in this graph.
 Iterator<E> edgesFrom(V v)
          Returns an iterator over the outgoing edges from the given vertex.
 Iterator<E> edgesTo(V v)
          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()
          The hasCycle method can be used to determine if the graph has a directed 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 e)
          Removes the given edge from this graph.
 boolean removeVertex(V v)
          Removes the given vertex from this graph.
 PositionalCollection<V> topologicalOrder()
          The hasCycle method can be called first to find out if the graph has a cycle.
 String toString()
           
 InTree<V,E> unweightedShortestPaths(V s)
          Uses breadth-first search to compute and return a shortest path tree for the given source vertex.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

INF

public static final double INF
Representation for infinity.

See Also:
Constant Field Values
Constructor Detail

AbstractGraph

public AbstractGraph(GraphRepresentation<V,E> graph,
                     boolean multigraph)
It creates an abstract graph with the given specification.

Parameters:
graph - the graph representation
multigraph - true if the graph allows multi-edges
Method Detail

isDirected

public boolean isDirected()
Description copied from interface: Graph
Returns true if and only if this graph is a directed graph.

Specified by:
isDirected in interface Graph<V,E extends Edge<V>>
Returns:
true if and only if the graph is directed

allowsMultiEdges

public boolean allowsMultiEdges()
Description copied from interface: Graph
Returns true if and only if this graph allows multi-edges.

Specified by:
allowsMultiEdges in interface Graph<V,E extends Edge<V>>
Returns:
true if and only if the graph is a multigraph.

numVertices

public int numVertices()
Description copied from interface: Graph
Returns the number of vertices in this graph.

Specified by:
numVertices in interface Graph<V,E extends Edge<V>>
Returns:
the number of vertices in this graph

containsVertex

public boolean containsVertex(V v)
Description copied from interface: Graph
Returns true if and only if the given vertex is in this graph.

Specified by:
containsVertex in interface Graph<V,E extends Edge<V>>
Parameters:
v - the target vertex
Returns:
true if and only if v is in this graph.

containsEdge

public boolean containsEdge(V source,
                            V dest)
Description copied from interface: Graph
Returns true if and only if there is an edge from source to dest in this graph.

Specified by:
containsEdge in interface Graph<V,E extends Edge<V>>
Parameters:
source - the source vertex
dest - the destination vertex
Returns:
true if and only if there is an edge in the graph from the source vertex to the destination vertex

getEdge

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

Specified by:
getEdge in interface Graph<V,E extends Edge<V>>
Parameters:
source - the source vertex
dest - the destination vertex
Returns:
an edge in the graph from the source vertex to the destination vertex, or null if no such edge exists.

addVertex

public boolean addVertex(V v)
Description copied from interface: Graph
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.

Specified by:
addVertex in interface Graph<V,E extends Edge<V>>
Parameters:
v - the vertex to add to this graph
Returns:
true if v is added to this graph, or false if v is already in this graph.

removeVertex

public boolean removeVertex(V v)
Description copied from interface: Graph
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

Specified by:
removeVertex in interface Graph<V,E extends Edge<V>>
Parameters:
v - the vertex to remove
REQUIRES: the removed vertex (or any equivalent vertex) is never added back into the graph because edges are deleted lazily in some implementations on the basis of whether or not the incident vertices are still in the graph
Returns:
true if v is removed, or false if v is not in the graph, and so cannot be removed.

addEdge

public void addEdge(E e)
Description copied from interface: Graph
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.

Specified by:
addEdge in interface Graph<V,E extends Edge<V>>
Parameters:
e - the edge to add to this graph
REQUIRES: multi-edges are added only to multigraphs

removeEdge

public boolean removeEdge(E e)
Description copied from interface: Graph
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.

Specified by:
removeEdge in interface Graph<V,E extends Edge<V>>
Parameters:
e - the edge to remove
Returns:
true if e is removed, or false if e is not in the graph.

iterator

public NonMutatingIterator<V> iterator()
Description copied from interface: Graph
Returns a non-mutating iterator over the vertices in this graph.

Specified by:
iterator in interface Graph<V,E extends Edge<V>>
Specified by:
iterator in interface Iterable<V>
Returns:
a non-mutating iterator defined over all vertices that is initialized to be just before the first vertex in the set

edgesFrom

public Iterator<E> edgesFrom(V v)
Description copied from interface: Graph
Returns an iterator over the outgoing edges from the given vertex.

Specified by:
edgesFrom in interface Graph<V,E extends Edge<V>>
Parameters:
v - the desired vertex
Returns:
an iterator defined over all outedges of v that is initially positioned just before the first one. If the graph is an undirected graph, then the iteration order will include all edges incident to v.

edgesTo

public Iterator<E> edgesTo(V v)
Description copied from interface: Graph
Returns an iterator over the incoming edges for the given vertex. This is an optional operation for directed graphs.

Specified by:
edgesTo in interface Graph<V,E extends Edge<V>>
Parameters:
v - the desired vertex
Returns:
a non-mutating iterator defined over all inedges of v that is initialized just before the first one. If the graph is an undirected graph then the iterator will include all edges incident to v.
Throws:
UnsupportedOperationException - the graph representation does not support this capability

unweightedShortestPaths

public InTree<V,E> unweightedShortestPaths(V s)
Description copied from interface: Graph
Uses breadth-first search to compute and return a shortest path tree for the given source vertex.

Specified by:
unweightedShortestPaths in interface Graph<V,E extends Edge<V>>
Parameters:
s - the source vertex
Returns:
an in-tree that is a shortest path tree for source vertex s.

hasCycle

public boolean hasCycle()
Description copied from interface: Graph
Returns true if and only this graph has a cycle.

Specified by:
hasCycle in interface Graph<V,E extends Edge<V>>
Returns:
true if and only if this graph has a directed cycle

getCycle

public PositionalCollection<E> getCycle()
The hasCycle method can be used to determine if the graph has a directed cycle.

Specified by:
getCycle in interface Graph<V,E extends Edge<V>>
Returns:
a positional collection holding a directed cyclic in the graph
Throws:
GraphException - the graph is acyclic

numConnectedComponents

public int numConnectedComponents()
Description copied from interface: Graph
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.

Specified by:
numConnectedComponents in interface Graph<V,E extends Edge<V>>
Returns:
the number of connected components in this graph
Throws:
GraphException - the graph is directed, since the connected components are defined only for undirected graphs

getConnectedComponents

public Set<Set<V>> getConnectedComponents()
Description copied from interface: Graph
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.

Specified by:
getConnectedComponents in interface Graph<V,E extends Edge<V>>
Returns:
the connected components in this graph
Throws:
GraphException - the graph is directed, since the connected components are only defined for undirected graphs

topologicalOrder

public PositionalCollection<V> topologicalOrder()
The hasCycle method can be called first to find out if the graph has a cycle.

Specified by:
topologicalOrder in interface Graph<V,E extends Edge<V>>
Returns:
a positional collection holding a valid topological order in the graph
Throws:
GraphException - the graph is cyclic

getStronglyConnectedComponents

public Set<Set<V>> getStronglyConnectedComponents()
Description copied from interface: Graph
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.

Specified by:
getStronglyConnectedComponents in interface Graph<V,E extends Edge<V>>
Returns:
a set of sets of vertices, with one set corresponding to each strongly connected component of this graph
Throws:
GraphException - the graph is undirected, since the strongly connected components are defined only for directed graphs

numStronglyConnectedComponents

public int numStronglyConnectedComponents()
Description copied from interface: Graph
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.

Specified by:
numStronglyConnectedComponents in interface Graph<V,E extends Edge<V>>
Returns:
the number of strongly connected components in this graph.
Throws:
GraphException - the graph is undirected, since the strongly connected components are defined only for directed graphs

toString

public String toString()
Overrides:
toString in class Object