graph
Interface Digraph

All Known Subinterfaces:

KeyedDigraph

All Known Implementing Classes:

AdjListDigraph, HashKeyedDigraph

public interface Digraph

This is the simplest useful directed graph interface. It mainly just has outIncidentEdges(). That is enough to support traversal algorithms like DFS, BFS, and Dijkstra's algorithm. The interface is missing many graph methods proposed in the textbook's section 12.1.1 -- to start with, inIncidentEdges() -- but it could be extended to have those methods.

An implementation of just this simple interface doesn't have to store much data. For example, it is not necessary to store a list of all vertices. Many algorithms don't require the class to maintain such a list. Instead, the algorithm itself may store one or more of the vertices created and returned by insertVertex(); for example, a start vertex may be enough.

The name "Digraph" is a common abbreviation for "directed graph."

Method Summary

graph.DirectedEdge	insertDirectedEdge(graph.Vertex from, graph.Vertex to, java.lang.Object element) Adds a new directed edge from one vertex to another.
void	insertReverseOf(graph.DirectedEdge e) Convenience method: Add the reverse of the given edge, with the same element.
graph.Vertex	insertVertex(java.lang.Object element) Insert and return a new vertex.
int	numEdges() Return the size of the graph (number of edges, m).
int	numVertices() Return the order of the graph (number of vertices, n).
java.util.Iterator	outIncidentEdges(graph.Vertex v) Return an iterator over all the directed edges from a vertex.

Method Detail

numVertices

public int numVertices()

Return the order of the graph (number of vertices, n).

numEdges

public int numEdges()

Return the size of the graph (number of edges, m).

outIncidentEdges

public java.util.Iterator outIncidentEdges(graph.Vertex v)

Return an iterator over all the directed edges from a vertex.

insertVertex

public graph.Vertex insertVertex(java.lang.Object element)

Insert and return a new vertex. The vertex has no incident edges yet.

Parameters:

element - the element stored at the vertex.

insertDirectedEdge

public graph.DirectedEdge insertDirectedEdge(graph.Vertex from,
                                             graph.Vertex to,
                                             java.lang.Object element)
                                      throws InvalidPositionException

Adds a new directed edge from one vertex to another.

Parameters:

element - the element stored on the edge.

Throws:

InvalidPositionException - if the implementation detects that one of the vertices is not actually in this graph.

insertReverseOf

public void insertReverseOf(graph.DirectedEdge e)

Convenience method: Add the reverse of the given edge, with the same element. Thus, to add a pair of opposing edges, you can do something like

    insertReverseOf(insertDirectedEdge(from, to, element));
 

This is convenient if from, to, or element is a complicated expression.