|
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
public interface DirectedGraph
The interface describing directed graphs. Any object may be a vertex. Following the convention of the Collection interface, some operations are optional. In this case the modification methods are all optional allowing for mutable or immutable graphs. Typically the definition of a directed graph requires a non-empty set of vertices. We will slightly abuse the term by allowing empty directed graphs(graphs with no vertices). This is done in order to simplify incremental creation and destruction of the graph, as well as to conform to the conventions of the Collection interface. The inspiration for this interface comes from the book Structures in Java. In many respects the implementation is similar. Passing an Object that is not a vertex when a vertex is called for is considered bad form, so behavior may vary from implementation to implementation.
Method Summary | |
---|---|
boolean |
addEdge(Object vertex1,
Object vertex2)
Adds the directed edge to the graph(Optional operation). |
boolean |
addVertex(Object vertex)
Adds vertex to the graph(Optional operation). |
Object |
clone()
|
boolean |
contains(Object vertex)
Returns whether or not a particular Object is a vertex in the graph. |
boolean |
containsEdge(Object vertex1,
Object vertex2)
Returns whether or not a particular edge is in the graph. |
int |
degree(Object vertex)
Returns the degree of the vertex. |
boolean |
hasPath(Object vertex1,
Object vertex2)
Determines if there is a directed path from vertex1 to vertex2. |
Set |
inComing(Object vertex)
Constructs an Iterator over the vertices adjacent to edges entering the specified vertex. |
int |
inDegree(Object vertex)
Returns the number of edges entering the vertex. |
boolean |
isAcyclic()
Determines whether or not the graph is acyclic. |
boolean |
isSinglyConnected()
Determines whether or not the graph is a singly connected. |
boolean |
isWeaklyConnected()
Determines whether or not the graph is weakly connected. |
boolean |
isWeaklyConnected(Object vertex1,
Object vertex2)
Determines if there is an undirected path from vertex1 to vertex2. |
boolean |
maintainsAcyclicity(Object vertex1,
Object vertex2)
Check whether adding the proposed edge would keep the graph acyclic. |
int |
numEdges()
|
int |
outDegree(Object vertex)
Returns the number of edges leaving the vertex. |
Set |
outGoing(Object vertex)
Constructs an Iterator over the vertices adjacent to edges leaving the specified vertex. |
boolean |
removeEdge(Object vertex1,
Object vertex2)
Removes the directed edge from the graph(Optional operation). |
boolean |
removeVertex(Object vertex)
Removes vertex from the graph(Optional operation). |
void |
replaceVertex(Object oldVertex,
Object newVertex)
|
void |
replaceVertices(Map verticesOldToNew,
NodeLinearTask task)
|
int |
size()
Returns the number of vertices in the graph. |
List |
topologicalOrder()
|
Set |
vertices()
Constructs an Iterator over all vertices. |
Methods inherited from interface Collection |
---|
add, addAll, clear, containsAll, equals, hashCode, isEmpty, iterator, remove, removeAll, retainAll, toArray, toArray |
Method Detail |
---|
Object clone()
List topologicalOrder()
void replaceVertex(Object oldVertex, Object newVertex)
void replaceVertices(Map verticesOldToNew, NodeLinearTask task)
boolean maintainsAcyclicity(Object vertex1, Object vertex2)
Check whether adding the proposed edge would keep the graph acyclic.
Precondition: the graph is acyclic.
Set vertices()
Set inComing(Object vertex)
vertex-
- An Object which is in the graph.
Set outGoing(Object vertex)
vertex-
- An Object which is in the graph.
int degree(Object vertex)
vertex-
- An Object which is in the graph.
int inDegree(Object vertex)
vertex-
- An Object which is in the graph.
int outDegree(Object vertex)
vertex-
- An Object which is in the graph.
boolean containsEdge(Object vertex1, Object vertex2)
vertex1-
- An Object which is in the graph.vertex2-
- An Object which is in the graph.
boolean contains(Object vertex)
contains
in interface Collection
vertex-
- Any Object.
int size()
size
in interface Collection
int numEdges()
boolean isAcyclic()
boolean isWeaklyConnected()
boolean isWeaklyConnected(Object vertex1, Object vertex2)
vertex1-
- An Object which is in the graph.vertex2-
- An Object which is in the graph.
boolean hasPath(Object vertex1, Object vertex2)
vertex1-
- An Object which is in the graph.vertex2-
- An Object which is in the graph.
boolean isSinglyConnected()
boolean addVertex(Object vertex)
vertex-
- An Object to be added as a vertex.
boolean removeVertex(Object vertex)
vertex-
- An Object which is currently in the graph.boolean addEdge(Object vertex1, Object vertex2)
boolean removeEdge(Object vertex1, Object vertex2)
|
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |